From: William James <w_a_x_man@...>
Date: 2007-04-11T17:55:17+09:00
Subject: Re: How to Write a Spelling Corrector


Brian Adkins wrote:
> Peter Norvig wrote a simple spelling corrector in 20 lines of Python 2.5,
> so I thought I'd see what it looks like in Ruby. I'm not too pleased with
> my version, if anyone can make it more elegant, that would be great. Some
> of the sticking points were:
>
> 1) List comprehensions in Python made the edits1 function more elegant
> IMO. Hopefully someone can improve that function.
>
> 2) The boolean expression in the correct function evaluates empty
> sets/arrays as false in Python but not in Ruby, so I had to add the
> "result.empty? ? nil : result" expression to several functions. I expect
> there's a better way to handle this also.
>
> 3) Minor point, but apparently Python has a built in constant for the set
> of lower case characters "string.lowercase", so I just defined a constant.
>
> Otherwise, the translation was pretty straightforward.
>
> Here's a link to Norvig's page: http://www.norvig.com/spell-correct.html
>
> That page includes a link to a text file that I saved locally as
> holmes.txt: http://www.norvig.com/holmes.txt
>
> Note: I wrapped a few of the longer lines for posting.
>
> def words text
>   text.downcase.scan(/[a-z]+/)
> end
>
> def train features
>   model = Hash.new(1)
>   features.each {|f| model[f] += 1 }
>   return model
> end
>
> NWORDS = train(words(File.new('holmes.txt').read))
> LETTERS = 'abcdefghijklmnopqrstuvwxyz'
>
> def edits1 word
>   n = word.length
>   deletion = (0...n).collect {|i| word[0...i]+word[i+1..-1] }
>   transposition = (0...n-1).collect {
>     |i| word[0...i]+word[i+1,1]+word[i,1]+word[i+2..-1] }
>   alteration = []
>   n.times {|i| LETTERS.each_byte {
>     |l| alteration << word[0...i]+l.chr+word[i+1..-1] } }
>   insertion = []
>   (n+1).times {|i| LETTERS.each_byte {
>     |l| insertion << word[0...i]+l.chr+word[i..-1] } }
>   result = deletion + transposition + alteration + insertion
>   result.empty? ? nil : result
> end

Letters = ('a'..'z').to_a

class String
  def replace( which, what )
    self[0...which] + what + self[which+1 .. -1]
  end
end

def edits1 word
  n = word.size
  return nil   if n.zero?
  deletion = (0...n).map{|pos| word.replace(pos, "") }
  transposition = (0...n-1).map{|i|
    word[0...i]+word[i+1,1]+word[i,1]+word[i+2..-1] }
  alteration = (0 ... n).to_a.map{|pos|
    Letters.map{|ch| word.replace(pos, ch) }}.flatten
  insertion = (0 .. n).to_a.map{|pos|
    Letters.map{|ch| word[0...pos] + ch + word[pos..-1] }}.flatten
  deletion + transposition + alteration + insertion
end