Erzeugen einer perfekten Hash-Funktion bei bekannter String-Liste?

Question

Angenommen, ich habe eine Liste von N Zeichenfolgen, die zur Kompilierzeit bekannt sind.

Ich möchte (zur Kompilierzeit) eine Funktion generieren, die jeden String auf eine bestimmte ganze Zahl zwischen 1 und N einschließlich abbildet. Die Funktion sollte sehr wenig Zeit oder Platz zur Ausführung benötigen.

Angenommen, meine Saiten sind:

{"apple", "orange", "banana"} 

Eine solche Funktion zurückgeben kann:

f("apple") -> 2 
f("orange") -> 1 
f("banana") -> 3 

Was ist eine Strategie, um diese Funktion zu generieren?

Ich dachte, um die Zeichenfolgen zur Kompilierzeit zu analysieren und nach ein paar Konstanten zu suchen, die ich oder durch etwas hinzufügen oder hinzufügen könnte?

Die Zeit/Raum zum Generieren der Kompilierung kann ziemlich teuer sein (aber offensichtlich nicht lächerlich).

Answer 1

Sagen Sie bitte m verschiedene Saiten haben, und lassen Sie ein _{i, j} das te Zeichen des i ten String j sein. Im Folgenden gehe ich davon aus, dass sie alle gleich lang sind. Dies kann leicht in jede vernünftige Programmiersprache übersetzt werden durch Behandlung ein _{i, j} als Null-Zeichen, wenn j ≥ | a _i |.

Die Idee Ich schlage vor, setzt sich aus zwei Teilen zusammen:

1. Suche (höchstens) m - 1 Positionen die Saiten Differenzierung, und diese Positionen speichern.

2. Erstellen Sie eine perfekte Hash-Funktion, indem Sie die Strings als length- m Vektoren betrachten und die Parameter der perfekten Hash-Funktion speichern. 1 Positionen -

---

Offensichtlich Im Allgemeinen muss die Hash-Funktion mindestens m überprüfen. Es ist leicht, dies durch Induktion zu sehen. Bei 2 Strings muss mindestens 1 Zeichen überprüft werden. Angenommen, es gilt für i Zeichenfolgen: i - 1 Positionen müssen überprüft werden. Erstellen Sie eine neue Gruppe von Zeichenfolgen, indem Sie 0 an das Ende der einzelnen Zeichenfolgen anhängen, und fügen Sie eine neue Zeichenfolge hinzu, die mit einer der Zeichenfolgen identisch ist, außer dass sie am Ende eine 1 hat.

Im Gegensatz dazu ist es offensichtlich, dass es möglich ist, höchstens zu finden m - 1 Positionen ausreichend für die Saiten Differenzierung (für einige Sätze die Zahl natürlich könnte an der Basis des Alphabets Größe log niedriger, so niedrig sein, m). Auch das ist durch Induktion leicht zu sehen. Zwei unterschiedliche Strings müssen sich an einer bestimmten Position unterscheiden. Platzieren Sie die Zeichenfolgen in einer Matrix mit m Zeilen, muss es eine Spalte geben, in der nicht alle Zeichen identisch sind. Wenn Sie die Matrix in zwei oder mehr Teile partitionieren und das Argument rekursiv auf jeden Teil mit mehr als zwei Zeilen anwenden, wird dies angezeigt.

Sprich die m - 1 Positionen p 1, ..., p _{m - 1}. Im Folgenden erinnert an die Bedeutung wie oben für ein _{i, p j} für p _j ≥ | a _i |: Es ist das Nullzeichen.

---

lassen Sie uns h definieren (a _i) = ∑ _{j = 1}^{m - 1} [q _j einem _{i, p j}% n], für zufällig q _j und einige n. Dann hknown to be a universal hash function ist: die Wahrscheinlichkeit der Paarkollisions P (x ≠ y ∧ h (x) = h (y)) ≤ 1/n.

---

Angesichts einer universellen Hash-Funktion gibt es known constructions for creating a perfect hash function from it. Vielleicht die einfachste ist die Schaffung einer Vektor der Größe m und nacheinander die oben h mit Versuch n = m mit randomisierten Koeffizienten, bis es keine Kollisionen gibt. Die Anzahl der Versuche, die benötigt werden, bis dies erreicht ist, wird erwartet 2 und die Wahrscheinlichkeit, dass mehr Versuche benötigt werden, nimmt exponentiell ab.

Answer 2

Es ist einfach. Erstellen Sie ein Wörterbuch und weisen Sie 1 dem ersten Wort, 2 dem zweiten, ... zu. Es ist nicht nötig, die Dinge kompliziert zu machen, nummerieren Sie einfach Ihre Wörter.

Verwenden Sie trie oder die binäre Suche oder ein anderes Tool, das Ihre Sprache bereitstellt, um die Suche effektiv zu gestalten.