最近、phpのマニュアルを眺めていたら、面白い関数を見つけた。levenshtein関数、レーベンシュタインと読む。
どうやら、文字列の類似性を見積もる系統の関数で、文字列Aから文字をとったり入れたりして文字列Bにするのに何手かかるかを計算するようだ。オーダーはO(m*n)と、意外と少ない。主な使用法としては、入力された単語が完全にマッチしなかった場合は「もしかして、xxxx？」と、候補をこちらから提示してあげることができるようになる。
ちなみにsimilar_textという文字列の類似性を調べる関数が存在するが、そちらのオーダーはO(max(n,m)^3)と、とんでもない大きさだ。

phpマニュアルのほうにも簡単なサンプルが載っているし、下記にいくつかのリンクを載せておいたので、参考にして欲しい。

PHP: levenshtein – Manual
Do You PHP はてな – levenshtein関数
zuzara : 類似文字列マッチの実装例 今度はPHPのlevenshtein関数