levenshtein関数から移動リストを取得できますか？

Question

私は単語の類似点を比較する必要があります。ユーザーが入力したサンプルと管理者のコントロールがあります。 levenshtein関数は、私の状況での違い/コントロールの長さがどのように変換されるかのように、これを正しく行います。しかし、私はまた、ユーザーが間違っていることを強調したいと思いますが、PHPに組み込まれている関数levenshteinはそれに関する情報を私に与えることはできません。

OK、私は「私は私自身のレーベンシュタイン機能を作成し、それが変化しない場所を吐き出す作ります」を考え出した..しかし、私もそれのいずれかになった前に、私は簡単なバージョン

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)); 
} 

を作りました

そして、それは、パフォーマンス上のハード障害が発生した機能に建てられたが、数ミリ秒でそれをしない一方で、それは10文字の単語間の距離を計算するために13秒のようになります。

だから今、私は2つの質問で探しています：

1. は機能に建てにする方法はありますどこを教え、それが最小距離のために、「コスト」の何種類を追加？
2. 組み込みバージョンと同じように機能を最適化する方法はありますか？

Answer 1

私はレーベンシュタイン機能に精通していないよ、しかし、彼らは最も近いものを保存する例を持っているhttp://php.net/manual/en/function.levenshtein.phpドキュメントは、あなたが似た何かをすることができませんでしたし、その後、ちょうど手で自分をそれらの2つの単語を比較しますか？私はここで終わりに、粗比較する機能を追加しましたが、あなたは、エラーなどのためにそれを微調整することもできますし、ユーザーが単語を入力した場合、それは現在だけのために組み込まれている長いコントロールよりもですが、うまくいけば、それは

出発点です

<?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; 
} 


?>*