Hatena::ブログ(Diary)

naoyaのはてなダイアリー

March 23, 2009

第11回 Kansai.pm / スペルミス修正プログラムを作ろう

昨日は第11回 Kansai.pm でした。

f:id:naoya:20090323110817j:image:w400

今回は無理を言って自分がホストを担当させていただきましたが、面白い発表が多く開催した自分も非常に満足でした。

PFI の吉田さんによる Cell Challenge での計算機に合わせたアルゴリズムのチューニング手法の発表 (発表資料) は圧巻でした。伊奈さんの本文抽出の話 (発表資料)、はこべさんのコルーチンの話 (発表資料)、いずれも難解になりがちなところを凄く分かりやすく解説されていて、さすがだなと思いました。各々ショートトークも、いずれも良かったです。

スペルミス修正プログラムを作ろう

自分も 20 分ほど時間をいただいて、スペルミス修正プログラムの作り方について発表しました。

スペルミス修正プログラムについてはずばり スペル修正プログラムはどう書くか に解説があったのですが、この文書内の実装は編集距離が 1 から 2 の単語を辞書に対して総当たりに調べていく実装になっていて、対象がアルファベット前提の手法です。このままでは日本語の辞書には難しいなと思っていたところ Introduction to Information Retrieval の第3章にNグラムインデックスを使う手法が解説されていたので、ミックスして試してみました。また、編集距離よりも特定のケースで良い精度が出る Jaro-Winkler 距離というのがあることを最近知ったので、それも試しています。CPAN にある Levenshtein 距離, Jaro-Winkler 距離の実装は Unicode を考慮していないので、その辺の再実装を行う必要がありました。

スペルミス修正プログラムがなぜこれで正しく動くか、というところは確率的言語モデルの観点から数学的に考えることで理論を補強することができます。その辺についても少し触れてみました。

PFI の吉田さんの発表が編集距離の計算をチューニングする話で、またいいむらさんの発表は POPFile をテーマにベイズ定理の話 (発表資料) でして、自分の発表と話が偶然つながっていて面白かったです。

見つけた発表資料、感想は kansai.pm タグで集めています。