問題タブ [trie]

したがって、ハッシュテーブルまたはプレフィックスツリーのどちらかを選択する必要がある場合、どちらかを選択するように導く識別要因は何ですか. 私自身の素朴な観点からは、トライを使用すると、配列として保存されないため、余分なオーバーヘッドがあるように見えますが、実行時間の観点からは（最長のキーが最長の英単語であると仮定して）、本質的に O になる可能性があります(1) (上限に関して)。たぶん、最も長い英単語は50文字ですか？

ハッシュ テーブルは、インデックスを取得するとすぐに検索されます。ただし、インデックスを取得するためにキーをハッシュすると、50 近くの手順を簡単に実行できるように思えます。

誰かがこれについてより経験豊富な視点を提供できますか? ありがとう！

自家製の Trie を実装する必要があり、Iterator の部分で行き詰まっています。トライのインクリメント方法がわかりません。

誰かが私が物事を片付けるのを手伝ってくれることを願っています.

イテレータのコードは次のとおりです。

そして、ここに私のトライがあります：

プレフィックストライがあります。リレーショナル データベースでこの構造を表すために推奨されるスキーマは何ですか? 効率を維持するには、部分文字列の一致が必要です。

文字列からさまざまなオブジェクトへの多くのマッピングを格納する Java プログラムがあります。

現在、私のオプションは、ハッシュ (HashMap 経由) またはバイナリ検索 (TreeMap 経由) に依存することです。人気のある高品質のコレクション ライブラリに、効率的で標準的なトライベースのマップ実装があるかどうか疑問に思っています。

私は過去に自分で書いたことがありますが、可能であれば標準的なものを使いたいと思います。

簡単な説明: 私の質問は一般的なものですが、現在のプロジェクトでは、完全修飾クラス名またはメソッド シグネチャによってインデックス付けされた多くのデータを扱っています。したがって、多くの共有プレフィックスがあります。

大学時代のお気に入りのデータ構造の 1 つはTrieでした。プレフィックスが共有されている場合、大量の文字列セットを保持するための優れたデータ構造です。セット内の文字列の数に関係なく、文字列の O(|length|) で検索が行われるため、ルックアップも優れています。

比較すると、バランスの取れたツリーは、セット項目の数に O(log N) と、比較のために支払う金額を加えたものになります。ハッシュテーブルには、ハッシュ計算、比較などが含まれます。

したがって、ほとんどの言語の標準ライブラリに Trie の実装がないことは、私にとって驚くべきことです。

私が思いついた唯一の理由は、メモリアクセスコストが高すぎる可能性があるということでした. ツリー ルックアップを実行する場合に O(log N) の場所を調査するのではなく、O(|length|) の異なる場所を実行していないため、すべての結果が得られます。文字列が長い場合、これはやりすぎになる可能性があります。

だから私は疑問に思っています：私が今説明した懸念はいくらですか？文字列の大規模なセットまたはマップを格納する必要がある場合はどうしますか?

私はVB.NETで予測テキスト入力用のトライを実装しています-トライの使用に関する限り、基本的にオートコンプリートです。汎用辞書クラスに基づいて、トライを再帰的なデータ構造にしました。

それは基本的に：

単語内の各文字（すべて大文字）は、新しいWordTrieのキーとして使用されます。リーフのヌル文字は、単語の終了を示します。接頭辞で始まる単語を見つけるために、接頭辞が尽きるまでトライを歩き、すべての子の単語を収集します。

私の質問は基本的にトライ自体の実装についてです。辞書ハッシュ関数を使用してツリーを分岐しています。リストを使用してリストを線形検索するか、他のことを行うことができます。ここでのスムーズな動きは何ですか？これは私の分岐を行うための合理的な方法ですか？

ありがとう。

アップデート：

明確にするために、私は基本的に、辞書の分岐アプローチが他の方法よりも明らかに劣っているかどうかを尋ねています。このデータ構造を使用しているアプリケーションでは大文字のみを使用しているため、配列アプローチが最適な場合があります。将来、より複雑な先行入力状況（より多くの文字）に同じデータ構造を使用する可能性があります。その場合、辞書が正しいアプローチのように思えます。一般的にもっと複雑なものを使用する必要があるところまでです。

私はトライとそれを変更するいくつかの関数を持っています。

ここで、関数をデバッグおよび/またはテストするために、試行を出力する必要があります。

再帰的に試してみましたが、第 2 レベルよりも第 1 レベルを取得できません...

それを行う良い方法は何ですか？

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

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

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

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

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

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

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

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

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

ありがとう ：）

jQueryのオートコンプリートを使用してタグを検索するためのオートコンプリート機能のような「GoogleSuggest」を実装しています。

jQueryにWebサービスを提供して、ユーザーが入力した内容に基づいた提案のリストを提供する必要があります。Webサービスを実装する2つの方法があります。

1）すべてのタグをデータベースに保存し、ユーザー入力をプレフィックスとして使用してDBを検索するだけです。これは簡単ですが、レイテンシーが心配です。

2）処理中のトライを使用してすべてのタグを保存し、一致する結果を検索します。すべてが進行中であるため、レイテンシーがはるかに低くなると思います。しかし、いくつかの問題があります。-プロセスの起動時にトライを初期化するための良い方法は何ですか？おそらく、タグデータをDBに保存して取得し、プロセスを開始するときにそれらをトライに変換します。しかし、その方法はわかりません。Python/Djangoを使用しています。-ユーザーが新しいタグを作成する場合、新しいタグをトライに挿入する必要があります。しかし、5つのDjangoプロセスがあり、したがって5つの試行があるとしましょう。他の4つの試行にも、新しいタグを挿入する必要があることをどのように伝えるのでしょうか。-Djangoプロセスがスレッド化されるのでトライがスレッドセーフであることを確認する方法（私はmod_wsgiを使用しています）。または、Pythonのせいでthreadsaftyについて心配する必要はありませんか？s GIL？-タグの使用頻度をトライ内にも保存する方法はありますか？タグの文字列がいつ終了し、頻度がいつ開始するかを知るにはどうすればよいですか？apple213をトライに保存すると、頻度213の「apple」ですか、それとも頻度13の「apple2」ですか。

上記の問題に関するヘルプや、別のアプローチに関する提案をいただければ幸いです。

C/C++ での trie の速度とキャッシュ効率の高い実装はありますか? トライが何であるかは知っていますが、車輪を再発明して自分で実装したくありません。