[PHP]「もしかして: ～」スペルミス時の修正候補を表示する

Google などでお馴染みの修正候補を表示する機能は、PHP の標準関数 levenshtein() を活用すれば実現できます。

<?php
$word = "brue";
 
//候補一覧
$wordlist = array(
  "apple", "orange", "grape", "banana",
  "book", "car", "house", "water",
  "red", "green", "blue", "black"
);
 
$cost = array();
foreach($wordlist as $value){
    $cost[] = levenshtein($word, $value);
}
array_multisort($cost, SORT_NUMERIC, SORT_ASC, $wordlist);
 
if( $cost[0] > 0 && $cost[0] <= 2){
  echo "もしかして: " . $wordlist[0];
}

出力結果:

もしかして: blue

サンプルでは「brue」というキーワードに対して、「blue」という修正候補が表示されます。
もし正しく「blue」と入力した場合や、「yellow」と入力した場合など、修正候補とあまりにかけ離れている時は表示されません。
if 文「reset($cost) <= 2」の「2」がその許容量を表しています。修正にかかるコストが2以下の場合のみ表示することになっています。
キーワードがリストの単語と一致するとき、コストは「0」なのでこの場合も表示しません。

原理はかなりシンプルですが、単語リストが増えれば処理時間も増えるのでコストが「0」か「1」のものがあった場合 break するなどの工夫する必要があるかもしれません。
あるいは、文字数ごとにリストを用意し、キーワードの文字数プラスマイナス1文字の単語グループの中から修正候補を表示するようにすればずっと早く終わります。

言い忘れましたが、levenshtein() はマルチバイト非対応です。 mb_levenshtein があればいいのですが標準ではないので、代わりに前回作った関数で代用して下さい。

function mb_levenshtein($str1, $str2){
  $length1 = mb_strlen($str1, 'utf-8');
  $length2 = mb_strlen($str2, 'utf-8');
 
  $str1 = mb_str_split($str1, 'utf-8');
  $str2 = mb_str_split($str2, 'utf-8');
  
  $distance = array();
  for($i=0;$i<=$length1;$i++){
    $distance[$i] = array();
    $distance[$i][0] = $i;
  }
  for($i=0;$i<=$length2;$i++){
    $distance[0][$i] = $i;
  }
  $cost = 0;
  for($i=1;$i<=$length1;$i++){
    for($j=1;$j<=$length2;$j++){
	
      $cost = ($str1[$i - 1] === $str2[$j-1]) ? 0 : 1;
      $distance[$i][$j] = min(
        $distance[$i - 1][$j] + 1,
        $distance[$i][$j - 1] + 1,
        $distance[$i - 1][$j - 1] + $cost
      );
    }
  }
  return $distance[$length1][$length2];
}

function mb_str_split($str, $encoding){
  $arr = array();
  $length = mb_strlen($str, $encoding);
  for($i=0;$i<$length;$i++){
    $arr[] = mb_substr($str, $i, 1, $encoding);
  }
  return $arr;
}

文字列を一文字ずつ配列に分解する str_split() という便利な関数があるのですが、こちらもマルチバイトはないので mb_str_split() として作っておきました。
日本語は大変・・・。

PHP Archive

Webサイト開発初心者の備忘録

[PHP]「もしかして: ～」スペルミス時の修正候補を表示する

コメントを残す