机器学习中不同的距离定义汇总（二：字符串的距离）
本文主要参考了此博客和文末列出的参考内容
汉明距离（Hamming Distance）
- 在信息论中，两个等长字符串之间的汉明距离（英语：Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
- 汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是1的个数，所以11101的汉明重量是4。
- 1011101与1001001之间的汉明距离是2。
- 2143896与2233796之间的汉明距离是3。
- “toned”与”roses”之间的汉明距离是3。
python实现：
def HammingDistance(x, y):
return sum(x_ch != y_ch for x_ch, y_ch in zip(x, y))
编辑距离（Edit Distance，Levenshtein Distance）
编辑距离是针对二个字符串（例如英文字）的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个（或哪几个）是比较可能的字。DNA也可以视为用A、C、G和T组成的字符串，因此编辑距离也用在生物信息学中，判断二个DNA的类似程度。Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子。
编辑距离有几种不同的定义，差异在可以对字符串进行的处理。
- 在莱文斯坦距离中，可以删除、加入、取代字符串中的任何一个字元，也是较常用的编辑距离定义，常常提到编辑距离时，指的就是莱文斯坦距离[1]。
- 也存在其他编辑距离的定义方式，例如 Damerau-Levenshtein 距离是一种莱文斯坦距离的变种，但允许以单一操作交换相邻的两个字符（称为字符转置），如 AB→BA 的距离是 1（交换）而非 2（先删除再插入、或者两次替换）。
- LCS（最长公共子序列）距离只允许删除、加入字元[1]:37。
- Jaro 距离只允许字符转置。
- 汉明距离只允许取代字元[1]。
python实现：
def EditDistance(x, y):
dp = np.zeros((len(x) + 1,len(y) + 1))
for i in range(len(x) + 1):
dp[i][0] = i
for j in range(len(y) + 1):
dp[0][j] = j
for i in range(1, len(x) + 1):
for j in range(1, len(y) + 1):
delta = 0 if x[i-1] == y[j-1] else 1
dp[i][j] = min(dp[i - 1][j - 1] + delta, min(dp[i-1][j] + 1, dp[i][j - 1] + 1))
return int(dp[len(x)][len(y)])
