最小编辑距离重构

Question

最小编辑距离重构

11

我知道在stackoverflow和网上都有类似的答案，但我感觉缺少了些什么。给定下面的代码，我们需要重构导致结果最小编辑距离的事件序列。对于下面的代码，我们需要编写一个输出函数：

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')

- Adam_G

3个回答

11

我建议您看一下python-Levenshtein模块。可能会对您有所帮助：

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

你可以根据编辑操作的输出来生成详细的指令。

- MattH

2

我不知道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
    }

- Ohad Schneider

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- senderle · Accepted Answer

在这种情况下，我认为更深入地了解算法很重要。与其给你一些伪代码，不如让我带你走一遍算法的基本步骤，并向你展示所需数据在最终矩阵中是如何"编码"的。当然，如果你不需要自己编写算法，那么你显然应该使用别人的，就像MattH建议的那样！

大局观

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

  _ h
_ 0 1
i 1 1

在这里，'_'表示空字符串，矩阵中的每个单元格对应于将输入(''或'i')转换为输出(''或'h')的编辑序列。从空字符串到长度为L的任何字符串的距离为L(需要L个插入)。从长度为L的任何字符串到空字符串的距离也是L(需要L个删除)。这涵盖了第一行和第一列中的值，它们只是简单地递增。从那里开始，您可以通过从上方、左方和左上方的值中取最小值并加1来计算任何位置的值，或者如果该字母在字符串中的那个点相同，则不改变左上角的值。对于上面表格中(1,1)处的值，最小值是(0,0)处的0，因此(1,1)处的值为1，这是从'i'到'h'的最小编辑距离(一个替换)。因此，通常情况下，最小编辑距离始终在矩阵的右下角。

现在我们再来比较一下is和hi，同样地，矩阵中的每个单元格对应一个编辑序列，将输入('', 'i', 或 'is')转换为输出('', 'h', 或 'hi')。请保留HTML标签。

  _ 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 #

让我们来看一下在(1, 2)处的值。现在情况有些不同，因为表格中对应的字母是相同的--它们都是i。这意味着我们可以选择取上方左侧单元格中的值而不添加一个。指导思想是，我们不必增加计数，因为相同的字母被添加到了这个位置的两个字符串中。由于两个字符串的长度都增加了一，所以我们向对角线移动。

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

随着最后一个空单元格的出现，一切都恢复正常。相应的字母是和，所以我们再次取最小值并加上1，得到<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)，请记住，如果当前值与最小值相同，则必须转到左上角单元格，因为这是唯一不增加编辑距离的移动方式。
以下是您可以采取的详细步骤。从完成矩阵的右下角开始，重复以下步骤，直到达到左上角：

查看左上方的相邻单元格。如果不存在，请执行第3步。如果存在单元格，则记录存储在其中的值。

上述单元格中的值是否等于当前单元格中的值？如果是，则执行以下操作：

记录一个空操作（即Equal）。在此情况下，不需要编辑，因为此位置上的字符相同。

更新当前单元格，向上和向左移动。

返回第1步。

这里有许多分支：

如果左侧和上方都没有单元格，则您位于左上角，并且算法已完成。

如果左侧没有单元格，请转到第4步。（这将一直循环，直到达到左上角。）

如果上方没有单元格，请转到第5步。（这将一直循环，直到达到左上角。）

否则，请在左侧单元格、左上方单元格和上方单元格之间进行三路比较。选择具有最小值的单元格。如果有多个候选项，则可以随机选择一个；它们在此阶段都是有效的。（它们对应于具有相同总编辑距离的不同编辑路径。）

如果选择了上方单元格，请转到第4步。

如果选择了左侧单元格，请转到第5步。

如果选择了左上方单元格，请转到第6步。

您正在向上移动。执行以下操作：

记录当前单元格中输入字符的删除。

更新当前单元格，向上移动。

返回第1步。

您正在向左移动。执行以下操作：

记录输出字符在当前单元格中的插入。

更新当前单元格，向左移动。

返回第1步。

您正在对角线移动。执行以下操作：

记录当前单元格中输入字符替换为输出字符的替换。

更新当前单元格，向上和向左移动。

返回第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。

我会把第二个最小路径留作练习。请记住，这两条路径完全等效；它们可能不同，但会得到相同的最小编辑距离，因此可以完全互换。当您通过矩阵向后工作时，如果看到两个不同的可能局部最小值，则可以选择任何一个，并且最终结果保证是正确的。

一旦您理解了所有这些，编码就不难了。在这种情况下，关键是先深入理解算法。一旦做到了这一点，编码就轻而易举了。

累积 vs. 重建
作为最后的说明，你可能会选择在填充矩阵时累积编辑。在这种情况下，您的矩阵中的每个单元格都可以是一个元组：(2, ('ins'，'eq'，'del'，'eq'，'eq'))。您将增加长度，并附加对应于从最小先前状态移动的操作。这样做可以消除回溯，从而减少代码的复杂性；但它占用额外的内存。如果您这样做，最终的编辑序列将出现在矩阵的右下角，同时显示最终的编辑距离。