🧙🏾 🏠 🤾 正しいことをしたか 👤 👇🏾 👨🏾‍🎤

Zaktak：これは私の最初の投稿で、いつものように最初の投稿はパンケーキです:)。

最近、サイトでの検索を最新化するタスクを受け取りました。そのため、「Did You Mean」機能を作成する必要がありました。

ところで、彼のYandexのような 日曜大工検索記事について、 同志のalexblack alexblackに感謝します。

次に、これをすべて行った方法をリストし始めます。 PHP、MySQLデータベース、サイト言語-英語。

（正しい決定は最後にあります:)

0）インデックスの作成

サイトのコンテンツ全体で実行する小さなスクリプトを作成し（ 残念ながら 、すべてデータベースにあります）、フィールドword-単語自体、 search_index-単語インデックス（設定に応じてsoundexまたはmetaphone）およびcount-単語の出現頻度を含むguess_wordテーブルを作成します。

すべての単語は以前に小文字に変換されており、文字以外はすべて切り取られていました。

1）soudex +会議の頻度

単語が見つからなかった場合、soudexインデックスを取得し、データベースを検索して、会議の頻度で並べ替えます。

動作しますが、悪いです。常に最も頻繁に現れる単語が常に正しいヒントとは限りません。

2）soundex +レベンシュタイン

同じsoundexインデックスを持つすべての単語を見つけ、それらから最小のレーベンシュタイン距離を持つ単語を選択します。

はるかに良いですが、まだ問題があります。標準的なタイプミスでは、茶は茶を見つけます（茶と茶の間の距離は茶と茶の間の距離よりも大きいため）。

3）メタフォン

メタフォンを拒否すると、結果が悪化します。（もちろん奇妙ですが）。

4）単語間の正しい距離を計算します。

レーベンシュタイン距離では、文字の置換、削除、挿入が可能ですが、場所の交換は考慮されていません。

アイデアA：単語に含まれる文字の数を数え、その結果を距離に追加します。同時に、レーベンシュタイン距離では、取り外し/挿入がすでに計算されているため、取り外し/挿入の価格を交換の価格よりも低くします。

結果A：そうではありません。今、最も近いのはテです

アイデアB：レーベンシュタインの価格で遊ぶ。

結果B：期待したものとは少し異なります。たとえば、交換品の価格を引き上げる場合、アルゴリズムは削除と挿入を介してより収益性の高いものに変換することを決定します。もちろん良いですが、適切ではありません。

アイデアC：自己記述関数を支持して、レーベンシュタインを放棄します。

function words_dist($str_a, $str_b) 
      

        
        
        
      

     { 
      

        
        
        
      

     if ($str_a == $str_b) return 0; 
      

        
        
        
      

     
      

        
        
        
      

     // (begin of)    .    btlfsa 
      

        
        
        
      

     // (    php.net/levenshtein)      
      

        
        
        
      

     //  btlfsa teh:tehh = 0, words_dist teh:tehh = 1 
      

        
        
        
      

     
      

        
        
        
      

     $arr_a = array(); 
      

        
        
        
      

     for ($i = 0; $i < strlen($str_a); $i++) { 
      

        
        
        
      

     $arr_a[$str_a{$i}] = (array_key_exists($str_a{$i}, $arr_a) ? $arr_a[$str_a{$i}] : 0) + 1; 
      

        
        
        
      

     } 
      

        
        
        
      

     
      

        
        
        
      

     $arr_b = array(); 
      

        
        
        
      

     for ($i = 0; $i < strlen($str_b); $i++) { 
      

        
        
        
      

     $arr_b[$str_b{$i}] = (array_key_exists($str_b{$i}, $arr_b) ? $arr_b[$str_b{$i}] : 0) + 1; 
      

        
        
        
      

     } 
      

        
        
        
      

     
      

        
        
        
      

     foreach($arr_a as $k=>$v) { 
      

        
        
        
      

     if (!array_key_exists($k, $arr_b)) $arr_b[$k] = 0; 
      

        
        
        
      

     } 
      

        
        
        
      

     
      

        
        
        
      

     $dst = 0; 
      

        
        
        
      

     foreach ($arr_b as $k=>$v) $dst += abs((array_key_exists($k, $arr_a) ? $arr_a[$k] : 0) - $v); 
      

        
        
        
      

     
      

        
        
        
      

     // (end of)     
      

        
        
        
      

     
      

        
        
        
      

     //  /         
      

        
        
        
      

     $dst *= 2; 
      

        
        
        
      

     
      

        
        
        
      

     if (strlen($str_a) < strlen($str_b)) 
      

        
        
        
      

     { 
      

        
        
        
      

     $l = strlen($str_b)-strlen($str_a); 
      

        
        
        
      

     for ($i = 0; $i < $l; $i++) $str_a .= ' '; 
      

        
        
        
      

     } 
      

        
        
        
      

     elseif (strlen($str_b) < strlen($str_a)) 
      

        
        
        
      

     { 
      

        
        
        
      

     $l = strlen($str_a)-strlen($str_b); 
      

        
        
        
      

     for ($i = 0; $i < $l; $i++) $str_b .= ' '; 
      

        
        
        
      

     } 
      

        
        
        
      

     
      

        
        
        
      

     //        
      

        
        
        
      

     for ($i = 0; $i < strlen($str_a); $i++) { if ($str_a{$i} != $str_b{$i}) $dst++; } 
      

        
        
        
      

     
      

        
        
        
      

     return $dst; 
      

        
        
        
      

     }

コメントなしのコードへのリンク（念のため）

結果C：うまくいきます。（今のところ:)、多分それからさまざまな不正確さがあります）

5）インデックスによる検索を修正します

soudexインデックスは、類似した単語に対して常に同じインデックスを与えるとは限りません。たとえば、stcokとステージのインデックスは同じですが、stcokとストックは異なります（劇場と四塩化物はまだ面白いです）。

アイデアA：インデックスを2つの部分（文字と数字）に分割し、[文字] [数字-2]から[文字] [数字+ 2]まで検索します

結果A：最初の文字が間違っている可能性があると考えたため、それをしませんでした。

アイデアB： 「L」など、同じ最初の文字を単語に追加します。現在、最初の文字は同じなので、インデックスに入力しても意味がありません。 $ index = substr（soundex（ 'L'。$ word）、1）;

結果B：私の期待を超えました。範囲検索さえする必要はありませんでした（-2 ... +2）。

*）結果

a）インデックスsoundex

b）インデックス付けする前に、単語に同じ最初の文字を追加します。$ index = substr（soundex（ 'L'。$ word）、1）

c）可能な単語のリストから自己記述関数を選択し、レーベンシュタイン距離を使用しない

また、ボーナスとして、推測された単語（間違った文字で強調表示された赤い文字）から装飾を作成します。コードは非常に明白でボリュームがありますので、リンクを張ってください： zame-dev.org/pub/highlight.html

デモンストレーション

upd：おそらく、soundex（ 'Lteom'）はsoundex（ 'Lterm'）に似ていません（ただし、まだsoundex（ 'teom'）およびsoundex（ 'term'）よりもずっと近いため、範囲で検索する必要があります）

正しいことをしたか

More articles: