如何在 1-edit 距离内生成一个单词的所有变体 (Levenshtein)？

Question

我想使用 Levenshtein 距离在 1-edit 距离内生成一个词的所有变体。

PHP 有一个函数，它将两个字符串作为参数，并且 return 只是将 str1 转换为 str2 所需的插入、替换和删除操作的数量 (int)。 PHP Manual - levenshtein

int levenshtein ( string $str1 , string $str2 )

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

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
}

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

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

如何在 1-edit 距离内生成一个单词的所有变体 (Levenshtein)？

How can I generate all variants of a word within 1-edit distance (Levenshtein)?

php

levenshtein-distance