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