计算字符串相似度的简易算法
算法设计背景：
最近设计知识管理系统的资源导入功能，为了尽量的做到组件化，方便扩展，方便其他模块使用。简化组件提供的和需要的接口，设计并实现了基于 Mapping 机制的导入框架。其中有一功能用到了计算两个字符串相似度的算法，简单设计如下以便参考：
设计思想：
把两个字符串变成相同的基本操作定义如下：
1. 修改一个字符（如把 a 变成 b）
2. 增加一个字符 (如 abed 变成 abedd)
3. 删除一个字符（如 jackbllog 变成 jackblog）
针对于 jackbllog到jackblog 只需要删除一个或增加一个 l 就可以把两个字符串变为相同。把这种操作需要的次数定义为两个字符串的距离 L, 则相似度定义为 1/(L+1) 即距离加一的倒数。那么jackbllog和jackblog的相似度为 1/1+1=1/2=0.5 也就是所两个字符串的相似度是 0.5，说明两个字符串已经很接近啦。
任意两个字符串的距离都是有限的，都不会超过他们的长度之和，算法设计中我们并不在乎通过一系列的修改后，得到的两个相同字符串是什么样子。所以每次只需一步操作，并递归的进行下一计算。JAVA 的实现如下：
1
/** *//**
2
*
3
*/
4
package org.blogjava.arithmetic;
5
6import java.util.HashMap;
7import java.util.Map;
8
9/** *//**
10 * @author jack.wang
11 *
12 */
13public class StringDistance 
{
14
15 public static final Map<String, String> DISTANCE_CACHE = new HashMap<String, String>();
16
17 private static int caculateStringDistance(byte[] firstStr, int firstBegin,
18
int firstEnd, byte[] secondStr, int secondBegin, int secondEnd) {
19 String key = makeKey(firstStr, firstBegin, secondStr, secondBegin);
20 if (DISTANCE_CACHE.get(key) != null) {
21 return Integer.parseInt(DISTANCE_CACHE.get(key));
22 } else {
23 if (firstBegin >= firstEnd) {
24 if (secondBegin >= secondEnd) {
25 return 0;
26 } else {
27 return secondEnd - secondBegin + 1;
28
}
29 }
30 if (secondBegin >= secondEnd) {
31 if (firstBegin >= firstEnd) {
32 return 0;
33 } else {
34 return firstEnd - firstBegin + 1;
35 }
36 }
37 if (firstStr[firstBegin] == secondStr[secondBegin]) {
38 return caculateStringDistance(firstStr, firstBegin + 1,
39 firstEnd, secondStr, secondBegin + 1, secondEnd);
40 } else {
41 int oneValue = caculateStringDistance(firstStr, firstBegin + 1,
42 firstEnd, secondStr, secondBegin + 2, secondEnd);
43 int twoValue = caculateStringDistance(firstStr, firstBegin + 2,
44 firstEnd, secondStr, secondBegin + 1, secondEnd);
45 int threeValue = caculateStringDistance(firstStr,
46 firstBegin + 2, firstEnd, secondStr, secondBegin + 2,
47 secondEnd);
48 DISTANCE_CACHE.put(key, String.valueOf(min(oneValue, twoValue,
49 threeValue) + 1));
50 return min(oneValue, twoValue, threeValue) + 1;
51 }
52 }
53 }
54
55 public static float similarity(String stringOne, String stringTwo) {
56 return 1f / (caculateStringDistance(stringOne.getBytes(), 0, stringOne
57 .getBytes().length - 1, stringTwo.getBytes(), 0, stringOne
58 .getBytes().length - 1) + 1);
59 }
60
61 private static int min(int oneValue, int twoValue, int threeValue) {
62 return oneValue > twoValue ? twoValue
63 : oneValue > threeValue ? threeValue : oneValue;
64 }
65
66 private static String makeKey(byte[] firstStr, int firstBegin,
67 byte[] secondStr, int secondBegin) {
68 StringBuffer sb = new StringBuffer();
69 return sb.append(firstStr).append(firstBegin).append(secondStr).append(
70 secondBegin).toString();
71 }
72
73 /** *//**
74 * @param args
75 */
76 public static void main(String[] args) {
77 float i = StringDistance.similarity("jacklovvedyou", "jacklodveyou");
78 System.out.println(i);
79 }
80}
81
本博客为学习交流用，凡未注明引用的均为本人作品，转载请注明出处，如有版权问题请及时通知。由于博客时间仓促，错误之处敬请谅解，有任何意见可给我留言，愿共同学习进步。