编辑距离

编辑距离用于评估两个序列之间的差异程度。

编辑距离定义：通过多少次操作才能让两个字符串变得相同。

变数：

• 操作的定义
• 目标串的定义

编辑距离是一个较为宏观的概念，它有许多变种。

• 在莱文斯坦距离中，可以删除、加入、取代字符串中的任何一个字元，也是较常用的编辑距离定义，常常提到编辑距离时，指的就是莱文斯坦距离。
• Damerau-Levenshtein 距离是一种莱文斯坦距离的变种，但允许以单一操作交换相邻的两个字符（称为字符转置），如 AB→BA 的距离是 1（交换）而非 2（先删除再插入、或者两次替换）
• LCS（最长公共子序列）距离只允许删除、加入字元
• Jaro 距离只允许字符转置
• 汉明距离只允许取代字元

参考资料

https://zh.wikipedia.org/wiki/編輯距離
https://zh.wikipedia.org/wiki/萊文斯坦距離
https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein Distance.htm