前提
已经很久没深入研究过算法相关的东西，毕竟日常少用，就算死记硬背也是没有实施场景导致容易淡忘。最近在做一个「脱敏数据和明文数据匹配」的需求的时候，用到了一个算法叫Levenshtein Distance Algorithm，本文对此算法原理做简单的分析，并且用此算法解决几个常见的场景。
什么是Levenshtein Distance
Levenshtein Distance，一般称为编辑距离（Edit Distance，Levenshtein Distance只是编辑距离的其中一种）或者莱文斯坦距离，算法概念是俄罗斯科学家弗拉基米尔·莱文斯坦（Levenshtein · Vladimir I）在1965年提出。此算法的概念很简单：Levenshtein Distance指「两个字串之间，由一个转换成另一个所需的最少编辑操作次数」，允许的编辑操作包括：
- 将其中一个字符替换成另一个字符（
Substitutions）。 - 插入一个字符（
Insertions）。 - 删除一个字符（
Deletions）。
❝下文开始简称
❞Levenshtein Distance为LD
Levenshtein Distance公式定义
这个数学公式最终得出的数值就是LD的值。举个例子：
将kitten这个单词转成sitting的LD值为3：
- kitten → sitten （k→s）
- sitten → sittin （e→i）
- sittin → sitting （insert a 'g'）
Levenshtein Distance动态规划方法
可以使用动态规划的方法去测量LD的值，步骤大致如下：
- 初始化一个
LD矩阵(M,N)，M和N分别是两个输入字符串的长度。 - 矩阵可以从左上角到右下角进行填充，每个水平或垂直跳转分别对应于一个插入或一个删除。
- 通过定义每个操作的成本为1，如果两个字符串不匹配，则对角跳转的代价为1，否则为0，简单来说就是：
- 如果
[i][j]位置的两个字符串相等，则从[i][j]位置左加1，上加1，左上加0，然后从这三个数中取出最小的值填充到[i][j]。 - 如果
[i][j]位置的两个字符串不相等，则从[i][j]位置左、左上、上三个位置的值中取最小值，这个最小值加1（或者说这三个值都加1然后取最小值），然后填充到[i][j]。
- 按照上面规则
LD矩阵(M,N)填充完毕后，最终「矩阵右下角的数字」就是两个字符串的LD值。
这里不打算证明上面动态规划的结论（也就是默认这个动态规划的结果是正确的），直接举两个例子说明这个问题：
- 例子一（两个等长字符串）：
son和sun。 - 例子二（两个非等长字符串）：
doge和dog。
「例子一：」
初始化LD矩阵(3,3)：
s |
o |
n |
||
0 |
1 |
2 |
3 |
|
s |
1 |
|||
u |
2 |
|||
n |
3 |
计算[0][0]的位置的值，因为's' = 's'，所以[0][0]的值 = min(1+1, 1+1, 0+0) = 0。
s |
o |
n |
||
0 |
1 |
2 |
3 |
|
s |
1 |
0 | ||
u |
2 |
|||
n |
3 |
按照这个规则计算其他位置的值，填充完毕后的LD矩阵`如下：
s |
o |
n |
||
0 |
1 |
2 |
3 |
|
s |
1 |
0 | 1 | 2 |
u |
2 |
1 | 1 | 2 |
n |
3 |
2 | 2 | 1 |
那么son和sun的LD值为1。
「例子二：」
初始化LD矩阵(4,3)：
d |
o |
g |
||
0 |
1 |
2 |
3 |
|
d |
1 |
|||
o |
2 |
|||
g |
3 |
|||
e |
4 |
接着填充矩阵：
d |
o |
g |
||
0 |
1 |
2 |
3 |
|
d |
1 |
0 |
1 |
2 |
o |
2 |
1 |
0 |
1 |
g |
3 |
2 |
1 |
0 |
e |
4 |
3 |
2 |
1 |
那么doge和dog的LD值为1。
Levenshtein Distance算法实现
依据前面提到的动态规划方法，可以相对简单地实现LD的算法，这里选用Java语言进行实现：
public enum LevenshteinDistance { // 单例 X; /** * 计算Levenshtein Distance */ public int ld(String source, String target) { Optional.ofNullable(source).orElseThrow(() -> new IllegalArgumentException("source")); Optional.ofNullable(target).orElseThrow(() -> new IllegalArgumentException("target")); int sl = source.length(); int tl = target.length(); // 定义矩阵,行列都要加1 int[][] matrix = new int[sl + 1][tl + 1]; // 首行首列赋值 for (int k = 0; k <= sl; k++) { matrix[k][0] = k; } for (int k = 0; k <= tl; k++) { matrix[0][k] = k; } // 定义临时的编辑消耗 int cost; for (int i = 1; i <= sl; i++) { for (int j = 1; j <= tl; j++) { if (source.charAt(i - 1) == target.charAt(j - 1)) { cost = 0; } else { cost = 1; } matrix[i][j] = min( // 左上 matrix[i - 1][j - 1] + cost, // 右上 matrix[i][j - 1] + 1, // 左边 matrix[i - 1][j] + 1 ); } } return matrix[sl][tl]; } private int min(int x, int y, int z) { return Math.min(x, Math.min(y, z)); } /** * 计算匹配度match rate */ public BigDecimal mr(String source, String target) { int ld = ld(source, target); // 1 - ld / max(len1,len2) return BigDecimal.ONE.subtract(BigDecimal.valueOf(ld) .divide(BigDecimal.valueOf(Math.max(source.length(), target.length())), 2, BigDecimal.ROUND_HALF_UP)); } } 复制代码
算法的复杂度为O(N * M)，其中N和M分别是两个输入字符串的长度。这里的算法实现完全参照前面的动态规划方法推论过程，实际上不一定需要定义二维数组（矩阵），使用两个一维的数组即可，可以参看一下java-string-similarity中Levenshtein算法的实现。以前面的例子运行一下：
public static void main(String[] args) throws Exception { String s = "doge"; String t = "dog"; System.out.println("Levenshtein Distance:" +LevenshteinDistance.X.ld(s, t)); System.out.println("Match Rate:" +LevenshteinDistance.X.mr(s, t)); } // 输出 Levenshtein Distance:1 Match Rate:0.75 复制代码
Levenshtein Distance算法一些使用场景
LD算法主要的应用场景有：
DNA分析。- 拼写检查。
- 语音识别。
- 抄袭侦测。
- 等等......
其实主要就是"字符串"匹配场景，这里基于实际遇到的场景举例。
脱敏数据和明文数据匹配
最近有场景做脱敏数据和明文数据匹配，有时候第三方导出的文件是脱敏文件，格式如下：
| 姓名 | 手机号 | 身份证 |
张*狗 |
123****8910 |
123456****8765**** |
己方有明文数据如下：
| 姓名 | 手机号 | 身份证 |
张大狗 |
12345678910 |
123456789987654321 |
要把两份数据进行匹配，得出上面两条数据对应的是同一个人的数据，原理就是：当且仅当两条数据中手机号的LD值为4，身份证的LD值为8，姓名的LD值为1，则两条数据完全匹配。
使用前面写过的算法：
public static void main(String[] args) throws Exception { String sourceName = "张*狗"; String sourcePhone = "123****8910"; String sourceIdentityNo = "123456****8765****"; String targetName = "张大狗"; String targetPhone = "12345678910"; String targetIdentityNo = "123456789987654321"; boolean match = LevenshteinDistance.X.ld(sourceName, targetName) == 1 && LevenshteinDistance.X.ld(sourcePhone, targetPhone) == 4 && LevenshteinDistance.X.ld(sourceIdentityNo, targetIdentityNo) == 8; System.out.println("是否匹配:" + match); targetName = "张大doge"; match = LevenshteinDistance.X.ld(sourceName, targetName) == 1 && LevenshteinDistance.X.ld(sourcePhone, targetPhone) == 4 && LevenshteinDistance.X.ld(sourceIdentityNo, targetIdentityNo) == 8; System.out.println("是否匹配:" + match); } // 输出结果 是否匹配:true 是否匹配:false 复制代码
拼写检查
这个场景看起来比较贴近生活，也就是词典应用的拼写提示，例如输入了throwab，就能提示出throwable，笔者认为一个简单实现就是遍历t开头的单词库，寻找匹配度比较高（LD值比较小）的单词进行提示（实际上为了满足效率有可能并不是这样实现的）。举个例子：
public static void main(String[] args) throws Exception { String target = "throwab"; // 模拟一个单词库 List<String> words = Lists.newArrayList(); words.add("throwable"); words.add("their"); words.add("the"); Map<String, BigDecimal> result = Maps.newHashMap(); words.forEach(x -> result.put(x, LevenshteinDistance.X.mr(x, target))); System.out.println("输入值为:" + target); result.forEach((k, v) -> System.out.println(String.format("候选值:%s,匹配度:%s", k, v))); } // 输出结果 输入值为:throwab 候选值:the,匹配度:0.29 候选值:throwable,匹配度:0.78 候选值:their,匹配度:0.29 复制代码
这样子就可以基于输入的throwab选取匹配度最高的throwable。
抄袭侦测
抄袭侦测的本质也是字符串的匹配，可以简单认为匹配度高于某一个阈值就是属于抄袭。例如《我是一只小小鸟》里面的一句歌词是：
❝我是一只小小小小鸟，想要飞呀飞却飞也飞不高
❞
假设笔者创作了一句歌词：
❝我是一条小小小小狗，想要睡呀睡却睡也睡不够
❞
我们可以尝试找出两句词的匹配度：
System.out.println(LevenshteinDistance.X.mr("我是一只小小小小鸟，想要飞呀飞却飞也飞不高", "我是一条小小小小狗，想要睡呀睡却睡也睡不够")); // 输出如下 0.67 复制代码
可以认为笔者创作的歌词是完全抄袭的。当然，对于大文本的抄袭侦测（如论文查重等等）需要考虑执行效率的问题，解决的思路应该是类似的，但是需要考虑如何分词、大小写等等各种的问题。
小结
本文仅仅对Levenshtein Distance做了一点皮毛上的分析并且列举了一些简单的场景，其实此算法在日常生活中是十分常见的，笔者猜测词典应用的单词拼写检查、论文查重（抄袭判别）都可能和此算法相关。算法虽然学习曲线比较陡峭，但是它确实是一把解决问题的利刃。Levenshtein Distance存在明显的优势和劣势：
- 明显的劣势：算法的时间复杂度是
O(M * N)，存在两重循环，「效率比较低」。 - 明显的优势：根据此算法得到的匹配度或者说「结果和现实生活的真实场景最接近」。
对于其劣势，可以考虑选择一些改良的编辑距离算法，这里就不做展开了。
参考资料：
