天天看點

計算字元串相似度的簡易算法

計算字元串相似度的簡易算法

算法設計背景:

最近設計知識管理系統的資源導入功能,為了盡量的做到元件化,友善擴充,友善其他子產品使用。簡化元件提供的和需要的接口,設計并實作了基于 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

計算字元串相似度的簡易算法

33

計算字元串相似度的簡易算法

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

計算字元串相似度的簡易算法

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

計算字元串相似度的簡易算法

繼續閱讀