计算字符串相似度的简易算法
算法设计背景:
最近设计知识管理系统的资源导入功能,为了尽量的做到组件化,方便扩展,方便其他模块使用。简化组件提供的和需要的接口,设计并实现了基于 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
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
本博客为学习交流用,凡未注明引用的均为本人作品,转载请注明出处,如有版权问题请及时通知。由于博客时间仓促,错误之处敬请谅解,有任何意见可给我留言,愿共同学习进步。