trie - 欠落文字検索アルゴリズム

Question

そのため、文字が欠落している単語 (クロスワードで使用) を検索する必要があり、残りのスペースの可能な単語のリストを維持する必要もあります。

今私の質問は、検索のための最速のアルゴリズムである場合、そのバーストトライをグーグルで検索したことです。しかし、これをトライでコーディングすると、バーストトライに移行するのはどれほど難しいでしょうか??

あなたが得られなかった何かが何かを明確にするためにコメントすることができる場合は、私に我慢してください.

Answer 1

最初の免責事項ですが、私はバーストトライを書いていません。しかし、あなたの質問を読んで、バーストトライを提案した最初の論文Burst Tries: A Fast, Ecient Data Structure for String Keysを見つけました。私はいくつかのトライ データベースと多数の付属関数を作成しました。

私が読んだところによると、標準的なアプローチに従ってトライを記述し、構造体に bst オプションを追加して、それを char の最後のシーケンスに使用するだけのように聞こえます。次に、「バースト」関数を trie クラスに追加し、設定で、bst を新しいレベルの trie 構造体に「バースト」し、bst サフィックス ツリーを続行します。

したがって、あなたの質問に対する答えは「はい、トライをバースト トライに変換するのは簡単です」だと思います。