0

レーベンシュタイン検索で、配列に対して検索クエリ内のすべての単語をチェックすることは可能ですか?

コードは次のとおりです。

        $input = $query;

    // array of words to check against
    $words  = $somearray;

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

            if ($shortest == 0) {
      echo "Exact match found: $closest\n";
       } else {
         echo "Did you mean: $closest?\n";
        }

この例では、おそらく最初の単語のみまたは文全体を、配列と一致する文字列と見なします。結果を取得し、修正された単語を含む文全体を表示するにはどうすればよいですか?

4

1 に答える 1

0

あなたの質問から私が理解したことに基づいて、まず、次のように文を単語に分割する必要があります。たとえば、文を 単語の配列に変換するにはどうすればよいですか?

その後、最初の配列をループし、その内部で 2 番目の配列をループすることにより、各単語を辞書と比較できます。たとえば、次のようになります。

foreach ($words as $word)
{
    $min_distance = strlen($word); // use mb_strlen() for non-Latin
    foreach ($dictionary as $new_word)
    {
        $dist = levenshtein($word, $new_word);
        if (($dist < $min_distance) and ($dist > -1))
        {
            $min_distance = $dist;
            $suggestion = $new_word;
        }
    }
}

次に、距離が 0 より大きい場合は、 を提案し$suggestionます。

これは実際には非常に非効率的であることに注意してください。levinshtein()単語ごとに辞書全体をループする必要があるため、O(1) で実行されると仮定すると、Θ(n*m) で実行されます。おそらく、概念的な観点から、これらが実際にどのように設計されているかを知りたいと思うか、少なくとも長い単語だけを提案して、辞書のより関連性の高い部分をループすることをお勧めします。

于 2013-02-04T14:37:12.190 に答える