Eindeutige ID aus einem String berechnen

[Bünni]

Für die Lösung eines Problems benötige ich demnächst vermutlich etwas wie eine eindeutige ID, welche ich aus einem gegebenem String berechnen kann, der ohnehin schon eindeutig ist und nur einmal vorkommen kann. Die ID benötige ich aus diversen Gründen zusätzlich.

Die ID sollte wenn möglich nicht so lang sein wie MD5. Welche Möglichkeiten bleiben mir da noch? Mir stehen dafür unter anderem die Wolfgang Ehrhardt Komponenten zur Verfügung.

Ich habe gerade CRC32 getestet. Aber ist das eindeutig genug?

Delphi-Quellcode:

function CRC32String(const Text: string): string;
var
 i: Integer;
 TextLen: Word;
 buf: array [0 .. 4095] of Byte;
 CRC: LongInt;
 ctx: TCRC_ctx;
begin
 TextLen := Length(Text);
 for i := 1 to TextLen do
  buf[i - 1] := Byte(Text[i]);

 cm_Create(CRC32_Zip, nil, ctx);
 cm_Full(ctx, CRC, @buf, TextLen);

 Result := IntToHex(CRC, 8);
end;

[hoika]

Hallo,
wenn es ein kann ist, nimm eine GUID und lass den arnen String in Ruhe.

[Bünni]

Meinst du damit GUID := System.SysUtils.StringToGUID('test') ?

Laut fandom funktioniert das nur mit Strings im GUID Format
https://delphi.fandom.com/wiki/StringToGUID_Routine

[TigerLilly]

CRC ist eine Kontrollsumme, die es dir erlaubt, zu prüfen, ob ein String verändert wurde. CRCs sind nicht eindeutig, soll heißen, unterschiedliche Strings können gleiche CRCs haben.

Eine Hash-Funktion wäre eine Möglichkeit, aber da kann es auch zu Kollisionen kommen.

Du kannst ein Lexikon anlegen + deine Strings nummerieren.
Du kannst die Zahlenwerte der Zeichen nehmen und so eine Zahl erzeugen, die ist eindeutig (sogar eineindeutig, weil umkehrbar).

Was magst denn machen, mit den IDs + was sind denn das für Strings?

[peterbelow]

Zitat:

Zitat von Bünni (Beitrag 1430604)

Für die Lösung eines Problems benötige ich demnächst vermutlich etwas wie eine eindeutige ID, welche ich aus einem gegebenem String berechnen kann, der ohnehin schon eindeutig ist und nur einmal vorkommen kann. Die ID benötige ich aus diversen Gründen zusätzlich.

Die ID sollte wenn möglich nicht so lang sein wie MD5. Welche Möglichkeiten bleiben mir da noch? Mir stehen dafür unter anderem die Wolfgang Ehrhardt Komponenten zur Verfügung.

Ich habe gerade CRC32 getestet. Aber ist das eindeutig genug?

Nein, definitiv nicht. Egal wie Du die ID berechnest, wenn sie kürzer ist als der Ursprungsstring kannst Du nie garantieren, das die erhaltene ID nicht auch aus einem anderen Input resultieren könnte. Das ist auch der Grund, wieso man bei Datenstrukturen, die einen aus einem String oder anderen Daten berechneten Hash-Wert als Schlüssel benutzen, den Orginalwert immer mit ablegen muss, damit man später solche Kollisionen erkennen kann.

Man kann zwar (theoretisch) für jeden gegebenen Satz von Strings ein Hash-Funktion finden, die innerhalb dieses Satzes für jeden der Strings einen eindeutigen Wert liefert, aber halt garantiert nur für Strings in dem vorgegebenen Satz, nicht für andere.

Wozu brauchst Du denn die ID, und muss sie unbedingt aus dem String berechnet sein? Wenn beides eigentlich voneinander unabhängig ist und Du nur eine eindeutige ID brauchst ist eine GUID keine schlechte Wahl.

[Klaus01]

.. von wievielen Strings sprechen wir denn hier?

was zum Lesen: https://ethblog.de/wie-funktioniert-hashing/
https://arstechnica.com/civis/viewtopic.php?t=149670

eine GUID ist nicht wesentlich kürzer als z.B. ein MD5 Hash

