我试图使用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算法非常相似.
我希望这有助于您更好地定义所需的准确类型.
