0%

两个字符串的匹配度

在某个项目中遇到判断字符串相似程度的需求,google 了一下,原来python标准库里面没有这样的函数,反而是 PHP 里面有一个similar_text()函数,果然PHP 是世界上最好的编程语言

函数原型

similar_text 的原型是这样的

1
int similar_text(string str1, string str2 [, float percent])

他返回的是两个字符串中能匹配的字符数量,如果有第三个参数,就修改第三个参数的值为 [0, 100] 区间的一个浮点数,表示匹配程度

例子

1
2
3
4
5
6
7
8
9
10
11
12
$number = similar_text('aaaa', 'aaaa', $percent);
var_dump($number); // int(4)
var_dump($percent); // int(100)


$number = similar_text('aaaa', 'aaaabbbb', $percent);
var_dump($number); // int(4)
var_dump($percent); // int(67)

$number = similar_text('abcdef', 'aabcdefg', $percent);
var_dump($number); // int(6)
var_dump($percent); // int(86)

原理分析

similar_text 代码可以在 github 找到,搜索PHP_FUNCTION(similar_text) 就可以了

研究了一下发现,主要分为三步:

  1. 找出两个字符串中相同部分最长的一段
  2. 再用同样的方法在剩下的两段中分别找出相同部分最长的一段,以此类推,直到没有任何相同部分
  3. 相似度 = 所有相同部分的长度之和 * 200.0 / 两个字符串的长度之和

下面是实现相关的代码,中文注释是我加上去进行说明的

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// 找出两个字符串中相同部分最长的一段
static void php_similar_str(const char *txt1, size_t len1, const char *txt2, size_t len2, size_t *pos1, size_t *pos2, size_t *max)
{
char *p, *q;
char *end1 = (char *) txt1 + len1;
char *end2 = (char *) txt2 + len2;
size_t l;

*max = 0;
// 以第一个字符串为基准开始遍历
for (p = (char *) txt1; p < end1; p++) {
// 遍历第二个字符串
for (q = (char *) txt2; q < end2; q++) {
// 发现有字符相同,继续循环找,l为相同部分的长度
for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
// 记录最长的l,和他在两个字符串的位置
if (l > *max) {
*max = l;
*pos1 = p - txt1;
*pos2 = q - txt2;
}
}
}
}

// 计算两个字符串的相同部分的总长度
static size_t php_similar_char(const char *txt1, size_t len1, const char *txt2, size_t len2)
{
size_t sum;
size_t pos1 = 0, pos2 = 0, max;

// 找出两个字符串相同部分最长的一段
php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);

// 这里是对sum的初始赋值,也是对max值的判断
// 如果 max == 0,表示两个字符串没有任何相同的字符,则不会进行递归
if ((sum = max)) {
// 对前半段递归,相同段长度累加
if (pos1 && pos2) {
sum += php_similar_char(txt1, pos1,
txt2, pos2);
}
// 对后半段递归,相同段长度累加
if ((pos1 + max < len1) && (pos2 + max < len2)) {
sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,
txt2 + pos2 + max, len2 - pos2 - max);
}
}

return sum;
}

/* {{{ proto int similar_text(string str1, string str2 [, float percent])
Calculates the similarity between two strings */
// PHP函数定义
PHP_FUNCTION(similar_text)
{
zend_string *t1, *t2;
zval *percent = NULL;
int ac = ZEND_NUM_ARGS();
size_t sim;

// 检查参数合法性
if (zend_parse_parameters(ZEND_NUM_ARGS(), "SS|z/", &t1, &t2, &percent) == FAILURE) {
return;
}

if (ac > 2) {
convert_to_double_ex(percent);
}

// 如果两个字符串长度都为0,返回0
if (ZSTR_LEN(t1) + ZSTR_LEN(t2) == 0) {
if (ac > 2) {
Z_DVAL_P(percent) = 0;
}

RETURN_LONG(0);
}

// 调用上面的函数,计算两个字符串的相似度
sim = php_similar_char(ZSTR_VAL(t1), ZSTR_LEN(t1), ZSTR_VAL(t2), ZSTR_LEN(t2));

// 如果有第三个参数,则改变计算方式
if (ac > 2) {
Z_DVAL_P(percent) = sim * 200.0 / (ZSTR_LEN(t1) + ZSTR_LEN(t2));
}

RETURN_LONG(sim);
}

进行移植

因为前文提到的项目主要是用 python 写的,所以我将 similar_text 这个函数移植到了 python,具体代码如下

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
# -*- coding: utf-8 -*-

def similar_str(str1, str2):
"""
return the len of longest string both in str1 and str2
and the positions in str1 and str2
"""
max_len = tmp = pos1 = pos2 = 0
len1, len2 = len(str1), len(str2)

for p in range(len1):
for q in range(len2):
tmp = 0
while p + tmp < len1 and q + tmp < len2 \
and str1[p + tmp] == str2[q + tmp]:
tmp += 1

if tmp > max_len:
max_len, pos1, pos2 = tmp, p, q

return max_len, pos1, pos2


def similar_char(str1, str2):
"""
return the total length of longest string both in str1 and str2
"""
max_len, pos1, pos2 = similar_str(str1, str2)
total = max_len

if max_len != 0:
if pos1 and pos2:
total += similar_char(str1[:pos1], str2[:pos2])

if pos1 + max_len < len(str1) and pos2 + max_len < len(str2):
total += similar_char(str1[pos1 + max_len:], str2[pos2 + max_len:]);

return total


def similar_text(str1, str2):
"""
return a int value in [0, 100], which stands for match level
"""
if not (isinstance(str1, str) or isinstance(str1, unicode)):
raise TypeError("must be str or unicode")
elif not (isinstance(str2, str) or isinstance(str2, unicode)):
raise TypeError("must be str or unicode")
elif len(str1) == 0 and len(str2) == 0:
return 0.0
else:
return int(similar_char(str1, str2) * 200.0 / (len(str1) + len(str2)))

也可以在 github 上查看

参考

PHP source code