1

問題を説明しましょう：

  1. 私が図書館を持っているとしましょう。図書館には多くの本があり、各本には章があり、各章には文字列が含まれています (文字列はドット "." で始まりドット "." で終わります)。
  2. 繰り返しますが、ライブラリ -> 本 -> 章 -> 文字列です。
  3. 本から文字列を抽出しました。これを「本の文字列」と呼びましょう。
  4. ユーザーが検索フォームに文字列を入力できるシステムがあり、システムは入力された文字列と完全に一致するものを「本の文字列」から返す必要があります。入力された文字列が books 文字列のどの文字列とも一致しない場合、何も返されません。

私はそれについて考え、解決策を見つけました。すべての本の文字列を MD5 し、ハッシュされた本の文字列を保存します。ユーザーが検索する文字列を入力すると、それもハッシュし、ハッシュされた書籍の文字列で一致するものを検索します。単純な検索よりも安価 (各文字列で 32 文字または 64 文字) であり、正確な一致のみを返します。

コメント、アイデア、より良い解決策はありますか?

PSそのようなアルゴリズムの名前は何ですか? 検索またはマッチング？

4

9 に答える 9

4

それは悪いことではありませんが、Lucene を調査する必要があります。これはパブリック シェアウェアであり、多数の言語で実装されているテキスト インデックス作成および検索ツールです。そのうちの 1 つが .Net です.. (どのプラットフォーム/言語で作業していますか?)主なモデルは、特定の市場セグメント (多数の雑誌記事、本の抜粋など) でコンテンツを提供することでした。Lucene は私たちにとって非常にうまく機能しました。

ルセン

于 2009-01-14T00:47:10.083 に答える
4

Boyer-Mooreアルゴリズムのような単純な方法からサフィックス ツリーのような複雑なデータ構造まで、文字列を検索するためのアルゴリズムは多数あります。これらの完全なプレゼンテーションは、次の場所にあります。

  • Gusfield、Dan (1999)、文字列、シーケンス、およびツリーのアルゴリズム。ケンブリッジ: ユニバーシティ プレス。

ただし、あなたの場合、本のテキストを個々のトークン (単語) に分割し、これらをインデックスに格納する方がおそらく理にかなっています (たとえば、単純に Map に、またはLuceneのようなインデックス作成と検索のための完全なフレームワークを使用します)。

于 2009-01-14T01:21:03.603 に答える
3

これはハッシングと呼ばれ、検索またはマッチングと考えることができます。

ハッシュの生成に使用された文字列も比較して、MD5 ハッシュが正しいことを確認する必要があります。これにより、誤検知がなくなります。

考慮すべきもう1つのことは、ある種の検索から始まるサポートを行うことが有益である可能性があるということです。 検討

Mary Queen of Scots
Mary Livingston
Mary Had a Little Lamb, and other silly stories

Aは Mary の検索から開始し、これら 3 つのレコードと、おそらくそれ以上のレコードを返すはずです。MD5 の種類のハッシュは高速ですが、状況に応じて最適なメリットとコストのバランスを見つけるために、他の回答に示されている手法も考慮する必要があります。

于 2009-01-14T04:49:52.403 に答える
2

代わりに、すべての本の章をサフィックス ツリーに変換する必要があります。接尾辞ツリーは Trie の一種です (divo によって言及されています)。

サフィックス ツリーは、特に高速テキスト検索での使用を目的としています。サフィックス ツリーの利点の 1 つは、長さ n の文字列の検索に O(n) 時間かかることです。これは、アルゴリズムのアイデアと同じくらい (漸近的に) 優れています (文字列のハッシュには O(n) 時間がかかるため) が、部分的な文でも機能するため、はるかに柔軟です。ピリオドで検索を開始/終了すると、文検索になります。

明確化: より正確には、すべてに対して 1 つのサフィックス ツリーが存在します。

于 2009-01-14T01:04:32.263 に答える
1

