4

たとえば、次のような数百のキーがあります。

  • 赤いリンゴ
  • maninred
  • フォアマン
  • ブルーアップル

これらのキーに関連するデータがあります。データは文字列であり、最後に関連するキーがあります。

  • redapple：the-tree-has-redapple
  • maninred：彼女はmaninredを見た
  • フォアマン：彼らは現在のフォアマンを買った
  • ブルーアップル：それは驚くべきことでしたが、それはブルーアップルでした

キーに従ってデータを記録するためにハッシュテーブルとハッシュ関数を使用することが期待されており、テーブルからデータを取得できることが期待されています。

ハッシュ関数とハッシュテーブルを使うことは知っていますが、ここでは問題ありません。

だが;

私はプログラムに部分文字列として行われる文字列を与え、一致するキーのデータを取得することが期待されています。

例えば：

私は「赤」を与えなければならず、得ることができなければなりません

  • redapple：the-tree-has-redapple
  • maninred：彼女はmaninredを見た

出力として。

また

私は「リンゴ」を与えなければならず、得ることができなければなりません

  • redapple：the-tree-has-redapple
  • ブルーアップル：それは驚くべきことでしたが、それはブルーアップルでした

出力として。

一致する部分文字列がある場合にのみすべてのキーを検索することを考えることができますが、他の解決策はありますか？すべてのクエリのすべてのキー文字列を検索する場合、ハッシュの使用は不要であり、意味がありませんか？

しかし、すべてのキーで部分文字列を検索するのはO（N）であり、O（1）の問題を解決することが期待されます。

ハッシュを使用すると、キーをハッシュできます。たとえば、「redapple」をたとえば943に、「maninred」をたとえば332にハッシュできます。

そして、クエリマンは文字列「赤」を与えます。943と332から、キーに「赤」の部分文字列があることをどのように見つけることができますか？それは私のcs思考スキルから外れています。

アドバイス、アイデアをありがとう。

4

3 に答える 3

3

n-grammの反転インデックスを使用する必要がある可能性があります。同じアプローチが、スペル修正に使用されます。ワードレッドアップルの場合、次の3グラムの赤、eda、dap、app、ppl、pleのセットがあります。n-grammごとに、それを含む文字列のリストがあります。たとえば、赤の場合は

赤->maninred、redapple

このリストの単語は順序付けする必要があります。aa give substringを含むすべての文字列を検索する場合は、n-grammで部分文字列を分割し、n-grammの単語のリストをインターセプトします。

このalogriphmはO（n）ではありませんが、十分な速度で動作します。

于 2012-05-10T10:56:25.960 に答える
3

ハッシュテーブルではうまくできません。与えられた部分文字列-文字列全体のハッシュ結果を予測することはできません1

合理的な代替手段は、接尾辞木を使用することです。接尾辞ツリーの各端末は、完全な文字列の参照のリストを保持します。この接尾辞はに関連しています。

部分文字列が与えられ、tそれが実際にsコレクション内の一部の部分文字列である場合、の接頭辞でxあるs-の接尾辞があります。を読みながら接尾辞木をトラバースして、そこから到達したノードから到達可能なすべての端末を見つけます。これらの端子には、必要なすべての文字列が含まれています。txt

（1）妥当なハッシュ関数を仮定するとhashCode() == 0、各要素について、明らかにハッシュ値を予測できます。

于 2012-05-10T12:41:10.267 に答える
-1

私は最近この問題を調査しましたが、これはできないと確信しています。ハッシュテーブルがあなたのような検索速度の向上に役立つことを願っていますが、それは私を失望させます。

于 2020-02-07T01:47:37.033 に答える