35

PHP levenshtein関数を使用して文字列を比較することに成功しました。

ただし、位置が入れ替わった部分文字列を含む 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 つの可能なアプローチは、比較の前に、文字列内のすべての単語をアルファベット順に並べることです。これにより、単語の元の順序が比較から完全に除外されます。ただし、これの欠点は、単語の最初の文字だけを変更すると、1 文字を変更する場合よりもはるかに大きな混乱が生じる可能性があることです。

私が達成しようとしているのは、人に関する 2 つの事実 (フリー テキスト文字列) を比較し、これらの事実が同じ事実を示している可能性を判断することです。事実とは、たとえば、その人が通った学校、雇用主または発行者の名前などです。2 つのレコードは、同じ学校の綴りが異なっていたり、単語の順序が異なっていたり、余分な単語があったりする可能性があるため、それらが同じ学校を指していると推測するには、マッチングが多少あいまいである必要があります。これまでのところ、スペルミスに対しては非常にうまく機能していますが (私はこれに加えて metaphone に似た表音アルゴリズムを使用しています)、学校でよく見られる単語の順序を入れ替えると非常にうまく機能しません: "xxx college" vs 「○○大学」。

4

9 に答える 9

9

それは簡単です。文字の代わりに単語にダメラウ・レーベンシュタイン距離を使用するだけです。

于 2009-05-06T05:24:34.173 に答える
3

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

$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よりも類似していることを示します。

于 2009-05-06T09:34:45.557 に答える
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]....

標準メソッドにこれが含まれていない理由がわかります。

于 2009-06-05T19:44:12.203 に答える
1

この回答を使用して、次の変更を行います。

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]);
  }
}

これはトライでの辞書検索用ですが、1語にマッチさせる場合も同じ考え方です。あなたは分岐限定を行っており、コストを与える限り、いつでも好きなように変更できます。

于 2009-05-06T17:24:49.200 に答える
1

これは、ベクトル空間検索エンジンを使用するための代表的な例だと思います。

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

ベクトル空間からの結果をファジー化するには、ステミング/類似の自然言語処理手法を実行し、レーベンシュタインを使用して、語彙全体で発生する類似の単語の二次クエリを作成することを検討できます。

于 2010-08-07T20:57:56.987 に答える
1

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

于 2009-05-06T17:41:49.627 に答える
0

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

  1. AとBを言葉に分ける
  2. A のすべての単語について、B で最も一致する単語を見つけます (レーベンシュタインを使用)
  3. その単語を B から削除し、A の一致する単語と同じインデックスで B* に配置します。
  4. A と B を比較します*

例：

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

ステップ 2 を複数のパスで実行することで改善できます。最初は完全一致のみを検索し、次に B* にまだコンパニオンがない A の単語に近い一致を検索し、次に近い一致を少なくします。

于 2011-01-29T23:48:41.283 に答える