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

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

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

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

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

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序列片段之间的“差别”（或称“距离”）。

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