Vor nicht allzu langer Zeit musste ich eine Funktionalität implementieren, die bereits von anderen Leuten und mehrmals implementiert wurde, aber für einige Eigenschaften nicht geeignet war. In diesem Fall war eine Art Datenstruktur mit der Möglichkeit erforderlich, nach einem Zeichenfolgenschlüssel oder mehreren Anfangszeichen des Schlüssels zu suchen. Der Schlüssel ist in jedem Fall eine Folge lateinischer Buchstaben, Leerzeichen und Zahlen.
Andere Implementierungen passten zuallererst nicht zum verbrauchten Speicher. In jedem Fall wird eine weitere Implementierung des Präfixbaums nicht überflüssig sein.
Die Idee wurde wahrscheinlich von
diesem Artikel inspiriert, da entschieden wurde, den Bitmap-Index zum Indizieren von Links zu nachfolgenden Knoten im Knoten zu verwenden.
Offensichtlich darf die Anzahl der Verknüpfungen in einem Knoten nicht mehr als 63 betragen (10 Ziffern, 26 Buchstaben in jedem Register plus ein Leerzeichen). Daher wird für einen Bitmap-Index an jedem Knoten eine 64-Bit-Nummer verwendet. Das gesetzte Bit an einer beliebigen Position bedeutet das Vorhandensein des entsprechenden Symbols und Knotens (Teilbaum).
Die Verteilung im Bitmap-Index ist wie folgt: Zahlen von 0 bis 9 belegen 0 bis 9 Bit, Buchstaben az von 10 bis 35 Bit, Buchstaben AZ von 36 bis 62 Bit und ein Leerzeichen belegen 63 Bit. Um die Bitnummer zu erhalten, wird einfach der ASCII-Zeichencode verwendet, der um eine bestimmte Zahl verringert wird. Für jeden Zeichenbereich ist die Zahl unterschiedlich: für die Zahlen 48 (der Ziffernbereich in ASCII-Codes beginnt mit 48), für die Buchstaben az 87 (der Buchstabenbereich az beginnt mit minus 10 Bits, die bereits mit 10 Ziffern belegt sind) und so weiter.
Die entsprechende Tabelle ist unten dargestellt.
Der Knoten wird durch den folgenden Code dargestellt:
type Trie struct { rw sync.RWMutex characters uint64 subTries []*Trie data interface{} }
Somit speichert jeder Knoten den Bitmap-Index der folgenden Zeichen, ein Slice mit Links zu Teilbäumen und den Daten selbst. Ich werde kurz auf die Such-, Einfüge- und Löschmechanismen eingehen.
Bei der Eingabe der Eingabe durchläuft der Schlüssel symbolisch den Baum, beginnend mit dem Stammknoten. Für jedes Zeichen aus seinem ASCII-Code wird die Bitnummer berechnet, und auf deren Grundlage wird der Index in der Schicht von Verknüpfungen (SubTries) zu Unterbäumen berechnet. Der Indexwert ist die Anzahl der Bits vor dem gewünschten Bit. Zum Beispiel haben wir einen solchen Index: 00 ... 101. Dies bedeutet, dass es im Bitmap-Index die Nummern 0 und 2 gibt. Dann ist der Index für die Nummer 0 Null, und für die Nummer 2 ist es 1, dh SubTries speichert 2 Links zu Unterbäumen: SubTries [0] und SubTries [1]. .
Der Code zum Abrufen der Bitnummer für das Zeichen:
func calcBitNum(char rune) (uint64, bool) {
Der Code zum Abrufen des Knotenindex für das Zeichen:
func (trie *Trie) getSubTreeIndex(bitNum uint64) int { shifted := trie.characters << (64 - bitNum) return bits.OnesCount64(shifted) }
Der Code zum Abrufen des Knotens für das angegebene Zeichen:
func (trie *Trie) getSubTrie(char rune) (uint64, int, *Trie) { bitNum, _ := calcBitNum(char) subTrieId := trie.getSubTreeIndex(bitNum)
Einfügen
Ein Baum wird durchlaufen, um ein Element einzufügen. Fehlt ein Zeichen (und damit alle nachfolgenden), wird es in den Bitmap-Index eingefügt. Es wird ein Teilbaum erstellt, dessen Verknüpfung an der richtigen Stelle der Slice-SubTries eingefügt wird (die richtige Stelle wird durch die Anzahl der Bits bis zur gewünschten bestimmt). Wenn sie das letzte Zeichen des Schlüssels erreicht haben, werden Daten in den letzten Teilbaum eingefügt.
Suche
Zum Suchen "rennt" der Schlüssel symbolisch durch den Baum. Sobald es vorbei ist, wird das Ergebnis zurückgegeben. Wenn für den Schlüssel keine Daten vorhanden sind, aber weitere Teilbäume vorhanden sind, werden die Ergebnisse aus allen nachfolgenden Teilbäumen mit Daten ausgewählt. Das Limit für die Anzahl der zurückgegebenen Daten kann festgelegt werden. Somit ist es möglich, einen Knoten durch das Zusammentreffen des gesamten Schlüssels oder eine Menge von Knoten durch das Zusammentreffen mehrerer Anfangszeichen zu suchen.
Löschen
Der Entfernungsvorgang war (wie erwartet) komplizierter als der Rest. Um einen Schlüssel zu löschen, wird ein Baum durchlaufen, während dessen Knoten ohne Daten in einem separaten Slice aufgezeichnet werden. Wenn ein Knoten mit Daten gefunden wird, wird die Schicht auf Null zurückgesetzt und der Durchgang durch den Baum wird weiter fortgesetzt. Das heißt, das Segment der zu löschenden Knoten sollte eine Folge von Knoten enthalten, die keine Daten enthalten. Wenn das Slice am Ende nicht leer ist, wird die Reihenfolge umgekehrt, und die entsprechenden Bits werden aus dem Bitmap-Index entfernt und die Knoten werden gelöscht.
Zusammenfassung
Das Ergebnis ist ein Präfixbaum, der hinsichtlich Geschwindigkeit und Speicherverbrauch anderen Analoga überlegen ist (durchschnittlich 30% weniger Speicher und ebenso viel schneller). Außerdem war ich nicht zu faul, Multithreading-Vorgänge mit einem Baum zu ermöglichen, was die Produktivität insbesondere bei Suchvorgängen erheblich steigert. Natürlich ist die Lösung ziemlich spezialisiert (Beschränkung in Form von lateinischen Zeichen, Zahlen und einem Leerzeichen als Schlüsselkomponenten).
Basierend auf dem Zweck des Präfixbaums kann mit dieser Lösung ein Wörterbuch und ein Suchindex erstellt werden.
Ich habe die Einfüge-, Such- und Löschcodes nicht zitiert, um den Artikel nicht zu
überfrachten . Außerdem ist der Quellcode
auf dem Github verfügbar.