0

部分文字列/文字の一致を使用して実装された検索機能と、トークン ベースの一致を使用して実装された検索機能の違いは何ですか? 商品企画のために、直感的で技術的すぎない説明を探しています。以下は私の説明です。多かれ少なかれ正しいですが、直感的でも完全でもありません。

答えは、一致の最小単位として何を選択するかに関係があります。個々の文字と一致していますか、それとも個々の単語と一致していますか? 部分文字列一致の例:

"lady's hat".contains("l") == true
"lady's hat".contains("lady's hat") == true

一方、トークンのマッチングは次のようになります。

Array("lady", "s", "hat").contains("l") == false
Array("lady", "s", "hat").contains("lady") == true
Array("lady", "s", "hat").contains("lady's hat") == false

明らかに、これは非常に単純化しすぎており、多くの疑問が生じます。間違った抽象化レベルで問題を説明しようとしているのかもしれません。

コンテキスト: Web アプリケーションの検索およびフィルタリング機能について Java で作業しています。私たちの現在のアプローチは、LIKE演算子と MySQL を使用しており、完全なテーブル スキャンの明らかなパフォーマンスの問題に悩まされています。Lucene、Solr、またはリレーショナル データの非正規化を使用することを検討しています。

4

1 に答える 1

1

文字マッチング
文字マッチングは負荷が高く、常に O(NP) になります。ここで、N = 検索する文字数、P = 検索する用語数です。

これは、線形検索の疑似コードです。

function linear_search(items, terms, match_mode) {
  matched_items = new array();
  for(item_idx=0, item_count=count(items);item_idx < item_count;++item_idx) {
      doc = items[item_idx];
      match_count = 0;
      for(term_idx=0, term_count=count(terms);term_idx < term_count;++term_idx) {
          term = terms[term_idx];
          for(i=0, doc_len = strlen(doc), term_len = strlen(term) ; i < doc_len; i += term_len) {
              if(substr(doc, i, term_len) == term) { 
                  if(mode == 'ANY') {
                      matched_items[]=item_idx;
                      continue 3;
                  }  
                  ++match_count;
                  break;
              }
          }
       }
       if(mode == 'ALL' && (match_count == count(items)) matched_items[]=item_idx;
  }
  return matched_items;
}

各ドキュメント (行) は線形検索操作を使用して検索する必要があるため、N は実際にはデータ セット全体の sum(strlen(N)) です (各行、つまりドキュメントは N です)。O(NP) は、大規模なドキュメント、または多数のドキュメント、またはその両方に対する非常に長い操作です。

逆インデックス (トークン検索)
一方、トークン ベースの検索では、データをトークンに事前解析し、「逆インデックス」を作成します。各文書 (検索対象のテキスト) はまず用語に分割され、次に用語が索引付けされて文書を指します。
たとえば、生データが与えられた場合:

1, the quick brown fox
2, all cows eat grass
3, all the world

逆索引が作成されます。

all => 2, 3
brown => 1
cows => 2
eat => 2
fox => 1
grass => 2
quick => 1
the => 1, 3
world => 3

通常、b ツリーはトークンに対して作成されます。したがって、トークンのルックアップは O(log(N)) であり、トークンに一致するドキュメントのリストを取得します。実際のデータを取得するためのルックアップは、通常、別の O(log(N)) 操作です。
これにより、B ツリー構造を想定して、逆インデックス操作のコスト計算が行われます。

O(log(TERM_COUNT)) + O(log(DOC_MATCH_COUNT))

単語位置分析
通常、インデックスには、一致した文書とともに、文書内の単語位置が格納されます。これにより、ドキュメント自体を調べることなく、「bar」の近くの「foo」などの位置分析が可能になります。

all => 2:1, 3:1
brown => 1:3
cows => 2:2
eat => 2:3
fox => 1:4
grass => 2:4
quick => 1:2
the => 1:1, 3:2
world => 3:3

ステミング
さらに、Porter Stemmer (http://en.wikipedia.org/wiki/Stemming) などの「ステミング」は、通常、インデックス作成前および検索前に用語に適用されます。

ステマーは、「branded」や「branding」などの単語を「brand」に変換し、ブランドを検索すると、branded、branding、または brand に一致するドキュメントが返されるようにします。

于 2012-08-01T00:15:27.673 に答える