[算法] 计算字符串的相似度

2013 九月 13 周五 Zoey Young 算法&数据结构笔试面试 Python DP 动态规划《编程之美》

《编程之美》3.3 计算字符串的相似度

许多程序会大量使用字符串. 对于不同的字符串, 我们希望能够有办法判断其相似程度. 我们定义了一套操作方法来把两个不相同的字符串变得相同, 具体的操作方法为:

修改一个字符(如把"a"替换为"b");
增加一个字符(如把"abdd"变为"aebdd");
删除一个字符(如把"travelling"变为"traveling");

比如, 对于"abcdefg"和"abcdef"两个字符串来说, 我们认为可以通过增加/减少一个"g"的方式来达到目的. 上面的两种方案, 都仅需要一次操作. 把这个操作所需要的次数定义为两个字符串的距离, 而相似度等于"距离+1"的倒数. 也就是说, "abcdefg"和"abcdef"的距离为1, 相似度为1/2=0.5.

给定任意两个字符串, 你是否能写出一个算法来计算它们的相似度呢？

分析与解法

不难看出, 两个字符串的距离肯定不超过它们的长度之和(我们可以通过删除操作把两个串都转化为空串). 虽然这个结论对结果没有帮助, 但至少可以知道, 任意两个字符串的距离都是有限的.

[想到动态规划]我们还是应该集中考虑如何才能把这个问题转化成规模较小的同样的问题. 如果有两个串A=xabcdae和B=xfdfa, 它们的第一个字符是相同的, 只要计算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距离就可以了. 但是如果两个串的第一个字符不相同, 那么可以进行如下的操作(lenA和lenB分别是A串和B串的长度).

删除A串的第一个字符, 然后计算A[2,...,lenA]和B[1,...,lenB]的距离.
删除B串的第一个字符, 然后计算A[1,...,lenA]和B[2,...,lenB]的距离.
修改A串的第一个字符为B串的第一个字符, 然后计算A[2,...,lenA]和B[2,...,lenB]的距离.
修改B串的第一个字符为A串的第一个字符, 然后计算A[2,...,lenA]和B[2,...,lenB]的距离.
增加B串的第一个字符到A串的第一个字符之前, 然后计算A[1,...,lenA]和B[2,...,lenB]的距离.
增加A串的第一个字符到B串的第一个字符之前, 然后计算A[2,...,lenA]和B[1,...,lenB]的距离.

在这个题目中, 我们并不在乎两个字符串变得相等之后的字符串是怎样的. 所以, 可以将上面的6个操作合并为:

一步操作之后, 再将A[2,...,lenA]和B[1,...,lenB]变成相字符串.
一步操作之后, 再将A[1,...,lenA]和B[2,...,lenB]变成相字符串.
一步操作之后, 再将A[2,...,lenA]和B[2,...,lenB]变成相字符串.

这样, 很快就可以完成一个递归程序:

# 注意, 和书上不同的是, 这里字符串起始位置是0
def calculate_str_distance(s1='', pos_s1=0, len_s1=None, s2='', pos_s2=0, len_s2=None):
    if len_s1 is None: len_s1 = len(s1)
    if len_s2 is None: len_s2 = len(s2)
    if pos_s1 == len_s1 and pos_s2 == len_s2: return 0
    if pos_s1 == len_s1: return len_s2 - pos_s2
    if pos_s2 == len_s2: return len_s1 - pos_s1
    if s1[pos_s1] == s2[pos_s2]:
        return calculate_str_distance(s1, pos_s1+1, len_s1, s2, pos_s2+1, len_s2)
    else:
        d1 = calculate_str_distance(s1, pos_s1+1, len_s1, s2, pos_s2, len_s2)
        d2 = calculate_str_distance(s1, pos_s1, len_s1, s2, pos_s2+1, len_s2)
        d3 = calculate_str_distance(s1, pos_s1+1, len_s1, s2, pos_s2+1, len_s2)
        return min(d1, d2, d3) + 1

d1 = calculate_str_distance(s1="abcdefg", s2="abcdef")
print(d1)
d2 = calculate_str_distance(s1="xabcdae", s2="xfdfa")
print(d2)

上面的递归程序, 有什么地方需要改进呢? 问题在于: 在递归的过程中, 有些数据被重复计算了.

计算字符串的相似度--编程之美3.3

def calculate_str_distance(s1, s2):
    len_s1 = len(s1)
    len_s2 = len(s2)
    c = [[0 for i in range(len_s2+1)] for i in range(len_s1+1)]
    # 初始化边界值
    for i in range(len_s1+1):
        c[i][len_s2] = len_s1-i
    for j in range(len_s2+1):
        c[len_s1][j] = len_s2-j
    for i in reversed(range(len_s1)):
        for j in reversed(range(len_s2)):
            if s1[i] == s2[j]:
                c[i][j] = c[i+1][j+1]
            else:
                c[i][j] = min(c[i][j+1], c[i+1][j], c[i+1][j+1]) + 1
    return c[0][0]

边界值: c[i, j]的边界值就是当s1为空字符串(len_s1 = 0)或s2为空字符串(len_s2 = 0)时所计算出的编辑距离

# 与上面方法一样, 只是从头开始分析, 而不是从尾开始分析
def calculate_str_distance(s1, s2):
    len_s1 = len(s1)
    len_s2 = len(s2)
    c = [[0 for i in range(len_s2+1)] for i in range(len_s1+1)]
    for i in range(len_s1+1):
        c[i][0] = i
    for j in range(len_s2+1):
        c[0][j] = j
    for i in range(1, len_s1+1):
        for j in range(1, len_s2+1):
            if s1[i-1] == s2[j-1]:
                c[i][j] = c[i-1][j-1]
            else:
                c[i][j] = min(c[i][j-1], c[i-1][j], c[i-1][j-1]) + 1
    return c[len_s1][len_s2]