計算字元串相似度的簡易算法
算法設計背景：
最近設計知識管理系統的資源導入功能，為了盡量的做到元件化，友善擴充，友善其他子產品使用。簡化元件提供的和需要的接口，設計并實作了基于 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
6
import java.util.HashMap;
7
import java.util.Map;
8
9
10
* @author jack.wang
11
12
13
public 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
33
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
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