文字列データを格納するために、 Trieまたはその他のツリーベースのデータ構造を使用したい場合があります。

トライは、ハッシュ テーブルを置き換えるためにも使用できます。これには、次の利点があります。

  • 不完全なハッシュ テーブルと比較して、最悪の場合、O(m) 時間、トライでデータを検索する方が高速です。不完全なハッシュ テーブルでは、キーの競合が発生する可能性があります。キーの衝突は、ハッシュ テーブル内の同じ位置に異なるキーをマッピングするハッシュ関数です。不完全なハッシュ テーブルでの最悪の場合のルックアップ速度は O(N) 時間ですが、通常は O(1) であり、O(m) 時間がハッシュの評価に費やされます。

  • トライでは異なるキーの衝突はありません。

  • キーの衝突を格納するハッシュ テーブル バケットに類似したトライ内のバケットは、1 つのキーが複数の値に関連付けられている場合にのみ必要です。

  • ハッシュ関数を提供したり、より多くのキーがトライに追加されたときにハッシュ関数を変更したりする必要はありません。

  • トライでは、エントリをキーでアルファベット順に並べることができます。

試行にはいくつかの欠点もあります。

  • 場合によっては、データを検索するためのハッシュ テーブルよりも試行が遅くなることがあります。特に、メイン メモリに比べてランダム アクセス時間が長いハードディスク ドライブやその他の二次記憶装置でデータに直接アクセスする場合は特にそうです。
  • すべてのキーを浮動小数点数などの文字列として表すのは簡単ではありません。浮動小数点数は、1、1.0、1.00、+1.0 など、同じ浮動小数点数に対して複数の文字列表現を持つことができます。
  • 試行は、多くの場合、ハッシュ テーブルよりもスペース効率が低くなります。

( http://en.wikipedia.org/wiki/Trieを参照)

于 2009-01-14T00:51:28.827 に答える
0

私は Trie に同意します - 1 つ追加すると、soundx アルゴリズムを使用して文字列を trie id/node に変換します - したがって、スペルミスが考慮されます

于 2009-01-14T19:58:27.327 に答える
0

トライは最良のアプローチです。これはサフィックス マップとも呼ばれます。ハッシュのアイデアよりもトライを使用する利点は、トライを使用すると、オートコンプリート型の構文を非常に簡単に表示できることです。単語を見つけるのにかかる時間は O(n) です。ここで、n は単語の長さです。Trie の各ノードで、特定の単語を含む本のリストを保存する必要があります。

于 2009-01-14T02:44:08.380 に答える
-1

これはハッシングと呼ばれます。あなたの方法はうまくいくかもしれませんが、あまり柔軟ではありません。ここでも、完全一致のみを取得します。2 つのプリイメージが同じイメージを共有する (2 つの異なる文字列が同じ値にハッシュされる) 可能性もありますが、その可能性は非常に低いため、実際の問題ではありません。柔軟性がないのでお勧めしませんが、それが気にならなければ、これでうまくいくと思います。これは基本的に、人々がパスワードの保存と検証に使用する手法と同じです (ただし、明らかに「ソルト」値は使用していません)。

于 2009-01-14T00:46:58.540 に答える
-1

まず、使用する必要があるのはデータベースのように聞こえますが、これはまさにデータベースの目的です。(これを独自のアプリケーションに組み込みたい場合は、組み込みライブラリとして使用するように設計された軽量の DBMS であるSQLiteを調べてください。)

第二に、あなたのハッシュ ソリューションが正確な一致のみを返すということは、まったく正しくありません... MD5 ダイジェストは 128 ビットであるため、文字列の任意のペアが同じハッシュ値を生成する可能性が 1/2^128 であることを意味します。 . ええ、小さい数ですが、本をたくさん持っていると、弦のペアがたくさんあります。そのため、ハッシュ値を比較したら、全文比較を行って誤検出を排除する必要があります。

于 2009-01-14T02:14:27.600 に答える