PHP编辑距离算相似度

wen PHP项目 2026-08-11 182

本文目录导读：

PHP编辑距离算相似度

使用PHP内置函数
自定义实现（动态规划）
增强版相似度计算
实用函数集合
性能优化版本
使用建议

我来为你介绍几种在PHP中计算文本编辑距离（Levenshtein距离）及相似度的方法。

使用PHP内置函数

PHP提供了内置的levenshtein()函数，这是最简单的实现方式：

<?php
// 基本用法
$str1 = "hello world";
$str2 = "hello php";
$distance = levenshtein($str1, $str2);
echo "编辑距离: " . $distance . "\n"; // 输出: 6
// 计算相似度（百分比）
function similarity_percentage($str1, $str2) {
    $distance = levenshtein($str1, $str2);
    $maxLen = max(strlen($str1), strlen($str2));
    if ($maxLen == 0) {
        return 100.0;
    }
    $similarity = (1 - $distance / $maxLen) * 100;
    return round($similarity, 2);
}
echo "相似度: " . similarity_percentage("hello world", "hello php") . "%\n";
?>

自定义实现（动态规划）

如果需要更复杂的编辑距离算法（如支持自定义权重），可以自己实现：

<?php
class EditDistance {
    // 标准编辑距离（Levenshtein）
    public static function levenshteinDistance($str1, $str2, $costInsert = 1, $costDelete = 1, $costReplace = 1) {
        $len1 = strlen($str1);
        $len2 = strlen($str2);
        // 初始化矩阵
        $dp = array();
        for ($i = 0; $i <= $len1; $i++) {
            $dp[$i][0] = $i * $costDelete;
        }
        for ($j = 0; $j <= $len2; $j++) {
            $dp[0][$j] = $j * $costInsert;
        }
        // 动态规划计算
        for ($i = 1; $i <= $len1; $i++) {
            for ($j = 1; $j <= $len2; $j++) {
                $cost = ($str1[$i-1] == $str2[$j-1]) ? 0 : $costReplace;
                $dp[$i][$j] = min(
                    $dp[$i-1][$j] + $costDelete,     // 删除
                    $dp[$i][$j-1] + $costInsert,     // 插入
                    $dp[$i-1][$j-1] + $cost         // 替换或匹配
                );
            }
        }
        return $dp[$len1][$len2];
    }
    // 计算相似度
    public static function similarity($str1, $str2) {
        $distance = self::levenshteinDistance($str1, $str2);
        $maxLen = max(strlen($str1), strlen($str2));
        if ($maxLen == 0) return 100;
        return (1 - $distance / $maxLen) * 100;
    }
}
// 使用示例
$str1 = "kitten";
$str2 = "sitting";
$distance = EditDistance::levenshteinDistance($str1, $str2);
$similarity = EditDistance::similarity($str1, $str2);
echo "编辑距离: $distance\n";
echo "相似度: " . round($similarity, 2) . "%\n";
?>

增强版相似度计算

<?php
function getSimilarity($str1, $str2, $multibyte = true) {
    if ($multibyte) {
        return getSimilarityMultibyte($str1, $str2);
    } else {
        return getSimilarityAscii($str1, $str2);
    }
}
// ASCII版本
function getSimilarityAscii($str1, $str2) {
    $distance = levenshtein($str1, $str2);
    $maxLen = max(strlen($str1), strlen($str2));
    if ($maxLen == 0) return 100.0;
    return (1 - $distance / $maxLen) * 100;
}
// 支持多字节字符（中文等）
function getSimilarityMultibyte($str1, $str2) {
    $chars1 = preg_split('//u', $str1, -1, PREG_SPLIT_NO_EMPTY);
    $chars2 = preg_split('//u', $str2, -1, PREG_SPLIT_NO_EMPTY);
    $distance = mb_levenshtein($chars1, $chars2);
    $maxLen = max(count($chars1), count($chars2));
    if ($maxLen == 0) return 100.0;
    return (1 - $distance / $maxLen) * 100;
}
// 多字节Levenshtein
function mb_levenshtein($chars1, $chars2) {
    $len1 = count($chars1);
    $len2 = count($chars2);
    $dp = array();
    for ($i = 0; $i <= $len1; $i++) {
        $dp[$i][0] = $i;
    }
    for ($j = 0; $j <= $len2; $j++) {
        $dp[0][$j] = $j;
    }
    for ($i = 1; $i <= $len1; $i++) {
        for ($j = 1; $j <= $len2; $j++) {
            $cost = ($chars1[$i-1] === $chars2[$j-1]) ? 0 : 1;
            $dp[$i][$j] = min(
                $dp[$i-1][$j] + 1,     // 删除
                $dp[$i][$j-1] + 1,     // 插入
                $dp[$i-1][$j-1] + $cost // 替换或匹配
            );
        }
    }
    return $dp[$len1][$len2];
}
// 测试
$str1 = "你好世界";
$str2 = "你好世界！";
echo "相似度（支持中文）: " . round(getSimilarity($str1, $str2), 2) . "%\n";
?>

