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

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

简单点说：

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

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

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

以下是他们的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

本文出自 “凡星的技术博客” 博客，请务必保留此出处http://ustb80.blog.51cto.com/6139482/1569542