問題タブ [prefix-tree]

質問があります。30000 名の名前を含むビジネス アドレス帳を実装する必要があります。すべての名前には姓と名が含まれます。名だけでなく姓でも検索するオートコンプリート テキスト ボックスを実装する必要があります。Googleで検索すると、この問題はパトリシアトライを使用して解決されることがわかりましたが、プレフィックス検索のみを行うため、ファーストネーム+ラストネームでトライを作成した場合、ファーストネームだけでなくラストネームでも検索するにはどうすればよいですか?

このように 2 つの文字列を挿入するエントリを複製する必要がありますか? ファーストネーム+ラストネームとラストネーム+ファーストネーム

私を助けてください！！！

検索は非常に効率的でなければなりません。

ありがとう。

私の特定のアプリケーションでは、F# の Map と Set のパフォーマンスがかなり不足しています。良い接頭辞 trie は、特に名前によるシンボル検索に関して、インタープリターのパフォーマンスをかなり向上させるようです。唯一の注意点は、追加操作と検索操作 (特にキーが文字列の場合) に対して非常に効率的であり、永続性 (非破壊的な更新を意味する) に対して不変でなければならないということです。

そのようなビーストが利用できない場合は、OCaml または Haskell からの参照実装を使用して開始することができます。

よろしくお願いします！

文字ではなく記号として単語を使用してテキストを圧縮したいのですが、それが良い考えかどうかはよくわかりませんが、(科学のために) テストしたいだけです。

問題は、英語のすべての単語を実際に保存することはできないため、スペルチェッカーが単語の派生形式を保存するのと同じように、変更する予定の非常に一般的な単語 (約 1600 単語) のリストを収集したことです。(例: 動詞、形容詞などに応じて、kill、kill-ing、kill-er、kill-s など)

http://en.wikipedia.org/wiki/Canonical_Huffman_code

「辞書」は頻繁に変更されることはなく、解凍ツールで配布できるため、この特別なバージョンのハフマン コーディングが私のニーズに合っているかどうか知りたいです。また、元のハフマン ツリーを作成して正規のハフマン ツリーに変換する前に、単語の頻度を指定する必要があるようです。

ここでポイントが抜けている場合、またはそれが良いアイデアか悪いアイデアかを訂正してもらえますか?

オーダーが 10^12 程度の文字列の大規模なセットがあり、適切なデータ構造を選択して、文字列が提供されると、O(log(n)) のような整数値を取得して関連付けることができるようにする必要があります。または O(m) 時間、'n' は文字列のリストの長さ、'm' は各文字列の長さです。

それぞれの長さが「m」で、サイズが「q」のアルファベットでエンコードされた文字列のセットは、この長さのほぼすべての可能な文字列をカバーすると予想できます。たとえば、長さが m = 39 の 10^12 個のすべてが一意のバイナリ文字列があるとします。これは、この長さの可能なすべてのバイナリ文字列のセットの ~54% をカバーしたことを意味します。

そのため、衝突を回避する文字列の適切なハッシュ関数を見つけることに関心があります。私が使用できる良いものはありますか？n 個の文字列のセットにインデックスを付けるのにどれくらいの時間がかかりますか?

または、サフィックスツリーを使用する必要がありますか? Ukkonen のアルゴリズムが線形時間の構築を可能にしていることはわかっていますが、類似した文字列が多数ある場合、これによりスペースが節約されるのではないでしょうか?

標準の挿入メカニズムを使用してプレフィックスツリーを実装しています。アルファベット順に単語のリストが表示されることがわかっている場合、挿入を変更していくつかの手順をスキップする方法はありますか？私はJavaでコーディングしていますが、特定の言語のコードは探していません。各単語のノードをキューに追加し、次の単語のプレフィックスになるまでそれを逆方向にホッピングすることを検討しましたが、これはプレフィックスツリーの全体のポイントを回避している可能性があります。

このようなことについて何か考えはありますか？入力が非常によく似た単語などである場合を除いて、有用な実装を思い付くのは難しいと("aaaaaaaaaab", "aaaaaaaaaac", "aaaaaaaaaad", ...)感じています。ただし、その場合でも、プレフィックスに対して文字列比較を行うことは、通常、プレフィックスツリーを使用する場合と同様のコストになる可能性があります。

私は、接頭辞ツリーを使用して O(1) で単一の最近傍を見つけることができたと彼らが言及している論文を読んでいます。一般的な問題を説明し、次に古典的な解決策を説明し、最後に提案された解決策を論文で説明します。

