8

私は次の2つの文字列を持っています:

String A: Manchester United
String B: Manchester Utd

どちらの文字列も同じ意味ですが、異なる値が含まれています。

これらの文字列を比較して「一致スコア」を得るにはどうすればよいですか。最初の単語が「マンチェスター」と似ていて、2 番目の単語に似た文字が含まれているが、適切な場所にない場合です。

2 つの文字列を指定した後に「一致スコア」を返す単純なアルゴリズムはありますか?

4

6 に答える 6

9

2つの文字列間のレーベンシュタイン距離を計算できます。それが（定義する必要のある）値よりも小さい場合は、それらがかなり近いと見なすことができます。

于 2012-05-08T09:25:18.837 に答える
6

私はこのようなことをする必要があり、レーベンシュタイン距離を使用しました。

100 万を超える行 (および最大 6 または 7 語のテキスト) を持つクエリで使用されている SQL Server UDF に使用しました。

各単語を個別に比較すると、アルゴリズムがより高速に実行され、「類似度インデックス」がより正確になることがわかりました。つまり、各入力文字列を単語に分割し、1 つの入力文字列の各単語を他の入力文字列の各単語と比較します。

レーベンシュタインが差を与えることを忘れないでください。それを「類似度指数」に変換する必要があります。距離を最長の単語の長さで割ったようなものを使用しました（ただし、いくつかのバリエーションがあります）

最初のルール: 単語の順序と数

次のことも考慮する必要があります。

  • 両方の入力に同じ数の単語が含まれている必要がある場合、または変更できる場合
  • 順序が両方の入力で同じでなければならない場合、または変更される可能性があります。

これに応じてアルゴリズムが変わります。たとえば、単語数が異なる場合、最初のルールを適用すると非常に高速です。そして、2 番目のルールは、特に比較されるテキストに多くの単語がある場合に、比較の数を減らします。これについては、後で例を挙げて説明します。

2 番目のルール: 比較される各ペアの類似性に重みを付ける

また、グローバルな類似性インデックスを取得するために、短い単語よりも長い単語に重みを付けました。私のアルゴリズムは、比較されたペアの 2 つの単語のうち最長のものを使用し、短い単語のペアよりも長い単語のペアに高い重みを与えますが、ペアの長さに正確に比例するわけではありません。

サンプル比較: 同順

この例では、異なる数の単語を使用しています:

  • 「マンチェスター・ユナイテッド」を「マンチェスター・ユナイテッドFC」と比較する

両方の入力の単語の順序が同じであることが保証されている場合は、これらのペアを比較する必要があります。

Manchester United
Manchester Utd    FC

(マンチェスター、マンチェスター) (ユナイテッド、ユナイテッド) (FC: 比較なし)

Manchester     United
Manchester Utd FC

(マンチェスター,マンチェスター) (ユナイテッド: 比較なし) (ユナイテッド,FC)

           Machester United
Manchester Utd       FC

(マンチェスター: 比較なし) (マンチェスター、Utd) (ユナイテッド、FC)

明らかに、最高のスコアはペアの最初のセットになります。

実装

単語を同じ順序で比較する。

単語数が多い文字列は固定ベクトルであり、この例では A、B、C、D、E として示されています。ここで、v[0] は単語 A、v[1] は単語 B などです。

単語数が少ない文字列については、最初のセットと比較できるインデックスのすべての可能な組み合わせを作成する必要があります。この場合、単語数の少ない文字列は a,b,c で表されます。

単純なループを使用して、比較するペアを表すすべてのベクトルを次のように作成できます。

A,B,C,D,E   A,B,C,D,E   A,B,C,D,E   A,B,C,D,E   A,B,C,D,E   A,B,C,D,E
a,b,c       a,b,  c     a,b,    c   a,  b,c     a,  b,  c   a,    b,c
0 1 2       0 1   3     0 1     4   0   2 3     0   2   4   0     3 4

A,B,C,D,E   A,B,C,D,E   A,B,C,D,E   A,B,C,D,E
  a,b,c       a,b,  c     a,  b,c       a,b,c
  1 2 3       1 2   4     1   3 4       2 3 4

サンプルの数値は、単語の最初のセットのインデックスを持つベクトルであり、最初のセットのインデックスと比較する必要があります。つまり、v[0]=0 は、ショート セット (a) のインデックス 0 をロング セット (A) のインデックス 0 と比較することを意味し、v[1]=2 は、ショート セット (b) のインデックス 1 をインデックス 2 と比較することを意味します。ロングセット（C）など。

このベクトルを計算するには、単純に 0,1,2 から始めます。移動できなくなるまで、移動可能な最新のインデックスを右に移動します。

最後の 1 つを移動して開始します。

0,1,2 -> 0,1,3 -> 0,1,4 
No more moves possible, move the previous index, and restore the others
to the lowest possible values (move 1 to 2, restore 4 to 3)

最後のものがそれ以上移動できない場合は、最後の 1 つ前に移動し、最後のものを可能な限り近い場所にリセットします (1 は 2 に移動し、4 は 3 に移動します)。

0,2,3 -> 0,2,4
No more moves possible of the last, move the one before the last

最後の前のものをもう一度移動します。

