計算字符串相似度的簡易算法
算法設計背景：
最近設計知識管理系統的資源導入功能，為了盡量的做到組件化，方便擴展，方便其他模塊使用。簡化組件提供的和需要的接口，設計并實現了基于 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
本博客為學習交流用，凡未注明引用的均為本人作品，轉載請注明出處，如有版權問題請及時通知。由于博客時間倉促，錯誤之處敬請諒解，有任何意見可給我留言，愿共同學習進步。