3

私は短い弦の大きなセットを持っています。部分文字列を含むアイテムのリストをフィルタリングするためのアルゴリズムとインデックス作成戦略は何ですか? たとえば、次のリストがあるとします。

val words = List(
  "pick",
  "prepick",
  "picks",
  "picking",
  "kingly"
  ...
)

部分文字列 "king" を含む文字列を見つけるにはどうすればよいですか? 次のように問題をブルートフォースすることができます：

words.filter(_.indexOf("king") != -1) // yields List("picking", "kingly")

これは小さなセットの場合にのみ実用的です。現在、1,000 万の文字列をサポートする必要があり、将来の目標は数十億です。明らかに、インデックスを作成する必要があります。どんな指標？

MySQL に格納されている ngram インデックスの使用を検討しましたが、これが最善のアプローチかどうかはわかりません。検索文字列が ngram サイズよりも長い場合に、インデックスを最適にクエリする方法がわかりません。

Lucene の使用も検討しましたが、これは部分文字列の一致ではなく、トークンの一致を中心に最適化されており、単純な部分文字列の一致の要件をサポートしていないようです。Lucene には ngrams に関連するクラスがいくつかあります (org.apache.lucene.analysis.ngram.NGramTokenFilterは一例です) が、これらは部分文字列の一致ではなく、スペル チェックとオートコンプリートのユース ケースを対象としているようで、ドキュメントは薄いです。

他にどのようなアルゴリズムとインデックス作成戦略を検討する必要がありますか? これをサポートするオープン ソース ライブラリはありますか? SQL または Lucene 戦略 (上記) を機能させることはできますか?

要件を説明する別の方法は、SQL を使用したものです。

SELECT word FROM words WHERE word LIKE CONCAT('%', ?, '%');

はユーザー?が指定した検索文字列で、結果は検索文字列を含む単語のリストです。

4

2 に答える 2

2

一番長い単語はどれくらいの大きさですか？それが約7〜8文字の場合、すべての文字列のすべての部分文字列を見つけて、その部分文字列をトライに挿入できます（これはAho-Corasikで使用されています - http://en.wikipedia.org/wiki/Aho-Corasick）ツリーの構築には時間がかかりますが、すべての出現箇所の検索は O(length(searched word)) になります。

于 2012-08-02T19:36:57.227 に答える
1

Postgresにはトリグラムインデックスを実行するモジュールがあります

それも興味深いアイデアのようです-トリグラムインデックスを作成します。

nグラムの長さを超えるテキスト検索を分類する方法に関する質問のコメントについて：

これが機能する1つのアプローチです：

「abcde」という検索文字列があり、トリグラムインデックスを作成したとします。（より短い長さの文字列があります-これはあなたにとってスイートスポットに当たる可能性があります）abc = S1、bcd = S2、cde = S3の検索結果を許可します（S1、S2、S3はインデックスのセットです）

次に、S1、S2、S3の最も長い共通の部分文字列が、必要なインデックスを提供します。

LCSを実行する前に、インデックスの各セットを区切り文字（スペースなど）で区切られた単一の文字列として変換できます。

LCSを見つけたら、検索語を分類したので、完全なパターンのインデックスを検索する必要があります。つまり、「abc-XYZ-bcd-HJI-def」を持つ結果を整理する必要があります。

文字列のセットのLCSは、接尾辞配列で効率的に見つけることができます。または接尾辞木

于 2012-08-05T19:07:53.113 に答える