Eindeutige ID/Hash aus Werten

[BeRsErKeR]

Ich bin leider nicht so erfahren im Bereich Hash-Werte und Generierung eindeutiger IDs. Es geht um Hilfe-IDs, die abhängig von 3 Werten eindeutig sein müssen:

• n: Nummer (5-stellig von 0 bis 60000)
• z: Zusatznummer (3-stellig von 0 bis 256)
• f: Einem 32Bit Flagwert

Bei f gilt, dass bislang 0, 1, 2 oder 3 beliebige Bits gesetzt sein können. In Zukunft könnte sich die Anzahl der gesetzten Bits aber eventuell noch erhöhen.

Noch zu beachten ist, dass die generierte ID nur 32Bit groß sein darf. Mir macht dieser Flagwert einen Strich durch die Rechnung. Wenn nur 1 Bit gesetzt werden könnte, könnte man einfach die Stelle dieses Bits (1-32 und 0 für kein Bit) nehmen und das ganze so kodieren:

ffnnnnnzzz

Die Zahl wäre dann immer kleiner als 4 Milliarden (da am Anfang maximal 32 steht) und würde so immer in 32 Bits passen. Unglücklicherweise können mehrere Bits gesetzt sein, daher brauch ich eine Art Hash-Algorithmus oder eine andere Kodierung.

Hat da vielleicht jemand eine Idee oder kennt hilfreiche Literatur zu dem Thema?

[Alexander Kornrumpf]

Der Sinn bei nem Hash ist ja dass es Kollision geben kann.

Wenn du eindeutige IDs braucht, brauchst du ja für jede Kombination aus Werten eine ID. Was du tasächlich willst ist

log(60000) + log(256) + 32bit also etwa 56 bit verlustfrei in 32 bit stecken. Wie soll das gehen? Ich bin jetzt zu Faul auszurechnen wieviele bits von dem Flag du effektiv tatsächlich nutzt. Wenn es mehr als 8 sein sollten ist dein Problem so nicht lösbar.

EDIT: Also ich gehe davon aus dass die Entropie von jedem Bit auch wirklich näherungsweise 1 bit ist.

[antisteo]

Als "Hashfunktion" kann ich dir ein Base64 der Einzelbits empfehlen, das kodiert immer eindeutig.

Oder willst du den Wert zusätzlich scrambeln?

[EyDu]

Es wurde ja bereits beschrieben, warum das mathematisch gesehen im allgemeinen Fall nicht funktionieren kann. Hilfreich wären vielleicht Informationen wie stark du die einzelnen Wertebereiche ausnutzt. Sind für n, z und f wirklich alle Kombinationen erlaubt oder werden bestimmte Bits vielleicht gar nicht genutzt? Es wäre auch interessant, warum du dich auf 32 Bit beschränkst und wie du die Hashwerte einsetzen willst. Soll er einfach nur zur Identifikation dienen oder handelt es sich dabei beispielsweise um ein Schlüssel für ein Dictionary (dann wären 32 Bit nämlich etwas viel ^^).

Sebastian

[BeRsErKeR]

Es gibt in der Regel pro n nur eine Hand voll z-Kombinationen. Insgesamt sind es in etwa 50000-100000 verschiedene Kombinationen (also wirklich die endgültigen 32Bit Werte). Allerdings folgen diese keinen bestimmten Regeln.

32Bit deshalb, weil es sich um HilfeIDs (in CHM-Dateien) handelt und diese halt als DWORD festgelegt sind. Das ganze muss mindestens auf WindowsXP (32Bit) laufen!

Wie gesagt sind nur maximal 100000, vielleicht auch 150000 IDs von den 2^32 möglichen, nötig. Das Problem ist halt, dass mehr oder minder zufällig ist, welche Kombinationen es gibt und welche nicht. Und es MUSS in jedem Fall eindeutig sein.


Noch ein bischen genauer:

