当前位置: 首页> 最新文章列表> PHP 实现汉明距离总和计算示例

PHP 实现汉明距离总和计算示例

gitbox 2025-06-30

什么是汉明距离?

汉明距离是衡量两个等长字符串之间不同字符数量的方法。具体来说,两个字符串对应位置上字符不同的个数即为汉明距离。

例如,考虑以下两个字符串:

"abcdefgh" 与 "abcxtdhy"

它们的汉明距离为4,因为它们在第4、5、6和8个位置上字符不同。

PHP 计算汉明距离总和的实例

假设我们有一个包含多个等长二进制字符串的数组,如下所示:


// 一个包含多个等长二进制字符串的数组
$array = ["1100", "1010", "1111", "0000"];

问题是:如何计算这些字符串两两之间的汉明距离总和呢?我们可以先定义一个计算汉明距离的函数:


/**
 * 计算汉明距离
 * @param string $str1
 * @param string $str2
 * @return int
 */
function hammingDistance($str1, $str2) {
    $dist = 0;
    $n = strlen($str1);
    for ($i = 0; $i < $n; $i++) {
        if ($str1[$i] !== $str2[$i]) {
            $dist++;
        }
    }
    return $dist;
}

该函数通过遍历两个字符串的每个字符,如果字符不同,则计数器加1。

接下来,我们可以使用双重循环来计算所有字符串的汉明距离总和:


$len = count($array);
$sum = 0;
for ($i = 0; $i < $len; $i++) {
    for ($j = $i + 1; $j < $len; $j++) {
        $sum += hammingDistance($array[$i], $array[$j]);
    }
}
echo $sum; // 输出 10

通过这个过程,我们可以得出该数组中所有二进制字符串两两之间的汉明距离总和。

示例解释

假设数组为["1100", "1010", "1111", "0000"],每对二进制字符串的汉明距离如下:

1100
1010   2
1111 3 1
0000 4 2 5

因此,汉明距离总和为10。

总结

本文介绍了汉明距离的基本概念,并提供了一个PHP示例,演示了如何计算多个二进制字符串之间的汉明距离总和。汉明距离在数据传输、加密和纠错等领域有着广泛应用,掌握这一方法可以帮助我们更好地解决相关问题。