与编辑距离有关

✤ Apr 20, 2014 ✤

最近几天在整理以前收集的和用过有点忘记的编程、算法等相关信息。
当初毕设做的字符串测试数据自动生成算法中就是应用了编辑距离，那会捯饬这个浪费了不少时间。
所谓编辑距离，是指两个任意字符串s, t。由s经过编辑操作编程t所需的操作次数，这里的编辑操作包括插入、替换、删除三种操作。
由此，两个字符串之间的编辑距离可以定义为：

ED(s:a,t:b)=min(ED(s:a,t)+1,ED(s,t:b)+1,ED(s,t)+ED(a,b))

在这里，s, t是两个可能为空的字符串；s:a，t:b是字符串s，t的子串；a，b为字符。如果两个字符串均为空，则它们的编辑距离是0；一个非空字符串和空字符串的编辑距离是非空字符串的长度。
0.0 介个是编辑距离相关的信息，恩，如果用程序实现计算编辑距离肿么做呢。
可以用动态规划来实现编辑距离~

首先定义这样一个函数——edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。
显然可以有如下动态规划公式：

那算法就是这样，譬如可以有如下一个示例。串A：GUMBO，串B：GAMBOL，计算它们之间的编辑距离。

Steps 1 and 2
= = G U M B O
= 0 1 2 3 4 5
G 1
A 2
M 3
B 4
O 5
L 6

Steps 3 to 6 When i = 1
= = G U M B O
= 0 1 2 3 4 5
G 1 0
A 2 1
M 3 2
B 4 3
O 5 4
L 6 5

Steps 3 to 6 When i = 2
= = G U M B O
= 0 1 2 3 4 5
G 1 0 1
A 2 1 1
M 3 2 2
B 4 3 3
O 5 4 4
L 6 5 5

Steps 3 to 6 When i = 3
= = G U M B O
= 0 1 2 3 4 5
G 1 0 1 2
A 2 1 1 2
M 3 2 2 1
B 4 3 3 2
O 5 4 4 3
L 6 5 5 4

Steps 3 to 6 When i = 4
= = G U M B O
= 0 1 2 3 4 5
G 1 0 1 2 3
A 2 1 1 2 3
M 3 2 2 1 2
B 4 3 3 2 1
O 5 4 4 3 2
L 6 5 5 4 3

Steps 3 to 6 When i = 5
= = G U M B O
= 0 1 2 3 4 5
G 1 0 1 2 3 4
A 2 1 1 2 3 4
M 3 2 2 1 2 3
B 4 3 3 2 1 2
O 5 4 4 3 2 1
L 6 5 5 4 3 2

Step 7
所以，A、B之间的编辑距离最右下角的数字，即edit(A,B)=2。

算法说完了，最后说一下python中的具体实现。其实，实现的代码真的是灰常简单，(⊙v⊙)嗯，闲言碎语不要讲，直接附代码~

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

def edit_dis(m,n):
    """
    动态规划算法,计算编辑距离，操作包括插入、删除、替换
    simple input:
    >>> print edit_dis("abc","abec")
    1
    >>> print edit_dis("ababec","abc")
    3
    """
    len_1=lambda x:len(x)+1

    c=[[i] for i in range(0,len_1(m)) ]
    c[0]=[j for j in range(0,len_1(n))]

    for i in range(0,len(m)):
        for j in range(0,len(n)):
            c[i+1].append(
                min(
                    c[i][j+1]+1, # 插入操作
                    c[i+1][j]+1, # 删除操作
                    c[i][j] + (0 if m[i]==n[j] else 1 ) # 替换操作
                )
            )
    return c[-1][-1]

if __name__ == '__main__':
    print edit_dis("abc","abedfsfc")

恩，就酱~

© 鹅玉✱ since 2013. cc by-nd 4.0.