分享程序员开发的那些事...
更新时间：2022-10-02 14:32:32
在计算字符串或图形的相似度时，常用的两个算法，一个是编辑距离，另一个是汉明距离。
简单点说：
编辑距离是通过几次编辑能把一个字符串变成另一个字符串
汉明距离是对应位置进行比较，找出不同的字符个数
想了解详情的请自行搜索。
以下是他们的php代码实现。
|
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
|
<?php/** * 计算编辑距离
*
* @param string $s1
* @param string $s2
*/
function levDist($s1, $s2)
{ $len1 = strlen($s1);
$len2 = strlen($s2);
if($len1 == 0)
{
return $len2;
}
if($len2 == 0)
{
return $len1;
}
for($i = 0; $i <= $len1; $i++)
{
$matrix[$i][0] = 0;
}
for($j = 0; $j <= $len2; $j++)
{
$matrix[0][$j] = 0;
}
for($i = 1; $i <= $len1; $i++)
{
$ch1 = $s1[$i - 1];
for($j = 1; $j <= $len2; $j++)
{
$ch2 = $s2[$j - 1];
$temp = $ch1 == $ch2 ? 0 : 1;
$arr = array(
$matrix[$i - 1][$j] + 1,
$matrix[$i][$j - 1] + 1,
$matrix[$i - 1][$j - 1] + $temp
);
$matrix[$i][$j] = min($arr);
}
}
return $matrix[$len1][$len2];
}/** * 计算汉明距离
*
* @param string $s1
* @param string $s2
* @return boolean number
*/
function hamDist($s1, $s2)
{ $len1 = strlen($s1);
$len2 = strlen($s2);
if($len1 != $len2)
{
return false;
}
$dist = 0;
for($i = 0; $i < $len1; $i++)
{
if($s1[$i] != $s2[$i])
{
$dist++;
}
}
return $dist;
}$s1 = "abcde";
$s2 = "acdeb";
echo levDist($s1, $s2);// 输出2
echo hamDist($s1, $s2);// 输出4
|