n ist eine Parameternummer aus einem Gerät. Diese kann wirklich alles von 0-60000 sein. z ist quasi eine Ausprägung des Geräteparameters, da es den Parameter mehrfach für spezielle Zusatzmodule etc geben kann. Diese sind allerdings sehr begrenzt, sodass es halt meist gar keinen oder maximal 2-3 Ausprägungen gibt. z ist dabei aber eine bestimmte Identifikationsnummer, also nicht hochgezählt von 0 bis 3 oder so. Die Flags haben eine ähnliche Aufgabe für aufgesetzte Zusatzmodule. Jedes Bit entspricht dabei einem Slot. Ich habe keine Möglichkeit diesen Ramsch umzubauen, ich kann nur die Schnittstelle anpassen. Bislang geschieht das über ein Mapping in einer Art INI-Datei, die zu diesen Kombinationen die Hilfe-ID speichert. Aber beim Hilfeaufruf jedesmal eine riesige Datei zu laden um eine ID auszulesen ist einfach nicht tragbar. Daher mein Anliegen. Die IDs zu Beginn einmal auszulesen und im Speicher zu halten ist leider auch nicht möglich. Ich kann wirklich nur den Hilfeaufruf modifizieren und die Berechnung der ID.

[Schrompf]

Flag-Möglichkeiten durchzählen und dafür eine ID cachen. Eine andere Möglichkeit sehe ich nicht, da andere ja bereits gezeigt haben, dass der vollständige Wertebereich die 32Bit übersteigt. Wenn aber die Werte-Anzahl von f eingeschränkt ist, müsstest Du mit reinem Durchzählen auf einen sehr viel kleineren Wertebereich kommen.

Ob es allerdings reicht, weiß ich nicht. In Deinem Eingangspost steht, dass Du nur 8 Bit für alle f-Möglichkeiten hast. Damit kommst Du nicht weit.

[edit] Ich sehe gerade Deine näheren Erläuterungen. Du könntest evtl. eine vollständige 64Bit-ID aus allen Parametern bilden und die einfach durchzählen und cachen.

[Alexander Kornrumpf]

Warum muss die ID überhaupt von den genannten drei Werten abhängig sein?
Musst du von der ID auch wieder zu den Werten zurück? Vermutlich nein, wenn du nach einem Hash fragst.

[BeRsErKeR]

Ich habe insgesamt 32Bit zur Verfügung. Wieviel davon auf n, z oder f entfallen ist mir ja überlassen. Es wird eine 32Bit-ID draus. n, z und f erhalte ich als 32Bit-Wert, aber wie gesagt sind n und z sehr begrenzt, f kann aber im worst-case auch das 31. Bit gesetzt haben, also prinzipiell 32Bit brauchen.

Das dumme ist auch, dass ich beim Hilfeaufruf nicht alle möglichen Kombinationen kenne. Ich bekomme lediglich die 3 genannten Werte. Ein Durchgehen aller f-Kombinationen ist daher leider nicht möglich.

@Alexander: Du musst bedenken, dass innerhalb der Hilfedatei (CHM) auch eine Zuordnung von ID zum Topic (HTML) erfolgen muss. Sie kann zwar unabhängig von den 3 Werten sein, aber dann muss ich in der Hilfedatei die gleiche Zuordnung herstellen können. Und das geht halt nicht ohne irgendwelchen Abhängigkeiten. Wichtig ist, dass ich die gleiche ID oder den gleichen Hash auf beiden Seiten (Aufrufseite und in der Hilfedatei) berechnen kann. Und da sind halt diese 3 Werte jeweils bekannt.

Prinzipiell ist mir klar, dass man die Informationsmenge nicht in 32Bit gepresst bekommt, aber da sichergestellt ist (bis ans Ende aller Tage), dass nur ein Bruchteil aller möglichen Kombinationen vorhanden sind, sollte es ja schon gehen.

[Alexander Kornrumpf]

Also suchst du eigentlich Kompression (two-way) und keinen Hash?!

Da wird Krishty sicher was zu sagen können.

Ich dilettiere alldiweil ein wenig herum:

