极客笔记Python中查找字符串及其子字符串的总相似度的程序
在Python中，我们经常需要查找字符串及其子字符串的相似度。如果我们需要找到一个字符串与另一个字符串之间的相似度或多个字符串中最相似的一对，我们就需要使用一些算法来计算它们之间的相似度。下面就介绍一些Python中常用的算法。
Levenshtein Distance算法
Levenshtein Distance算法是一种用于计算字符串相似度的算法，也称为编辑距离算法，指的是在把S1转换为S2的最小次数编辑操作数。编辑操作包括插入，删除和替换。下面是一个用Python编写的实现该算法的代码：
def LevenshteinDistance(s1, s2):
m, n = len(s1), len(s2)
if m < n:
s1, s2 = s2, s1
m, n = n, m
distance = range(n+1)
for i in range(1, m+1):
previous, distance = distance, [i]+[0]*n
for j in range(1, n+1):
add, delete = previous[j]+1, distance[j-1]+1
change = previous[j-1] if s1[i-1] == s2[j-1] else previous[j-1]+1
distance[j] = min(add, delete, change)
return distance[n]
在上面的代码中，我们用到了Python内置的range函数生成一个整数序列。它将生成0到n-1的整数序列。同时，我们使用了Python的列表推导式来生成一个长度为n的0列表。
我们可以用下面的代码调用LevenshteinDistance函数：
s1 = "kitten"
s2 = "sitting"
distance = LevenshteinDistance(s1, s2)
print("The Levenshtein distance between {0} and {1} is {2}".format(s1, s2, distance))
运行上面的代码，输出结果为：
The Levenshtein distance between kitten and sitting is 3
汉明距离算法
汉明距离算法是用于计算两个等长字符串之间的汉明距离的算法，其定义为将一个字符串中的字符替换成另一个字符串中的字符所需进行的最小操作次数。下面是Python中实现汉明距离算法的代码：
def HammingDistance(s1, s2):
if len(s1) != len(s2):
raise ValueError("Undefined for strings of unequal length")
return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))
在上面的代码中，我们使用了Python的内置zip函数，该函数可以将两个列表一一对应地配对起来，形成一个由元组组成的列表，其中元组中的每个元素都来自输入列表的相应位置。如：
list1 = [1, 2, 3]
list2 = [4, 5, 6]
zipped = zip(list1, list2)
print(list(zipped))
输出结果为：
[(1, 4), (2, 5), (3, 6)]
我们可以用下面的代码调用HammingDistance函数：
s1 = "karolin"
s2 = "kathrin"
distance = HammingDistance(s1, s2)
print("The Hamming distance between {0} and {1} is {2}".format(s1, s2, distance))
运行上面的代码，输出结果为：
The Hamming distance between karolin and kathrin is 3
Jaccard相似度算法
Jaccard相似度算法一般用于计算两个集合之间的相似度。在Python中，我们可以使用set函数来实现集合的创建和操作，从而计算Jaccard相似度。下面是用Python实现Jaccard相似度算法的代码：
def JaccardSimilarity(set1, set2):
intersection = set1 & set2
union = set1 | set2
return len(intersection) / len(union)
在上面的代码中，我们使用了Python的set函数来创建两个集合，并使用&运算符取出两个集合的交集，使用|运算符取出两个集合的并集。
我们可以用下面的代码调用JaccardSimilarity函数：
set1 = set("apple")
set2 = set("banana")
similarity = JaccardSimilarity(set1, set2)
print("The Jaccard similarity between {0} and {1} is {2}".format(set1, set2, similarity))
运行上面的代码，输出结果为：
The Jaccard similarity between {'p', 'a', 'e', 'l'} and {'n', 'a', 'b'} is 0.4
最长公共子序列算法
最长公共子序列算法用于计算两个字符串之间的最长公共子序列的长度。下面是Python中实现最长公共子序列算法的代码：
def LongestCommonSubsequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]
在上面的代码中，我们用Python的内置函数range生成了一个整数序列，遍历两个字符串s1和s2的所有字符，最终计算出它们的最长公共子序列的长度。
我们可以用下面的代码调用LongestCommonSubsequence函数：
s1 = "ACDEF"
s2 = "CBEGF"
length = LongestCommonSubsequence(s1, s2)
print("The length of the longest common subsequence between {0} and {1} is {2}".format(s1, s2, length))
运行上面的代码，输出结果为：
The length of the longest common subsequence between ACDEF and CBEGF is 3
结论
在Python中，我们可以使用多种算法来计算字符串及其子字符串之间的相似度。Levenshtein Distance算法是计算两个字符串之间的编辑距离的经典算法；汉明距离算法用于计算两个等长字符串之间的汉明距离；Jaccard相似度算法用于计算两个集合之间的相似度；最长公共子序列算法用于计算两个字符串之间的最长公共子序列的长度。