python - 最小編集距離の再構成

Question

オンラインだけでなく、スタックにも同様の答えがあることは知っていますが、何かが足りないと感じています。以下のコードを考えると、結果として生じる最小編集距離につながるイベントのシーケンスを再構築する必要があります。以下のコードでは、以下を出力する関数を作成する必要があります。

Equal, L, L
Delete, E
Equal, A, A
Substitute, D, S
Insert, T

編集：コードは私の（部分的に正しい）ソリューションで更新されます

これが私の部分的な解決策を含むコードです。たとえば、私が与えられた例（ "lead"-> "last"）では機能しますが、以下の例（ "hint"-> "isnt"）では機能しません。これは、最初の文字が等しいためだと思います。これにより、コードがスローされます。正しい方向へのヒントや指針は素晴らしいでしょう！

def printMatrix(M):
        for row in M:
                print row
        print

def med(s, t):  
        k = len(s) + 1
        l = len(t) + 1

        M = [[0 for i in range(k)] for j in range(l)]
        MTrace = [["" for i in range(k)] for j in range(l)]

        M[0][0] = 0


        for i in xrange(0, k):
                M[i][0] = i
                MTrace[i][0] = s[i-1]

        for j in xrange(0, l):
                M[0][j] = j
                MTrace[0][j] = t[j-1]

        MTrace[0][0] = "DONE"

        for i in xrange(1, k):
                for j in xrange(1, l):

                        sub = 1
                        sub_op = "sub"
                        if s[i-1] == t[j-1]:
                                # equality
                                sub = 0
                                sub_op = "eq"


                        # deletion
                        min_value = M[i-1][j] + 1
                        op = "del"
                        if min_value > M[i][j-1] + 1:
                                # insertion
                                min_value = M[i][j-1] + 1
                                op = "ins"
                        if min_value > M[i-1][j-1] + sub:
                                # substitution
                                min_value = M[i-1][j-1] + sub
                                op = sub_op


                        M[i][j] = min_value
                        MTrace[i][j] = op                        

        print "final Matrix"
        printMatrix(M)
        printMatrix(MTrace)

############ MY PARTIAL SOLUTION

        def array_append(array,x,y):
            ops_string = MTrace[x][y]
            if ops_string == 'ins':
                array.append(("Insert",MTrace[0][y]))
            elif ops_string == 'sub':
                array.append(("Substitute",MTrace[x][0],MTrace[0][y]))
            elif ops_string == 'eq':
                array.append(("Equal",MTrace[x][0],MTrace[0][y]))
            elif ops_string == 'del':
                array.append(("Delete",MTrace[x][0]))


        i = len(s)
        j = len(t)

        ops_array = []
        base = M[i][j]
        array_append(ops_array,i,j)


        while MTrace[i][j] != "DONE":
            base = M[i][j]
            local_min = min(M[i][j-1],M[i-1][j],M[i-1][j-1])
            if base == local_min:
                i = i - 1
                j = j - 1
                array_append(ops_array,i,j)
            elif M[i][j-1] < M[i-1][j]:
                j = j -1
                array_append(ops_array,i,j)
            elif M[i-1][j] < M[i][j-1]:
                i = i - 1
                array_append(ops_array,i,j)
            else:
                i = i - 1
                j = j - 1
                array_append(ops_array,i,j)

        print ops_array
#########

        return M[k-1][l-1]      

print med('lead', 'last')

Answer 1

この場合、アルゴリズムをより深く理解することが重要であると私は考えています。いくつかの擬似コードを提供するのではなく、アルゴリズムの基本的な手順を説明し、必要なデータが結果の最終的なマトリックスにどのように「エンコード」されるかを示します。もちろん、独自のアルゴリズムを実行する必要がない場合は、MattHが提案しているように、明らかに他の誰かのアルゴリズムを使用する必要があります。

大きな絵

これは、 Wagner-Fischerアルゴリズムの実装のように見えます。基本的な考え方は、「近くの」プレフィックス間の距離を計算し、最小値を取り、そこから現在の文字列のペアの距離を計算することです。たとえば、2つの文字列'i'と。があるとし'h'ます。次のように、マトリックスの垂直軸と水平軸に沿って配置してみましょう。

  _ h
_ 0 1
i 1 1

