Ist es möglich, die Liste der Züge aus der Levenshtein-Funktion zu holen?

Question

Ich muss die Ähnlichkeit der Wörter vergleichen, ich habe eine Probe vom Benutzer eingegeben und Kontrolle vom Administrator. Die Levenshtein-Funktion tut das genau richtig, so wie sich die Differenz/Kontrolllänge in meiner Situation in einen Prozentsatz übersetzt. Ich möchte aber auch auf die Fehler aufmerksam machen, die Benutzer gemacht haben, aber afaik, die in php eingebaute levenshtein-Funktion, kann mir dafür keine Informationen geben.

OK dachte ich: „Ich werde meine eigene levenshtein Funktion machen und machen es die Orte ausspucken, wo es um die Änderungen tut“ .. aber bevor ich auch nur zu einem, dass bekam, habe ich eine einfachere Version

function toMbChars($s) { 
    $len = mb_strlen($s); 
    $ret = array(); 
    for ($i = 0; $i < $len; $i++) { 
     array_push($ret, mb_substr($s, $i, 1)); 
    } 
    return $ret; 
} 

function cmpLevenshteinDistanceOpt($a, $aLen, $b, $bLen) { 
    if (!$aLen) return $bLen; 
    if (!$bLen) return $aLen; 

    $cost = $a[$aLen - 1] != $b[$bLen - 1]; 

    return min(cmpLevenshteinDistanceOpt($a, $aLen - 1, $b, $bLen ) + 1, 
       cmpLevenshteinDistanceOpt($a, $aLen , $b, $bLen - 1) + 1, 
       cmpLevenshteinDistanceOpt($a, $aLen - 1, $b, $bLen - 1) + $cost);  
} 
function cmpLevenshteinDistance($a, $b) { 
    $aChars = toMbChars($a); 
    $bChars = toMbChars($b); 
    return cmpLevenshteinDistanceOpt($aChars, count($aChars), $bChars, count($bChars)); 
} 

Und es fällt schwer auf die Leistung, dauert es 13 Sekunden, um den Abstand zwischen 10 Buchstaben Wörter zu berechnen, während die eingebaute Funktion es in ein paar Millisekunden tut.

So jetzt bin ich bei 2 Fragen suchen:

1. Gibt es eine Möglichkeit die integrierte Funktion, um mir zu sagen, wo und welche Art von „Kosten“ hinzugefügt für den minimalen Abstand nach oben?
2. Gibt es eine Möglichkeit, meine Funktion zu optimieren, um so gut wie die integrierte Version durchzuführen?

Answer 1

Ich bin mit der Levenshtein Funktion nicht vertraut, aber die docs http://php.net/manual/en/function.levenshtein.php ein Beispiel, wo sie am nächsten kommt speichern, könnten Sie nicht etwas ähnliches tun und dann vergleichen Sie nur diese zwei Worte selbst manuell? Ich habe eine grobe Vergleichsfunktion am Ende hier hinzugefügt, aber Sie könnten es für Fehler etc. optimieren und es ist derzeit nur für gebaut, wenn der Benutzer Wort eingegeben ist länger als das Steuerelement, aber hoffentlich ist es ein Ausgangspunkt

<?php 
// input misspelled word 
$input = 'caarrrot'; 

// array of words to check against 
$words = array('apple','pineapple','banana','orange', 
       'radish','carrot','pea','bean','potato'); 

// no shortest distance found, yet 
$shortest = -1; 

// loop through words to find the closest 
foreach ($words as $word) { 

    // calculate the distance between the input word, 
    // and the current word 
    $lev = levenshtein($input, $word); 

    // check for an exact match 
    if ($lev == 0) { 

     // closest word is this one (exact match) 
     $closest = $word; 
     $shortest = 0; 

     // break out of the loop; we've found an exact match 
     break; 
    } 

    // if this distance is less than the next found shortest 
    // distance, OR if a next shortest word has not yet been found 
    if ($lev <= $shortest || $shortest < 0) { 
     // set the closest match, and shortest distance 
     $closest = $word; 
     $shortest = $lev; 
    } 
} 

echo "Input word: $input\n"; 
if ($shortest == 0) { 
    echo "Exact match found: $closest\n"; 
} else { 

    echo "Did you mean: $closest?\n"; 
    $diff = wordDifference($input, $closest); 
    echo $diff; 
} 

function wordDifference($word1, $word2){ 
    $difference = ''; 
    $offset = 0; 
    for($i =0; $i < strlen($word1); $i++){ 
     $word1letter = $word1[$i]; 

     $word2letter = $word2[$i - $offset] ? $word2[$i - $offset] : ''; 

     if($word1letter !== $word2letter){ 
      $offset++; 
      $difference .= '<span style="background:red">'.$word1letter.'</span>'; 
     }else{ 
      $difference .= $word1letter; 
     } 
    } 
    return $difference; 
} 


?>*