2

文字列のセットを別の文字列のセットと比較して、どの文字列が類似しているかを見つける必要があります（あいまい文字列の一致）。例えば：

{ "A.B. Mann Incorporated", "Mr. Enrique Bellini", "Park Management Systems" } 
and
{ "Park", "AB Mann Inc.", "E. Bellini" }

ゼロベースのインデックスを想定すると、一致は0-1、1-2、2-0になります。明らかに、この種のことで完璧なアルゴリズムはありません。

私はレーベンシュタイン距離アルゴリズムの実用的な実装を持っていますが、それを使用して各セットから類似の文字列を見つけるには、比較を行うために両方の文字列セットをループする必要があり、結果としてO（n ^ 2）アルゴリズムになります。これは、適度なサイズのセットでも許容できないほど遅くなります。

また、shinglingとJaccard係数を使用するクラスタリングアルゴリズムも試しました。残念ながら、これもO（n ^ 2）で実行されるため、ビットレベルの最適化を行っても速度が遅くなります。

これを実現するための、より効率的なアルゴリズム（O（n ^ 2）よりも高速）、またはさらに良いことに、すでにC＃で記述されたライブラリを知っている人はいますか？

4

3 に答える 3

1

O(N^2) に対する直接の回答ではなく、N1 アルゴリズムに関するコメントです。

これはサンプル データですが、すべてクリーンです。これは、私が Levenstien を使用するデータではありません。Incrimate は Inc. よりも Incorporated との距離が近くなります。E. は Enrique とはあまり一致しません。

レーベンシュタイン距離は、キー入力エラーの検出に優れています。
OCRの照合にも適しています。

クリーンなデータがある場合は、ステミングやその他のカスタム ルールを使用します。
Porter Stemmer は C# で使用でき、クリーンなデータがある場合は
EG
remove を使用できます。およびその他の句読点
を削除する ストップ ワード (the)
ステム
各リストを 1 回解析し、一意のステムごとに int 値を割り当てます int
で一致を実行します
まだ N^2 ですが、N1 の方が高速
ですwith cap は部分的なスコアを取得
します 単語数も考慮する必要があります
3 に一致する 5 の 2 つのグループは、4 に一致する 10 の 2 つのグループよりも高いスコアを獲得 する必要があります

フレーズごとに Int ハッシュセットを作成し、交差してカウントします。

N^2 から抜け出せるかどうかわからない。
しかし、N1を見ることをお勧めします。

Lucene はフレーズ マッチングを備えたライブラリですが、実際にはバッチ用に設定されていません。
何度も使用されることを意図してインデックスを作成し、インデックスの検索速度がインデックスの作成時間にわたって最適化されるようにします。

于 2012-11-07T21:09:52.743 に答える
0

与えられた例では、少なくとも 1 つの単語が常に一致します。考えられるアプローチでは、マルチマップ (キーごとに複数のエントリを格納できる辞書) またはDictionary<TKey,List<TVlaue>>. 最初のセットの各文字列は、1 つの単語に分割されます。これらの単語はマルチマップのキーとして使用され、文字列全体が値として格納されます。

これで、2 番目のセットの文字列を 1 つの単語に分割し、各単語に対して O(1) 検索、つまりすべての単語に対して O(N) 検索を実行できます。これにより、最初の生の結果が得られます。各一致には、少なくとも 1 つの一致する単語が含まれています。最後に、他のルール (イニシャルや略語の検索など) を適用して、この生の結果を絞り込む必要があります。

于 2012-11-07T21:26:57.910 に答える
0

「文字列類似性結合」と呼ばれるこの問題は、研究コミュニティで最近よく研究されています。そのようなアルゴリズムhttp://flamingo.ics.uci.edu/releases/4.1/src/partenum/を実装する Flamingo と呼ばれる C++ のソース コード パッケージをリリースしました。データ セットが単一のマシンには大きすぎる場合は、 http: //asterix.ics.uci.edu/fuzzyjoin/ に Hadoop ベースの実装もあります。

于 2012-11-08T06:24:22.980 に答える