Grüße
Klaus

[Bünni]

Ich brauche diese ID leider. MD5 und andere Hashes sind zu lang, da ich sonst Probleme mit zu langen Pfaden im Dateisystem bekommen könnte (nicht sicher).
Anders als aus einem String kann ich die ID auch nicht berechnen, da ich nur den String als Basisinformation habe.

Anhand des Strings wird ein Verzeichnis angelegt. Der String wird vorher aber bereinigt und unzulässige Zeichen und andere besondere Zeichen entfernt.
Es gibt Konstellationen, da bleibt am Ende das gleiche Ergebnis übrig. Deswegen würde ich gerne eine ID hinten dranhängen.

Eine GUID würde ich gerne vermeiden da man so nie weiß welches Verzeichnis mit welcher GUID zu welchem Datensatz gehört.

[FaTaLGuiLLoTiNe]

Kannst du nicht einfach laufende Nummern verwenden und dir irgendwo ein Verzeichnis anlegen, in dem du dir die Zuordnung von String zu Nummer (= Name des Ordners) merkst?

[Bünni]

Jeder Datensatz hat intern einen Index, der sich aber bei jedem Programmstart ändern kann je nachdem, ob die Daten verändert wurden oder nicht. Im Normalfall ist davon auszugehen, dass sich die Daten bei jeder Sitzung mindestens einmal stark ändern. Leider nicht möglich mit einem Index.

Eine GUID wäre eventuell eine Lösung, wenn ich sie auch für jeden Datensatz in der Konfigurationsdatei mit ablege.
Aber wie berechnet man eine korrekt formatierte GUID aus einem String?

[Schokohase]

Ob der MD5 HashWert in der Darstellung zu lang wird, hat doch nur etwas mit der Art der Darstellung zu tun.

Ein MD5-HashWert hat 128-bit. Diesen kann man Hexadezimal darstellen und erhält 32 Zeichen.

Code:

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

Zu lang? Dann hätten wir da noch eine Base64-Darstellung und erhalten von dem gleichen Wert

Code:

/////////////////////w==

also 24 Zeichen (bzw. 22 denn die letzten beiden sind in diesem Falle immer gleich).

Also, wie lang darf die errechnete ID aus dem String denn nun sein?

PS: Wer jetzt einwenden möchte, dass in dem Base64 Zeichen vorkommen, die in einem Pfad nicht vorkommen dürfen, der hat Recht und ich überlasse es jedem selber dieses mit etwas Fantasie selber zu lösen.

[Bünni]

So gesehen darf die ID so lang sein, bis das Dateisystem damit nicht mehr zurecht kommt. Der besseren Lesbarkeit aber dachte ich, je kürzer desto besser.

Ich glaube CRC32 reicht nachdem ich mir die Antwort von Victor Stoddard durchgelesen habe
https://stackoverflow.com/questions/...for-common-use

Und dann wäre da noch S. Lott
https://stackoverflow.com/questions/...-vs-crc-length

[Uwe Raabe]

Zitat:

Zitat von Bünni (Beitrag 1430616)

Anhand des Strings wird ein Verzeichnis angelegt. Der String wird vorher aber bereinigt und unzulässige Zeichen und andere besondere Zeichen entfernt.
Es gibt Konstellationen, da bleibt am Ende das gleiche Ergebnis übrig. Deswegen würde ich gerne eine ID hinten dranhängen.

In dem Fall könnte der CRC-Wert des originalen Strings tatsächlich funktionieren. Die Wahrscheinlichkeit, daß der CRC-Wert unterschiedlicher Strings gleich ist und das auch die bereinigten Strings dasselbe Ergebnis bringen ist ziemlich unwahrscheinlich.

Kannst du den Originalstring nicht in einer kleinen Textdatei in dem jeweiligen Verzeichnis speichern? Dann könnte man solche Kollisionen zumindest erkennen und man hätte auch noch Zugriff auf den Originalstring.

[Bünni]

Die Originalstrings werden bereits gespeichert und etwaige Duplikate schon behandelt.
Die einfachste Umsetzung wäre es das Verzeichnis in den jeweiligen MD5 Hash umzubenennen. Die Benutzerfreundlichkeit sinkt dann aber, weil ein Benutzer nicht mehr auf Anhieb sieht, welches Verzeichnis zu welchem Datensatz gehört.