0,3,4
No more moves possible of the last, move the one before the last
Not possible, move the one before the one before the last, and reset the others:

前のものを移動します。

1,2,3 -> 1,2,4

等々。写真を見る

可能な組み合わせがすべて揃ったら、定義されたペアを比較できます。

3 番目のルール: 比較を停止するための最小の類似性

最小の類似性に達したときに比較を停止: 実行したい内容に応じて、しきい値に達したときにペアの比較を停止するしきい値を設定できます。

しきい値を設定できない場合でも、少なくとも単語のペアごとに 100% の類似性が得られればいつでも停止できます。これにより、多くの時間を割くことができます。

場合によっては、類似度が少なくとも 75% 程度の場合は、単純に比較を停止することができます。これは、ユーザーが提供したものに類似したすべての文字列をユーザーに表示する場合に使用できます。

例：語順の変化との比較

順序が変わる可能性がある場合は、最初のセットの各単語と 2 番目のセットの各単語を比較し、すべての順序で並べられた最短のペアのすべての単語を含む結果の組み合わせに対して最高スコアを取得する必要があります。 2番目のペアの異なる単語と比較して、可能な方法。このために、(n X m) 要素の行列の上または下の三角形にデータを入力し、行列から必要な要素を取得できます。

第 4 のルール: 正規化

次のように、比較する前に単語を正規化する必要もあります。

  • 大文字と小文字が区別されない場合は、すべての単語を大文字または小文字に変換します
  • アクセントを区別しない場合は、すべての単語のアクセントを削除します
  • 通常の略語があることがわかっている場合は、それらを正規化して、高速化する略語にすることもできます（つまり、utd を united に変換するのではなく、united を utd に変換します）。

最適化のためのキャッシング

手順を最適化するために、可能なものは何でもキャッシュしました。つまり、A のベクトル 0,1,2-0,1,3,-0,1,4-0,2,3 のような異なるサイズの比較ベクトルです。 ,B,C,D,E から a,b,c への比較の例: 長さ 3,5 のすべての比較は、最初の使用時に計算され、着信する 3 語から 5 語までのすべての比較で再利用されます。

その他のアルゴリズム

ハミング距離を試してみましたが、結果はあまり正確ではありませんでした。

セマンティック比較、音声比較、いくつかの文字がまったく同じであると見なすなど、はるかに複雑なことを行うことができます（スペイン語などのいくつかの言語では と のようbにv、区別はありません）。これには、実装が非常に簡単なものもあれば、非常に難しいものもあります。

注: レーベンシュタイン距離の実装は含めませんでした。さまざまな言語で実装されていることが簡単にわかるからです。

于 2012-05-08T11:14:01.920 に答える
5

この記事を見てください。この記事では、その方法を説明し、サンプルコードも提供しています:)

あいまいマッチング（レーベンシュタイン距離）

アップデート：

これは、2つの文字列をパラメーターとして受け取り、2つの文字列の「レーベンシュタイン距離」を計算するメソッドコードです。

public static int Compute(string s, string t)
    {
    int n = s.Length;
    int m = t.Length;
    int[,] d = new int[n + 1, m + 1];

    // Step 1
    if (n == 0)
    {
        return m;
    }

    if (m == 0)
    {
        return n;
    }

    // Step 2
    for (int i = 0; i <= n; d[i, 0] = i++)
    {
    }

    for (int j = 0; j <= m; d[0, j] = j++)
    {
    }

    // Step 3
    for (int i = 1; i <= n; i++)
    {
        //Step 4
        for (int j = 1; j <= m; j++)
        {
        // Step 5
        int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

        // Step 6
        d[i, j] = Math.Min(
            Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
            d[i - 1, j - 1] + cost);
        }
    }
    // Step 7
    return d[n, m];
    }
于 2012-05-08T09:26:21.877 に答える
1

重複の検出は、レーベンシュタイン距離の計算よりも「少し」複雑な場合があります。次の例を検討してください。

1. Jeff, Lynch, Maverick, Road, 181, Woodstock  
2. Jeff, Alf., Lynch, Maverick, Rd, Woodstock, NY

この重複は、複雑なクラスタリング アルゴリズムによって照合できます。

詳細については、「大規模データベースでの重複検出のための効果的な増分クラスタリング」などの研究論文を確認してください。

（例は論文より）

于 2012-05-08T10:10:47.640 に答える
1

探しているのは、文字列の類似度です。これには複数の方法があります。

  1. 2 つの文字列間の距離を編集します (回答 #1 のように)
  2. 文字列を文字セット (通常はバイグラムまたは単語) に変換し、2 つのセットでブルース係数またはダイス係数を計算します。
  3. 文字列を用語ベクトル (単語またはバイグラムのいずれか) に射影し、2 つのベクトル間の余弦距離を計算します。

一般的に、オプション #2 が実装が最も簡単であることがわかります。文字列がフレーズである場合は、単語境界で単純にトークン化できます。上記のすべてのケースで、トークン化する前にまずストップ ワード (and、a、the などの一般的な単語) を削除することをお勧めします。 更新:リンク

サイコロ係数

コサイン類似度

C# で Naive Similarity エンジンを実装する*警告: 恥知らずな自己宣伝

于 2012-05-08T09:51:28.900 に答える