[解決済み] Pythonでトライを作成する方法

質問

トライやDAWG（direct acyclic word graph）に興味があり、いろいろ読んでいるのですが、トライやDAWGの出力ファイルがどのようなものであるべきかがよくわかりません。

• トライはネストされた辞書のオブジェクトであるべきですか？各文字が文字に分割されているようなものですか？
• このような辞書で検索を行った場合、100kや500kの項目があったとしても高速に検索できるでしょうか？
• で区切られた複数の単語からなるワードブロックをどのように実装するか？ - またはスペースが必要ですか？
• 単語の接頭辞や接尾辞を構造上の別の部分につなげるにはどうしたらよいか？(DAWGの場合)

を理解したい。 出力構造 を作成し、使用する方法を考えるためです。

をどうすればいいのかも教えてほしいです。 DAWGの出力 とともに トライ .

私は、泡が互いにリンクしているグラフィカルな表現を見たいのではなく、一連の単語がトライまたはDAWGになった後の出力オブジェクトが知りたいのです。

どのように解決するのですか？

アンワインド 大規模でスケーラブルなトライでは、ネストされた辞書は面倒になり、少なくともスペース的には非効率になるかもしれません。しかし、あなたはまだ始めたばかりなので、これが最も簡単な方法だと思います。 trie を数行で済ませることができます。まず、トライを構築するための関数です。

>>> _end = '_end_'
>>> 
>>> def make_trie(*words):
...     root = dict()
...     for word in words:
...         current_dict = root
...         for letter in word:
...             current_dict = current_dict.setdefault(letter, {})
...         current_dict[_end] = _end
...     return root
... 
>>> make_trie('foo', 'bar', 'baz', 'barz')
{'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 
             'z': {'_end_': '_end_'}}}, 
 'f': {'o': {'o': {'_end_': '_end_'}}}}

をよく知らない人は setdefault の場合、単に辞書のキーを調べるだけです（ここでは。 letter または _end ). キーが存在する場合は関連する値を返し、存在しない場合はそのキーにデフォルト値を割り当ててその値を返します ( {} または _end ). (これは get も辞書を更新します)。

次に、その単語がトライに含まれるかどうかをテストする関数。

>>> def in_trie(trie, word):
...     current_dict = trie
...     for letter in word:
...         if letter not in current_dict:
...             return False
...         current_dict = current_dict[letter]
...     return _end in current_dict
... 
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'baz')
True
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barz')
True
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barzz')
False
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'bart')
False
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'ba')
False

挿入と削除は練習としてお任せします。

もちろん、Unwindの提案もそれほど難しくはないでしょう。正しいサブノードを見つけるために線形探索が必要になるという点で、若干の速度的な不利はあるかもしれません。しかし、この検索は可能な文字数に制限されます。 _end . また、彼の言うように大量のノードリストを作成してインデックスでアクセスしても何の得もありません。リストをネストするだけでもいいかもしれません。

最後に、有向無サイクル単語グラフ（DAWG）の作成は、現在の単語が構造内の他の単語と接尾辞を共有している状況を検出する必要があるため、もう少し複雑になることを付け加えておきます。実際、DAWGをどのように構成するかによって、これはかなり複雑になります。について、いくつか学ぶ必要があるかもしれません。 レーベンシュタイン 距離 をクリックすると、正しく表示されます。