問題タブ [ternary-search-tree]

こんにちはスタックオーバーフラワー！

200.000 文字列エントリの単語リストがあり、平均文字列長は約 30 文字です。この単語のリストがキーであり、各キーにはドメイン オブジェクトがあります。キーの一部を知っているだけで、このコレクション内のドメイン オブジェクトを見つけたいと考えています。たとえば、検索文字列「kov」は、キー「stackoverflow」と一致します。

現在、私は通常 100 ミリ秒以内にアイテムを見つける三分探索木 (TST) を使用しています。ただし、これは私の要件には遅すぎます。TST の実装は、いくつかの小さな最適化によって改善される可能性があり、ツリーのバランスを取ることができました。しかし、これらのことは、私が目指している 5 倍から 10 倍の速度向上にはつながらないと考えました。非常に遅い理由は、基本的にツリー内のほとんどのノードにアクセスする必要があるためだと思います。

アルゴリズムの速度を改善する方法についてのアイデアはありますか? 私が見なければならない他のアルゴリズムはありますか？

前もってありがとう、オスカー

三分木がハッシュテーブルよりも優れているかどうかを知る必要があります。

この質問に出くわしたのは、別の質問への回答で、三分木はハッシュ テーブルよりも高速であることが多いと誰かが言ったときでした。信じがたいことだったので、少し調べてみることにしました。

プリンストンからのこの 1 つの Web サイトは、信念の源のようです。O(log n + k) と記述されているアルゴリズムを調べました。ここで、n は格納されている単語の数、k はキーの長さです。

これを高速化する唯一の方法は、まだ保存されていない要素を頻繁に検索する場合です。私を悩ませているもう 1 つのことは、トライの非連続的なクロールにより、スワップ アウトされたページにヒットする傾向があることですが、これが大きな影響であるかどうかは、ベンチマークによってのみ確認できます。

どちらにもおそらく長所と短所があることがわかったので、もしそうなら、それらが何であるかを知りたい. ベンチマークも役立ちます。

三分探索木の「バランスをとる」にはどうすればよいでしょうか。ほとんどのtst実装はバランシングに対応していませんが、最適な順序で挿入することをお勧めします（これは制御できません）。

学校のプロジェクト用に三分探索木を構築しようとしています。私の知る限り、私のコードは問題ないようです。
しかし、malloc を使用すると、元のルート関数のリーフ ノードが初期化されません。したがって、最初の文字列を超えるすべての文字列比較 (ルートの文字列が何であれ) は空になります (null ではなく "")。関数の引数としてポインターを渡していないので、何が問題なのかわかりません。助けてください！
問題はコードのこの部分のどこかにあると思われます。私は本当に頭を悩ませて検索しましたが、自分の問題が何であるかを理解できません。
必要に応じて、より多くのコードを利用できます。

私が確認したところ、最初のパスで root->right が current->right とはまったく異なる場所を指しています。それが私の本当の問題です。宣言の誤りか何かに違いないと思いますが、わかりません。

文字列を使用して単語のシーケンスを追加すると、セグメントadd()内に印刷され if(t==NULL)ますが、ツリーが形成されません。つまり、ノードがリンクされません。

三分探索木について私が理解していることから、それらは探して見つけることができるアイテムで逆決定論的です（正しい用語についてはわかりません）。つまり、 cat、bicycle、axisの三分木を作成し、その三分木を誰かに渡せば、その人はそこからこれらの 3 つの単語を差し引くことができるはずです。

これは正しいです？

ISMAP、SELECTED、COMPACT (実際、HTML 4 の属性) などの単語を含む 3 項ツリー構造があり、そのツリーに格納されている項目の完全なリストを取得できるかどうか疑問に思っているためです (元のドキュメントなくなっている）。構造は次のようになります。

三分探索木を変更して単語が存在することを確認し、その単語で始まる (またはその単語で終わる) すべての単語を検索することは可能でしょうか? たとえばdo=>dog dogsなど。

サンプルコードはこちらのサイトから。最初にすべての単語を三分木にロードしてから、メソッドを使用して単語が存在するかどうかを確認できます。

これにより、私は頭の中で大きくなります:(
その単語を取得する方法は何でもかまいません。しかし、私はそのレベルのアルゴリズムに弱いです..
これに関する質問を重複させないことを願っています. .

私は現在、予測テキスト SMS システムに取り組んでいます。TST データ構造とバイグラム (現在のキー シーケンス 12 キーパッドに基づいて次の可能性のある単語を予測する) を使用して実装したいと考えています。
現在、私はコーパスを持っており、利用可能なアプリケーションを使用して、辞書、バイグラム、および頻度を考え出しました。現在、次の質問を念頭に置いています。

1. この場合、J2ME TST 実装または適切な Trie を見つけることができますか? (利用可能な TST トライに関するより詳細な説明は素晴らしいものになる可能性があります)
2. このプロジェクト アプローチに関する一般的なガイダンス

NB:私は似たような Trie の実装を見てきましたが、まだ進むべき道を見つけることができません。

「三分探索木」ライブラリ ( sourceforge & http://code.google.com/p/ternary-search-tree/ )から再帰関数を変更したい。デフォルトの動作では、指定されたワイルドカード文字列に一致するすべての文字列を三分検索ツリーで検索します。つまり、ツリーに 'KEY'、'KE1'、'KE2' があると、'KE*' を検索するとすべてのエントリが見つかります。しかし、逆の動作が必要です。指定された文字列に一致するすべてのエントリを (ワイルドカードを含む) 三分探索ツリーで検索します。つまり、ツリーに 'KE*'、'KEY'、'K*' があると、'KEY' を検索するとすべてのエントリが見つかるはずです。

ツリー/ノードは次のように定義されます。

そして、デフォルトの動作を持つ関数:

pmVectorPtr は int の Vector への Pointer であり、関数 get は root-element と searchkey を引数として呼び出されます。私はすでにそれを適応させようとしましたが、まだ理解できていません。私自身のコード:

私はこれをデバッガを広範囲に使用してコーディングしましたが、私が知る限り、動作するように見えます (ワイルドカードが文字列の先頭または途中にある場合でも)。しかし、例に「K*」と「Ke*」を追加すると、「Key」のソリューション (この場合は Ke*) が 1 つしか見つかりません。ツリーから 'Ke*' を削除すると、'Key' の検索クエリに対して 'K*' が見つかります。理由はまだわかりません。

それについてのアイデアはありますか？

付録（私のテストケース）：