我正在尋找PHP的Damerau–Levenshtein算法的實現，但似乎我找不到任何與我的朋友谷歌。到目前爲止，我必須使用PHP實現的Levenshtein（沒有Damerau轉置，這非常重要），或者獲取原始源代碼（使用C，C++，C＃，Perl）並將其寫入（轉換）到PHP。Damerau-Levenshtein php
有沒有人有任何PHP實現的知識？
我在企業內部網上使用soundex和double metaphone作爲「您的意思是：」擴展名，我想實現Damerau-Levenshtein算法來幫助我更好地對結果進行排序。類似於這個想法的東西：http://www.briandrought.com/blog/?p=66，我的實現類似於前5個步驟。
我有一個stab at it遞歸解決方案。
/*
* 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
);
}
}
看一看our implementation（含測試和文檔）。
如何使用內置的PHP函數...？
http://php.net/manual/en/function.levenshtein.php
int levenshtein (string $str1 , string $str2)
int levenshtein (string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del)
有在維基百科頁面僞代碼;當然，這不會太難以移植到PHP？ – Piskvor 2010-07-02 11:12:41