实用函数集合

<?php
class TextSimilarity {
    // 获取编辑距离
    public static function distance($str1, $str2) {
        return levenshtein($str1, $str2);
    }
    // 获取相似度百分比
    public static function percent($str1, $str2, $round = 2) {
        $distance = self::distance($str1, $str2);
        $maxLen = max(strlen($str1), strlen($str2));
        if ($maxLen == 0) return 100;
        $similarity = (1 - $distance / $maxLen) * 100;
        return round($similarity, $round);
    }
    // 判断是否相似（阈值判断）
    public static function isSimilar($str1, $str2, $threshold = 80) {
        $similarity = self::percent($str1, $str2);
        return $similarity >= $threshold;
    }
    // 模糊匹配，返回最佳匹配
    public static function findBestMatch($input, array $candidates) {
        $bestMatch = null;
        $bestScore = 0;
        foreach ($candidates as $candidate) {
            $score = self::percent($input, $candidate);
            if ($score > $bestScore) {
                $bestScore = $score;
                $bestMatch = $candidate;
            }
        }
        return array(
            'match' => $bestMatch,
            'score' => $bestScore
        );
    }
}
// 使用示例
$s = new TextSimilarity();
// 测试不同字符串
$tests = array(
    array("hello world", "hello php"),
    array("apple", "apples"),
    array("PHP Programming", "PHP Programming Language"),
    array("test", "test")
);
foreach ($tests as $test) {
    $percent = $s->percent($test[0], $test[1]);
    echo "编辑距离: " . $s->distance($test[0], $test[1]) . 
         ", 相似度: " . $percent . "%\n";
}
// 模糊匹配示例
$candidates = array("PHP Tutorial", "JavaScript Guide", "Python Manual", "PHP Basics");
$result = $s->findBestMatch("PHP Learning", $candidates);
echo "最佳匹配: " . $result['match'] . " (得分: " . $result['score'] . "%)";
?>

性能优化版本

<?php
// 为长字符串优化的版本
function levenshtein_optimized($str1, $str2, $maxDistance = null) {
    $len1 = strlen($str1);
    $len2 = strlen($str2);
    // 快速判断
    if (abs($len1 - $len2) > $maxDistance) {
        return ($maxDistance !== null) ? $maxDistance + 1 : null;
    }
    if ($len1 == 0) return $len2;
    if ($len2 == 0) return $len1;
    // 使用一行数组优化内存
    $prevRow = range(0, $len2);
    for ($i = 1; $i <= $len1; $i++) {
        $currentRow = array($i);
        $char1 = $str1[$i-1];
        for ($j = 1; $j <= $len2; $j++) {
            $insertCost = $currentRow[$j-1] + 1;
            $deleteCost = $prevRow[$j] + 1;
            $replaceCost = $prevRow[$j-1] + ($char1 != $str2[$j-1]);
            $currentRow[$j] = min($insertCost, $deleteCost, $replaceCost);
        }
        $prevRow = $currentRow;
    }
    return $prevRow[$len2];
}
?>