内容简介:--------------------------------------跟我交流,向我提问:
前言
目前计算句子相似性有很多不同的方案,比如基于语义词典的方法、基于相同词汇的方法、基于统计的方法和基于编辑距离的方法。这篇文章先介绍编辑距离的基础。
编辑距离
编辑距离其实就是指把一个字符串转换为另外一个字符串所需要的最小编辑操作的代价数。包括插入字符、替换字符和删除字符。编辑距离越小,相似度越大。
比如我们要将 what
转换成 where
,可能是将 a -> e,接着 t -> r ,变为 wher
,最后添加 e,完成。因为每一步都可以插入、删除或替换,那么如何才能在最终得到一个最小的代价,这是就会用到动态规划来求解。
假设我们有长度分别为 i、j
的两个字符串,设编辑距离为 edit(i,j)
。接着我们看下,如果它们最后的字符相等,则编辑距离其实等于 edit(i-1,j-1)
。而如果最后的字符不相等,那么我们可以通过插入或替换来使其相等,但是不同的操作对应的代价不相同,如果插入则为 edit(i,j-1)+1
或 eidit(i-1,j)+1
,替换则为 edit(i-1,j-1)+1
。
求解
用以下动态方程来表示:
其中
举个前面的例子,what 到 where,假设两个字符分别为空时对应的代价数如下,
编辑距离 | 空 | w | h | a | t |
空 | 0 | 1 | 2 | 3 | 4 |
动态规划后为:
编辑距离 | 空 | w | h | a | t |
空 | 0 | 1 | 2 | 3 | 4 |
w | 1 | 0 | 1 | 2 | 3 |
h | 2 | 1 | 0 | 1 | 2 |
e | 3 | 2 | 1 | 1 | 2 |
r | 4 | 3 | 2 | 2 | 2 |
e | 5 | 4 | 3 | 3 | 3 |
在整个动态规划过程中一直都是选择最小的代价数,所以最终的3即是这两个字符串的最小代价数,即编辑距离。
github
https://github.com/sea-boat/TextAnalyzer/blob/master/src/main/java/com/seaboat/text/analyzer/distance/CharEditDistance.java
实现
public class EditDistance { public static int getEditDistance(String s, String t) { int d[][]; int n; int m; int i; int j; char s_i; char t_j; int cost; n = s.length(); m = t.length(); if (n == 0) { return m; } if (m == 0) { return n; } d = new int[n + 1][m + 1]; for (i = 0; i <= n; i++) { d[i][0] = i; } for (j = 0; j <= m; j++) { d[0][j] = j; } for (i = 1; i <= n; i++) { s_i = s.charAt(i - 1); for (j = 1; j <= m; j++) { t_j = t.charAt(j - 1); cost = (s_i == t_j) ? 0 : 1; d[i][j] = Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1); d[i][j] = Math.min(d[i][j], d[i - 1][j - 1] + cost); } } return d[n][m]; } public static void main(String[] args) { EditDistance ed = new EditDistance(); System.out.println(ed.getEditDistance("what", "where")); } }
--------------------------------------
跟我交流,向我提问:
公众号的菜单已分为“读书总结”、“分布式”、“机器学习”、“深度学习”、“NLP”、“Java深度”、“Java并发核心”、“JDK源码”、“Tomcat内核”等,可能有一款适合你的胃口。
-------------推荐阅读------------
以上所述就是小编给大家介绍的《怎样衡量两个字符串的相似度(编辑距离动态规划求解)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 动态规划求解最长公共子序列
- Haskell – 优化微分方程求解器
- 最大子序列的求解-算法之一分析
- 八皇后问题分析和 golang 求解
- 漫画:一文看懂螺旋矩阵求解
- [经典算法]8皇后问题sql求解(回溯算法)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。