官方博客
官方博客

编辑距离及汉明距离的php实现

原文链接:https://yq.aliyun.com/articles/539049

在计算字符串或图形的相似度时,常用的两个算法,一个是编辑距离,另一个是汉明距离。


简单点说:

编辑距离是通过几次编辑能把一个字符串变成另一个字符串

汉明距离是对应位置进行比较,找出不同的字符个数

想了解详情的请自行搜索。


以下是他们的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++)
    {
        $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


2019-10-01 18:51:02
0 热度