[Uwe Raabe]

Hast du mal probiert, ob es tatsächlich noch zu Kollisionen kommt, wenn du den CRC an den bereinigten String anhängst?

[dummzeuch]

Welche Zeichen können in den Strings denn vorkommen? Ggf. kann durch eine geschickte Kodierung daraus immernoch eindeutige aber deutlich kürzere Binärcodes erzeugen.

Beispiel:

Wenn in den Strings nur die Großbuchstaben A-Z und die Ziffern 0-9 vorkommen, muss pro Zeichen eigentlich nur ein Wert von 0-35 abgespeichert werden, nicht von 0-255 (AnsiChar) oder gar mehr. Damit könnte man 256/36 = > 7 Zeichen in einem Byte abspeichern.

Das ist natürlich nicht ganz ungefährlich, wenn Du nicht sicherstellen kannst, dass sich dieser Zeichenbereich nicht irgendwann ändert. Irgendwann kommt der Chef und sagt, "Wir lassen jetzt auch Kleinbuchstaben und Sonderzeichen zu.", und schon fliegt Dir der Algorithmus um die Ohren. Und erfahrungsgemäß wird der Programmierer bei solchen Entscheidungen nicht vorher gefragt.

EDIT: Ich sehe gerade, dass es im Ergebnis um Verzeichisnamen geht. Damit kann man meine Idee nicht mehr so einfach umsetzen.

[Bünni]

Zitat:

Zitat von Uwe Raabe (Beitrag 1430628)

Hast du mal probiert, ob es tatsächlich noch zu Kollisionen kommt, wenn du den CRC an den bereinigten String anhängst?

Das kann ich leider später erst testen. Ich bin mir aber sehr sicher, dass es nicht mehr zu Kollisionen kommt.

Zitat:

Wenn in den Strings nur die Großbuchstaben A-Z und die Ziffern 0-9 vorkommen, muss pro Zeichen eigentlich nur ein Wert von 0-35 abgespeichert werden, nicht von 0-255 (AnsiChar) oder gar mehr.

Der Zeichenbereich dürfte wegen Kompatibilitätsgründen eigentlich immer gleich bleiben. Aber es sind dann leider doch ein paar Zeichen mehr die erlaubt sind.

[peterbelow]

Zitat:

Zitat von Bünni (Beitrag 1430626)

Die Originalstrings werden bereits gespeichert und etwaige Duplikate schon behandelt.
Die einfachste Umsetzung wäre es das Verzeichnis in den jeweiligen MD5 Hash umzubenennen. Die Benutzerfreundlichkeit sinkt dann aber, weil ein Benutzer nicht mehr auf Anhieb sieht, welches Verzeichnis zu welchem Datensatz gehört.

Mal eine Bemerkung dazu, die vielleicht etwas off -topic ist. Für einen Benutzer ist das Ablegen von Datensätzen in Dateien mit langen Namen ein usability-Alptraum, egal ob Du nun noch eine ID anhängst oder nicht. Hast Du mal versucht, in einem Verzeichnis mit mehreren Hundert Dateien mit langen Namen etwas zu finden? Das geht eigentlich (im Explorer) nur mit der Suchfunktion, alles andere ist eine Strafe, besonders, wenn die Namen auch noch so lang sind, dass sie im Explorerfenster abgeschnitten werden.

Häng die ID an, das macht es auch nicht viel schlimmer als es eh schon ist.

[Bünni]

Die Verzeichnisse werden jetzt nach einem MD5 Hash benannt. Das war die einfachste Umsetzung, ohne dass man noch an anderen Stellen Anpassungen machen muss die bei jeder kleinen Änderung hinfällig sind. Eigentlich hat ein Nutzer in diesen Daten nichts zu suchen, da alles über die Benutzeroberfläche und Business Logik erledigt wird.

[Dennis07]

