Wie kann ich alle Varianten eines Wortes innerhalb von 1-Edit-Entfernung (Levenshtein) generieren?

Question

Ich möchte alle Varianten eines Wortes innerhalb 1-Edit-Abstand mit Levenshtein Abstand zu generieren.

PHP hat eine Funktion, die zwei Strings als Parameter akzeptiert und nur die Zahl (int) der Operationen insert, replace und delete zurückgibt, die benötigt werden, um str1 in str2 umzuwandeln. PHP Manual - levenshtein

int levenshtein (string $str1 , string $str2) 

Ich suche eine PHP-Lösung, einen Algorithmus zu erstellen, die die Varianten eines bestimmten Wortes erzeugt.

Answer 1

Das ist ziemlich einfach für die Entfernung 1. Das Erzeugen aller Möglichkeiten für Entfernungen> 1 wird etwas komplexer.

Beginnen Sie mit einem Wort:

$input = 'word'; 

Split das Wort in Buchstaben und eine Liste der Ersatz zu erzeugen.

$letters = str_split($input); 

$alphabet = range('a', 'z'); 

Löschungen sind die einfachste, nur eine Schleife über jede Position und ersetzen mit '':

foreach ($letters as $i => $letter) { 
    $variants[] = substr_replace($input, '', $i, 1); 
} 

Einfügungen und Ersetzungen können zur gleichen Zeit durchgeführt werden, weil sie werden sowohl eine Schleife über die erfordern Buchstaben in der Eingabe verschachtelt in einer Schleife über dem Alphabet.

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 
} 

Sie können die Ergebnisse überprüfen die levenshtein Abstände korrekt sind, um zu überprüfen:

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