問題タブ [trie]

一定時間またはほぼ一定時間で次の操作をサポートするメモリ内データ構造に格納する必要がある文字列キー（平均長10文字）の大規模なセット（500万から2000万）を使用しています。

Javaのハッシュマップは、スループットに関する限り満足のいくものであることが証明されていますが、多くのメモリを消費しています。私は、メモリ効率が高く、それでもまともなスループット（ハッシュと同等またはほぼ同等）をサポートするソリューションを探しています。

挿入/削除の時間は気にしません。私のアプリケーションでは、挿入のみを実行し（起動時のみ）、その後contains、アプリケーションの存続期間中、メソッドを使用してデータ構造をクエリするだけです。

HAT-Trieのデータ構造が私のニーズに最も近いことを読みました。実装されているライブラリがあるかどうか疑問に思います。

実装へのポインタを含む他の提案を歓迎します。

ありがとうございました。

3つの操作をサポートする非常に単純なTrieをJavaで実装しようとしています。insertメソッド、hasメソッド（つまり、トライ内の特定の単語）、および文字列形式でトライを返すtoStringメソッドが必要です。挿入は適切に機能していると思いますが、hasとtoStringは難しいことがわかっています。これが私がこれまでに持っているものです。

トライクラス。

そしてノードクラス

したがって、基本的に、Trieを作成する場合、TrieNodeは26の子を持つルートとして作成されます。挿入が試行されると、そのルートノードで挿入が呼び出され、正しい位置に新しいノードが再帰的に作成され、単語が完了するまで続行されます。メソッドは正しく機能していると思います。

何らかの理由で括弧の外にreturnステートメントが必要なため、私のhas関数は非常に壊れています。else句に含めることができないか、コンパイラが文句を言います。それ以外は、少し調整すればうまくいくと思いますが、一生理解できません。

toStringは私が取り組もうとした獣ですが、何も投げないので、問題が解決するまでそのままにしておきます。動作するようになれば、それをtoString関数に再フォーマットする方法を見つけることができるかもしれません。

int val = word.charAt（0）-64;の目的 入力する各文字列はすべて大文字でなければならないため（後でこれを確実にするために文字列フォーマット関数を作成します）、最初の文字のint値-64が配列内の位置になります。つまり、配列インデックス0はAであるため、A = 64、A-64 =0です。B=65、B-64=1などです。

Trie各ノードが単語を表すデータ構造を開発しています。したがって、単語st、stack、stackoverflowおよびoverflowは次のように配置されます。

My Trie はHashTable内部的に を使用しているため、すべてのノード ルックアップに一定の時間がかかります。以下は、アイテムをトライに挿入するために思いついたアルゴリズムです。

1. トライでアイテムの存在を確認します。存在する場合は戻り、存在しない場合はステップ 2 に進みます。
2. の各文字を繰り返しkey、単語の存在を確認します。新しい値を子として追加できるノードを取得するまで、これを行います。ノードが見つからない場合は、ルート ノードの下に追加されます。
3. 挿入後、新しいノードが挿入されたノードの兄弟を再配置します。これにより、すべての兄弟がウォークスルーされ、新しく挿入されたノードと比較されます。いずれかのノードが新しいノードと同じ文字で始まる場合、そこから移動され、新しいノードの子として追加されます。

これがトライを実装する正しい方法かどうかはわかりません。提案や改善は大歓迎です。

使用言語：C++

今日、会社が実施する筆記試験を受けました。全体的なテストは、データ構造に焦点を当てていました。解決したと思っていた問題が発生しました。しかし、データ構造の Big O 関数を計算するのに苦労しました。私が思いついた質問と答えを提供します。

保存する必要があるドキュメントとドキュメント内の単語を指定すると、単語が入力されたときにカウントを返すことができるはずです。が提供されchar* GetNextWord()ます。

1. どのデータ構造を選択しますか
2. アルゴリズムを与える
3. アルゴリズムの順序はどうなりますか

質問 1 では、TRIE データ構造に行きますと書きました。質問 2 では、簡単なアルゴリズムを示しました。私は次のようにTRIEデータ構造を構築すると書きました。

各単語に対してconstructTrie()実行するメソッドがあります。addToTrie()

addToTrie()の順序はO( k )と書きました。ここで、 kは長さです。の順序はconstructTrie()N * O( k ) で、Nは単語数です。

私の質問はこれです: 私が言及した注文が正しいかどうか? そうでない場合は、将来このような問題にどのように対処するか (ds が注文を見つけた場合)。O( k )を使用した後、私は本当に混乱しました。O(1)だと思い込んでしまいます。

ヒント/ヒント/アドバイスは大公開!!

編集：すべての一意の単語の単語数を保存する必要があることを明確に述べている質問を修正しました。

私は、メソッド、、を使用して、および迅速な検索（プレフィックス検索を含む）のために単語の大きな辞書を格納する手段として、addWord()PatriciaTrieを実装しようとしています。私は概念を読みましたが、それらは実装を明確にしていません。Trie、特にノードを実装する方法を（JavaまたはPythonコードで）知りたい（または再帰的に実装する必要がある）。26個の子ノードの配列をnull/Noneに設定して実装した人を見ました。より良い戦略（文字をビットとして扱うなど）はありますか？それをどのように実装しますか？isWord()isPrefix()

どの構造が最高のパフォーマンス結果を提供しますか。トライ（プレフィックスツリー）、サフィックスツリーまたはサフィックス配列？他に同様の構造はありますか？これらの構造の優れたJava実装は何ですか？

編集：この場合、テキスト上の辞書の名前を識別するために、名前の大きな辞書と自然言語のテキストの大きなセットの間で文字列照合を行いたいと思います。

辞書データベース、または英語の単語の全リストを含むテキストまたは単語ファイルが必要なTRIEデータ構造で作業することを計画しています。サイズが大きいかどうかは関係ありません。大きいほど良い。

trie文字列処理を行うために使用しているものがあります。私はいくつかのデータから生成する単純なコンパイラを持っていtrieます。一度生成されると、trie実行時に変更されません。

トライをファイルに保存して効果的にロードできるアプローチを探しています。私はsqlliteそれらがどのように持続しているかを理解するために調べましたb-treeが、それらのファイル形式は少し高度に見え、それらすべてを必要としないかもしれません。

誰かが永続化して読むためのアイデアを提供できれば便利ですtrie。私はCを使ってプログラミングしています。

次のコードを使用して、トライに一致する単語があるかどうかを確認するのではなく、ユーザーが入力したプレフィックスで始まるすべての単語のリストを返すことを検討しています。誰かが私を正しい方向に向けることができますか? 全然やる気が出ない……。

簡単にするために、テーブルには英語辞書のすべての単語が含まれています。

私がやりたいことは、データをトライとして保存できることです。このようにして、トライのさまざまな分岐をたどり、最も関連性の高い結果を返すことができます。

まず、データをテーブルにトライとして格納するにはどうすればよいですか?

次に、ツリーをどのようにトラバースしますか?

それがまったく役立つ場合、この前の質問の提案は、この質問がどこから発生したかです。

私たちが話しているSQLであることを確認してください。ポインターのおかげでMike DunlaveyのC実装を理解しましたが、この部分（トライ自体）がSQLでどのように機能するかわかりません。

ありがとう、
マット