语句相似度算法-编辑距离算法
Python 2022/5/20 21:46:27 点击：不统计
判断两个句子或者段落，通过每个字符进行距离计算，来判断啊两个字符串的相似度，
由一个字符串转换为另一个字符串需要操作的次数，当值越小，越相似。
（1）当距离结果为0时，则两个字符串一样。
（2）通过生成两个字符串对应的 每个字符对比，有对应的3中操作，替换 删除 和添加
我们按照 二重循环的方式 进行替换值的记录，定义distance_matrix[i][j]
为 我们操作 第一个字符串前i个字符变换为 第二个字符前j个字符 对应操作(上述3中操作)量
然后我们取对应的最小值 存放到 distance_matrix[i][j]
那最后的 distance_matrix[i][j] 就 数最小的操作量
看下面的代码：可以直接复制为 py文件运行
看下面的代码：可以直接复制为 py文件运行
def minDistance(first, second):
if len(first) == 0 or len(second) == 0:
return max(len(first),len(second));
first_length = len(first) + 1 #获取长度+1 用来表示字符串变换时的索引id
second_length = len(second) + 1 #获取长度+1 用来表示字符串变换时的索引id
#创建二维数组
distance_matrix = [list(range(second_length)) for x in range(first_length)]
print("开始计算编辑距离算法")
for i in range(1, first_length):
for j in range(1, second_length):
deletion = distance_matrix[i - 1][j] + 1 #如果是删除 第一个字符串删除，基于上次操作 则对应操作+1
insertion = distance_matrix[i][j - 1] + 1 # 如果是添加，在第二个字符串添加 ，基于上次操作 则对应操作+1
#上述的 删除和添加可以相互更换，因为不存在顺序问题，要么 添加第一个字符串内容，要么删除第二个字符串内容。
substitution = distance_matrix[i - 1][j - 1]# 如果是替换 则对应操作
#比较字符，如果不相等，则替换操作内容加 1
if first[i - 1] != second[j - 1]:
substitution += 1
#获取每一次操作的最小值，并放到相应的 distance_matrix[i][j] 矩阵中
# 当 i j 到结束，则distance_matrix[i][j] 保存的是 第一个字符串前i个（全部） 转换到第二个字符串j个（全部）的操作步骤
distance_matrix[i][j] = min(insertion, deletion, substitution)
return distance_matrix[first_length - 1][second_length - 1]
str2 = "www.forasp.cn"
str1 = "cn.forasp.www"
edit_distance = minDistance(str1, str2)
print(edit_distance)
#上述编辑距离结果为 6
# 即从str1 转换到str2 需要 替换 6个字符即可。分别是www 和 .cn
str2 = "www.forasp.cn"
str1 = "www.forasp"
edit_distance = minDistance(str1, str2)
print(edit_distance)
#上述编辑距离结果为 3
# 即从str1 转换到str2 需要 删除3个字符.cn 或者添加.cn