博客

Levenshtein距离，又称L氏


编辑距离，


是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。原子


编辑操作包括增、删、改，即


插入一个字符，删除一个字符，


将一个字符


替换成另一个字符


。一般来说，


Levenshtein


距离越小，两个串的相似度越大。



Levenshtein 距离已经在DNA分析、拼音纠错、命名实体抽取、实体共指、机器翻译等方面有广泛应用。

具体计算公式参见维基百科，下面从自然语言表达和python实现两个方面介绍其计算逻辑。

2.1 自然语言表达

例如要计算“垃圾消息”和“A垃圾信息”的


Levenshtein距离，步骤如下：

第一步：依据两字符串长度构造字符串矩阵，并填入相应的位置数据，如下表：

第三步：循环使用第二步操作，将其他格子填满。结果如下表：

第四步：取右下角数值2，即为L氏编辑距离。

2.2 python实现

def



levenshtein_distance

(first

,

second):



”’





计算两个字符串之间的L氏编辑距离





:输入参数 first: 第一个字符串





:输入参数 second: 第二个字符串





:返回值: L氏编辑距离





”’









if



len

(first) ==

0



or



len

(second) ==

0

:



return



len

(first) +

len

(second)

first_length =

len

(first) +

1




second_length =

len

(second) +

1




distance_matrix = [

range

(second_length)


for



i



in



range

(first_length)]

# 初始化矩阵






for


i


in



range

(

1


,

first_length):



for


j


in



range

(

1


,

second_length):

deletion = distance_matrix[i-

1

][j] +

1




insertion = distance_matrix[i][j-

1

] +

1




substitution = distance_matrix[i-

1

][j-

1

]



if


first[i-

1

] != second[j-

1

]:

substitution +=

1




distance_matrix[i][j] =

min

(insertion

,

deletion

,

substitution)



return


distance_matrix[first_length-

1

][second_length-

1

]

if


__name__ ==

‘__main__’

:



print


levenshtein_distance(

u”垃圾消息”


,


u”A垃圾信息”

)

# 运行结果为：2

参考资料

https://en.wikipedia.org/wiki/Levenshtein_distance