レーベンシュタイン距離:単語の位置の入れ替えをより適切に処理するにはどうすればよいでしょうか?

https://stackoverflow.com/questions/828132

06-07-2019
|

質問

PHPを使用して文字列を比較することに成功しましたレーベンシュタイン関数。

ただし、位置が入れ替わった部分文字列を含む 2 つの文字列の場合、アルゴリズムはそれらをまったく新しい部分文字列としてカウントします。

例えば：

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

持っているものとして扱われます 共通点が少ない よりも：

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

私は、 最初の2つ より似ていました。

位置が切り替わった部分文字列を編集とは異なるものとして識別できる比較関数をどのように考え出すことができるでしょうか?

私が考えた考えられるアプローチの 1 つは、比較する前に文字列内のすべての単語をアルファベット順に並べることです。これにより、単語の元の順序が比較から完全に削除されます。ただし、これの欠点は、単語の最初の文字だけを変更すると、単一の文字を変更する場合よりもはるかに大きな混乱が生じる可能性があることです。

私が達成しようとしているのは、自由なテキスト文字列である人々に関する 2 つの事実を比較し、これらの事実が同じ事実を示す可能性がどの程度あるかを判断することです。事実とは、たとえば、誰かが通っていた学校、雇用主、出版社の名前などです。2 つのレコードには、同じ学校の綴りの違い、単語の順序の違い、余分な単語などが含まれている可能性があるため、それらが同じ学校を指していると適切に推測するには、一致が多少あいまいでなければなりません。これまでのところ、スペルミスに対しては非常にうまく機能しています (これに加えて、metaphone に似たフェネティックアルゴリズムを使用しています) が、学校でよくあると思われる単語の順序を入れ替えると、非常にうまく機能しません。「○○大学」対「○○大学」。

解決

Nグラム

使用 Nグラム, をサポートします テキスト全体にわたる複数の文字の置き換え.

一般的な考え方は、問題の 2 つの文字列を可能なすべての 2 ～ 3 文字の部分文字列 (n グラム) に分割し、2 つの文字列間で共有される n グラムの数を類似性メトリックとして扱うことです。これは、共有数を長い文字列内の n グラムの合計数で割ることによって正規化できます。これは計算するのは簡単ですが、かなり強力です。

例文の場合:

A. The quick brown fox
B. brown quick The fox
C. The quiet swine flu

AとBのシェア 18 2グラム

AとCのシェアのみ 8 2グラム

から 20 合計可能です。

これについては、次の記事で詳しく説明しています。グラバノら。紙.

tf-idf とコサインの類似度

それほど簡単ではありませんが、情報理論に基づいた代替案は、次の用語を使用することです。用語頻度 - 逆文書頻度 (tf-idf) トークンを重み付けし、文ベクトルを構築してから使用します。コサイン類似度類似性メトリックとして。

アルゴリズムは次のとおりです。

文ごとの 2 文字のトークン頻度 (tf) を計算します。
逆文頻度 (idf) を計算します。これは、コーパス内のすべての文の数 (この場合は 3) をすべての文にわたって特定のトークンが出現する回数で割った商の対数です。この場合番目はすべての文に含まれているため、情報内容はゼロです (log(3/3)=0)。
tf テーブルと idf テーブル内の対応するセルを乗算して、tf-idf 行列を生成します。
最後に、すべての文ペアのコサイン類似度行列を計算します。ここで、A と B は、対応するトークンの tf-idf テーブルからの重みです。範囲は 0 (似ていない) から 1 (等しい) です。

レーベンシュタイン修正とメタフォン

その他の回答に関しては。ダメラウ＝レーベンシュタイン変更は転置のみをサポートします 隣接する2つの 文字。メタフォン類似性のマッチングではなく、同じように聞こえる単語に一致するように設計されました。

他のヒント

簡単です。文字ではなく単語の Damerau-Levenshtein 距離を使用します。

スペースで分解し、配列をソートして分解し、レーベンシュタインを実行します。

これも試すことができます。（単なる追加の提案）

$one = metaphone("The quick brown fox"); // 0KKBRNFKS
$two = metaphone("brown quick The fox"); // BRNKK0FKS
$three = metaphone("The quiet swine flu"); // 0KTSWNFL

similar_text($one, $two, $percent1); // 66.666666666667
similar_text($one, $three, $percent2); // 47.058823529412
similar_text($two, $three, $percent3); // 23.529411764706

これは、1番目と2番目が1と3と2と3よりも類似していることを示します。

スペルチェッカーにレベンシュタインを実装しています。

求めているのは、移調を1つの編集としてカウントすることです。

これは、1語の転置だけを数えたい場合に簡単です。ただし、2つ以上離れた単語の転置の場合、アルゴリズムへの追加は最悪のシナリオ！（max（wordorder1.length（）、wordorder2.length（）））です。すでに二次アルゴリズムに非線形サブアルゴリズムを追加することはお勧めできません。

これがどのように機能するかです。

if (wordorder1[n] == wordorder2[n-1])
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1, workarray[x-2, y-2]);
}
  else
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1);
}

移調に触れるだけ。すべての転置が必要な場合は、すべてのポジションについて、そのポイントから逆方向に比較する必要があります

1[n] == 2[n-2].... 1[n] == 2[0]....

だから、なぜ彼らはこれを標準的な方法に含めないのかがわかります。

この回答と次の変更を行います：

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
  /* TRY SWAPPING FIRST TWO CHARACTERS */
  if (w[1]){
    swap(w[0], w[1]);
    match(t, w, s, budget-1);
    swap(w[0], w[1]);
  }
}

これはトライでの辞書検索用ですが、単一の単語とのマッチング用でも同じ考えです。あなたはブランチとバウンドを行っており、いつでも、あなたがそれにコストを与える限り、あなたが好きな変更を加えることができます。

2つの文字列間で重複する単語を削除してから、レーベンシュタインを使用します。

iは、これがベクトル空間検索エンジンを使用するための代表的な例であると考えています。

この手法では、各ドキュメントは本質的に、コーパス全体に含まれる異なる単語と同じ数の次元を持つベクトルになります。同様の文書は、そのベクトル空間内の隣接する領域を占有します。このモデルの優れた特性の1つは、クエリも単なるドキュメントであるということです。クエリに答えるには、ベクトル空間での位置を計算するだけで、結果は最も近いドキュメントになります。私は、PHPの取得および解決策がそこにあると確信しています。

ベクトル空間からの結果をファジー化するには、語幹/類似の自然言語処理技術を使用し、レベンシュタインを使用して、語彙全体で発生する類似語の二次クエリを構築することを検討できます。

最初の文字列がAで、2番目の文字列がBの場合：

AとBを単語に分割する
Aのすべての単語について、Bで最適な単語を検索します（レベンシュタインを使用）
Bからその単語を削除し、Aの一致する単語と同じインデックスでB *に入れます。
AとB *を比較します

例：

A: The quick brown fox
B: Quick blue fox the
B*: the Quick blue fox

ステップ2を複数のパスで実行し、最初に完全に一致するものだけを見つけてから、B *にコンパニオンがまだないAの単語に近い一致を見つけて、次にあまり一致しないなどの方法で改善できます。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow