如何在1个编辑距离（Levenshtein）内生成单词的所有变体？

Question

我希望使用Levenshtein距离生成一个单词的所有1编辑距离变体。

PHP有一个函数，它将把两个字符串作为参数，并返回将str1转换为str2所需的插入、替换和删除操作数量（int）。PHP手册-levenshtein

int levenshtein ( string $str1 , string $str2 )

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

- Diego Vidal

---

可能是重复的问题，参考如何找到与给定字符串编辑距离相同的所有字符串。 - Daniel A. Thompson

嗨，丹尼尔，我已经阅读了那篇文章，但它是用Python编写的，并且他们谈论了Google搜索的工作原理。我不认为我的问题是重复的。我正在寻找一个PHP解决方案。 - Diego Vidal

你会如何使用笔和纸完成这个任务？假设你的单词是“AB”，你的字母表是“A”，“B”，“C”。我猜你在纸上解决这个问题很简单。现在请编写PHP代码，执行与你手工操作相同的操作。 - Roman Hocke

我认为这并不简单。我正在使用Levenshtein距离查找一个单词的所有变体，其编辑距离在1以内（即插入、删除或替换）。对于单词“kingdom”，我需要生成：kongdom、pingdom...、kngdom...、kingdomo... - Diego Vidal

Answer 1

这对于距离为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);
}

- Don't Panic

---

你的答案非常完美。我正在开发自己的解决方案并取得了良好的结果。这是一种与你类似的方法，但你的方法更好。感谢你的努力。 - Diego Vidal

谢谢你帮我打发时间，让我不再感到无聊。 - Don't Panic