私は動作するアルゴリズムを作ったが、実行時間は非常に恐ろしい。はい、私はそれが恐ろしいが、あまりそれほどではないことを最初から知っています。わずか200,000レコードの場合、プログラムは1時間以上実行されます。NLP - ファジーストリングマッチングの実行時間とリコールの改善
基本的に私がやっている何がある:
for each searchfield in search fields
for each sample in samples
do a q-gram matching
if there are matches then return it
else
split the searchfield into uniwords
for each sample in samples
split sample into uniwords
for each uniword in samples
if the uniword is a known abbreviation
then search the dictionary for its full word or other known abbr
else do a jaro-winkler matching
average the distances of all the uniwords
if the average is above threshold then make it as a match and break
end for
if there is a match make a comment that it matched one of the samples partially
end else
end for
はい、このコードは非常にループ幸せです。リコールは非常に重要なので私はブルートフォースを使用しています。だから、何百万ものデータのために200000データ用に実行しているだけでなく、クライアントのコンピュータはハイエンドではない(Ram-Pentium 4またはDual-Coreの1GB-2GB、このプログラムをテストするコンピュータは、4GBのRAMを搭載したデュアルコアです)。私はTF/IDFに出くわしましたが、十分かどうかわかりません。そして私はどのようにGoogleがリアルタイムで検索を行うことができるのだろうか。
ありがとうございます!
編集: このプログラムはデータフィルタリングプログラムです。 200,000のダミーデータ(実際のデータは約12M)から、サンプルとは関係のないデータをフィルタリングする必要があります(500ダミーのサンプル、実際のサンプルの量はまだわかりません)。
与えられたダミーのデータとサンプルでは、実行時間は約1時間ですが、ここでは微調整してから10〜15分に短縮できました。私は同じ文字で始まるフィールドとサンプルをグループ化して(特殊で意味のない単語、例えばa、anを割り引く)、フィールドを同じ最初の文字でサンプルにマッチングさせることでそれを減らしました。私はそこに問題があることを知っています。フィールドの最初の文字のスペルが間違っている場合はどうなりますか?しかし、私はそれらの数はごくわずかだと思います。サンプルは常に維持されているため、正確に記入されています。
わかりません。あなたは200,000個のアイテムを持っています(それは 'samples'ですか?)、あなたは入力を受け取り、入力に類似するアイテムを検索しますか?入力項目は同じ200,000項目ですか、または異なる入力ですか?検索フィールドは何を意味しますか? _similarity_検索のみについてですか、_relevance_(情報検索のように)という概念がありますか? – jogojapan
検索対象のアイテムは200,000アイテム(ダミーデータ、実際のデータは約12M)ですが、サンプルは500個です。検索アイテムはサンプルと異なる場合があります。はい、類似点だけではなく、検索項目とサンプルとの関連性も考慮する必要があります。実際には私はここでコードを修正し、実行時間を10-15分に短縮しました。 – MindSeeker