Präfix Suche gegen eine halbe Milliarde Strings

Wenn Sie den Benutzer zum Beispiel zwingen möchten, mindestens 4 Buchstaben zu setzen, können Sie eine Schlüssel-Wert-Karte, einen Speicher oder eine Festplatte speichern, wobei die Schlüssel alle Kombinationen aus 4 Buchstaben sind (wenn sie nicht zu groß sind) Groß- / Kleinschreibung ist nicht zu beachten, sonst können Sie auf drei beschränken), und die Werte sind eine Liste der Positionen aller Strings, die mit der Kombination beginnen.

Nachdem der Benutzer die drei (oder vier) Buchstaben eingegeben hat, haben Sie alle möglichen Zeichenfolgen gleichzeitig. Von diesem Punkt an schlingen Sie nur diese Teilmenge.

Im Durchschnitt ist diese Teilmenge klein genug, d. h. 500M geteilt durch 26 ^ 4 ... nur als Beispiel. Eigentlich größer, weil wahrscheinlich nicht alle Sätze von 4 Buchstaben als Präfix für Ihre Strings verwendet werden können.

Vergessen Sie zu sagen: Wenn Sie der großen Liste einen neuen String hinzufügen, aktualisieren Sie auch die Liste der Indizes, die dem Schlüssel in der Map entsprechen.

In diesem hypothetischen Fall, in dem die indizierten Strings nicht mit anderen Informationen verknüpft sind (z. B. andere Spalten in derselben Zeile), gibt es relativ wenig Unterschied zwischen einem vollständigen Index und der Sortierung der Strings (wie in ein kleiner Unterschied, aber nicht so viel, wie du dir erhoffst. Angesichts des wachsenden Charakters der Liste und der Kosten für deren Aktualisierung könnte der gegenteilige Ansatz die von Ihnen gewünschten Performance-Kompromisse besser erfüllen.

Für ein beliebiges Zeichen an einer beliebigen Stelle in der Zeichenfolge ist Ihr Basisfall, dass keine Zeichenfolge existiert, die diesen Buchstaben enthält. Zum Beispiel, sobald 'Hallo' eingegeben wurde, wenn der nächste Buchstabe 't' ist, dann ist Ihr Grundfall, dass es keinen String gibt, der 'hellot' beginnt. Es gibt eine endliche Anzahl von Zeichen, die "Hallo" an Position 5 (sagen wir 26) folgen könnten. Sie benötigen 26 Leerzeichen mit fester Länge, in denen Informationen über Zeichen gespeichert werden, die an Position 5 "Hallo" folgen. Jedes Leerzeichen sagt Null, wenn keine Zeichenfolge vorhanden ist, z. B. "t" folgt "Hallo" oder enthält eine Zahl von Datenspeicheradressen, durch die zu suchen ist, um die Liste von Zeichen zu finden, für die eine oder mehrere Zeichenfolgen das Zeichen nach "hellot" an Stelle 6 verwenden (oder absolute Datenspeicheradressen verwenden, obwohl nur relative Adressen den vorgeschlagenen Algorithmus erlauben) unterstützt eine unendliche Anzahl von Strings unendlicher Länge ohne irgendeine Modifikation, um größere Zeiger zu ermöglichen, wenn die Liste wächst.)

Der Algorithmus kann sich dann durch diese auf der Festplatte gespeicherten Daten vorwärts bewegen, indem er einen Baum von Stringanfängen im Speicher erstellt und Verzögerungen vermeidet, die durch Lesezugriffe mit wahlfreiem Zugriff verursacht werden. Für einen speicherinternen Index speichern Sie einfach den Teil des Baums, der dem Stamm am nächsten ist, im Speicher. Nachdem der Benutzer "Hallo" getippt hat und der Algorithmus die Informationen über eine oder mehrere Zeichenfolgen verfolgt hat, die an der Datenspeicheradresse X beginnen, findet der Algorithmus eine von zwei Arten von Listen an einer Position. Entweder ist es eine andere Sequenz B. 26 Räume mit fester Länge mit Informationen über Charaktere, die nach "Hellot" an Position 6 folgen, oder es ist ein vorab zugeteilter Raumblock, der alle Post-Fixes auflistet, die "hellot" folgen, abhängig davon, wie viele solcher Post-Fixes existieren. Sobald es genügend Post-Fixes gibt, dass die Verwendung eines herkömmlichen Such- und / oder Sortieralgorithmus zum Aktualisieren und Durchsuchen der Post-Fix-Liste nicht die gewünschten Leistungsvorteile bietet, wird es aufgeteilt und durch eine Sequenz ersetzt, z. 26 Räume fester Länge.

Dies beinhaltet die Vorabzuweisung einer relativ großen Menge an Festplattenspeicher im Voraus, mit der Abwägung, dass Ihr Baum in sortierter Form verwaltet werden kann, ohne dass für die meisten Updates etwas herumgereicht werden muss, und Ihre Suchen können durchgeführt werden Voll in einem single sequential read . Es bietet außerdem mehr Flexibilität und benötigt wahrscheinlich weniger Speicherplatz als eine Lösung, die darauf basiert, die Zeichenfolgen selbst als Zeichenfolgen fester Länge zu speichern.