Levenshtein距离与后跟踪在PHP

我试图使用Levenshtein距离算法在 PHP中对齐字符串.问题是我的后跟踪代码在所有情况下都不能正常工作.例如,当第二个数组在开头插入行时.那么后面的跟踪只能在i = 0的时候进行.

如何正确实施追溯Levenshtein距离？

Levenshtein距离,$s和$t是字符串(行)的数组

function match_rows($s,$t)
{
$m = count($s);
$n = count($t);

for($i = 0; $i <= $m; $i++) $d[$i][0] = $i;
for($j = 0; $j <= $n; $j++) $d[0][$j] = $j;

for($i = 1; $i <= $m; $i++)
{
    for($j = 1; $j <= $n; $j++)
    {
        if($s[$i-1] == $t[$j-1])
        {
            $d[$i][$j] = $d[$i-1][$j-1];
        }
        else
        {
            $d[$i][$j] = min($d[$i-1][$j],$d[$i][$j-1],$d[$i-1][$j-1]) + 1;
        }
    }
}

// backtrace
$i = $m;
$j = $n;
while($i > 0 && $j > 0)
{
    $min = min($d[$i-1][$j],$d[$i-1][$j-1]);

    switch($min)
    {
        // equal or substitution
        case($d[$i-1][$j-1]):
            if($d[$i][$j] != $d[$i-1][$j-1])
            {
                // substitution
                $sub['i'][] = $i;
                $sub['j'][] = $j;
            }
            $i = $i - 1;
            $j = $j - 1;
            break;

        // insertion
        case($d[$i][$j-1]):
            $ins[] = $j;
            $j = $j - 1;
            break;

        // deletion
        case($d[$i-1][$j]):
            $del[] = $i;
            $i = $i - 1;
            break;
    }
}

这不是挑剔的,而是帮助您找到所需的答案(并改进实现).

您使用的算法是Wagner-Fischer算法,而不是Levenshtein算法.此外,Levenshtein距离不用于对齐字符串.它是严格的距离测量.

有两种类型的对齐方式：全局和局部.全局对齐用于最小化两个整个字符串之间的距离.示例：“REACH”上的全局对齐“RACE”,您将获得“RxACx”. x是差距.

一般来说,这是Needleman-Wunsch算法,它与Wagner-Fischer算法非常相似.本地对齐查找长字符串中的子字符串,并将短字符串与长字符串的子字符串之间的差异最小化.

示例：“UMBRELLA”上的本地对齐“BELL”,您可以在“BRELL”上对齐“BxELL”. Smith-Waterman算法又一次与Wagner-Fischer算法非常相似.

我希望这有助于您更好地定义所需的准确类型.

原文链接：https://www.f2er.com/php/131852.html

Levenshtein距离与后跟踪在PHP

猜你在找的PHP相关文章