计算字符串相似度的简易算法
算法设计背景：
最近设计知识管理系统的资源导入功能，为了尽量的做到组件化，方便扩展，方便其他模块使用。简化组件提供的和需要的接口，设计并实现了基于 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
本文转自BlogJava 新浪blog的博客，原文链接：计算字符串相似度的简易算法，如需转载请自行联系原博主。2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81