机器学习基础之数学上的距离（二）：字符串之间的距

前面的文章中，我们介绍了机器学习中点在空间中的距离（

机器学习基础之数字上的距离（一）：点在空间中的距离

），今天我们来介绍一下自然语言处理中最为常用的字符串之间的距离。

字符串距离用于度量两个字符串之间的相似度，常用的字符串距离有以下几种：

1、汉明距离

汉明距离（Hamming Distance）是等长字符串之间对应的位置差异的度量，即两个字符串对应位置的不同字符的个数，换句话说，它就是将一个字符串变换成另外一个字符串的需要替换的字符个数。

在实际应用中，汉明重量也是自然语言处理中的一个重要概念，它是一个字符串对于同样长度的纯零字符串的汉明距离，也就是说，它是一个字符串中非零元素的个数。对于二进制出字符串来说，就是1的个数，所以11001110的汉明重量是4。

汉明距离的示例如下：

10110111与11110111的汉明距离是1

19980124与19991225的汉明距离是4

take和cake的汉明距离是1

汉明距离最开始是由理查德·卫斯理·汉明在误差检测与校正码的基础性论文中引入的，用于统计在通信中累计定长二进制中发生翻转的错误数据位，所以它也被称为信号距离。而汉明重量分析在信息论、编码理论、密码学等领域都有应用。

2、编辑距离

汉明距离标识了两个字符串之间的差异性，但是通常情况下，我们不仅要比较字符串的差异进行替换，还要进行插入与删除的运算。在这种情况下，汉明距离就不是很适合了，因此，我们需要使用编辑距离。

展开全文

编辑距离（Edit

Distance，Levenshtein

Distance）是一个度量两个字符序列之间差异的字符串度量标准，两个单词之间的编辑距离是将一个字符串转换为另一个字符串所需的单字符编辑（插入、删除或替换）的最小数量。换句话说，就是一个字符串变为另一个字符串所需要的最小操作字符数。

编辑距离由苏联数学家Vladimir

Levenshtein发明，它的量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串，处理只包括三种：插入一个字符、新增一个字符、删除一个字符。在自然语言处理中，编辑距离常用于拼写检查，即根据一个拼错的单词和其它正确的单词之间的编辑距离，判断哪些单词是可能正确的拼写。

编辑距离的示例如下：

intention变为execution

第一次处理：intention -> ntention，删除i

第二次处理：ntention -> etention，n替换成e

第三次处理：etention -> exention，t替换成x

第四次处理：exention -> execntion，插入c

第五次处理：execntion -> execution，n替换成u

所以intention和execution之间的编辑距离是5。

基于编辑距离，人们设计出了

Smith-Waterman 算法和Needleman-Wunsch

算法，其中后者还是历史上最早的应用动态规划思想设计的算法之一，而前者是后者的一个变体，Smith-Waterman

算法的优势在于可以在给定的打分方法下找出两个序列的最优的局部比对（打分方法使用了置换矩阵和空位罚分）。在实际运用中，人们通常使用该算法的优化版本。

现在Smith-Waterman 算法和Needleman-Wunsch 算法在生物信息学领域也有重要应用，研究人员常常用它们来计算两个DNA序列片段之间的“差异”（或称“距离”）。

喜欢本文的话，欢迎关注活在信息时代哦：）