在计算字符串或图形的相似度时，常用的两个算法，一个是编辑距离，另一个是汉明距离。
简单点说：
编辑距离是通过几次编辑能把一个字符串变成另一个字符串
汉明距离是对应位置进行比较，找出不同的字符个数
想了解详情的请自行搜索。
以下是他们的php代码实现。
计算
安全
数据库
网络和加速
企业服务
<?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++)
{
$ch2 = $s1[$i - 1];
for($j = 1; $j <= $len2; $j++)
{
$ch3 = $s2[$j - 1];
$temp = $ch2 == $ch3 ? 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亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
