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

算法设计背景：

最近设计知识管理系统的资源导入功能，为了尽量的做到组件化，方便扩展，方便其他模块使用。简化组件提供的和需要的接口，设计并实现了基于 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