問題: ビット ベクトル L (すべてのベクトルは同じ長さ) とクエリ ビット ベクトル q のリストが与えられた場合、q の最近傍を見つけたいとします。距離メトリックは、ハミング距離 (異なるビット数) です。単純なアプローチは、リストを調べて、リスト内の各ベクトルと q の間のハミング距離を計算することです。これには O(N) が必要です。ただし、非常に高価な数百万のビット ベクトルがあることを考えると、それを削減したいと考えています。

古典的な解決策: この問題に対する古典的な解決策は、近似を使用して最近傍を見つけ、O(logN) を達成することです。これを行う方法は、最初に L を辞書順に並べ替えて、同様のビット ベクトルが互いに近くなるようにすることです。次に、q が与えられると、ソートされたリストにバイナリ検索を適用して、ソートされたリスト内で q が存在する可能性のある位置を取得し、リスト内でその上と下にあるベクトルを取得して (それらはソートの点で類似しているため)、それらの間の距離を調べ、ハミング距離が最も小さいものを選択します。ただし、単純に 1 つの並べ替えを行うだけでは、多くの同様のベクトルを見逃す可能性があるため、できるだけ多くの同様のベクトルをカバーするために、P 個のリストと P 個のジャンブリング関数を使用します。各ジャンブリング関数は、各リストに対応しています。次に、対応するジャンブリング関数でビットをジャンブリングした後、各ビット ベクトルを P の各リストに挿入します。したがって、それぞれがビット ベクトルを持ちますが、ビットの順序が異なる P 個のリストになります。P の各リストを辞書順に並べ替えます。q が与えられると、P の各リストに同じ二分探索を適用しますが、ここでは、アクセスしているリストに応じて q にジャンブリング関数を適用する前に適用します。このステップでは、q に最も類似した P 個のベクトルを取得するため、最終的に q に最も類似したベクトルを取得します。このようにして、できるだけ類似したベクトルをカバーします。ソートに必要な時間を無視すると、最近傍を見つけるのに必要な時間は O(log n) になります。これは、各リストでの二分探索の時間です。P の各リストを辞書順に並べ替えます。q が与えられると、P の各リストに同じ二分探索を適用しますが、ここでは、アクセスしているリストに応じて q にジャンブリング関数を適用する前に適用します。このステップでは、q に最も類似した P 個のベクトルを取得するため、最終的に q に最も類似したベクトルを取得します。このようにして、できるだけ類似したベクトルをカバーします。ソートに必要な時間を無視すると、最近傍を見つけるのに必要な時間は O(log n) になります。これは、各リストでの二分探索の時間です。P の各リストを辞書順に並べ替えます。q が与えられた場合、P の各リストに同じ二分探索を適用しますが、ここでは、アクセスしているリストに応じて q にジャンブリング関数を適用する前に適用します。このステップでは、q に最も類似した P 個のベクトルを取得するため、最終的に q に最も類似したベクトルを取得します。このようにして、できるだけ類似したベクトルをカバーします。ソートに必要な時間を無視すると、最近傍を見つけるのに必要な時間は O(log n) になります。これは、各リストでの二分探索の時間です。このようにして、できるだけ類似したベクトルをカバーします。ソートに必要な時間を無視すると、最近傍を見つけるのに必要な時間は O(log n) になります。これは、各リストでの二分探索の時間です。このようにして、できるだけ類似したベクトルをカバーします。ソートに必要な時間を無視すると、最近傍を見つけるのに必要な時間は O(log n) になります。これは、各リストでの二分探索の時間です。

提案された解決策: 論文で提案されているこのソリューション (ただし、説明はありません) は、プレフィックス ツリーを使用して O(1) 時間で最近傍を取得できることを示しています。論文では、P 個のプレフィックス ツリーと P 個のジャンブリング関数を使用すると述べています。ここで、各ジャンブリング関数は各ツリーに対応しています。次に、対応するジャンブリング関数で各ベクトルのビットをジャンブリングした後、ビット ベクトルを各ツリーに挿入します。q が与えられると、各ツリーに対応する q にジャンピング関数を適用し、各ツリーから q に最も類似したベクトルを取得します。これで、ツリーから取得された P ビットのベクトルが得られます。論文では、プレフィックスツリーから q に最も類似したベクトルを取得するだけで O(1) であると述べています。プレフィックスツリーの検索はO（M）であることがわかっているので、これはまったくわかりません.Mはビットベクトルの長さです。

これは私が参照している論文です (セクション 3.3.2): リアルタイム Web でのコンテンツベースの群集検索

http://students.cse.tamu.edu/kykamath/papers/cikm2012/fp105-kamath.pdf

また、これに関連する私の他の質問に答えていただければ幸いです: NN検索のプレフィックスツリーで最も類似したビットベクトルを検索する方法は?