数十億行のテキストと数百万の「キーワード」があるとしましょう。タスクは、これらの行を調べて、どの行にどのキーワードが含まれているかを確認することです。つまり、 と のマップが与えられた 場合、 、、(K1 -> V1)および(K2 -> V2)のマップを作成します。次の点にも注意してください。(K2 -> K1)K1=lineIDV1=textK2=keywordIDV2=keyword
- すべてのテキスト/キーワードは英語です
- テキスト (V1) にスペルミスが含まれている可能性があります。
- ほとんどのキーワード (V2) は 1 つの単語ですが、一部のキーワードは複数の英単語で構成されている場合があります (例:「きれいなタオル」)。
これまでのところ、これを解決するための私の最初のアイデアは次のとおりです。
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でうまくいくもの。
前もって感謝します！