Im Grunde musst du halt erstmal 56-bit indizes erzeugen und die durch ein Kompressionsverfahren jagen. Wenn du neue Artikel zur Hilfe hinzufügst, muss der Index jedes mal neu erzeugt werden. Das ist halt der Preis den du zahlst.

EDIT: Statt der INI Datei, die du im Moment lädst musst du dann wohl jedes mal die Kompressionsinformation laden. Die sollte aber kleiner sein(?!)

[BeRsErKeR]

Mein Problem ist dabei folgendes:

Da ich die Hilfe selbst generiere kann ich da schön Indizes erzeugen usw. Auf der Aufrufseite will ich aber gerade ohne das Einlesen einer Datei auskommen. Beim Zeitpunkt des Hilfeaufrufs kenne ich aber eigentlich nur die 3 Werte n, z und f, nicht aber alle anderen Werte. Ich kann also schlecht irgendwas generieren. Wenn ich hier die Index-Datei einlesen würde, könnte ich gleich bei meiner Mapping-Datei (3 Werte -> HilfeID) bleiben. Und wie gesagt kann ich auch nicht beim Programmstart irgendwas einlesen. Ich habe nur Zugriff auf die Schnittstelle des Hilfeaufrufs.

Aber ja, Kompression ist natürlich das was ich möchte. Allerdings mit einem eindeutigen Ergebnis.

[Alexander Kornrumpf]

Crossposting: siehe mein EDIT.

[BeRsErKeR]

Hmm mir liegt eigentlich eher der Dateizugriff schwer im Magen. Nicht nur weil er bei jedem Hilfeaufruf erfolgt, sondern auch, weil wir gerade im Zuge einer Umstrukturierung so viele Dateien wie möglich beseitigen wollen. Außerdem muss man solche Dateien auch immer mitpflegen (ob nun manuell oder automatisiert spielt keine Rolle). Man hat also wieder eine potentielle Fehlerquelle mehr.

Ich habe das Mapping übrigens schon so weit reduziert, dass dort nur noch die f-Kombinationen gezählt werden (wie Schrompf vorschlug) und dazu dann halt Indizes von 0-31 gemappt werden. Damit komme ich wieder zu meiner 32Bit-ID der Form ffnnnnnzzz. Die nnnnnzzz-Komponente ist ja eh immer eindeutig und passt rein. Dadurch muss ich nicht alle Kombinationen aus n und z auch noch mappen. Die Mapping-Datei ist also schon relativ klein.

[EyDu]

Dann würde ich behaupten, dass dein Problem nicht lösbar ist. Wenn du weder alle Werte generieren kannst, noch ein Vorwissen über die Einzelnen Wertebereiche und deren Kombinationen, dann kann nur der allgemeinste Fall angenommen werden. Dann ist auch keine Komprimierung möglich.

[BeRsErKeR]

Naja die Wertebereiche kenne ich. Ich kann sogar die Flags einschränken, indem maximal 3 Bits gleichzeitig gesetzt sein können. n ist wie gesagt maximal 60000 (passt also sogar in 16 Bit rein), z ist maximal 256 (bzw. 255 sind es eigentlich), passt also in 8 Bit rein.

Ich hab also 8 Bit für die Flags und da können maximal 3 gesetzt sein. Ich wette da kann man was machen...

[Alexander Kornrumpf]

Du wirst dich damit abfinden müssen, dass es prinzipbedingt nicht mehr besser werden kann, als das was du jetzt gemacht hast. Deine Geschätzten 100000 Kombinationen würden theoretisch natürlich auch in weniger als 32 bit passen, aber warum solltest du das wollen.

Im Grunde ist es doch so. Entweder es gibt statische Regeln für die Kombinationen, die existieren, dann kannst du Problemwissen in den Code stecken, oder die Regeln sind dynamisch, d.h. es können überraschend neue Kombinationen hinzukommen, die keiner vorher bekannten Regel folgen. Dann brauchst du ein Verfahren (eben das Kompressionsverfahren) was die Regeln für dich dynamisch induziert. Und dann muss dein Code die Regeln natürlich auch kennen. Also entweder aus einer Datei lesen, oder eben hardkodieren. Was aber im dynamischen Fall zu umständlich ist, weil sich die induzierten Regeln halt ändern wenn sich die Daten ändern. Andere Optionen gibt es nicht

