私は数十億行のテキストと数百万の "キーワード"を持っているとしましょう。タスクは、これらの行を調べ、どの行にどのキーワードが含まれているかを調べることです。換言すれば、(K1 -> V1)
と(K2 -> V2)
のマップを与えた場合、K1=lineID
,V1=text
,K2=keywordID
およびV2=keyword
のマップを作成してとする。また、その注意:数十億行の定義済みキーワードを検出する最も効率的な方法/ライブラリですか?
- すべてのテキスト/キーワードはスペルミスを含むことができ、英語
- テキスト(V1)です。
- ほとんどのキーワード(V2)は、単一の言葉ですが、次のようにいくつかのキーワードが複数の英語の単語(例えば「清潔なタオル」)
から構成することができる今のところ、これを解決するために、私の最初のアイデアは、次のとおりです。
1) Chop up all my keywords into single words and
create a large set of single words (K3)
2) Construct a BK-Tree out of these chopped up keywords,
using Levenshtein distance
3) For each line of data (V1),
3.1) Chop up the text (V1) into words
3.2) For each said word,
3.2.1) Retrieve words (K3) from the BK-Tree that
are close enough to said word
3.3) Since at this point we still have false positives,
(e.g. we would have matched "clean" from "clean water" against
keyword "clean towel"), we check all possible combination
using a trie of keyword (V2) to filter such false
positives out. We construct this trie so that at the
end of an successful match, the keywordID (K2) can be retrieved.
3.4) Return the correct set of keywordID (K2) for this line (V1)!
4) Profit!
私の質問
- これは良いアプローチですか?効率性は非常に重要です - よりよい方法はありますか?改善するものは何ですか?
- 使用できるライブラリはありますか?好ましくは、Javaでうまくいくもの。
ありがとうございます!
(https://code.google.com/p/luke/)Luceneのインデックスを分析するためLUKEツールを使用することができますhttp://stackoverflow.com/questions/4945829/improving-performance-of-fuzzy-string-matching-againstを参照してください。 -辞書 –