Bedenkt, dass Hashes ebenso nicht "eindeutig" sind, da zu jedem Hash auch unbegrenzt viele Strings gehören.
CRC32 ist nur deshalb keine Hashfunktion, weil du aus ihr den eigentlichen String sehr leicht wieder zurückgewinnen kannst. Dennoch hast du das gleiche Problem, wenngleich graduell geringer, auch bei Hashfunktionen (was diese von "Verschlüsselungen" unterscheidet).
Es gibt so gesehen keine wirklich effiziente Möglichkeit, einen String in eine Zahl zu verwandeln, die wirklich eindeutig ist, ohne den vollen String selber zu beinhalten.
Was du machen könntest, wäre noch folgendes (keine sichere Verschlüsselung!):
Jedes ACSII-Zeichen befindet sich im Bereich von 0 bis 127. Solltest du also nur diese Zeichen brauchen, kannst du den zweiten teil des Bytes hinten weg lassen und mit dem nächsten Zeichen füllen. Ist aber auch nicht 100%-ig eindeutig, und vor allem nur für Zeichen des Standardzeichensatzes.

[Nju]

Ich klinke mich mal mit ein:
Der Threadersteller möchte eine eindeutige ID. CRC ist nicht dazu gedacht, eindeutige IDs zu generieren, da eine Kollision zu schnell herbeigeführt werden kann. Wikipedia gibt dazu als Beispiel die Wörter "buckeroo" und "plumless" an, die den gleichen CRC32-Wert besitzen. Die Wahrscheinlichkeit, dass der Threadersteller eine Kollision erhält, ist nicht unwahrscheinlich.

*edit*
Ich habe mir den ganzen Thread nochmal durchgelesen. Der Sinn des Ganzen erstreckt sich mir zwar nicht, aber von CRC würde ich absehen. Eine fortlaufende Nummer reicht da in meinen Augen als eindeutige Identifizierung.

[dummzeuch]

Zitat:

Zitat von Dennis07 (Beitrag 1430672)

Bedenkt, dass Hashes ebenso nicht "eindeutig" sind, da zu jedem Hash auch unbegrenzt viele Strings gehören.
CRC32 ist nur deshalb keine Hashfunktion, weil du aus ihr den eigentlichen String sehr leicht wieder zurückgewinnen kannst.

Das ist falsch. Was man leicht finden kann, ist eine Eingabe, die denselben CRC32-Wert ergibt, nicht jedoch notwendigerweise die Eingabe, die den CRC32-Wert ergeben hat. Letzteres ist schlicht unmöglich, es sei denn, die möglichen Eingaben sind sehr beschränkt.

[Dennis07]

Zitat:

Zitat von dummzeuch (Beitrag 1430677)

Zitat:

Zitat von Dennis07 (Beitrag 1430672)

Bedenkt, dass Hashes ebenso nicht "eindeutig" sind, da zu jedem Hash auch unbegrenzt viele Strings gehören.
CRC32 ist nur deshalb keine Hashfunktion, weil du aus ihr den eigentlichen String sehr leicht wieder zurückgewinnen kannst.

Das ist falsch. Was man leicht finden kann, ist eine Eingabe, die denselben CRC32-Wert ergibt, nicht jedoch notwendigerweise die Eingabe, die den CRC32-Wert ergeben hat. Letzteres ist schlicht unmöglich, es sei denn, die möglichen Eingaben sind sehr beschränkt.

Der erste von dir zitierte Satz sagt doch genau das. Wenn du aber nur auf den zweiten inhaltlich eingehst, so kann es natürlich durchaus zu so einem Missverständnis kommen, da nur der allein nicht ganz eindeutig ist (genau wie Hashes und CRC32, ha ha).
Und selbst dann ist dein Einwand doch vollkommen irelevant, weil das Problem doch trotzdem da ist: Es gibt mehrere Strings mit dem selben CRC-Wert. Also ist er nicht eindeutig, zumindest nicht in beide Richtungen. Somit für die Fragestellung nicht zu gebrauchen. Meine Aussage war ja nur, dass das bei Hashfunktionen halt eben nur graduell anders ist: Auch diese sind nicht eindeutig.

Zur Sicherheit, und warum CRC für Hashes ungeeignet ist: Ja, natürlich bekommst du in beiden Fällen nicht das originale Word zurück. Ist aber doch vollkommen egal. Ein möglicher Hash reicht ja schon. Und da es bei CRC32 nun mal, wie von mir beschrieben, sehr leicht ist, diesen bzw. eins zu bekommen, ist es ungeeignet. Das heißt aber nicht, dass Hashfunktionen wie SHA128 "eindeutig" sind. Sie sind nur "eineutiger".

