編輯距離及漢明距離的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++)
    {
        $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