Ich versuche eine (perfekte) Hash-Tabelle zu schreiben, um das Mapping von unicode codepoint names to their codepoint number zu komprimieren (Zuordnung der zweiten Spalte zur ersten Spalte). Wie Sie dort sehen können, sind die möglichen Eingaben sehr eingeschränkt, tatsächlich gibt es genau 38 Zeichen im Alphabet: AB...YZ, 0...9, - und Leerzeichen. Darüber hinaus gibt es eine Menge von (Teilzeichenfolge) Wiederholung, DIGIT ZERO, DIGIT ONE, ..., LATIN CAPITAL LETTER A, LATIN CAPITAL LETTER B usw.Effiziente Hash-Funktion für alphanumerische Strings mit niedriger Entropie
Die perfekte Hash-Tabelle wird durch die Wahl eines Samens S, berechnet und dann eine perfekte Hash-Tabelle zu konstruieren versucht Seeding (in irgendeiner Weise) der Hasher von S. Wenn eine Tabelle nicht erstellt werden kann, wird mit einem neuen Seed erneut versucht. Bei vielen Kollisionen sind in der Regel mehr Wiederholungen erforderlich, da es für den Algorithmus schwieriger ist, alles anzupassen.
Das Ergebnis davon ist, dass meine Eingabe-Domain niedrige Entropie hat, und die Erstellung der Tabelle erfordert viele Wiederholungen mit einfachen Hash-Funktionen wie DJB2; Bessere Hashes wie FNV funktionieren ziemlich gut, aber kompliziertere und langsamere Funktionen wie SipHash scheinen im Durchschnitt noch weniger Wiederholungen zu erfordern.
Da dies völlig statisch und vorberechnet ist, mache ich mir keine Sorgen um Qualität um der Qualität willen (dh Sicherheit und probabilistische Verteilung für beliebige Eingabe zur Laufzeit ist egal), aber die höherwertigen Funktionen reduzieren die benötigte Vorberechnungszeit Für eine bestimmte Komprimierungsstufe kann ich umgekehrt eine höhere Komprimierung in einer bestimmten Zeit erreichen.
Frage: Gibt es effiziente veröffentlichte Hash-Funktionen, die auf Eingabe mit Domänenbedingungen wie diesem abgestimmt sind? Das heißt, gibt es Hash-Funktionen, die die zusätzliche Struktur ausnutzen, um weniger Operationen auszuführen, aber dennoch eine vernünftige Ausgabe zu erzielen?
Ich habe nach Dingen wie 'alphanumerische Hash-Funktion' gesucht, aber die Ergebnisse sind nicht verwandt (meist nur eine alphanumerische Zeichenfolge als Ausgabe einer Hash-Funktion generieren); sogar eine Anleitung über den richtigen Jargon, damit ich nach Papieren suchen kann, wäre hilfreich.
(Diese Frage wird durch geringfügig interessant zu lösen, nicht wirklich notwendig motiviert.)
Sie wollen einen perfekten Hash für 27268 Artikel? Scheint mir schwer. Warum nicht einfach eine * standard * -Hashfunktion verwenden und die Kollisionen behandeln? (und vielleicht einen niedrigen Füllfaktor) – wildplasser
@WildPlasser es funktioniert gut, es kann nur eine Weile dauern, um zu generieren. Z.B. [dieses Array] (https://github.com/huonw/unicode_names/blob/1f331f78201b914604346e1d6fc3e9b3b2eda772/src/generated_phf.rs # L771) ist die Hashtabelle selbst: Verwenden Sie den Hash der Eingabezeichenfolge als Index in diese Tabelle (und verifizieren Sie, dass sie korrekt ist). Der Sinn dieser Frage besteht darin, die Struktur der Eingabe so zu nutzen, dass sie schneller ist und möglichst wenig Arbeit verrichtet. Dies gilt auch für die Komprimierung, so dass ein niedriger Lastfaktor nicht gut ist. – huon
@wildplasser Schließlich, beachte, dass ich derzeit eine Standard-Hash-Funktion verwende (ich erwähne drei in der Frage). – huon