3/4〜3/15までフルタイムで某Web系の会社にインターンしてきました。
おそらくみなさんご存じのところです。

そこでアプリ開発的なことをしてきたわけですが、そのときに得た知見なんかを備忘録も兼ねて書きたいと思います。
タイトルにもある通り、表記揺れなどに対する類似文字列検索の話です。
ちなみに筆者は数学が不得意なのでどんどん突っ込んでくれるとありがたいです。 
たとえば、ナポリマフィアは「カモッラ」「カモルラ」などの表記揺れがあるわけですが、 「カモッラ」「カモルラ」を同じものと見なすにはどうすればいいでしょうか?
そんな問いは昔からあるらしく、情報科学の分野ではけっこう類似度の測定手法があるわけですが、代表的なものだとコサイン類似度やジャッカード(Jaccard)係数があります 。

2つのものの類似度をはかるのであればそんなに計算量は要らないのですが、ビッグデータが騒がれる昨今、類似度をはかる対象は数万のオーダーではきかなくなってきています。
そういった事情から、こういった類似度計算を手っ取り早く行いたいという需要が出てきました。

常識的な考えとしては、予め索引を作っておくなどするのが良いわけですが、その手法として最近熱いのがMinHashだとか。
岡野原先生のblogに詳しいので詳細は省くとして、 Jaccard係数を高速に検索できるのは良いのですが、いかんせんメモリを食います。MinHash自体は衝突を許さないので、ハッシュにそれなりの空間を要するからです。いや、すごく美しいんですけど。
そして、衝突を許すb-bitに関しては筆者の数学力では理解できないので無理です。

そんなわけでいろいろ検索してたところ、東北大学の岡崎直観先生がスゴイ論文[1]を書いてたので飛びつきました。 
このレジュメじゃわかんねーよ、って人はこっちを読むとよろし。
類似文字列検索における必要条件と十分条件から、問題をτ-オーバーラップ問題(初耳)に落とし込むくだりは絶頂モノです。転置インデックス化のあたりはレジュメだとわかりにくいので長い方を読んだ方がいいかもしれません。
そんなわけでめでたくSimString様に出会うことができましたが、Web上の(機械で処理するには)「ややこしい」表現はなにも表記揺れにとどまりません。

たとえば、略称。
「アイマス」も「アイドルマスター」も、両者の意味には差がありません。そして、略称というものは往々にして類似検索では見つかりません。
東大の村上先生[2]などにより研究は行われているようですが、やはり精度が問題となります。
筆者がかかわっていたサービスの場合、そのあたりはうまいことゴニョゴニョできる環境がありましたが、一般的にはこういう情報に対してはRDFの普及を待つ必要があると感じます。私見ですが。
/*セマンティック・ウェブはこういったもんにょりする部分にかなり切り込んでくれると思うのですが、いかんせん普及が遅れてますね。残念ですが当然だと思います。人力に頼る以上制度ができてないといけませんし。*/

こういった対策をいくら解析側が講じても、発信者というものは好き放題やります。
それがインターネットの良いところだと思いますし、それを否定してはいけないと思いますが、やはり「見る側」としては気持ちの良いものではなかったりするのです。
それが「味」だとしても、ニコニコ動画の病院系タグとか検索性を低めるだけだと思うのですよ。
エンジンに頑張ってもらおうにも、まだまだ検索エンジンはそこまで賢くないですし、
「検索すれば答えは出てくる」世界は遠いと感じます。簡易な検索エンジン作ってみた感想ですが。

ということで、前言撤回。やっぱり発信者は「正しい」言葉を使うべきです。
正しい言葉の定義はこの際措くとしても。


[1]岡崎直観, 辻井潤一. 高速な類似文字列検索アルゴリズム. 情報処理学会創立50周年記念(第72回)全国大会, pp. 1-567—1-568, 東京大学(東京都), 2010年3月 
[2]村山 紀文, 奥村 学:Noisy-channel model を用いた略語自動推定, 言語処理学会第12回年次大会, pp. 763–766,(2006)