ここで、'_'は空の文字列を示し、マトリックス内の各セルは、入力（''または'i'）を出力（''または）に受け取る編集シーケンスに対応し'h'ます。

空の文字列から長さLの任意の文字列までの距離はLです（Lの挿入が必要です）。長さLの任意の文字列から空の文字列までの距離もLです（L個の削除が必要です）。これは、単純に増分する最初の行と列の値をカバーします。

そこから、左上、左上、左上の値の中から最小値を取り、1を加算するか、文字列のそのポイントで文字が同じ場合は上値をとることで、任意の場所の値を計算できます。 -値は変更されません。(1, 1)上記の表のatの値の場合、最小値は0at(0, 0)であるため、atの値(1, 1)はであり、これがto1からの最小編集距離です（1回の置換）。したがって、一般的に、最小編集距離は常にマトリックスの右下隅にあります。'i''h'

次に、と比較して別のことを行いましょisうhi。ここでも、マトリックス内の各セルは、入力（、、、または）を出力（、、、または）に受け取る編集シーケンスに''対応'i'し'is'て''い'h'ます'hi'。

  _ h i
_ 0 1 2
i 1 1 #
s 2 # #

まず、マトリックスを拡大し、#まだわからない値のプレースホルダーとして使用し、最初の行と列をインクリメントして拡張します。そうしたら、上記の位置の結果の計算を開始できます#。(2, 1)（（行、列）、つまり行メジャー表記）から始めましょう。左上、左上、左の値のうち、最小値は1です。表内の対応する文字は-sとh-で異なるため、その最小値に1を追加して、を取得2し、続行します。

  _ h i
_ 0 1 2
i 1 1 #
s 2 2 #

の値に移りましょう(1, 2)。表の対応する文字が同じであるため、状況は少し異なります。両方ともiです。これは、 1つ追加せずに左上のセルの値を取得するオプションがあることを意味します。ここでの指針となる直感は、この位置で両方の文字列に同じ文字が追加されているため、カウントを増やす必要がないということです。そして、両方の弦の長さが1つ増えたので、斜めに移動します。

  _ h i
_ 0 1 2
i 1 1 1
s 2 2 #

最後の空のセルで、物事は通常に戻ります。対応する文字はとであるsためi、ここでも最小値を取得して1を加算し、次のようにします2。

  _ h i
_ 0 1 2
i 1 1 1
s 2 2 2

これは、 and- （句読点を無視）とis：で始まる2つの長い単語に対してこのプロセスを続行した場合に得られる表です。hiisnthint

  _ h i n t
_ 0 1 2 3 4
i 1 1 1 2 3
s 2 2 2 2 3
n 3 3 3 2 3
t 4 4 4 3 2

このマトリックスは少し複雑ですが、2これら2つの文字列の最後の2文字が同じであるため、ここでの最終的な最小編集距離はまだです。便利！

編集シーケンスの再作成

では、このテーブルから編集の種類をどのように抽出できますか？重要なのは、テーブル上の動きが特定の種類の編集に対応していることを理解することです。したがって、たとえば、からへの右方向への移動は、(0, 0)編集を必要としないから、1回の編集を必要とする、挿入へと(0, 1)私たちを連れて行きます。同様に、からへの下方への移動は、編集を必要としないから、1回の編集を必要とする、削除へと私たちを連れて行きます。そして最後に、からへの斜めの動きは、編集を必要としないから、1回の編集、置換を必要とするへと私たちを連れて行きます。_ -> __ -> h(0, 0)(1, 0)_ -> _i -> _(0, 0)(1, 1)_ -> _i -> h

したがって、今やらなければならないのは、ステップを逆にして、左上、左上、左上のセルの中から極小値を原点までさかのぼってトレースする(0, 0)ことです。現在の値が最小値と同じである場合は、編集距離を増加させない唯一の種類の動きであるため、左上のセルに移動する必要があります。

これを行うために実行できる手順の詳細な説明は次のとおりです。完成したマトリックスの右下隅から始めて、左上隅に到達するまで次の手順を繰り返します。

1. 左上の隣接するセルを見てください。存在しない場合は、手順3に進みます。セルが存在する場合は、そこに格納されている値をメモします。
2. 左上のセルの値は現在のセルの値と同じですか？その場合は、次のようにします。
   • 空の操作を記録します（つまりEqual）。この場合、この場所の文字は同じであるため、編集は必要ありませんでした。
   • 現在のセルを更新し、上下に移動します。
   • 手順1に戻ります。
