Как я могу сгенерировать все варианты слова на расстоянии 1 редактирование (Левенштейн)?

Question

Как я могу сгенерировать все варианты слова на расстоянии 1 редактирование (Левенштейн)?

Я хотел бы сгенерировать все варианты слова в пределах расстояния 1 редактирования, используя расстояние Левенштейна.

В PHP есть функция, которая принимает две строки в качестве параметра и возвращает только число (int) операций вставки, замены и удаления, необходимых для преобразования str1 в str2. Руководство по PHP — Левенштейн

int levenshtein ( string $str1 , string $str2 )

Я ищу решение PHP для создания алгоритма, который генерирует варианты данного слова.

0

levenshtein-distance php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Это довольно просто для расстояния 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);
}

2