[BeRsErKeR]

Naja aber nehmen wir mal den Fall an, dass in den Flags nur 1 Bit gesetzt werden könnte. Ich könnte aus dem 32Bit-Flagwert einen 5Bit-Wert machen, indem ich die Position des Bits speichere. Ok genau genommen bräuchte ich 1 Bit mehr um zu prüfen ob überhaupt ein Bit gesetzt ist. Aber das wäre eine Kompression, die nur auf dem Wissen beruht, dass nur 1 Bit gesetzt sein kann. Nun habe ich das Wissen, das maximal 3 Bits gesetzt sein können. Daher bin ich der Meinung, dass es auch dafür eine Kompression geben könnte. Für diese stehen 8 Bit zur Verfügung.

Als Beispiel könnte ich die 3 Positionen der 3 Bits speichern und wäre bei 15 Bits + 1 Bit (ist überhaupt ein Bit gesetzt?). Also aus dem 32Bit-Wert würde ein 16Bit-Wert. Reicht leider noch nicht, wäre aber schonmal eine gute Komprimierung.

[Alexander Kornrumpf]

EDIT: Hier stand totaler müll.

[Schrompf]

Du hast also 3 aus 32 Bit. Du könntest iterativ die Abstände zum nächsten kodieren, aber dafür bräuchtest Du schon für die Position des ersten gesetzten Bits 5Bit, jedes weitere Bit wäre dann wegen eingeschränktem Rest-Bereich mit weniger Bits zu kodieren. Das wird bei 8Bit aber verdammt knapp bis unmöglich.

[edit]Überholt. Du hattest bereits die gleiche Idee. Reicht aber immernoch nicht. Aber ein reines Aufzählen aller Möglichkeiten könnte evtl. noch was rausholen. Wenn das erste Bit ziemlich weit hinten liegt, können die anderen ja nur noch dahinter rauskommen. Ich kann das gerade nicht in Formeln fassen, aber so grob die Hälfte der Möglichkeiten fällt damit nochmal raus.

[Alexander Kornrumpf]

Anders ausgedrückt: Wenn du sicher bist, dass du nie mehr als 3 von 32 bits setzt reichen 9 bit um das systematisch zu kodieren. dann müsstest du aber noch an anderer stelle 0.8 bit oder so einsparen. Die frage ist ob du für deine anderen Werte ebenfalls so eine regel wie "es sind nie mehr als 3 bit gesetzt" formulieren kannst. Du sagstest bislang nein. Nichtmal die 3 bit regel sollte bis in alle Ewigkeit gelten sagtest du. Also wird es nicht gehen ohne dass du jedesmal wenn eine neue Kombination hinzukommst die Regeln anpasst.

[BeRsErKeR]

Ok vielen Dank erstmal. Ich versuche dann mal den harten Weg und versuche der Entwicklung zu verklickern, dass sie diesen FlagKrams als eigenständiges z kodieren soll. Dann sind die Probleme eh weg.

[B.G.Michi]

wenn für ein 32bit-Flag maximal 3 Werte gesetzt sein können, also 0, 1, 2 oder 3, hast du folgende Anzahl an Möglichkeiten:
(0 über 32) + (1 über 32) + (2 über 32) + (3 über 32) = 1 + 32 + 496 + 4960 = 5489
und das passt nicht in deine 8 verbleibenden Bits

edit: oh entschuldigt, hab die 2. Seite übersehen

[Alexander Kornrumpf]

Nur fürs Protokoll:

Ich hatte oben großen Mist gemacht, was die Anzahl der Möglichkeiten angeht.

B.G. Michi hat recht wobei es allerdings 32 über x heißen muss.

Du brauchst also etwa 13 bit und nicht 9 wie oben angegeben.