trieダウンロード - trieソースコードのダウンロード

trie

その他のソースコード

v0.0.1

ダウンロード

試してみる

Go での Trie データ構造の実装。これは、通常の Trie 接頭辞検索よりも多くの機能を提供し、自動補完に使用することを目的としています。

デモ

WebAssembly のデモは shivamMg.github.io/trie で試すことができます。

特徴

キーはstringではなく[]stringあるため、より多くのユースケースがサポートされます。たとえば、 []string{素早い茶色のキツネ} は、各単語がトライのノードとなるキーにすることができます。
Put キーと Delete キーのサポート
前置検索のサポート - たとえば、 nationを検索すると、 nation 、 national 、 nationalism 、 nationalistなどが返される場合があります。
編集距離検索 (別名レーベンシュタイン距離) のサポート - たとえば、小麦を検索すると、小麦、チート、熱、ワットなどの似たような単語が返される可能性があります。
検索結果の順序は決定的です。挿入順に従います。

例

tri := trie.New()// キー ([]string) と値 (任意)tri.Put([]string{"the"}, 1)tri.Put([]string{"the", "クイック", "ブラウン", "キツネ"}, 2)tri.Put([]string{"ザ", "クイック", "スポーツ", "車"}, 3)tri.Put([]string{" 」、 "緑", "木"}, 4)tri.Put([]string{"an", "リンゴ", "木"}, 5)tri.Put([]string{"an", "傘"} , 6)tri.Root().Print()// 出力 (($) で終わる端子を含む完全なトライ):// ^// §─ the ($)// │ ├─ クイック// │ │ ├─茶色// │ │ │ lux─ キツネ ($)// │ │ └─ スポーツ // │ │ └─ 車 ($)// │ └─ 緑 // │ └─ 木 ($)// lux─ と // ├─ リンゴ// │ └─ 木 ($)// └─ 傘 ($)results := tri.Search([]string{"the", "quick"})for _, res := range results.Results { fmt.Println(res.Key, res.Value)
}// 出力 (プレフィックスベースの検索):// [クイック ブラウン キツネ] 2// [クイック スポーツ カー] 3key := []string{"the", "tree"}results = tri.Search(key , trie.WithMaxEditDistance(2), // 編集は挿入、削除、置換可能trie.WithEditOps())for _, res := range results.Results { fmt.Println(res.Key, res.EditDistance) // EditDistance は [ツリー] に変換するのに必要な編集の数です}// 出力 ([ツリー] から 2 編集以内の結果が得られます):// [the ] 1// [緑の木] 1// [リンゴの木] 2// [傘] 2result := results.Results[2]fmt.Printf("変換するには %v to %v:n", result.Key, key)printEditOps(result.EditOps)// 出力 (結果を [ツリー] に変換するために必要な編集操作):// [リンゴの木] を [ツリー] に変換するには]:// - 「an」を削除します// - 「apple」を「the」に置き換えます// - 「tree」を編集しないでくださいresults = tri.Search(key, trie.WithMaxEditDistance(2), trie.WithTopKLeastEdited(), trie.WithMaxResults(2))for _, res := range results.Results { fmt.Println(res.Key, res.Value, res.EditDistance)
}// 出力 (最も編集されていない上位 2 つの結果):// [the] 1 1// [the green Tree] 4 1