3

ダメラウ・レーベンシュタイン距離アルゴリズムのこの実装で、削除のカウントを無効にするにはどうすればよいですか、または他のアルゴリズムがすでに実装されている場合は、それを指摘してください。

例（削除カウントの無効化）：

string1：お元気ですか？

string2：どのようにoyu？

距離： 1（転置の場合、4回の削除はカウントされません）

そして、ここにアルゴリズムがあります：

    public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
    {
        // Return trivial case - where they are equal
        if (string1.Equals(string2))
            return 0;

        // Return trivial case - where one is empty
        if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2))
            return (string1 ?? "").Length + (string2 ?? "").Length;


        // Ensure string2 (inner cycle) is longer_transpositionRow
        if (string1.Length > string2.Length)
        {
            var tmp = string1;
            string1 = string2;
            string2 = tmp;
        }

        // Return trivial case - where string1 is contained within string2
        if (string2.Contains(string1))
            return string2.Length - string1.Length;

        var length1 = string1.Length;
        var length2 = string2.Length;

        var d = new int[length1 + 1, length2 + 1];

        for (var i = 0; i <= d.GetUpperBound(0); i++)
            d[i, 0] = i;

        for (var i = 0; i <= d.GetUpperBound(1); i++)
            d[0, i] = i;

        for (var i = 1; i <= d.GetUpperBound(0); i++)
        {
            var im1 = i - 1;
            var im2 = i - 2;
            var minDistance = threshold;
            for (var j = 1; j <= d.GetUpperBound(1); j++)
            {
                var jm1 = j - 1;
                var jm2 = j - 2;
                var cost = string1[im1] == string2[jm1] ? 0 : 1;

                var del = d[im1, j] + 1;
                var ins = d[i, jm1] + 1;
                var sub = d[im1, jm1] + cost;

                //Math.Min is slower than native code
                //d[i, j] = Math.Min(del, Math.Min(ins, sub));
                d[i, j] = del <= ins && del <= sub ? del : ins <= sub ? ins : sub;

                if (i > 1 && j > 1 && string1[im1] == string2[jm2] && string1[im2] == string2[jm1])
                    d[i, j] = Math.Min(d[i, j], d[im2, jm2] + cost);

                if (d[i, j] < minDistance)
                    minDistance = d[i, j];
            }

            if (minDistance > threshold)
                return int.MaxValue;
        }

        return d[d.GetUpperBound(0), d.GetUpperBound(1)] > threshold
            ? int.MaxValue
            : d[d.GetUpperBound(0), d.GetUpperBound(1)];
    }
4

3 に答える 3

6 
 public static int DamerauLevenshteinDistance( string string1
                                            , string string2
                                            , int threshold)
{
    // Return trivial case - where they are equal
    if (string1.Equals(string2))
        return 0;

    // Return trivial case - where one is empty
    // WRONG FOR YOUR NEEDS: 
    // if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2))
    //      return (string1 ?? "").Length + (string2 ?? "").Length;

    //DO IT THIS WAY:
    if (String.IsNullOrEmpty(string1))
        // First string is empty, so every character of 
        // String2 has been inserted:
        return (string2 ?? "").Length;
    if (String.IsNullOrEmpty(string2))
        // Second string is empty, so every character of string1 
        // has been deleted, but you dont count deletions:
        return 0;

    // DO NOT SWAP THE STRINGS IF YOU WANT TO DEAL WITH INSERTIONS
    // IN A DIFFERENT MANNER THEN WITH DELETIONS:
    // THE FOLLOWING IS WRONG FOR YOUR NEEDS:
    // // Ensure string2 (inner cycle) is longer_transpositionRow
    // if (string1.Length > string2.Length)
    // {
    //     var tmp = string1;
    //     string1 = string2;
    //     string2 = tmp;
    // }

    // Return trivial case - where string1 is contained within string2
    if (string2.Contains(string1))
        //all changes are insertions
        return string2.Length - string1.Length;

    // REVERSE CASE: STRING2 IS CONTAINED WITHIN STRING1
    if (string1.Contains(string2))
        //all changes are deletions which you don't count:
        return 0;

    var length1 = string1.Length;
    var length2 = string2.Length;


    // PAY ATTENTION TO THIS CHANGE!
    // length1+1 rows is way too much! You need only 3 rows (0, 1 and 2)
    // read my explanation below the code!
    // TOO MUCH ROWS: var d = new int[length1 + 1, length2 + 1];
    var d = new int[2, length2 + 1];

    // THIS INITIALIZATION COUNTS DELETIONS. YOU DONT WANT IT
    // or (var i = 0; i <= d.GetUpperBound(0); i++)
    //    d[i, 0] = i;

    // But you must initiate the first element of each row with 0:
    for (var i = 0; i <= 2; i++)
        d[i, 0] = 0;


    // This initialization counts insertions. You need it, but for
    // better consistency of code I call the variable j (not i):
    for (var j = 0; j <= d.GetUpperBound(1); j++)
        d[0, j] = j;


    // Now do the job:
    // for (var i = 1; i <= d.GetUpperBound(0); i++)
    for (var i = 1; i <= length1; i++)
    {
        //Here in this for-loop: add "%3" to evey term 
        // that is used as first index of d!

        var im1 = i - 1;
        var im2 = i - 2;
        var minDistance = threshold;
        for (var j = 1; j <= d.GetUpperBound(1); j++)
        {
            var jm1 = j - 1;
            var jm2 = j - 2;
            var cost = string1[im1] == string2[jm1] ? 0 : 1;

            // DON'T COUNT DELETIONS!  var del = d[im1, j] + 1;
            var ins = d[i % 3, jm1] + 1;
            var sub = d[im1 % 3, jm1] + cost;

            // Math.Min is slower than native code
            // d[i, j] = Math.Min(del, Math.Min(ins, sub));
            // DEL DOES NOT EXIST  
            // d[i, j] = del <= ins && del <= sub ? del : ins <= sub ? ins : sub;
            d[i % 3, j] = ins <= sub ? ins : sub;

            if (i > 1 && j > 1 && string1[im1] == string2[jm2] && string1[im2] == string2[jm1])
                d[i % 3, j] = Math.Min(d[i % 3, j], d[im2 % 3, jm2] + cost);

            if (d[i % 3, j] < minDistance)
                minDistance = d[i % 3, j];
        }

        if (minDistance > threshold)
            return int.MaxValue;
    }

    return d[length1 % 3, d.GetUpperBound(1)] > threshold
        ? int.MaxValue
        : d[length1 % 3, d.GetUpperBound(1)];
}

