Hacker News Reader

Comment by jxf | Hacker News Reader

I notice the authors don't actually talk about accuracy. It's 1,000x faster, but what is gained or lost in terms of accuracy?

We can build a spelling corrector which is accurate most of the time and much faster than the Faroo implementation:

    def corrections_for(word)
      return [word]
    end

P.S. I added a gist here with some reformatting because I found it hard to read the code on the author's site:

https://gist.github.com/fj/8393399

The raw source is here:

https://gist.github.com/fj/8393399/raw/7d4acd14db21dd0c7d802...

View on HN

It looks like what they've done is more along the lines of finding a clever trick to improve the runtime performance of one of the common building blocks of a spell correction system (the part that given an input computes a set of candidate words that are close to it in terms of edit distance). It doesn't even seem to say anything about how to pick the best candidate once you've generated this set, so you can't really evaluate its accuracy as if it were a complete spell correction system. Norvig originally just used the straightforward "pick the most common word that has the smallest edit distance", but I didn't see them mention anything about any kind of strategy on their blog post.

In essence it appears to be a pre-filtering step before you look at the actual edit distance.

I'm also not sure how they benchmarked the other solution, as that clearly isn't optimised for runtime but for readability (it's a nice bit of code).

They seem to be comparing to Peter Norvig's spell corrector.

Compared to that, they have the exact same results. What they present is a faster way to find all dictionary words with edit distance <= 2 from a given word.

Isn't Norvig's spell corrector a really bare-bones implementation that he wrote while bored on a plane? Like, not really industrial-strength or anything. It's a very cool demo, but I wouldn't consider it worth benchmarking against, or anything... unless I've misunderstood what's going on here.

Plus they're benchmarking C# against Python. Python is generally 50-100x slower than C++, while C# is <2x slower. (based on computer languages shootout)

> I added a gist here with some reformatting because I found it hard to read the code on the author's site:

Thank you. Funny enough, that gist has the same problem on my screen (too much whitespace on either side of a box that I need to horrizontally scroll) - it's just not as bad.

Here's how the site shows up for me: http://imgur.com/CjXRHBC

Grumble.

Try using the raw link I posted afterwards. That'll give you as much room as your browser window has.

They are trading space for time.

Roughly speaking, they pre-compute some of the character substitutions done in traditional algorithm, and add it to the dictionary.

Reply on news.ycombinator.com