Я ищу реализации алгоритма Damerau–Levenshtein для PHP, но кажется, что я ничто не могу найти со своим другом Google. До сих пор я должен использовать PHP, реализованную Levenshtein (без перемещения Damerau, которое очень важно), или получите код первоисточника (в C, C++, C#, Perl) и запись (переводят) его в PHP.
У кого-либо есть знание реализации PHP?
Я использую soundex, и двойной метафон для "Сделал Вы имеете в виду": расширение на моей корпоративной интранет, и я хочу реализовать алгоритм Damerau–Levenshtein, чтобы помочь мне отсортировать результаты лучше. Что-то подобное этой идее: http://www.briandrought.com/blog/?p=66, моя реализация подобна первым 5 шагам.
Я пытался попытаться рекурсивное решение в то время.
/*
* Naïve implementation of Damerau-Levenshtein distance
* (Does not work when there are neighbouring transpositions)!
*/
function DamerauLevenshtein($S1, $S2)
{
$L1 = strlen($S1);
$L2 = strlen($S2);
if ($L1==0 || $L2==0) {
// Trivial case: one string is 0-length
return max($L1, $L2);
}
else {
// The cost of substituting the last character
$substitutionCost = ($S1[$L1-1] != $S2[$L2-1])? 1 : 0;
// {H1,H2} are {L1,L2} with the last character chopped off
$H1 = substr($S1, 0, $L1-1);
$H2 = substr($S2, 0, $L2-1);
if ($L1>1 && $L2>1 && $S1[$L1-1]==$S2[$L2-2] && $S1[$L1-2]==$S2[$L2-1]) {
return min (
DamerauLevenshtein($H1, $S2) + 1,
DamerauLevenshtein($S1, $H2) + 1,
DamerauLevenshtein($H1, $H2) + $substitutionCost,
DamerauLevenshtein(substr($S1, 0, $L1-2), substr($S2, 0, $L2-2)) + 1
);
}
return min (
DamerauLevenshtein($H1, $S2) + 1,
DamerauLevenshtein($S1, $H2) + 1,
DamerauLevenshtein($H1, $H2) + $substitutionCost
);
}
}