字符串的编辑距离

[likebeta]

定义

两个字符串的相似度可以定义为将一个字符串转换成另一个字符串需要付出的代价。转换可以通过插入，删除和替换三种方式，转换的代价就是编辑的次数，我们称之为字符串的编辑距离。字符串的转换方式不唯一， 可以对应多个编辑方式。

递归方式实现

def edit_distance(src, dest):
    def calc(src, dest, i, j):
        if len(src) == i:
            return len(dest) - j
        if len(dest) == j:
            return len(src) - i
        if src[i] == dest[j]:
            return calc(src, dest, i + 1, j + 1)
        ed_insert = calc(src, dest, i, j + 1) + 1
        ed_delete = calc(src, dest, i + 1, j) + 1
        ed_replace = calc(src, dest, i + 1, j + 1) + 1
        return min(ed_insert, ed_delete, ed_replace)

    return calc(src, dest, 0, 0)

这种递归算法的时间复杂度是3的n次方。当n变大的时候，算法将不可忍受。观察上面的递归会发现有很多的重复计算，下面考虑使用动态规划来改进算法。

带查表的递归方式

首先从状态转换关系开始入手定义阶段和子问题的递推关系。假设source有n个字符，target有m个字符
，如果将问题定义为求解将source的[1...n]个字符转换成target的[1...m]的个字符所需要的最少编辑次数, 则子问题就可以定义为将source的前[1...i]个字符转换成targe的前[1...j]个字符所需要的最少编辑次数，这就是该问题的最优子结构，因此可以用d[i,j]来表示子串之间的编辑距离。

def edit_distance_with_table(src, dest):
    def calc(src, dest, i, j, table):
        if len(src) == i:
            return len(dest) - j
        if len(dest) == j:
            return len(src) - i
        if table[i][j] is not None:
            # record reference statistics
            return table[i][j]
        if src[i] == dest[j]:
            return calc(src, dest, i + 1, j + 1, table)
        ed_insert = calc(src, dest, i, j + 1, table) + 1
        ed_delete = calc(src, dest, i + 1, j, table) + 1
        ed_replace = calc(src, dest, i + 1, j + 1, table) + 1
        table[i][j] = min(ed_insert, ed_delete, ed_replace)
        return table[i][j]

    table = []
    for _ in range(src):
        line = [None] * len(dest)
        table.append(line)
    return calc(src, dest, 0, 0, table)

通过统计发现大量的递归都是在进行查表，通过查表实现了动态规划的剪枝机制。

动态规划

下面可以将上面的算法修改为递推关系方式的动态规划算法。table[i, j]的递推关系可以分两种情况：

• source[i]等于target[j]: table[i, j] = table[i-1, j-1] + 0
• source[i]不等于target[j]: table[i, j] = min(table[i, j-1] + 1, table[j-1, j] + 1, table[i-1, j-1] + 1)

当target为空时， 编辑距离相当于将source中的字符逐个删除; 当source为空时，编辑距离相当于将target中的字符逐个插入。

def edit_distance_with_recursion(src, dest):
    table = []
    for _ in range(len(src) + 1):
        if _ == 0:
            line = range(len(dest) + 1)
        else:
            line = [None] * (len(dest) + 1)
        line[0] = _
        table.append(line)
    for i in range(1, len(src) + 1):
        for j in range(1, len(dest) + 1):
            if src[i - 1] == dest[j - 1]:
                table[i][j] = table[i - 1][j - 1]
            else:
                ed_insert = table[i][j - 1] + 1
                ed_delete = table[i - 1][j] + 1
                ed_replace = table[i - 1][j - 1] + 1
                table[i][j] = min(ed_insert, ed_delete, ed_replace)
    return table[-1][-1]

总结

以上是一个动态规划法应用的实例，从朴素的递归方式开始，通过明确状态定义，逐步过渡到动态规划法实现。虽然动态规划的概念很抽象，但是只要确定了问题的实质，按照动态规划的四个步骤逐步分析，实现动态规划法的算法也不是一件很困难的事情。