about 1 results (0.02 seconds)

面试题:编辑距离(Edit distance)

by LauCyun Jul 7,2017 15:58:17 15,765 views

问题描述:

给定 2 个字符串 a, b,编辑距离是将 a 转换为 b 的最少操作次数,操作只允许如下 3 种:

  1. 插入一个字符,例如:\(fj \to fxj\)
  2. 删除一个字符,例如:\(fxj \to fj\)
  3. 替换一个字符,例如:\(jxj \to fyj\)

 

解题思路:

用分治的思想解决比较简单,将复杂的问题分解成相似的子问题

假设:字符串 a,共 m 位,从 a[1] 到 a[m];字符串 b, 共 n 位,从 b[1] 到 b[n],d[i][j] 表示字符串 a[1]-a[i] 转换为 b[1]-b[i] 的编辑距离

那么有如下递归规律(a[i] 和 b[j] 分别是字符串 a 和 b 的最后一位):

  1. 当 a[i] 等于 b[j] 时,d[i][j] = d[i-1][j-1],\(fxy\to fay\) 的编辑距离等于 \(fx\to fa\) 的编辑距离
  2. 当 a[i] 不等于 b[j] 时,d[i][j] 等于如下 3 项的最小值:
    • d[i-1][j] + 1(删除 a[i]),如\(fxy \to fab \)的编辑距离 = \(fx \to fab \)的编辑距离 + 1
    • d[i][j-1] + 1(插入 b[j]),如\(fxy\to fab \)的编辑距离 = \(fxyb{\to} fab \)的编辑距离 + 1 = \( fxy \to fa \)的编辑距离 + 1
    • d[i-1][j-1] + 1(将 a[i] 替换为 b[j]),如\(fxy\to fab \)的编辑距离 = \(fxb \to fab \)的编辑距离 + 1 = \(fx \to fa\) 的编辑距离 + 1

递归边界:

  1. a[i][0] = i,b 字符串为空,表示将 a[1]-a[i] 全部删除,所以编辑距离为 i
  2. a[0][j] = j,a 字符串为空,表示 a 插入 b[1]-b[j],所以编辑距离为 j

 

代码示例:

#!/usr/bin/env python
# -*- coding: utf-8 -*-


"""
给定 2 个字符串 a, b,编辑距离是将 a 转换为 b 的最少操作次数,操作只允许如下 3 种:
    1. 插入一个字符,例如:fj -> fxj
    2. 删除一个字符,例如:fxj -> fj
    3. 替换一个字符,例如:jxj -> fyj
"""


def edit_distance(a, b, i, j):
    if i == 0:
        return j
    elif j == 0:
        return i
    elif a[i - 1] == b[j - 1]:
        return edit_distance(a, b, i - 1, j - 1)
    else:
        return min(
            edit_distance(a, b, i - 1, j) + 1,
            edit_distance(a, b, i, j - 1) + 1,
            edit_distance(a, b, i - 1, j - 1) + 1
        )


stra = "fxy"
strb = "fab"
print(edit_distance(stra, strb, len(stra), len(strb)))

输出:

2

但是有个严重的问题,就是代码的性能很低,时间复杂度是指数增长的。

上面的代码中,很多相同的子问题其实是经过了多次求解,解决这类问题的办法是用动态规划。

 

用动态规划思想优化时间复杂度

像以上解决思路,是从后往前算的,比如我想知道 edit_distance(a, b, i, j) 我可能需要知道 edit_distance(a, b, i - 1, j - 1)

有一种想法不错,就是从前往后算,先算出各个子问题,然后根据子问题,计算出原问题, 对于这个问题性能不错,而且也挺容易理解,下面就来说一说

例如以字符串 a = "fxy", b = "fab" 为例

  1. 首先建立一个矩阵,用来存放子问题及原问题的编辑距离,并将递归边界在矩阵中填好,如下:

  2. 然后计算 i = 1, j = 1 所对应的编辑距离:比较 a[i] 和 b[j] 是否相等然后根据递归规律算出这个值
    比如在这种情况下 a[i] = f 和 b[j] = f, 那么 d[i][j] 就等于 d[i-1][j-1] 等于 0
    然后计算 i = 1, j = 2 直到算出 i = 3, j = 3, 原问题的编辑距离就等于 d[3][3]
    最终矩阵如下:

现在的时间复杂度已到了可接受范围,为 O(mn)。

代码示例:

#!/usr/bin/env python
# -*- coding: utf-8 -*-


"""
给定 2 个字符串 a, b,编辑距离是将 a 转换为 b 的最少操作次数,操作只允许如下 3 种:
    1. 插入一个字符,例如:fj -> fxj
    2. 删除一个字符,例如:fxj -> fj
    3. 替换一个字符,例如:jxj -> fyj
"""


def edit_distance1(a, b):
    lena = len(a)
    lenb = len(b)
    d = [[0 for i in range(lenb + 1)] for j in range(lena + 1)]

    for i in range(lena + 1):
        d[i][0] = i
    for j in range(lenb + 1):
        d[0][j] = j

    for i in range(1, lena + 1):
        for j in range(1, lenb + 1):
            if a[i - 1] == b[j - 1]:
                d[i][j] = d[i - 1][j - 1]
            else:
                d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + 1)
    # print(d)
    return d[lena][lenb]


stra = "fxy"
strb = "fab"
print(edit_distance1(stra, strb))

这个算法的空间复杂度为 O(mn),当一步步填写矩阵的过程中,应该能够感受到, 空间复杂度可以继续优化,因为计算矩阵的时候总是需要有限的量,同一时间并不需要所有矩阵的值。

 

根据具体问题优化空间复杂度

还是以 a = "fxy", b = "fab" 为例,例如计算 d[1][3], 也就是下图中的绿色方块, 我们需要知道的值只需 3 个,下图中蓝色方块的值

进一步分析,我们知道,当计算 d[1] 这行的时候,我们只需知道 d[0] 这行的值, 同理我们计算当前行的时候只需知道上一行就可以了

再进一步分析,其实我们只需要一行就可以了,每次计算的时候我们需要的 3 个值, 其中上边和左边的值我们可以直接得到,左上角的值需要临时变量(如下代码使用 flag)来记录

代码示例:

#!/usr/bin/env python
# -*- coding: utf-8 -*-


"""
给定 2 个字符串 a, b,编辑距离是将 a 转换为 b 的最少操作次数,操作只允许如下 3 种:
    1. 插入一个字符,例如:fj -> fxj
    2. 删除一个字符,例如:fxj -> fj
    3. 替换一个字符,例如:jxj -> fyj
"""


def edit_distance2(a, b):
    lena = len(a)
    lenb = len(b)
    d = [0 for _ in range(lenb + 1)]

    for j in range(lenb):
        d[j] = j

    flag = -1
    for i in range(1, lena + 1):
        flag = i - 1
        d[0] = i
        for j in range(1, lenb + 1):
            temp = d[j]
            if a[i - 1] == b[j - 1]:
                d[j] = flag
            else:
                d[j] = min(d[j] + 1, d[j - 1] + 1, flag + 1)
            flag = temp
        print(d)
    return d[lenb]


stra = "fxy"
strb = "fab"
print(edit_distance2(stra, strb))

需要注意的一点就是,当一行计算好之后开始下一行的时候, 要初始化 flag 和 d[0] 的值

优化过后时间复杂度还是 O(mn), 空间复杂度降低了,以上代码是 O(n),其实很简单可以写成 O(min(m,n))。

 

(全文完)

...

Tags Read More..