On Fri, 13 Apr 2007 01:04:39 +0900, Nicolas Buet wrote:

> 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?

You may want to compare to my original at the start of this thread. I
don't have your code, so I can't benchmark it, but I have no noticeable
lag when I correct a word. It may have something to do with you having two
ranges, two collects and a flatten just to get the insertion set. Compare 

('a'..'z').collect {|c| (0..n).collect { |i| word[0,i] + c +
  word[i, n]} } ).flatten

to:

(n+1).times {|i| LETTERS.each_byte {
    |l| insertion << word[0...i]+l.chr+word[i..-1] } }

> 
> 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/.
>>
>>