trie Download – trie Quellcode herunterladen

trie

Anderer Quellcode

v0.0.1

Herunterladen

versuchen

Eine Implementierung der Trie-Datenstruktur in Go. Es bietet mehr Funktionen als die übliche Trie-Präfixsuche und ist für die automatische Vervollständigung gedacht.

Demo

Eine WebAssembly-Demo kann unter shivamMg.github.io/trie ausprobiert werden.

Merkmale

Schlüssel sind []string statt string , wodurch mehr Anwendungsfälle unterstützt werden – z. B. kann []string{the quick brown fox} ein Schlüssel sein, bei dem jedes Wort ein Knoten im Trie ist
Unterstützung für Put-Taste und Löschtaste
Unterstützung für die Präfixsuche – z. B. kann die Suche nach „Nation“ zu „Nation “, „National “, „Nationalismus “, „Nationalist “ usw. führen.
Unterstützung für die Suche nach Distanzen bearbeiten (auch bekannt als Levenshtein-Distanz) – z. B. kann die Suche nach Weizen ähnlich aussehende Wörter wie Weizen , Cheat , Hitze , Was usw. zurückgeben.
Die Reihenfolge der Suchergebnisse ist deterministisch. Es folgt die Einfügereihenfolge.

Beispiele

 tri := trie.New()// Setze Schlüssel ([]string) und Werte (any)tri.Put([]string{"the"}, 1)tri.Put([]string{"the", " quick", "brown", "fox"}, 2)tri.Put([]string{"the", "quick", "sports", "car"}, 3)tri.Put([]string{" der“, „grün“, „Baum“}, 4)tri.Put([]string{"an", "apple", "tree"}, 5)tri.Put([]string{"an", "umbrella"}, 6)tri.Root(). Print()// Ausgabe (vollständiger Versuch mit Terminals, die mit ($) enden):// ^// ├─ das ($)// │ ├─ schnell// │ │ ├─ braun// │ │ │ └─ Fuchs ($)// │ │ └─ Sport// │ │ └─ Auto ($)// │ └─ grün// │ └─ Baum ($)// └─ ein/ / ├─ Apfel// │ └─ Baum ($)// └─ Regenschirm ($)results := tri.Search([]string{"the", "quick"})for _, res := range results.Results { fmt.Println( res.Key, res.Value)
}// Ausgabe (präfixbasierte Suche):// [der schnelle braune Fuchs] 2// [der schnelle Sportwagen] 3key := []string{"the", "tree"}results = tri.Search(key , trie.WithMaxEditDistance(2), // Eine Bearbeitung kann eingefügt, gelöscht oder ersetzt werdentrie.WithEditOps())for _, res := range results.Results { fmt.Println(res.Key, res.EditDistance) // EditDistance ist die Anzahl der Bearbeitungen, die zum Konvertieren in [den Baum] erforderlich sind}// Ausgabe (Ergebnisse nicht mehr als 2 Bearbeitungen von [dem Baum] entfernt):// [der] 1// [der grüne Baum ] 1// [ein Apfelbaum] 2// [ein Regenschirm] 2result := results.Results[2]fmt.Printf("So konvertieren Sie %v in %v:n", result.Key, key)printEditOps(result.EditOps)// Ausgabe (Bearbeitungsvorgänge, die erforderlich sind, um ein Ergebnis in [den Baum] umzuwandeln):// So konvertieren Sie [einen Apfelbaum] in [den Baum]:// – löschen Sie „an“// - „apple“ durch „the“ ersetzen// – „tree“ nicht bearbeitenresults = tri.Search(key, trie.WithMaxEditDistance(2), trie.WithTopKLeastEdited(), trie.WithMaxResults(2))for _, res := range results.Results { fmt.Println(res.Key, res.Value, res.EditDistance)
}// Ausgabe (die beiden am wenigsten bearbeiteten Ergebnisse):// [der] 1 1// [der grüne Baum] 4 1