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 算法的实现。基本思想是计算“附近”前缀之间的距离，取最小值，然后计算当前字符串对的距离。例如，假设您有两个字符串'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)（在（行，列）中，即行主要符号）开始。在上、左上和左值中，最小值为1。表中对应的字母是不同的——s而且h——所以我们在最小值上加一来得到2，然后继续。

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

让我们继续讨论 at 的值(1, 2)。现在事情有点不同了，因为表中对应的字母是相同的——它们都是i. 这意味着我们可以选择在左上角的单元格中取值而不加一。这里的指导直觉是我们不必增加计数，因为在这个位置将相同的字母添加到两个字符串中。由于两条弦的长度都增加了 1，我们沿对角线移动。

  _ 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如果我们对以and开头的两个较长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)to向右移动(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。（一般情况下，要插入的字母来自输出字符串，而要删除的字母来自输入字符串。）那就是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
    }