19

Steven Skiena による The Algorithm Design Manual を読んでいて、動的プログラミングの章を読んでいます。彼は編集距離のサンプルコードをいくつか持っており、本でもインターネットでも説明されていないいくつかの機能を使用しています。だから私は疑問に思っています

a) このアルゴリズムはどのように機能しますか?

b) 関数 indel と match は何をしますか?

#define MATCH     0       /* enumerated type symbol for match */
#define INSERT    1       /* enumerated type symbol for insert */
#define DELETE    2       /* enumerated type symbol for delete */

int string_compare(char *s, char *t, int i, int j)
{
        int k;                  /* counter */
        int opt[3];             /* cost of the three options */
        int lowest_cost;        /* lowest cost */

        if (i == 0) return(j * indel(' '));
        if (j == 0) return(i * indel(' '));

        opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);
        opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]);
        opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]);

        lowest_cost = opt[MATCH];
        for (k=INSERT; k<=DELETE; k++)
                if (opt[k] < lowest_cost) lowest_cost = opt[k];

        return( lowest_cost );
}
4

6 に答える 6

30

本の 287 ページに次のように書かれています。

int match(char c, char d)
{
  if (c == d) return(0); 
  else return(1); 
}

int indel(char c)
{
  return(1);
}
于 2014-01-26T14:50:08.533 に答える
8

それらは本の中で説明されています。セクション8.2.4 さまざまな編集距離をお読みください。

于 2013-10-07T06:22:03.213 に答える
6

基本的に、ボトムアップまたはトップダウンの再計算を回避するために、問題の解決策がサブ問題の解決策に構築される問題解決の動的計画法を利用します。

問題の再帰的構造は、ここで指定されてi,jいるとおりです。ここで、2 つの文字列の開始 (または終了) インデックスはそれぞれです。

ここに画像の説明を入力

アルゴリズムをよく説明しているこのページからの抜粋を次に示します。

問題: サイズが m、n の 2 つの文字列と一連の操作の置換 (R)、挿入 (I)、および削除 (D) がすべて等しいコストで与えられます。ある文字列を別の文字列に変換するために必要な編集 (操作) の最小数を見つけます。

再帰的方法の識別:

この場合、副次的な問題は何になるでしょうか？小さなプレフィックスなど、文字列の一部の編集距離を見つけることを検討してください。ある 1< i < m および 1 < j < n に対して、それらを [1...i] および [1...j] と表しましょう。明らかに、最終問題のより小さなインスタンスを解決しています。これを E(i, j) とします。私たちの目標は、E(m, n) を見つけてコストを最小化することです。

プレフィックスでは、文字列を (i, -)、(-, j)、および (i, j) の 3 つの方法で右揃えできます。文字がないことを表すハイフン記号 (-)。例はそれをより明確にすることができます。

文字列 SUNDAY と SATURDAY を指定します。最小限の編集で SUNDAY を SATURDAY に変換したいと考えています。i = 2 と j = 4 を選択します。つまり、プレフィックス文字列はそれぞれ SUN と SATU です (文字列のインデックスが 1 から始まると仮定します)。右端の文字は、3 つの異なる方法で揃えることができます。

ケース 1: U と U の文字を揃えます。これらは等しく、編集は必要ありません。i = 1 および j = 3、E(i-1, j-1) の問題はまだ残っています。

ケース 2: 最初の文字列の右の文字を揃え、2 番目の文字列の文字を揃えません。ここでは削除 (D) が必要です。i = 1 および j = 4、E(i-1, j) の問題が残っています。

ケース 3: 2 番目の文字列の右の文字を揃え、最初の文字列の文字を揃えません。ここに挿入 (I) が必要です。まだ i = 2 と j = 3、E(i, j-1) の問題が残っています。

によって与えられる i と j で終わるプレフィックス文字列を整列するすべての副問題の最小コストを組み合わせる

E(i, j) = min( [E(i-1, j) + D], [E(i, j-1) + I], [E(i-1, j-1) + R if i ,j 文字は同じではありません] )

まだ完了していません。ベースケースは何ですか？

