莱文斯坦距离计算器（编辑距离）

莱文斯坦距离是把一个字符串变成另一个字符串所需的单字符插入、删除和替换的最少次数——拼写建议、模糊搜索、重复检测和 DNA 比对背后用的都是这个度量。这个计算器会给出距离和相似度百分比，列出具体的编辑，为较短的字符串展示动态规划表，还可以按与你的字符串的接近程度，对整个候选列表排序。

使用方法

1. 输入两个字符串（或一个字符串和一个列表，每行一个候选项）。
2. 选择普通莱文斯坦，或选择 Damerau，把相邻字符互换算作一次编辑。
3. 可选：忽略大小写和空白，或按单词比较。
4. 查看距离、相似度和编辑内容；字符串不超过 20 个字符时会显示表格。

计算公式

d[i][j] = min(d[i−1][j] + 1, d[i][j−1] + 1, d[i−1][j−1] + (aᵢ ≠ bⱼ)) · 相似度 = 1 − d ÷ max(|a|, |b|)

d[i][j] 是 a 的前 i 个字符与 b 的前 j 个字符之间的距离，从 d[i][0] = i 和 d[0][j] = j 开始。相邻互换（最优字符串对齐）变体在相邻两个字符互换时增加 d[i−2][j−2] + 1，但不会对同一子串编辑两次；无限制的 Damerau–莱文斯坦距离取消了这一限制（CA → ABC 是 2 而不是 3）。字符按 Unicode 码点计算，单词以空白分隔。

示例

北京大学 → 清华大学 = 2：把“北”替换为“清”，把“京”替换为“华”。两个字符串都是 4 个字符，所以相似度是 1 − 2/4 = 50%。上海 → 上海市 的距离是 1（插入“市”）。以北京大学为基准，对列表北京大学生、清华大学、北京交通大学、南京大学排序，距离为 1 的北京大学生排第一。