PHP项目怎么实现Jaro-Winkler距离？

本文目录导读：

1. 完整实现代码
2. 简化版本（如果不想使用类）
3. 安装第三方库（推荐）
4. 算法说明

PHP 实现 Jaro-Winkler 距离可以通过以下步骤来完成，Jaro-Winkler 距离是 Jaro 距离的改进版本,它给予起始部分匹配的字符串更高的分数。

完整实现代码

<?php
class JaroWinkler {
    /**
     * 计算两个字符串的 Jaro-Winkler 距离
     * 
     * @param string $s1 第一个字符串
     * @param string $s2 第二个字符串
     * @param float $prefixScale 前缀权重缩放因子 (默认 0.1)
     * @return float 返回相似度分数 (0-1)
     */
    public static function distance($s1, $s2, $prefixScale = 0.1) {
        $s1 = (string) $s1;
        $s2 = (string) $s2;
        // 如果字符串相等，直接返回 1.0
        if ($s1 === $s2) {
            return 1.0;
        }
        // 计算 Jaro 距离
        $jaroDistance = self::jaroDistance($s1, $s2);
        // 计算公共前缀长度（最多 4 个字符）
        $prefix = 0;
        $minLen = min(strlen($s1), strlen($s2));
        $maxPrefixLength = min(4, $minLen);
        for ($i = 0; $i < $maxPrefixLength; $i++) {
            if ($s1[$i] === $s2[$i]) {
                $prefix++;
            } else {
                break;
            }
        }
        // Jaro-Winkler 调整
        $jaroWinklerDistance = $jaroDistance + ($prefix * $prefixScale * (1.0 - $jaroDistance));
        // 确保结果在 0-1 范围内
        return min(1.0, max(0.0, $jaroWinklerDistance));
    }
    /**
     * 计算 Jaro 距离
     */
    private static function jaroDistance($s1, $s2) {
        $len1 = strlen($s1);
        $len2 = strlen($s2);
        if ($len1 == 0 && $len2 == 0) {
            return 1.0;
        }
        if ($len1 == 0 || $len2 == 0) {
            return 0.0;
        }
        // 匹配距离阈值
        $matchDistance = (int) (max($len1, $len2) / 2) - 1;
        if ($matchDistance < 0) {
            $matchDistance = 0;
        }
        // 标记是否匹配
        $match1 = array_fill(0, $len1, false);
        $match2 = array_fill(0, $len2, false);
        $matches = 0;
        // 查找匹配字符
        for ($i = 0; $i < $len1; $i++) {
            $start = max(0, $i - $matchDistance);
            $end = min($len2, $i + $matchDistance + 1);
            for ($j = $start; $j < $end; $j++) {
                if (!$match2[$j] && $s1[$i] === $s2[$j]) {
                    $match1[$i] = true;
                    $match2[$j] = true;
                    $matches++;
                    break;
                }
            }
        }
        if ($matches == 0) {
            return 0.0;
        }
        // 计算换位数
        $transpositions = 0;
        $j = 0;
        for ($i = 0; $i < $len1; $i++) {
            if ($match1[$i]) {
                while (!$match2[$j]) {
                    $j++;
                }
                if ($s1[$i] !== $s2[$j]) {
                    $transpositions++;
                }
                $j++;
            }
        }
        $transpositions = $transpositions / 2;
        // 计算 Jaro 距离
        return ($matches / $len1 + $matches / $len2 + ($matches - $transpositions) / $matches) / 3.0;
    }
}
// 使用示例
$s1 = "MARTHA";
$s2 = "MARHTA";
echo "字符串1: '" . $s1 . "'\n";
echo "字符串2: '" . $s2 . "'\n";
echo "Jaro-Winkler 距离: " . JaroWinkler::distance($s1, $s2) . "\n";
echo "Jaro 距离: " . JaroWinkler::jaroDistance($s1, $s2) . "\n\n";
// 更多测试
$testCases = [
    ["DWAYNE", "DUANE"],
    ["DIXON", "DICKSONX"],
    ["JELLYFISH", "SMELLYFISH"],
    ["HELLO", "HELLO"],
    ["ABC", "XYZ"],
];
foreach ($testCases as $test) {
    echo $test[0] . " vs " . $test[1] . ": " . 
         JaroWinkler::distance($test[0], $test[1]) . "\n";
}

简化版本（如果不想使用类）

<?php
/**
 * 计算 Jaro-Winkler 距离（简化版函数）
 */
function jaroWinklerDistance($s1, $s2, $prefixScale = 0.1) {
    $s1 = (string) $s1;
    $s2 = (string) $s2;
    if ($s1 === $s2) return 1.0;
    $len1 = strlen($s1);
    $len2 = strlen($s2);
    if ($len1 == 0 && $len2 == 0) return 1.0;
    if ($len1 == 0 || $len2 == 0) return 0.0;
    // 计算 Jaro 距离
    $matchDistance = (int) (max($len1, $len2) / 2) - 1;
    if ($matchDistance < 0) $matchDistance = 0;
    $match1 = array_fill(0, $len1, false);
    $match2 = array_fill(0, $len2, false);
    $matches = 0;
    for ($i = 0; $i < $len1; $i++) {
        $start = max(0, $i - $matchDistance);
        $end = min($len2, $i + $matchDistance + 1);
        for ($j = $start; $j < $end; $j++) {
            if (!$match2[$j] && $s1[$i] === $s2[$j]) {
                $match1[$i] = true;
                $match2[$j] = true;
                $matches++;
                break;
            }
        }
    }
    if ($matches == 0) return 0.0;
    $transpositions = 0;
    $j = 0;
    for ($i = 0; $i < $len1; $i++) {
        if ($match1[$i]) {
            while (!$match2[$j]) $j++;
            if ($s1[$i] !== $s2[$j]) $transpositions++;
            $j++;
        }
    }
    $transpositions /= 2;
    $jaroDistance = ($matches / $len1 + $matches / $len2 + 
                    ($matches - $transpositions) / $matches) / 3.0;
    // 计算公共前缀
    $prefix = 0;
    $minLen = min($len1, $len2);
    $maxPrefixLength = min(4, $minLen);
    for ($i = 0; $i < $maxPrefixLength; $i++) {
        if ($s1[$i] === $s2[$i]) {
            $prefix++;
        } else {
            break;
        }
    }
    // Jaro-Winkler 调整
    $distance = $jaroDistance + $prefix * $prefixScale * (1.0 - $jaroDistance);
    return min(1.0, max(0.0, $distance));
}
// 使用示例
echo jaroWinklerDistance("MARTHA", "MARHTA"); // 输出: 0.9444...

安装第三方库（推荐）

如果不想自己实现，可以使用 Composer 安装现成的库：

composer require patrick95/php-jaro-winkler

使用方式：

require 'vendor/autoload.php';
use PhpJaroWinkler\JaroWinkler;
$distance = JaroWinkler::distance('MARTHA', 'MARHTA');
echo $distance; // 输出: 0.9444

算法说明

1. Jaro 距离：基于三个因素：

   • 匹配字符数
   • 字符串长度
   • 换位字符数

2. Winkler 调整：如果字符串前几个字符相同，加权提高分数（最多前4个字符，权重默认0.1）

3. 返回值：0.0（完全不同）到 1.0（完全相同）

这个实现在字符串匹配、拼写检查和数据去重等场景中非常有用。