这对于距离为1的情况非常容易。对于距离大于1的所有可能性生成变得更加复杂。
从一个词开始:
$input = 'word';
将单词拆分为字母,并生成替换列表。
$letters = str_split($input);
$alphabet = range('a', 'z');
删除最简单,只需循环每个位置并替换为''
:
foreach ($letters as $i => $letter) {
$variants[] = substr_replace($input, '', $i, 1);
}
插入和替换可以同时进行,因为它们都需要在字母输入的循环内嵌套一个字母表的循环。
foreach ($alphabet as $variation) {
foreach ($letters as $i => $letter) {
// insertion
$variants[] = substr($input, 0, $i) . $variation . substr($input, $i);
// substitution
// (check that the letter is different or you'll get multiple copies of the input)
if ($variation != $letter) {
$variants[] = substr_replace($input, $variation, $i, 1);
}
}
$variants[] = $input . $variation; // handle insertion at the end
}
您可以检查结果以验证Levenshtein距离是否正确:
foreach ($variants as $variant) {
$result[$variant] = levenshtein($input, $variant);
}