[Sherlock]

Verstehe nicht, was gegen "Durchnummerieren" spricht.

Und nur zum Verständnis: eine GUID wird nicht aus einem String errechnet, sondern ist eine zusammengesetzte 128-Bit Zahl mit Zeitanteilen, Versionsangabe und einem großen pseudozufälligen Rest.

Sherlock

[Dennis07]

Zitat:

Zitat von Sherlock (Beitrag 1430793)

Verstehe nicht, was gegen "Durchnummerieren" spricht.

Ich denke das ist nicht wirklich, was er will.
Dafür müsstest du ja eine

Delphi-Quellcode:

TStringList

oder besser noch ein

Delphi-Quellcode:

TDictionary<String, Integer>

machen, und alles dort nochmal separat abspeichern.

[TurboMagic]

Schon mal nach alternativen Hash Algorithmen als MD5 geschaut? Es gibt auch welche die nur 64 bit oder 80 bit lange Hashes erzeugen.

DEC beispielsweise enthält die Klasse THash_Sapphire, welche einen Hash Algorithmus umsetzt, der 64 bit Ergebnisse produziert.
DEC ist via Github hier zu finden: https://github.com/winkelsdorf/Delph...tionCompendium

[jfheins]

Zitat:

Zitat von Bünni (Beitrag 1430626)

Die einfachste Umsetzung wäre es das Verzeichnis in den jeweiligen MD5 Hash umzubenennen. Die Benutzerfreundlichkeit sinkt dann aber, weil ein Benutzer nicht mehr auf Anhieb sieht, welches Verzeichnis zu welchem Datensatz gehört.

Ich würde mich da an vorhandenen Lösungen orientieren. git zum Beispiel speichert alle Objekcte unter ihren SHA1 Hash-Werten. Das heißt, ein Objekt hat den Hashwert d670460b4b4aece5915caf5c68d12f560a9fe3e4 und wird dann unter dem Dateipfad .git/objects/d6/70460b4b4aece5915caf5c68d12f560a9fe3e4 abgelegt.

Macht insg. maximal 256 Ordner und darin dann viele Dateien, im Falle von git meistens mit SHA-1 (wird aber umgestellt glaub ich).

Das Argument "Eigentlich hat ein Nutzer in diesen Daten nichts zu suchen, da alles über die Benutzeroberfläche und Business Logik erledigt wird." ist super, wenn eh alle in der Anwendung abrufbar ist, fummeln User in einer zugänglichen Datenstruktur nur zuviel rum.

[Jasocul]

Vielleicht ein wenig OT aber vielleicht doch relevant:

Zitat:

Zitat von Bünni (Beitrag 1430626)

Die Benutzerfreundlichkeit sinkt dann aber, weil ein Benutzer nicht mehr auf Anhieb sieht, welches Verzeichnis zu welchem Datensatz gehört.

Der Benutzer kann dirket auf die Verzeichnisse zugreifen?:gruebel:
Das halte ich für nicht ganz ungefährlich. Vielleicht gefällt dem Benutzer ja der Verzeichnisname nicht und er ändert den. Die Konsequenzen für deine Anwendung kannst nur du abschätzen.

Zitat:

Zitat von Bünni (Beitrag 1430620)

Jeder Datensatz hat intern einen Index, der sich aber bei jedem Programmstart ändern kann je nachdem, ob die Daten verändert wurden oder nicht. Im Normalfall ist davon auszugehen, dass sich die Daten bei jeder Sitzung mindestens einmal stark ändern.

Der Index (oder besser die ID) eines Datensatzes sollte man nicht ändern. Der Index in deinem TreeView, wo du möglicherweise deine Daten einliest, hat mit dem Datensatz absolut gar nichts zu tun.

Wenn deine Datensätze eine eindeutige ID haben, dann nutze diese. Wenn nicht, dann erzeuge dir welche. Damit bist du dein Problem sofort los, da du die ID für die Verzeichnisse nutzen kannst.
Ich kenne deine Anwendung nicht, aber die Nutzung dieser Verzeichnisse sollte nur über die Anwendung passieren. Sobald ein Anwender darin rumpfuschen kann, wird das auch passieren. D.h.: Die Verzeichnisnamen müssen (besser dürfen) für den Anwender nicht lesbar sein. Sobald diese lesbar sind, werden diese "verbessert".

