From: Nicolas Buet <nicolas.buet@...>
Date: 2007-04-13T01:04:39+09:00
Subject: Re: How to Write a Spelling Corrector

I am so glad I find this topic here! I was on the plane yesterday, and
just like Peter Norwig I managed to write a spelling corrector. An
obvious difference is that he started from nothing, while I started
from his code... Anyway, I did it in Ruby, it works, but... it's dead
slow. If I need to compute the second array (the one with 2 mistakes),
it takes about 1 second per suggestion.

My edit1 function is like this:
----------------------------
def edits1(word)
    n = word.length

    return ( (0..n-1).collect {|i| word[0,i] + word[i+1, n-1]}  + #deletion
    (0..n-2).collect {|i| word[0,i] + word[i+1,1] +word[i,1] +
word[i+2, n-1]} + #transposition
    ('a'..'z').collect {|c| (0..n-1).collect { |i| word[0,i] + c +
word[i+1, n-1]} } + #alteration
    ('a'..'z').collect {|c| (0..n).collect { |i| word[0,i] + c +
word[i, n]} } ).flatten #insertion

end
---------------------------------------------

I believe this is where I lose most of the time? when I call it, it
looks like that:

--------------------------------------------
edits2 = (edits1(word).collect {|i| edits1(i) & NWORDS }).flatten
--------------------------------------------

Can anyone see here a flaw in logic, or some function that should be
avoided because it's known as slow?

On 4/12/07, Drew Olson <olsonas@gmail.com> wrote:
> This may be a bit OT, but I am really struck as to how elegantly both of
> these languages (and the programmers as well) handle this seemingly
> difficult problem. I've been working with ruby mainly for fun over the
> past 8-9 months and seeing this solution (in Python and ruby) really
> heightens my respect for the elegance and expressiveness of both
> languages.
>
> </rave>
>
>
> --
> Posted via http://www.ruby-forum.com/.
>
>