両方の文字列のサイズが 0 の場合、コストは 0 です。文字列の 1 つだけが 0 の場合、非ゼロの長さの文字列として編集操作が必要です。数学的には、

E(0, 0) = 0、E(i, 0) = i、E(0, j) = j

良い説明のために、この講義を読むことをお勧めします。

この関数match()は、2 つの文字が一致しない場合 (最終的な回答にもう 1 つの手が追加されるため) 1 を返し、それ以外の場合は 0 を返します。

于 2013-10-07T17:11:35.230 に答える
1

これは動的計画法ではなく、再帰的なアルゴリズムです。i と j の両方が、アルゴリズムの開始時にそれぞれ s と t の最後の文字を指すことに注意してください。

indel は 1 を返します。 match(a, b) は、a = b の場合は 0 を返し (一致)、そうでない場合は 1 を返します (置換)

#define MATCH     0       /* enumerated type symbol for match */
#define INSERT    1       /* enumerated type symbol for insert */
#define DELETE    2       /* enumerated type symbol for delete */

int string_compare(char *s, char *t, int i, int j)
{
    int k;                  /* counter */
    int opt[3];             /* cost of the three options */
    int lowest_cost;        /* lowest cost */

    // base case, if i is 0, then we reached start of s and 
    // now it's empty, so there would be j * 1 edit distance between s & t
    // think of it if s is initially empty and t is not, how many
    // edits we need to perform on s to be similar to t? answer is where
    // we are at t right now which is j
    if (i == 0) return(j * indel(' '));
    // same reasoning as above but for s instead of t
    if (j == 0) return(i * indel(' '));

    // calculate opt[match] by checking if s[i] = t[j] which = 0 if true or 1 if not
    // then recursively do the same for s[i-1] & t[j-1]
    opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);
    // calculate opt[insert] which is how many chars we need to insert 
    // in s to make it looks like t, or look at it from the other way,
    // how many chars we need to delete from t to make it similar to s?
    // since we're deleting from t, we decrease j by 1 and leave i (pointer
    // in s) as is + indel(t[j]) which we deleted (always returns 1)
    opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]);
    // same reasoning as before but deleting from s or inserting into t
    opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]);

    // these lines are just to pick the min of opt[match], opt[insert], and
    // opt[delete]
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
            if (opt[k] < lowest_cost) lowest_cost = opt[k];

    return( lowest_cost );
}

アルゴリズムを理解するのは難しくありません。数回読むだけで済みます。いつも私を楽しませてくれるのは、それを発明した人物と、再帰が正しいことをするという信頼です。

于 2016-10-23T18:32:12.963 に答える
1

これは今のところOPの問題ではない可能性がありますが、テキストの理解を書き留めておきます.

/**
 * Returns the cost of a substitution(match) operation
 */
int match(char c, char d)
{
  if (c == d) return 0
  else return 1
}

/**
 * Returns the cost of an insert/delete operation(assumed to be a constant operation)
 */
int indel(char c)
{
  return 1
}

編集距離は、基本的に、特定の文字列を別の参照文字列に変換するために必要な、その文字列の変更の最小数です。ご存知のように、変更は次のようになります。

  1. Substitution (1文字の置換)
  2. 挿入 (文字列に 1 文字を挿入)
  3. 削除（文字列から一文字削除）

今、

文字列の類似性の問題を適切に提起するには、これらの文字列変換操作のそれぞれのコストを設定する必要があります。各操作に等しいコスト 1 を割り当てると、2 つの文字列間の編集距離が定義されます。

したがって、既知の 3 つの変更のそれぞれに一定のコスト O(1) があることがわかります。

しかし、どこを変更すればよいかをどうやって知るのでしょうか?

代わりに、文字列の末尾から 1 文字ずつ、必要な場合と必要でない場合がある変更を探します。そう、

  1. 文字列の末尾から開始して、すべての置換操作をカウントします
  2. 文字列の末尾から開始して、すべての削除操作をカウントします
  3. 文字列の末尾から開始して、すべての挿入操作をカウントします

最後に、このデータを取得したら、上記の 3 つの合計の最小値を返します。

于 2019-08-24T14:08:11.203 に答える