如何生成 1 编辑距离 (Levenshtein) 内单词的所有变体？ [关闭]

我想使用 Levenshtein 距离生成 1 编辑距离内单词的所有变体。

PHP 有一个函数，它将两个字符串作为参数，并仅返回将 str1 转换为 str2 所需的插入、替换和删除操作的数量 (int)。PHP 手册 - levenshtein http://php.net/manual/en/function.levenshtein.php

int levenshtein ( string $str1 , string $str2 )

我正在寻找一个 PHP 解决方案来创建一个生成给定单词的变体的算法。

对于距离 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
}

您可以检查结果以验证编辑距离是否正确：

foreach ($variants as $variant) {
    $result[$variant] = levenshtein($input, $variant);
}