对于最小编辑距离算法的理解:
1,一个字符串转化到另一个字符串的最少操作次数
2,操作有三种:增加,删除,替换。
3,它是一个不断最小取值的过程(每一步都是最小取值,至最后理所当然最少操作次数)PS:算法实现过程
最小编辑距离算法思想:
从第一位字符开始不断与相比较字符串比较,通过对比以添加,删除,替换三种方式找到最佳操作。
添加,删除,替换三种方式在代码中展示
import numpy as np
"""
编辑距离:用于比较两个字符串的相似程度
StrA: 字符串A
StrB:字符串B
函数包含处理过程
包含bug:处理不同长度的字符串的时候会出现报错
"""
def min_edit_dist(StrA,StrB):
#获取字符串长度
a_length = len(StrA)
b_length = len(StrB)
#创建矩阵
matrix = np.zeros((b_length+1, a_length+1))
#初始化矩阵
for i in range(1,a_length+1):
matrix[0][i] = i
for j in range(1,b_length+1):
matrix[j][0] = j
#开始进行动态规划
cost = 0 #代价值
for i in range(1,b_length+1):
for j in range(1,a_length+1):
if StrA[j-1] == StrB[i-1]:
cost = 0
else:
cost = 1
#三种字符串操作方式增加 删除 替换
edit_exchange_dis = matrix[j-1][i-1] + cost #替换
edit_add_dis = matrix[j-1][i] + 1 #添加
edit_del_dis = matrix[j][i-1] + 1 #删除
matrix[j][i] = min(edit_exchange_dis,edit_add_dis,edit_del_dis)
#print(matrix[j][i]) #最小编辑距离更改记录
print(matrix) #打印算法过程
print('______________________') #分割
# print(i) 遍历完整性
print('相似度为:',1-1/max(a_length,b_length)) #1-(字符串更改最少次数/字符串最
长距离)
# print(matrix)
# print(StrA[a_length-1])
# print(StrB[b_length-1])
# print(a_length)
min_edit_dist('jsi2nz','jsionz') #测试
刚才忘记结果及算法运行过程截图了,现在贴上,在我参考其他博主的相关文章里,字符串比较过程最多两种方式:
j | s | i | 2 | n | z |
j | |||||
s | |||||
i | |||||
o | |||||
n | |||||
z |
1,字符串A ------> jsi2nz字符串B ------> jsionz(上图代码展示这种方式)
(1),串甲的第一个字符j与串乙的j,js,jsi,jsio,jsion,jsionz分别比较
(2),串甲的前两个字符js与串乙的j,js,jsi,jsio,jsion,jsionz分别比较
(3)··························
2,字符串A ------> jsi2nz字符串B ------> jsionz
(1),串甲的第一个字符j,js,jsi,jsi2,jsi2n,jsi2nz分别与串乙的Ĵ比较
(2),串甲的第一个字符j,js,jsi,jsi2,jsi2n,jsi2nz分别与串乙的JS比较
(3)··························
过程截图:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2Lc1TPB9UMjRUT0EkeNBDOsJGcohVYsR2MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2LcRHelR3LcJzLctmch1mclRXY39DOwgTOwkjM1EjMyATM4EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
结果截图:
第一次写博客,不知道说些什么·····,额·····,有不懂的下方留言吧