EDIT:

Zitat:

Zitat von Bünni (Beitrag 1430616)

Anhand des Strings wird ein Verzeichnis angelegt. Der String wird vorher aber bereinigt und unzulässige Zeichen und andere besondere Zeichen entfernt.
Es gibt Konstellationen, da bleibt am Ende das gleiche Ergebnis übrig. Deswegen würde ich gerne eine ID hinten dranhängen

Wenn du es denn wirklich so machen willst, ist es ziemlich egal, welche Mehode du verwendest, da der String selbst ja ein Teil des Verzeichnisnamens ist. Ein angehänges crc, Hash oder sonstwas wird es dir eindeutig machen. Die Gefahr, das zwei verschiedene Strings die selbe "ID" erzeugen macht gar nichts, da der String auch Teil des Names ist.

[AndyDF]

Hier findest du noch Informationen zum Erzeugen eines 32-Bit Integer Hashes eines Strings:

https://stackoverflow.com/questions/...shing-function

Schau dir dort mal die Funktion Murmur2 an.

Kollisionen sind sicher möglich. Ist aber alles eine Frage der Wahrscheinlichkeit.

[Luckie]

Noch eine Anmerkung zu den gebrochenen Hashes. Ich denke, das spielt für ihn keine Rolle. Da das nur unter Laborbedingungen passiert oder bei gezielten Angriffen. Dass sein Programm doppelte Hashes erzeugt, dürfte verschwindet gering sein. Wie viele Jahrzehnte hat man mit ihnen selbst bei sicherheitskritischen Anwendungen gearbeitet?

[Rudy Velthuis]

Zitat:

Zitat von FaTaLGuiLLoTiNe (Beitrag 1430617)

Kannst du nicht einfach laufende Nummern verwenden und dir irgendwo ein Verzeichnis anlegen, in dem du dir die Zuordnung von String zu Nummer (= Name des Ordners) merkst?

Genau das war auch mein Gedanke. Einfach die Kollisionen durchnumerieren.

[Redeemer]

Zitat:

Zitat von dummzeuch (Beitrag 1430629)

Welche Zeichen können in den Strings denn vorkommen? Ggf. kann durch eine geschickte Kodierung daraus immernoch eindeutige aber deutlich kürzere Binärcodes erzeugen.

Beispiel:

Wenn in den Strings nur die Großbuchstaben A-Z und die Ziffern 0-9 vorkommen, muss pro Zeichen eigentlich nur ein Wert von 0-35 abgespeichert werden, nicht von 0-255 (AnsiChar) oder gar mehr. Damit könnte man 256/36 = > 7 Zeichen in einem Byte abspeichern.

Das ist auf so viele Arten und Weisen einfach nur falsch:

• Der Zeichenvorrat beträgt nicht 256. Wenn man von ANSI ausgeht, liegt die Anzahl der Zeichen bei etwa 215 (unter Abzug von neun sichtbaren nicht erlaubten Zeichen und 32 Steuerzeichen).
• Der Zeichensatz von NTFS ist aber UTF-16. Da man UTF-16-Codepunkte nicht beliebig aneinanderreihen kann, muss man stattdessen UCS-2 verwenden. Von dessen 63.488 Zeichen zieht man dann wieder die 41 ab. Ich würde mal vermuten, dass man auch hier nicht alle Zeichen verwenden kann, aber es geht um die Größenordnung.
• Und das schlimmste: Man kann nicht einfach dividieren. Korrekt wären also für ANSI lb(215)/lb(36), was nur ganz knapp unter 1,5 ergibt. Für UCS-2 ergibt sich mit lb(63447)/lb(36) erwartungsgemäßg gut das Doppelte (ca. 3,09). Von deiner 7 ist man sehr sehr weit entfernt.

(Edit: Natürlich kann man statt lb auch ln oder lg rechnen. lb ergibt aber am meisten Sinn, da man so sofort erkennt, dass es hier um die Entropie (in Bit) geht, die sich damit ergibt. Und das Verhältnis der Entropien ist ja anschaulich das, worum es dummzeuch ging.)