26 March 2009
Rubyでスペル修正プログラムを書こう！
青木靖さんの訳「スペル修正プログラムはどう書くか」を通して、Peter Norvigさんの「How to Write a Spelling Corrector」を知った。
僅か21行のPythonコードでスペル修正プログラムが書かれている。Pythonのコードを初めて見たけど、解説が丁寧にされていることもあり、またRubyにも似ているので何となく理解できた。配列の範囲表現とか空配列が偽になるとかの違いがあるのね。
等価のプログラムをRubyで書いた。速度的には問題ありだけどそこに時間を掛けるのはやめて、読みやすさを優先した。
ここのところSICP内でSchemeで書かれたコードをRubyで書き直す投稿を何度かしたけれど、このコードの書き直しは大変勉強になっている。それは言語によって機能実現のための表現方法が異なり、そこで驚きと共にコーディングに対する別の見方ができるからだ。少し続けてみよう。
詳細は先のサイトを見てもらうとして、スペル修正の手順は以下のようになる。
- 数冊の本と頻出用語集から作ったbig.txtを用意する。
- wordsメソッドでbig.txtに出現するすべての単語を小文字にしその配列(features)を作る。
- trainメソッドでfeaturesから単語とその出現頻度の組のハッシュ(NWORDS)を作る。
- edits1メソッドで対象ワードに対する1ストロークによる入力ミス(編集距離1)で得られる語の集合を作る。
- つまり1字不足(drop_char:削除)、1字入れ違い(trans_char:転位)、1字打ち間違い(alt_char:置換)、1字余分(insert_char:挿入)の各ケースにつき対象箇所を変えてこれらの処理を行う。これらの処理はStringクラスのメソッドとして実装した。
- edits2メソッドでedits1で生成されたものに対して再度edits1を繰り返し編集距離2として精度を上げる。最終出力をNWORDSに含まれている単語のみに限定するためそれと＆する。
- correctメソッドはスペル修正の対象ワードを引数としその誤りモデルに従って修正ワードを出力する。
- correctメソッドの誤りモデルは対象ワードが既知の語つまりNWORDSにあるならそれを最優先候補とする。そうでなければ編集距離1で既知の語群を候補とする。それらがなければ編集距離2で既知の語群を候補とする。それらもなければ入力語とする。語群が候補とされた場合はNWORDSにおける最大出現頻度の語が選ばれる。
big.txtはPeter Norvigさんのサイトから入手できます。
blog comments powered by Disqus
