Author Archives: HH

2016-12-26

文字列の類似度

こんにちは
GMOインサイトのエンジニアのHHです。
拙い文章で申し訳ありませんがどうぞよろしくお願いします。

私はSimplistingという検索連動型のリスティング広告サービスに携わっております。
Simplistingには日々いろんな検索リクエストが飛んでくるのですが
ときに表記ゆれというものがありまして
タイポだったり、省略形だったりいろんなものがあります。

「YOUTUBE」を例にしますと
「youtube」だったり「yuotube」だったり、はたまた「ようつべ」だったりと様々です。

(もとはタイポである「ようつべ」はもはや一般的なキーワードになっていますが)

検索したユーザーの意図は同じなのに表記ゆれによって機会損失にならないよう
カバーしてあげなければいけないのですがレリバンシーを保ちつつ広げていくところが難しいところであります。


前置きが長くなりましたが今回ご紹介したいのは「レーベンシュタイン距離」というもので
二つの文字列同士がどれくらい異なっているかを数値化する考え方です。

説明が下手なのでwikipediaから引用させていただきます。

二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離(へんしゅうきょり、英: edit distance)とも呼ばれる。
具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される

「レーベンシュタイン距離」『フリー百科事典 ウィキペディア日本語版』。2016年11月17日 15:29 (UTC)、URL: http://ja.wikipedia.org

例としては下図のようになります

levenshtein

このレーベンシュタイン距離はpythonだと
python-Levenshteinというパッケージがありますのでインストールして簡単に試すことができます。

 

日本語でも動作します。

また似たような考え方でジャロ・ウィンクラー距離というのがありまして
レーベンシュタイン距離とは逆に近さを数値化し、小数で表現します。
全く異なると0,完全に一致する場合は1を返します。

当然ですがWord2Vecなどと違いレーベンシュタイン距離は単純に文字列の比較なので意味の類似度は測れません。
また、漢字一文字などの単語につかってもあまり効果は発揮できないかと思います。

応用すれば正解辞書をつくっておきタイポを拾ってあげることもできると思います。

また機会があれば書かせていただきたいと思います。

では