1

近似文字列の一致は、見知らぬ問題ではありません。

私はそれを解決する方法を学び、理解しようとしています。私は今でもそれに深く入り込みたくはなく、強引な方法を理解したいだけです。

そのwikiページ（近似文字列マッチング）には、

ブルートフォースアプローチは、TのすべてのサブストリングのP（パターン）までの編集距離を計算してから、最小距離のサブストリングを選択することです。ただし、このアルゴリズムの実行時間はO（m * n ^ 3）で、nはTの長さ、mはPの長さです。

Ok。私はこの声明を次のように理解しています。

  1. Tのすべての可能な部分文字列を見つけます
  2. 文字列の各ペア{P、t1}、{P、t2}、..の編集距離を計算します。
  3. Pからの距離が最も短い部分文字列を見つけ、この部分文字列が答えです。

次の質問があります。

a。2つのforループを使用して、可能なすべてのサブストリングを取得できます。これには、O（n ^ 2）が必要です。それで、1つの部分文字列とパターンの編集距離を計算しようとすると、O（n * m）が必要ですか？なんで？

b。1つのペア（1つの部分文字列とパターン）の距離をどの程度正確に計算できますか？挿入、削除、置換ができることは知っていますが、1つのペアの計算だけを行うアルゴリズムを誰かに教えてもらえますか？

ありがとう

編集

わかりました。レーベンシュタイン距離を使用する必要がありますが、その方法がよくわかりません。

これがコードの一部です

for j from 1 to n
{
    for i from 1 to m
    {
      if s[i] = t[j] then  
        d[i, j] := d[i-1, j-1]       // no operation required
      else
        d[i, j] := minimum
                   (
                     d[i-1, j] + 1,  // a deletion
                     d[i, j-1] + 1,  // an insertion
                     d[i-1, j-1] + 1 // a substitution
                   )
    }
  }

だから、私が今比較していると仮定し{"suv", "svi"}ます。

だから'v' != 'i'、私は他の3つのペアを見る必要があります：

  1. {"su", "sv"}
  2. {"suv", "sv"}
  3. {"su", "svi"}

この部分をどのように理解できますか？なぜこれらの3つの部分を見る必要があるのですか？

2つのプレフィックス（または文字列）を等しくするために、変更の数がdistance between two prefixes必要であることを意味しますか？distance

それでは、を見てみましょう{"su", "sv"}。の距離が1であることがわかります。では、1を追加するだけで、{"su", "sv"}どのよう{"su", "sv"}になりますか？{"suv", "svi"}「su」に「v」を挿入し、「sv」に「v」を挿入してから、最後の「i」を「v」に置き換える必要があると思います。これには3つの操作が含まれます。

4

1 に答える 1

1

2つの文字列間の編集距離を測定する標準的な方法は、レーベンシュタイン距離と呼ばれます。ウィキペディアのページには、アルゴリズムの擬似コードが含まれています。

編集に関して：に変更する{"su", "sv"}最良の方法は、最後をに置き換えることである可能性があるため、確認する必要があります。そのコストは、に変更するためのコストに上乗せされます。または、何らかの方法で変更してからを追加するのが最善の方法である可能性があります。または、最初にfromを削除してから、に変更するのが最善の方法である可能性があります。この場合、最初の方法が最良（または他のオプションと同じくらい良い）であることがわかります。編集距離は確かに2であり、操作はをaに、ををに変更することです。"suv""svi"vi"su""sv""suv""sv"iv"suv""su""svi"uvvi

于 2012-05-28T22:53:08.993 に答える