字符串类似度算法(编辑距离Levenshtein Distance)

时间  2020-07-26 标签 字符串 类似 度 算法 编辑 距离 levenshtein distance

什么是Levenshtein

编辑距离（Edit Distance），最早是由俄国科学家Vladimir Levenshtein在1965年发明，用他的名字命名，又称Levenshtein距离。是指两个字串之间，由一个转成另外一个所需的最少编辑操做次数。许可的编辑操做包括将一个字符替换成另外一个字符，插入一个字符，删除一个字符。html

例如：将 jary 转成 jerry算法

jary --- jery (a->e)app

jery --- jerry ( ->r)oop

 

应用场景

DNA分析: 将DNA的一级序列如β-球蛋白基因的第一个外显子（Exon）转化为分子“结构图”，而后由所得“结构图”提取图的不变量，如分子链接性指数．以图的不变量做为自变量，再由类似度计算公式或距离公式进行类似度计算，其类似度的大小显示不一样物种间亲缘关系的远近程度，运用这种方法对人、猴及鼠等8个物种的β-球蛋白基因的第一个外显子的类似度进行计算，所得结果与生物学中的进化树符合得较好。性能

 

拼字检查：将每一个词与词典中的词条比较，英文单词每每须要作词干提取等规范化处理，若是一个词在词典中不存在，就被认为是一个错误，而后试图提示N个最可能要输入的词——拼写建议。经常使用的提示单词的算法就是列出词典中与原词具备最小编辑距离的词条。编码

 

语音辨识：语音识别技术，也被称为自动语音识别Automatic SpeechRecognition，(ASR)，其目标是将人类的语音中的词汇内容转换为计算机可读的输入，例如按键、二进制编码或者字符序列。url

而后以此做为系统输入，和你的语料库进行对比。就能够利用最小编辑距离来匹配识别。spa

 

抄袭侦测：串匹配算法是程序代码抄袭检测中标记匹配的重要算法，传统的模式匹配没法准确解决这个问题。.net

将原文本转化成可以描述程序特征的标记，这个标记能够是字符串、向量、xml文档等。而后用串匹配算法实现对标记序列的匹配查找，计算出类似度的值。大多数的抄袭检测系统都会给出这个值， 通常来讲，类似度越大说明抄袭的可能性越大。xml

 

实现原理

假设咱们肯定了两个字符串str1=“ste1“, str2=”ste2“。

 

1.    将两个字符串分别写到行和列中，第一行和第一列的值从0开始增加。

　

　

s

t

e

c

a

i

1

　

0

1

2

3

4

5

6

7

s

1


　

　

　

　

　

　

t

2

　

　

　

　

　

　

　

e

3

　

　

　

　

　

　

　

c

4

　

　

　

　

　

　

　

a

5

　

　

　

　

　

　

　

i

6

　

　

　

　

　

　

　


2.    A出得值取决于：左边的值(1)、上边的值(1)、左上角的值(0)。上面的值和左面的值都要求加1，这样获得1+1=2。A处因为是两个s相同，左上角的值加0.这样获得0+0=0。因此A处取他们里面最小的0. 

　

　

s

t

e

c

a

i

1

　

0

1

2

3

4

5

6

7

s

1

A

　

　

　

　

　

　

t

2

　

　

　

　

　

　

　

e

3

　

　

　

　

　

　

　

c

4

　

　

　

　

　

　

　

a

5

　

　

　

　

　

　

　

i

6

　

　

　

　

　

　

　

 

3.    同理，B出得值取决于：左边的值(0)、上边的值(2)、左上角的值(1)。上面的值和左面的值都要求加1，这样获得2+1=3, 0+1=1。 B处因为是t和s不相同，左上角的值加1.这样获得1+1=2。因此B处取他们里面最小的1.

　

　

s

t

e

c

a

i

1

　

0

1

2

3

4

5

6

7

s

1

0

B

　

　

　

　

　

t

2

　

　

　

　

　

　

　

e

3

　

　

　

　

　

　

　

c

4

　

　

　

　

　

　

　

a

5

　

　

　

　

　

　

　

i

6

　

　

　

　

　

　

　

 

4.    依次类推直到矩阵生成

　

　

s

t

e

c

a

i

1

　

0

1

2

3

4

5

6

7

s

1

0

1

2

3

4

5

6

t

2

1

0

1

2

3

4

5

e

3

2

1

0

1

2

3

4

c

4

3

2

1

0

1

2

3

a

5

4

3

2

1

0

1

2

i

6

5

4

3

2

1

0

1

5.      最后获得他们的距离=1，根据类似度计算公式：1 – 1 / Math.max(“stecai1”.length, “stecai2”.length) =0.857

 

Java代码实现

public final class EditDistance implements StringDistance {

    /**

     * {@inheritDoc}

     */

    public float getDistance(String s1, Strings2) {

        char[]sa;

        int n;

        int p[]; // 'previous' cost array, horizontally

        int d[]; // cost array, horizontally

        int _d[]; // placeholder to assist in swapping p and d

 

        sa = s1.toCharArray();

        n = sa.length;

        p = newint[n + 1];

        d = newint[n + 1];

 

        final int m = s2.length();

        if (n == 0 ||m == 0) {

            if (n ==m) {

                return 1;

            } else {

                return 0;

            }

        }

 

        // indexes into strings s and t

        int i; // iterates through s

        int j; // iterates through t

        char t_j; // jth character of t

        int cost; // cost

 

        for (i = 0;i <= n; i++) {

            p[i] =i;

        }

 

        for (j = 1;j <= m; j++) {

            t_j = s2.charAt(j - 1);

            d[0] = j;

 

            for (i = 1;i <= n; i++) {

                cost = sa[i - 1] == t_j ? 0 : 1;

                // minimum of cell to the left+1, to the top+1, diagonally left

                // and up +cost

                d[i] = Math.min(Math.min(d[i - 1] + 1,p[i] + 1), p[i - 1]

                        + cost);

            }

 

            // copy current distance counts to 'previous row' distance counts

            _d = p;

            p = d;

            d = _d;

        }

 

        // our last action in the above loop was to switch d and p, so p now

        // actually has the most recent cost counts

        return 1.0f - ((float)p[n] / Math.max(s2.length(),sa.length));

    }

}

 


局限性

因为须要利用LD矩阵，故空间复杂度为O(MN)。这个在两个字符串都比较短小的状况下，能得到不错的性能。不过，若是字符串比较长的状况下，就须要极大的空间存放矩阵。例如：两个字符串都是20000字符，则LD矩阵的大小为：20000*20000*2=800000000Byte=800MB。

 

参考：

1.        http://en.wikipedia.org/wiki/Levenshtein_distance

2.        http://www.cnblogs.com/ivanyb/archive/2011/11/25/2263356.html

3.        http://www.cnblogs.com/ac1985482/p/Levenshtein.html

4.        http://www.it165.net/pro/html/201306/6105.html

http://baike.baidu.com/link?url=heRGyycdv0HUWhVvTcG05wGQ17hBl2au4ZaYsAbFXj0guI59DjlRHJ7QGbuy5k8LpiIsZqT9POiuwgwJhZTMgmemJZwNqHm_amrFHPKYAb0GNBdMLiJCt9xjOr69HJq71SEXGc-KqqTlNJY7LtwIV12lD23F95ikzk-4-7k3Ysq
联系我们 沪ICP备2021010478号-7