青木靖さんの訳「スペル修正プログラムはどう書くか」を通して、Peter Norvigさんの「How to Write a Spelling Corrector」を知った。

僅か21行のPythonコードでスペル修正プログラムが書かれている。Pythonのコードを初めて見たけど、解説が丁寧にされていることもあり、またRubyにも似ているので何となく理解できた。配列の範囲表現とか空配列が偽になるとかの違いがあるのね。

等価のプログラムをRubyで書いた。速度的には問題ありだけどそこに時間を掛けるのはやめて、読みやすさを優先した。

ここのところSICP内でSchemeで書かれたコードをRubyで書き直す投稿を何度かしたけれど、このコードの書き直しは大変勉強になっている。それは言語によって機能実現のための表現方法が異なり、そこで驚きと共にコーディングに対する別の見方ができるからだ。少し続けてみよう。

詳細は先のサイトを見てもらうとして、スペル修正の手順は以下のようになる。

  1. 数冊の本と頻出用語集から作ったbig.txtを用意する。
  2. wordsメソッドでbig.txtに出現するすべての単語を小文字にしその配列(features)を作る。
  3. trainメソッドでfeaturesから単語とその出現頻度の組のハッシュ(NWORDS)を作る。
  4. edits1メソッドで対象ワードに対する1ストロークによる入力ミス(編集距離1)で得られる語の集合を作る。
  5. つまり1字不足(drop_char:削除)、1字入れ違い(trans_char:転位)、1字打ち間違い(alt_char:置換)、1字余分(insert_char:挿入)の各ケースにつき対象箇所を変えてこれらの処理を行う。これらの処理はStringクラスのメソッドとして実装した。
  6. edits2メソッドでedits1で生成されたものに対して再度edits1を繰り返し編集距離2として精度を上げる。最終出力をNWORDSに含まれている単語のみに限定するためそれと&する。
  7. correctメソッドはスペル修正の対象ワードを引数としその誤りモデルに従って修正ワードを出力する。
  8. correctメソッドの誤りモデルは対象ワードが既知の語つまりNWORDSにあるならそれを最優先候補とする。そうでなければ編集距離1で既知の語群を候補とする。それらがなければ編集距離2で既知の語群を候補とする。それらもなければ入力語とする。語群が候補とされた場合はNWORDSにおける最大出現頻度の語が選ばれる。

big.txtはPeter Norvigさんのサイトから入手できます。



blog comments powered by Disqus
ruby_pack8

100円〜で好評発売中!
M'ELBORNE BOOKS