Levenshtein距离

莱文斯坦距离，又称Levenshtein距离，是编辑距离的一种。 指两个字串之間，由一个转成另一个所需的最少编辑操作次数。 允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，刪除一个字符。

GitHub 提供了计算莱文斯坦距离的包。
安装方法：

pip install python-Levenshtein

https://www.lfd.uci.edu/~gohlke/pythonlibs/ 里面查找python-Levenshtein.xxx.whl 离线安装

1 Levenshtein

1.1 汉明距离

• Levenshtein.hamming(str1, str2)
  计算汉明距离。要求str1和str2必须长度一致。是描述两个等长字串之间对应位置上不同字符的个数。

  • 插入一个字符 +1
  • 删除一个字符 +1
  • 替换一个字符 +1

  import Levenshtein.hamming
  Levenshtein.hamming('hello', 'world')
  # 4
  Levenshtein.hamming('abc', 'abd')
  # 1
  

1.2 编辑距离

• Levenshtein.distance(str1, str2)
  计算编辑距离（也成Levenshtein距离）。是描述由一个字串转化成另一个字串最少的操作次数，在其中的操作包括插入、删除、替换。

• 编辑距离计算方式

  • 插入一个字符 +1
  • 删除一个字符 +1
  • 替换一个字符 +1

  import Levenshtein.distance
  Levenshtein.distance('hello', 'world')
  # 4
  Levenshtein.distance('abc', 'abd')
  # 1
  Levenshtein.distance('abc', 'aecfaf')
  # 4
  

1.3 莱文斯坦比

• Levenshtein.ratio(str1, str2)
  计算莱文斯坦比。计算公式 r = (sum - ldist) / sum, 其中sum是指str1 和 str2 字串的长度总和，ldist是类编辑距离
  注意：这里的类编辑距离与编辑距离不同

• 类编辑距离计算方式

  • 插入一个字符 +1
  • 删除一个字符 +1
  • 替换一个字符 +2

  莱文斯坦比越接近1，则两个字符串越接近

  import Levenshtein.ratio
  Levenshtein.ratio('hello', 'world')  # (10 -8) / 10
  0.2
  Levenshtein.ratio('abc', 'aecfaf')  # (9 - 2 - 3) / 9
  0.4444444444444444
  Levenshtein.ratio('abc', 'abd')  # (6 - 2) / 6
  0.6666666666666666
  Levenshtein.ratio('abc', 'abc')  # (6 - 0) / 6
  1.0