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
);
}
}
$tests = array();
// format: [string 1, string 2, expected result, comment]
$tests[] = array("", "", 0, 'Empty strings');
$tests[] = array("abc", "abc", 0, 'Identicle strings');
$tests[] = array("abc", "abcd", 1, 'Insert 1 character at end of string');
$tests[] = array("abc", "", 3, 'Adding 3 characters to empty string');
$tests[] = array("acbd", "abcd", 1, 'Swap 2 characters in middle of string');
$tests[] = array("abcd", "abdc", 1, 'Swap 2 characters at end of string');
$tests[] = array("abcde", "acde", 1, 'Insert 1 character in middle of string');
$tests[] = array("abcdef", "acebdf", 3, 'Adjacent transpositions');
?>
Levenshtein distance
Levenshtein distance algorithm
| S1 |
S2 |
levenshtein()
PHP function |
rLevenshtein() |
DamerauLevenshtein() |
Expected |
Comment |
|
|
|
|
|
|
|