最小编辑距离重构

Question

我知道在stack和在线上都有类似的答案，但我觉得我遗漏了一些东西。给定下面的代码，我们需要重建导致最小编辑距离的事件序列。对于下面的代码，我们需要编写一个输出函数：

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 suggests！

大局

在我看来，这是Wagner-Fischer algorithm的一个实现。基本思想是计算“邻近”前缀之间的距离，取最小值，然后计算当前字符串对与之之间的距离。例如，假设有两个字符串'i'和'h'。让我们沿着矩阵的垂直和水平轴排列它们，如下所示：

  _ h
_ 0 1
i 1 1

这里，'_'表示一个空字符串，矩阵中的每个单元格对应一个编辑序列，该编辑序列接受一个输入（''或'i'）到一个输出（''或'h'）。

空字符串到任何长度为L的字符串的距离是L（需要L插入）。任何长度为L的字符串到空字符串的距离也是L（需要删除L）。它包含第一行和第一列中的值，这些值只是递增的。

从那里，您可以计算任意位置的值，方法是从左上、左上和左上的值中取最小值，然后添加一个，或者，如果字符串中该点的字母相同，则不改变左上角的值。对于上表中(1, 1)处的值，最小值是0处的(0, 0)，因此(1, 1)处的值是1，这是从'i'到'h'（一个替换）的最小编辑距离。所以一般来说，最小编辑距离总是在矩阵的右下角。

现在我们再做一个，比较is和hi。这里，矩阵中的每个细胞都对应一个编辑序列，该编辑序列将输入（''，'i'，或'is'）转换为输出（''，'h'，或'hi'）。

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

我们首先放大矩阵，使用#作为我们还不知道的值的占位符，然后通过递增来扩展第一行和第一列。这样，我们就可以开始计算上面标记为#的位置的结果。让我们从(2, 1)（in（row，column）开始，即row major表示法。在上、左上和左上值中，最小值是1。表中对应的字母是不同的——s和h——所以我们在最小值上加一个字母，得到2，然后继续。

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

让我们转到(1, 2)处的值。现在情况有点不同了，因为表中对应的字母是相同的——它们都是i。这意味着我们可以选择在左上角单元格中取值，而无需添加一个。这里的指导直觉是，我们不必增加计数，因为同一个字母被添加到这个位置的两个字符串中。因为两条弦的长度都增加了一个，所以我们是对角移动的。

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

最后一个空牢房，一切恢复正常。对应的字母是s和i，因此我们再次取最小值并加上一个，得到2：

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

如果我们继续这个过程，用is和hi--isnt（忽略标点符号）和hint开头的两个更长的单词，就会得到这个表：

  _ 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，因为这两个字符串的最后两个字母是相同的。方便！

重新创建编辑序列

那么我们如何从这个表中提取编辑类型呢？关键是要认识到表上的移动对应于特定类型的编辑。例如，从(0, 0)向右移动到(0, 1)将我们从_ -> _带到无需编辑，_ -> h，需要一次编辑，一次插入。同样，从(0, 0)到(1, 0)的向下移动将我们从不需要编辑的_ -> _带到i -> _，需要一次编辑，一次删除。最后，从(0, 0)到(1, 1)的对角线移动将我们从不需要编辑的_ -> _移动到i -> h，需要一次编辑，一次替换。

所以现在我们所要做的就是反转我们的步骤，从左上、左上和左上三个单元格中跟踪局部最小值，回到原点(0, 0)，记住如果当前值与最小值相同，那么我们必须转到左上角的单元格，因为这是唯一一种不增加编辑距离的移动。

下面详细描述了您可以采取的步骤。从完成矩阵的右下角开始，重复以下步骤，直到到达左上角：

1. 看看左上角邻近的牢房。如果不存在，则转到步骤3。如果单元格确实存在，请注意存储在其中的值。
2. 左上角单元格中的值是否等于当前单元格中的值？如果是，请执行以下操作：
   • 记录空操作（即Equal）。在这种情况下不需要编辑，因为此位置的字符相同。
   • 更新当前单元格，向上和向左移动。
   • 返回步骤1。
3. 这里有很多分支：
   • 如果左边没有单元格，上面也没有单元格，那么你就在左上角，算法已经完成了。
   • 如果左侧没有单元格，请转到步骤4。（这将继续循环，直到到达左上角。）
   • 如果上面没有单元格，请转到步骤5。（这将继续循环，直到到达左上角。）
   • 否则，请在左侧单元格、左上方单元格和上方单元格之间进行三种方式的比较。选择值最小的那个。如果有多个候选者，您可以随机选择一个；它们在这个阶段都是有效的。（它们对应于具有相同总编辑距离的不同编辑路径。）
     • 如果您选择了上面的单元格，请转到步骤4。
     • 如果你选择左边的单元格，请转到步骤5。
     • 如果选择左上角的单元格，请转到步骤6。
4. 你在向上移动。执行以下操作：
   • 在当前单元格中记录输入字符的删除。
   • 更新当前单元格，向上移动。
   • 返回步骤1。
5. 你在向左移动。执行以下操作：
   • 在当前单元格中记录输出字符的插入。
   • 更新当前单元格，向左移动。
   • 返回步骤1。
6. 你在斜向移动。执行以下操作：
   • 记录当前单元格中输入字符替换为当前单元格中输出字符的情况。
   • 更新当前单元格，向上和向左移动。
   • 返回步骤1。

组合起来

在上面的示例中，有两种可能的路径：

(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。（通常，要插入的字母来自输出字符串，而要删除的字母来自In把字符串放进去。）这就是Delete, s。然后两个对角线移动值不变：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, ('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
    }