3行だけが必要な理由を説明します。

この行を見てください：

var d = new int[length1 + 1, length2 + 1];

一方の文字列の長さがnで、もう一方の文字列の長さがmの場合、コードには（n + 1）*（m + 1）整数のスペースが必要です。各整数には4バイトが必要です。文字列が長い場合、これはメモリの浪費です。両方の文字列の長さが35.000バイトの場合、4GBを超えるメモリが必要になります。

このコードでは、の新しい値を計算して書き込みますd[i,j]。d[i,jm1]これを行うには、上部の隣人（ ）、左の隣人（d[im1,j]）、左上の隣人（d[im1,jm1]）、最後に二重上部の二重左の隣人（ ）から値を読み取りますd[im2,jm2]。したがって、実際の行と2行前の値が必要です。

他の行の値は必要ありません。では、なぜそれらを保存したいのですか？3行で十分ですが、私の変更により、いつでも間違った値を読み取ることなく、この3行で作業できることがわかります。

于 2012-08-23T08:48:07.323 に答える
2

「無料」編集の特定のケースを処理するために、この特定のアルゴリズムを書き直さないことをお勧めします。それらの多くは、問題の概念を根本的に単純化して、メトリックが有用な情報を伝えないようにします。

たとえば、置換が自由な場合、すべての文字列間の距離はそれらの長さの差になります。小さい方の文字列を大きい方の文字列のプレフィックスに変換し、必要な文字を追加するだけです。（編集距離の文字ごとに1つの挿入が必要なため、距離が短くならないことを保証できます。）

転置が無料の場合、質問は文字数の差の合計を決定することになります。（すべてのアナグラム間の距離が0であるため、各文字列の文字を並べ替え、大きい方の文字列の一般的でない要素を交換または削除するのが最善の戦略です。数学的な引数は前の例と同様です。）

挿入と削除が自由な場合、任意の2つの文字列間の編集距離はゼロです。挿入または削除のみが自由である場合、これは距離メトリックの対称性を破ります-自由な削除では、aからaaまでの距離は1ですが、aaからaまでの距離は1です。アプリケーションによっては、これが望ましい場合があります。しかし、それがあなたが興味を持っているものであるかどうかはわかりません。提示されたアルゴリズムを大幅に変更する必要があります。これは、前述の1つの文字列の仮定が常に他の文字列よりも長いためです。

于 2012-08-21T20:09:49.267 に答える
0

に変更var del = d[im1, j] + 1;してみてくださいvar del = d[im1, j];、それはあなたの問題を解決すると思います。

于 2012-08-20T10:37:06.413 に答える