3. ここには多くのブランチがあります：
   • 左側にセルがなく、上部にセルがない場合は、左上隅にいて、アルゴリズムが完了しています。
   • 左側にセルがない場合は、手順4に進みます（左上隅に到達するまでループが続きます）。
   • 上にセルがない場合は、手順5に進みます（左上隅に到達するまでループが続きます）。
   • それ以外の場合は、左側のセル、左上のセル、および上のセルを3者間で比較します。値が最も小さいものを選択してください。複数の候補者がいる場合は、ランダムに1つ選ぶことができます。これらはすべてこの段階で有効です。（これらは、同じ合計編集距離を持つ異なる編集パスに対応します。）
     • 上記のセルを選択した場合は、手順4に進みます。
     • 左側のセルを選択した場合は、手順5に進みます。
     • 左上のセルを選択した場合は、手順6に進みます。
4. あなたは上に移動しています。以下をせよ：
   • 現在のセルで入力文字の削除を記録します。
   • 現在のセルを更新し、上に移動します。
   • 手順1に戻ります。
5. あなたは左に動いています。以下をせよ：
   • 現在のセルでの出力文字の挿入を記録します。
   • 左に移動して、現在のセルを更新します。
   • 手順1に戻ります。
6. あなたは斜めに動いています。以下をせよ：
   • 現在のセルの出力文字の代わりに、現在のセルの入力文字の置換を記録します。
   • 現在のセルを更新し、上下に移動します。
   • 手順1に戻ります。

それを一緒に入れて

上記の例では、2つの可能なパスがあります。

(4, 4) -> (3, 3) -> (2, 2) -> (1, 2) -> (0, 1) -> (0, 0)

と

(4, 4) -> (3, 3) -> (2, 2) -> (1, 1) -> (0, 0)

それらを逆にすると、

(0, 0) -> (0, 1) -> (1, 2) -> (2, 2) -> (3, 3) -> (4, 4)

と

(0, 0) -> (1, 1) -> (2, 2) -> (3, 3) -> (4, 4)

したがって、最初のバージョンの場合、最初の操作は右への移動、つまり挿入です。hに移動しているので、isnt挿入された文字はですhint。（これInsert, hは、詳細な出力に対応します。）次の操作は、対角線の動き、つまり、置換または操作なしのいずれかです。この場合、編集距離は両方の場所で同じであるため（つまり、文字が同じであるため）、操作はできません。だからEqual, i, i。次に、削除に対応する下向きの動き。削除された文字はs、です。ここでも、からisntに移動していhintます。（一般に、挿入する文字は出力文字列から取得され、削除する文字は入力文字列から取得されます。）つまり、Delete, sです。次に、値を変更せずに2つの斜めの動き：Equal, n, nおよびEqual, t, t。

結果：

Insert, h
Equal, i, i
Delete, s
Equal, n, n
Equal, t, t

これらの手順を実行するisnt：

isnt   (No change)
hisnt  (Insertion)
hisnt  (No change)
hint   (Deletion)
hint   (No change)
hint   (No change)

合計編集距離が2の場合。

演習として2番目の最小経路を残します。両方のパスが完全に同等であることに注意してください。それらは異なる場合がありますが、同じ最小編集距離2になるため、完全に交換可能です。行列を逆方向に作業するときはいつでも、2つの異なる可能な極小値が表示された場合、どちらか1つを取ることができ、最終結果は正しいことが保証されます。

これらすべてを理解したら、コーディングするのは難しいことではありません。このような場合の鍵は、最初にアルゴリズムを深く理解することです。それが済んだら、それをコーディングするのは簡単です。

蓄積と再構築

最後に、マトリックスにデータを入力するときに編集内容を蓄積することを選択する場合があります。その場合、マトリックス内の各セルはタプルになる可能性があります(2, ('ins', 'eq', 'del', 'eq', 'eq'))。長さをインクリメントし、最小の前の状態からの移動に対応する操作を追加します。これにより、バックトラックがなくなり、コードの複雑さが軽減されます。しかし、それは余分なメモリを消費します。これを行うと、最終的な編集シーケンスが、マトリックスの右下隅に最終的な編集距離とともに表示されます。

