Aus String eindeutige ID (oder ähnliches) machen

[Grendel]

Ist zwar nicht das kürzeste aber ich nutze in solchen Fällen immer eine GUID.

Bis neulich ...

[negaH]

Zitat:

Und zwar geht es darum, aus deinem String eine eindeutige ID zu machen

Denken wir einfach mal laut

Was ist ein String ?

Er besteht aus einer Kette von Zeichen aus dem ASCII Zeichensatz, nennen wir mal ein Set aus Symbolen. Ein Symbol in diesem Set kann einen Wert von 0 bis 255 haben, ergo 8Bit = 2^8 = 256 maximale Symbole gibt es. Jedes dieser Symbol kann GLEICHWERTIG in dem String vorkommen.

Wenn wir also einen String mit 1 Zeichen betrachten dann stellen wir fest das es 256 verschiedene Strings geben kann. Das bedeutet wenn wir die EINDEUTIGKEIT einer ID erhalten wollen dann würde die Mappingfunktion ID = f(String), also die Funktion f(), nichts anders als ein 1 zu 1 Mapping sein. Wir müssen also die max. vorkommende Länge deiner Strings hernehmen und daraus IDs erzeugen die die exakt gleiche maximale Länge haben.

Wenn du also eine EINDEUTIGE ID zu einem String haben möchtest dann ist defakto der String selber die ID. Denn der String IST eindeutig in der Menge aller vorkommenden Strings bestehend aus unseren Symbolen. Diese Eindeutigkeit kann nicht erhalten bleiben wenn unsere IDs kürzer als der String sein soll, denn logischerweise müssen wir wichtige Informationen entfernen um diese ID kürzer machen zu können als die eh schon eindeutigen Strings.

Es gibt also keine Funktion, kann es garnicht geben, die das kann was du suchst. Wenn du eine eindeutige ID benötigst die KÜRZER als der eigentliche String ist und immer noch eindeutig, dann geht dies nur wenn in deinen Strings nicht alle 256 Symbole des ASCIIs benutzt werden. Dann kannst du nämlich die Strings durch "Komprimierung" verkürzen. Zb. von den 256 Symbolen werden in den Strings nur die Symbole 'A'..'Z','a'..'z','0'..'9' benutzt. Dann werden also nur 62 Symbole von den 256 möglichen benutzt. Diese unnötige Redundanz die dadurch entsteht kann per Komprimierung/Umkodierung entfernt werden und wir bekomen eine EINDEUTIGE Repräsentation des gleichen Strings die KÜRZER kodiert ist. Nur 62/256*100=25% wäre die Größe deiner so erzeugten ID im Vergleich zu deinem String. Wenn dein String also 256 Zeichen lang ist so muß deine ID unter obigen Annahmen also minimal 64 Bytes groß sein.

Wir trennen uns von dem Gedanken einer "eindeutigen ID" zu einem beliebigen String, denn wie wir oben gesehen haben ist das garnicht logisch machbar wenn wir auch eine kurze ID benötigen und die Strings keine Redundanz im Symbolset enthalten.

Es gibt mehrere Ansatzpunkt die sich aber je nach Anwendungszweck unterscheiden:

1.) kryptographische Hash Funktionen. Diese sind immer dann gut wenn man zu einem String/Datensatz eine möglichst pseudo-eindeutige Signatur wünscht. Diese ID kann niemals wirklich eindeutig sein, aber der Punkt dabei ist das wir sehr sehr viel Zeit und Rechenpower benötigen um überhaupt 2 unterschiedliche Strings zu finden die die gleiche ID erzeugen. Bei MD5 wäre dieser Suchraum dann 2^128 groß und das ist so enorm groß das man keine Kollisionen in annehmbarer Zeit berechnen könnte.
Solche Hashfunktinen haben aber auch enorme Nachteile, je nach Anwednungszweck. Die Hashfunktion wird nämlich die Strings nicht lexikalisch transformieren und somit eine ID erzeugen die die lexikalische Ordnung der Strings widerspiegelt. Das ist defakto für die Kryptographie IDEAL aber nicht wenn wir zb. schnell Strings sortieren/suchen wollen. Dafür gibts

