字符串的相似度

发表于

Levenshtein Distance算法

Levenshtein Distance 算法，又叫编辑距离算法，是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括：

  • 替换一个字符

  • 插入一个字符

  • 删除一个字符

一般来说，编辑距离越小，两个串的相似度越大。相似度计算方式为：1 - (distance / maxLen)

注：distance 是所需的最少操作次数，maxLen是两个字符串长度的最大值。


算法实现原理图解

  1. 首先是有两个字符串，这里写一个简单的 abc 和 abe
  2. 将字符串想象成下面的结构

A处是一个标记，为了方便讲解

abc a b c
abe 0 1 2 3
a 1 A处
b 2
e 3
  1. 来计算A处出得值，它的值取决于：左边的值、上边的值、左上角的值

按照Levenshtein distance的意思：

  • 上面的值加 1 ，得到 1+1=2 插入或删除
  • 左面的值加 1 ，得到 1+1=2 插入或删除
  • 左上角的值根据字符是否相同，相同加 0 ，不同加 1 。替换

A处由于是两个 a 相同，左上角的值加 0 ，得到 0+0=0 ，然后从我们上面计算出来的 2，2，0 三个值中选取最小值，所以 A 处的值为 0 。

  1. 于是表成为下面的样子
abc a b c
abe 0 1 2 3
a 1 0
b 2 B处
e 3

在B处会同样得到三个值，左边计算后为 3 ，上边计算后为 1 ，在B处由于对应的字符为 a、b，不相等，所以左上角应该在当前值的基础上加 1 ，这样得到 1+1=2 ，在（3,1,2）中选出最小的为 B 处的值。

5.于是表就更新了
abc a b c
abe 0 1 2 3
a 1 0
b 2 1
e 3 C处

C处计算后：上面的值为 2 ，左边的值为 4 ，左上角的：a 和 e 不相同，所以加 1 ，即 2+1 ，左上角的为 3 。

在（2,4,3）中取最小的为 C 处的值。

6.于是依次推得到
a b c
0 1 2 3
a 1 A处 0 D处 1 G处 2
b 2 B处 1 E处 0 H处 1
e 3 C处 2 F处 1 I处 1

I处: 表示 abc 和 abe 有1个需要编辑的操作

I处的值需要通过动态规划方法来计算，因此需要获取一些额外的信息：

  • A处: 表示a和a需要有0个操作
  • B处: 表示ab和a需要有1个操作
  • C处: 表示abe和a需要有2个操作
  • D处: 表示a和ab需要有1个操作
  • E处: 表示ab和ab需要有0个操作
  • F处: 表示abe和ab需要有1个操作
  • G处: 表示a和abc需要有2个操作
  • H处: 表示ab和abc需要有1个操作
  • I处: 表示abe和abc需要有1个操作


主要应用

  • Spell checking 检查拼写
  • Speech recognition 语音识别
  • DNA analysis DNA分析
  • Plagiarism detection 检测抄袭


JS实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
const LevenshteinDistance = {
    _str1: null,
    _str3: null,
    _matrix: null,

    _isString: function(s) {
        return Object.prototype.toString.call(s) === '[object String]';
    },

    _isNumber: function(s) {
        return Object.prototype.toString.call(s) === '[object Number]';
    },

    init: function(str1, str2) {
        if (!this._isString(str1) || !this._isString(str2)) return;
        this._str1 = str1;
        this._str2 = str2;
        str1.length && str2.length && this._createMatrix(str1.length + 1, str2.length + 1);
        this._matrix && this._initMatrix();
        return this;
    },

    get: function() {
        return 1 - this._getDistance() / Math.max(this._str1.length, this._str2.length);
    },

    //计算编辑距离
    _getDistance: function() {
        var len1 = this._str1.length,
            len2 = this._str2.length;
        if (!len1 || !len2) return Math.max(len1, len2);
        var str1 = this._str1.split(''),
            str2 = this._str2.split('');
        var i = 0,
            j = 0,
            temp = 0;
        while (i++ < len1) {
            j = 0;
            while (j++ < len2) {
                temp = str1[i - 1] === str2[j - 1] ? 0 : 1;
                this._matrix[i][j] = Math.min(
                    this._matrix[i - 1][j] + 1,
                    this._matrix[i][j - 1] + 1,
                    this._matrix[i - 1][j - 1] + temp
                );
            }
        }
        return this._matrix[i - 1][j - 1];
    },

    /*
     * 初始化矩阵
     * 为第一行、第一列赋值
     */
    _initMatrix: function() {
        var cols = this._matrix[0].length,
            rows = this._matrix.length;
        var l = Math.max(cols, rows);
        while (l--) {
            cols - 1 >= l && (this._matrix[0][l] = l);
            rows - 1 >= l && (this._matrix[l][0] = l);
        }
    },

    /*
     * 创建矩阵
     * n:行
     * m:列
     */
    _createMatrix: function(n, m) {
        if (!this._isNumber(n) || !this._isNumber(m) || n < 1 || m < 1) return;
        this._matrix = new Array(n), i = 0;
        while (i < n) this._matrix[i++] = new Array(m);
    }
}
1
LevenshteinDistance.init('omiga.org','omiga').get();