こんにちは。フリーランス・コンサルタント＆エンジニアの PHPでは、２つの文字列がどれだけ似ているかを計算する方法として、以下２つの標準関数が用意されています。
- similar_text()
- levenshtein()
これらは精度も高いので、さすがはPHP！マイナーな場所にまで標準関数を用意してくれてるな、と感じていたんですが、やはりそこは汎用的な実装をしているからか、全ての状況でも精度が高いかと言うとそうでもない場合もあるため、今回独自でテキストの類似計算方法を考えてみることにしました。
類似度を計算する環境
文字列１（検索文字列）： ABCDEF
文字列２（オリジナル文字列）： ABXDEF
１．考え方
この方法では、「いかに長い文字列がマッチするか」という考え方がベースになっています。
２．実際の計算手順
１．ありうる全ての文字列を切り出す
まず検索文字列から、ありうる限りの分割文字列を作成します。
こんな感じです。
A
AB
ABC
ABCD
ABCDE
ABCDEF
B
BC
BCD
BCDE
BCDEF
C
CD
CDE
CDEF
D
DE
DEF
E
EF
F
そして、この中で一番長い文字列から順にもうひとつの文字列を比較していき、マッチしていたら類似ポイントを加算していきます。で、類似ポイントは比較がつきやすいように標準偏差のように２乗することにしました。
つまり、
文字列「ABC」がマッチしていたら、文字列の長さ「３」の２乗、つまり９ポイントが加算されるわけです。
では、なぜ長い文字列から順にしたかというと、区切られた文字がマッチする度に虫食いのように元の文字列から削除していく必要があるため。（つまり重複したマッチをなくすためです。）
例えば、「東京都葛飾区」というオリジナル文字列があって、もし「東京都 京都」という２つのキーワードで検索されてしまった場合、重複をなくしていないと、
１．東京都でマッチ（３文字＝９ポイント加算）
２．京都でもマッチ（２文字＝４ポイント加算）
となってしまうから。
つまり流れとしては、マッチする度にオリジナル文字列がテロメアのように短くなっていくイメージですね。
１．東京都でマッチ（３文字＝９ポイント加算。今後の比較文字列は、「東京都」を除いた、「葛飾区」だけ）
２．京都はマッチしない。なぜなら「葛飾区」しか残っていないから（０文字＝０ポイント加算）
これでやってみるとある程度の精度がでるようになったので、なかなかうまくいけたのかなー、と考えています。ただし、これにも弱点があって、あまりに短い検索文字列だとマッチしにくいんです。（とはいっても、それだと標準関数の方でもほぼ同じなんですけどね）
ということで、今回は短いですけど備忘録的にアイデアを書いておくことにしました。
（残念ながらまだテスト段階なので、パッケージなどにはしてません。今後時間ができたら考えたいと思います。）
ではでは〜。
