亲宝软件园·资讯

展开

Levenshtein Distance(编辑距离)算法与使用场景

throwable 人气:0
## 前提 已经很久没深入研究过算法相关的东西,毕竟日常少用,就算死记硬背也是没有实施场景导致容易淡忘。最近在做一个脱敏数据和明文数据匹配的需求的时候,用到了一个算法叫`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公式定义 ![](https://img2020.cnblogs.com/blog/1412331/202003/1412331-20200308213419929-2005882212.png) 这个数学公式最终得出的数值就是`LD`的值。举个例子: 将`kitten`这个单词转成`sitting`的`LD`值为3: 1. kitten → sitten (k→s) 2. sitten → sittin (e→i) 3. 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`语言进行实现: ```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); return 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算法的实现](https://github.com/tdebatty/java-string-similarity#levenshtein)。以前面的例子运行一下: ```java 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`分析。 - 拼写检查。 - 语音识别。 - 抄袭侦测。 - 等等...... 其实主要就是"字符串"匹配场景,这里基于实际遇到的场景举例。 ### 脱敏数据和明文数据匹配 最近有场景做脱敏数据和明文数据匹配,有时候第三方导出的文件是脱敏文件,格式如下: |姓名|手机号|SFZ| |:-:|:-:|:-:| |`张*狗`|`123****8910`|`123456****8765****`| 己方有明文数据如下: |姓名|手机号|SFZ| |:-:|:-:|:-:| |`张大狗`|`12345678910`|`123456789987654321`| 要把两份数据进行匹配,得出上面两条数据对应的是同一个人的数据,原理就是:当且仅当两条数据中手机号的`LD`值为4,SFZ的`LD`值为8,姓名的`LD`值为1,则两条数据完全匹配。 使用前面写过的算法: ```java 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`值比较小)的单词进行提示(实际上为了满足效率有可能并不是这样实现的)。举个例子: ```java public static void main(String[] args) throws Exception { String target = "throwab"; // 模拟一个单词库 List words = Lists.newArrayList(); words.add("throwable"); words.add("their"); words.add("the"); Map 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`。 ### 抄袭侦测 抄袭侦测的本质也是字符串的匹配,可以简单认为匹配度高于某一个阈值就是属于抄袭。例如《我是一只小小鸟》里面的一句歌词是: > 我是一只小小小小鸟,想要飞呀飞却飞也飞不高 假设笔者创作了一句歌词: > 我是一条小小小小狗,想要睡呀睡却睡也睡不够 我们可以尝试找出两句词的匹配度: ```java System.out.println(LevenshteinDistance.X.mr("我是一只小小小小鸟,想要飞呀飞却飞也飞不高", "我是一条小小小小狗,想要睡呀睡却睡也睡不够")); // 输出如下 0.67 ``` 可以认为笔者创作的歌词是完全抄袭的。当然,对于大文本的抄袭侦测(如论文查重等等)需要考虑执行效率的问题,解决的思路应该是类似的,但是需要考虑如何分词、大小写等等各种的问题。 ## 小结 本文仅仅对`Levenshtein Distance`做了一点皮毛上的分析并且列举了一些简单的场景,其实此算法在日常生活中是十分常见的,笔者猜测词典应用的单词拼写检查、论文查重(抄袭判别)都可能和此算法相关。算法虽然学习曲线比较陡峭,但是它确实是一把解决问题的利刃。 参考资料: - [维基百科 - Levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance) - [java-string-similarity](https://github.com/tdebatty/java-string-similarity) - [The Levenshtein Algorithm](https://www.cuelogic.com/blog/the-levenshtein-algorithm)

加载全部内容

相关教程
猜你喜欢
用户评论