2.) die Hashfunktionen die in Hash-Tabellen benutzt werden. Bei diesen Funktionen versucht man die ID möglichst kurz zu halten und das sie eben auch nach Möglichkeit nicht die lexikalische Ordnung der Strings zerstören. Die ID selber kann benutzt werden zur lexikalischen Sortierung der durch sie repräsentierten Strings. Aber viel öfters benutzt man diese IDs eigentlich nur als Index in die Hashtabelle um so viel schneller die richtige Position unseres Strings in unserer Hashtabelle zu finden. Kollisionen gibt es dabei zu Hauf und man umgeht das Problem indem man Strings mit gleicher Hash-ID in die Hash-Tabelle als verlinkte Liste einfügt. Das heist das zb. im Hashindex=ID=127 nicht nur 1 String eindeutig mappt sondern an dieser Stelle auch x Strings mit gleicher ID aber unterschiedlichen Strings als Liste abspeichert. Diese Hashfunktionen/Hashtabellen sollen also nur die Komplexität der Suche in solchen Bäumen noch weiter reduzieren so das man im Idealfalle auf eine Komplexität von O(n) kommt. Das wäre dann weitaus performanter als zb. eine normale sortierte Liste die mit QuickSort sortierbar ist und bei der man mit QuickFind=binäre Suche arbeiten kann. Die Größe dieser Hashtabelle richtet sich dann nach der zu erwartenden Anzahl der Strings die man unterscheiden möchte. Das bedeutet zb. das man zwar ein Set von 256 Zeichen Strings hat das dann 2^(256*8 ) mögliche Strings enthält. Man weiß aber das zu einem Zeitpunkt zb. durchschnitlich nur mit 1024 verschiedenen Strings zu rechnen ist. Die Hashtabelle würde dann eine Größe von 512 oder 1024 Einträgen besitzen. Im Idealfalle würden diese 1024 Strings alle unterschiedliche HashIDs erzeugen und somit die Hashtabelle komplett mit 1024 Eintrgen gefüllt sein. Die Komplexität wäre dann O(n).
Im schlechtesten Falle würden aber die 1024 Strings alle die gleiche HashID erzeugen und die Hashtabelle hätte nur 1 Eintrag gefüllt aber dann in diesem Eintrag eine verlinkte Liste mit 1024 Strings. In diesem Falle wäre die Komplexität nur noch so hoch wie die Komplexität des Algos. der bentzt wird um diese verlinkte Liste zu erzeugen und darin zu suchen, meisten per QuickSort und/oder QuickFind. Bei dieser Hashtabelle mit 1024 Einträgen müsste unsere ID, zu allen möglichen Strings, also 10 Bit groß = 2^10 = 1024 mögliche IDs zu allen auftretenden Strings. Wesentlich bei Hashtabellen ist es also das die Komplexität und benötigte Speichergröße NICHT mehr von den Größen der Strings abhängig ist sondern primär nur von der Größe der Hashtabelle und diese ist primär abhängig von der Anzahl der vorkommenden Strings die man zu einem Zeitpunt abarbeiten möchte. Man transformiert quasi das Problem und dessen naturgegebener Komplexität (Set der Strings) in ein anders Problem (Set der real abgearbeiten String in der Hashtabelle) mit geringerer Komplexität.

Wichtig ist: bei einer solchen Hashtabelle geht keinerlei Information verloren, da wir ja immer noch in dieser Tabelle die Strings 1 zu 1 abspeichern. Die HashID zu einem String soll und kann nicht eindeutig sein, sondern die Tabelle ansich stellt die Eindeutigkeit her. Die HashID selber dient nur zum schnelleren Auffinden eines Strings in der Tabelle. Wichtig dabei ist das diese Operation schneller sein sollte als alle bekannten Verfahren die man sonst hätte nutzen müssen.

3.) bei 1.) haben wir die Redundanzen innerhalb des Symbolraumes der Strings entfernt und somit eine Reduzierung der ID Größe ereicht. Das Gleiche kann man auch mit dem kompletten Set aller vorkommenden Strings machen. Man betrachtet also nicht mehr die Symbole sondern die Strings als Kombinationen von Symbolen. Dabei geht man davon aus das eben nicht alle möglichen Kombinationen auftreten und versucht diese Kombinationen zu entfernen. Im Idealfalle benutzt man dazu ein Wörterbuch/Dictionary in dem man alle gültigen Kombinationen speichert. Die erzeugte ID repräsentiert dann nichts anders als den Index in dieses Dictionary. Hier im Forum habe ich mein DAWG=Directed Acyclic Word Graph, gepostet (mit Source) mit dem man sowas idealerweise bewerksteligen kann. Damit dürftest du die höchste Komprimierungsrate erhalten, dh. die erzeugte EINDEUTE ID als Index in das Dictionary ist die kürzt mögliche die es überhaupt geben kann ohne die Eindeutigkeit zu verlieren.

Am besten ist es du erklärst ganz genau wofür du das benötigst.

Gruß Hagen