Answer 2

python-Levenshteinモジュールをご覧になることをお勧めします。おそらくそこにあなたを長い道のりに連れて行くでしょう：

>>> import Levenshtein
>>> Levenshtein.editops('LEAD','LAST')
[('replace', 1, 1), ('replace', 2, 2), ('replace', 3, 3)]

編集操作からの出力を処理して、詳細な指示を作成できます。

Answer 3

私はPythonを知りませんが、それが助けになれば、次のC＃コードが機能します。

public class EditDistanceCalculator
{
    public double SubstitutionCost { get; private set; }
    public double DeletionCost { get; private set; }
    public double InsertionCost { get; private set; }

    public EditDistanceCalculator() : this(1,1, 1)
    {
    }

    public EditDistanceCalculator(double substitutionCost, double insertionCost, double deletionCost)
    {
        InsertionCost = insertionCost;
        DeletionCost = deletionCost;
        SubstitutionCost = substitutionCost;
    }

    public Move[] CalcEditDistance(string s, string t)
    {
        if (s == null) throw new ArgumentNullException("s");
        if (t == null) throw new ArgumentNullException("t");

        var distances = new Cell[s.Length + 1, t.Length + 1];
        for (int i = 0; i <= s.Length; i++)
            distances[i, 0] = new Cell(i, Move.Delete);
        for (int j = 0; j <= t.Length; j++)
            distances[0, j] = new Cell(j, Move.Insert);

        for (int i = 1; i <= s.Length; i++)
            for (int j = 1; j <= t.Length; j++)
                distances[i, j] = CalcEditDistance(distances, s, t, i, j);

        return GetEdit(distances, s.Length, t.Length);
    }

    private Cell CalcEditDistance(Cell[,] distances, string s, string t, int i, int j)
    {
        var cell = s[i - 1] == t[j - 1]
                            ? new Cell(distances[i - 1, j - 1].Cost, Move.Match)
                            : new Cell(SubstitutionCost + distances[i - 1, j - 1].Cost, Move.Substitute);
        double deletionCost = DeletionCost + distances[i - 1, j].Cost;
        if (deletionCost < cell.Cost)
            cell = new Cell(deletionCost, Move.Delete);

        double insertionCost = InsertionCost + distances[i, j - 1].Cost;
        if (insertionCost < cell.Cost)
            cell = new Cell(insertionCost, Move.Insert);

        return cell;
    }

    private static Move[] GetEdit(Cell[,] distances, int i, int j)
    {
        var moves = new Stack<Move>();
        while (i > 0 && j > 0)
        {
            var move = distances[i, j].Move;
            moves.Push(move);
            switch (move)
            {
                case Move.Match:
                case Move.Substitute:
                    i--;
                    j--;
                    break;
                case Move.Insert:
                    j--;
                    break;
                case Move.Delete:
                    i--;
                    break;
                default:
                    throw new ArgumentOutOfRangeException();
            }
        }
        for (int k = 0; k < i; k++)
            moves.Push(Move.Delete);
        for (int k = 0; k < j; k++)
            moves.Push(Move.Insert);

        return moves.ToArray();
    }

    class Cell
    {
        public double Cost { get; private set; }
        public Move Move { get; private set; }

        public Cell(double cost, Move move)
        {
            Cost = cost;
            Move = move;
        }
    }
}

public enum Move
{
    Match,
    Substitute,
    Insert,
    Delete
}

いくつかのテスト：

    [TestMethod]
    public void TestEditDistance()
    {
        var expected = new[]
            {
                Move.Delete, 
                Move.Substitute, 
                Move.Match, 
                Move.Match, 
                Move.Match, 
                Move.Match, 
                Move.Match, 
                Move.Insert,
                Move.Substitute, 
                Move.Match, 
                Move.Substitute, 
                Move.Match, 
                Move.Match, 
                Move.Match, 
                Move.Match
            };
        Assert.IsTrue(expected.SequenceEqual(new EditDistanceCalculator().CalcEditDistance("thou-shalt-not", "you-should-not")));

        var calc = new EditDistanceCalculator(3, 1, 1);
        var edit = calc.CalcEditDistance("democrat", "republican");
        Console.WriteLine(string.Join(",", edit));
        Assert.AreEqual(3, edit.Count(m => m == Move.Match)); //eca
    }