走在架构师的大道上 Jack.Wang's home

Java, C++, linux c, C#.net 技术,软件架构,领域建模,IT 项目管理 Dict.CN 在线词典, 英语学习, 在线翻译

BlogJava 首页 新随笔 联系 聚合 管理
  195 Posts :: 3 Stories :: 728 Comments :: 0 Trackbacks
 

计算字符串相似度的简易算法

算法设计背景:

最近设计知识管理系统的资源导入功能,为了尽量的做到组件化,方便扩展,方便其他模块使用。简化组件提供的和需要的接口,设计并实现了基于 Mapping 机制的导入框架。其中有一功能用到了计算两个字符串相似度的算法,简单设计如下以便参考:

设计思想:

   把两个字符串变成相同的基本操作定义如下:

1.     修改一个字符(如把 a 变成 b

2.     增加一个字符 ( abed 变成 abedd)

3.     删除一个字符(如 jackbllog 变成 jackblog

针对于 jackbllogjackblog 只需要删除一个或增加一个 l 就可以把两个字符串变为相同。把这种操作需要的次数定义为两个字符串的距离 L, 则相似度定义为 1/(L+1) 即距离加一的倒数。那么jackbllogjackblog的相似度为 1/1+1=1/2=0.5 也就是所两个字符串的相似度是 0.5,说明两个字符串已经很接近啦。

任意两个字符串的距离都是有限的,都不会超过他们的长度之和,算法设计中我们并不在乎通过一系列的修改后,得到的两个相同字符串是什么样子。所以每次只需一步操作,并递归的进行下一计算。JAVA 的实现如下:

 1/**
 2 * 
 3 */

 4package 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




本博客为学习交流用,凡未注明引用的均为本人作品,转载请注明出处,如有版权问题请及时通知。由于博客时间仓促,错误之处敬请谅解,有任何意见可给我留言,愿共同学习进步。
posted on 2009-01-19 23:53 Jack.Wang 阅读(10942) 评论(9)  编辑  收藏 所属分类: 开发技术数学&算法

Feedback

# re: 计算字符串相似度的简易算法 2009-01-20 09:37 Anonymous
看看算法书再来吧  回复  更多评论
  

# re: 计算字符串相似度的简易算法[未登录] 2009-01-20 10:44 IceRao
使用向量吧。  回复  更多评论
  

# re: 计算字符串相似度的简易算法 2009-01-20 10:59 夜弓
字符串不是字节流
相似度是不好这样简单算的
比如
helloworld
hollywood
9个字母里面就有6个相同
显然不是那么简单回事  回复  更多评论
  

# re: 计算字符串相似度的简易算法 2009-01-20 16:29 Anonymous
计算编辑距离是个好想法,但还是有局限性的

另外你的相似度计算公式从分布上并不很natural,比如两个长度在30的单词,如果编辑距离为1,他们的相似度会比两个长度在5编辑距离为1的单词要更加高一些(我觉得这样的想法会更natural一点)。

从编辑距离本身的定义角度,我觉得还是不适合作为字符串相似的量度的,但可以作为辅助手段来对可能的错误输入产生提示。  回复  更多评论
  

# re: 计算字符串相似度的简易算法 2009-01-20 20:21 Jack.Wang
这么多人回复啊!
@Anonymous
恩,说的很好,谢谢啦!之前没看相关的算法书,只是有这个想法!顺便写了写!应该有更好的量度来计算两个字符串的相似度!等看看算法书或者有 blog 友贴贴!  回复  更多评论
  

# re: 计算字符串相似度的简易算法 2009-08-29 23:41 cricket
递归算法的复杂度非常高,动态规划算法能把复杂度降到O(M*N),改进后能到O(N+K^2),自动机和bit-parallelism算法甚至能到O(N)  回复  更多评论
  

# re: 计算字符串相似度的简易算法 2009-10-14 14:54 yeluolei
有那么简单么……  回复  更多评论
  

# re: 计算字符串相似度的简易算法 2009-12-17 14:02 黄凯
是的,使用编辑距离(尤其是改良后的Levenshtein算法)其算法复杂度可以缩短至O(2k+1)。不过lz的思想和Levenshtein算法的初衷本质上是一致的,还是值得赞赏的,可惜人家比你早很多年提出来~  回复  更多评论
  

# re: 计算字符串相似度的简易算法 2010-03-25 09:18 szx
老大,这是《编程之美》上的原题源代码  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: