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さんのサイトから入手できます