18

これがアルゴリズムについて質問する場所かどうかはわかりません。しかし、答えが得られるかどうか見てみましょう... :)

ご不明な点がございましたら、喜んでご説明させていただきます。

PythonでTrieを実装しました。ただし、（シンプルさを愛する人として）必要以上に複雑なように思えました。おそらく誰かが同様の問題を抱えていましたか？

私の目的は、サブトライの最大共通プレフィックスをルートに格納することで、ノードの数を最小限に抑えることでした。たとえば、stackoverflow、stackbase、stackbasedという単語がある場合、ツリーは次のようになります。

              [s]tack
[o]verflow ______/ \_______ [b]ase
                                  \___ [d]

1 つの文字 (子ノードの最初の文字) を持つエッジを考えることができることに注意してください。

Find -query は簡単に実装できます。 挿入は難しくありませんが、私が望むよりもやや複雑です.. :(

私のアイデアは、最初に挿入するキー k ( Find (k)) を検索し、次にノードをローカルで再配置/分割することにより、(空のトライから開始して) キーを次々に挿入することでした。検索手順が停止します。4 つのケースがあることが判明しました: (挿入するキーを k とし、検索が終了したノードのキーを k' とします)

  1. k は k' と同じです
  2. k は k' の「適切な」接頭辞です
  3. k' は k の「適切な」接頭辞です
  4. k と k' は共通の接頭辞を共有していますが、(1)、(2)、(3) のいずれも発生しません。

それぞれのケースは独特であり、したがってトライの異なる修正を暗示しているようです。しかし、それは本当に複雑ですか？何か不足していますか？より良いアプローチはありますか？

ありがとう ：）

4

5 に答える 5

19

一見、Patricia Trieを実装したように見えます。このアプローチは、一部の文献ではパス圧縮とも呼ばれています。挿入アルゴリズムを含む ACM ペイウォールの背後にないその論文のコピーがあるはずです。

検討したい別の圧縮方法もあります: レベル圧縮です。パス圧縮の背後にある考え方は、単一の子ノードの文字列を「スキップ」カウントを持つ単一のスーパー ノードに置き換えることです。レベル圧縮の背後にある考え方は、完全またはほぼ完全なサブツリーを、ノードがデコードするキーの桁数を示す「次数」カウントを持つスーパー ノードに置き換えることです。幅の圧縮と呼ばれる 3 番目のアプローチもありますが、メモリが不足していて、グーグルで簡単に説明を見つけることができなかったのではないかと心配しています。

レベル圧縮は平均パスを大幅に短縮できますが、動的配列と同様にトライ ノードを管理する必要があるため、挿入および削除アルゴリズムは非常に複雑になります。適切なデータ セットの場合、レベル圧縮されたツリーは高速になります。私の記憶では、これらは IP ルーティング テーブルを格納するための 2 番目に速い方法であり、最も速い方法はある種のハッシュ トライです。

于 2009-06-07T02:09:25.913 に答える
2

多少の関係はありますが、Trie 内のノードの数が非常に心配な場合は、単語の接尾辞を結合することも検討してください。DAWG (Directed Acyclic Word Graph) のアイデアを見てみましょう: http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

これらの欠点は、あまり動的ではなく、作成が難しいことです。ただし、辞書が静的な場合は、非常にコンパクトになる可能性があります。

于 2009-06-07T05:33:28.310 に答える
2

実装に関して質問があります。プレフィックス ツリーを作成するために文字列を分割する際の粒度のレベルはどれくらいですか。スタックを s、t、a、c、k または st、ta、ac、ck およびその他の多くの ngram として分割できます。ほとんどのプレフィックス ツリーの実装では、言語のアルファベットが考慮されます。このアルファベットに基づいて、分割を行います。

Python のプレフィックス ツリーの実装を構築している場合、アルファベットは def、:、if、else... などになります。

適切なアルファベットを選択すると、効率的なプレフィックス ツリーの構築に大きな違いが生じます。あなたの答えについては、トライを使用して最長共通部分文字列計算を行う CPAN の PERL パッケージを探すことができます。それらの実装のほとんどはかなり堅牢であるため、運が良いかもしれません。

于 2009-06-07T05:46:21.657 に答える
2

あなたのアプローチに何の問題もありません。スパイク ソリューションを探している場合、おそらくケース 4 で実行されるアクションは、最初の 3 つのケースで実際に実行可能です。IE は共通のプレフィックスを見つけて、kそれk'を念頭に置いてノードを再構築します。キーが互いの接頭辞だった場合でも、結果として得られるトライは正しいものになりますが、実装が実際に必要以上に多くの作業を行っただけです。しかし、繰り返しますが、コードを見る必要がなく、これがあなたのケースで機能するかどうかを言うのは難しいです.

于 2009-06-07T01:21:00.317 に答える
1

見てください： http ://www.dalkescientific.com/Python/PyJudy.htmlのJudy-arraysとpythonインターフェース

于 2009-06-13T08:05:25.410 に答える