4 ms·
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
by jxf 13y ago
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 https://gist.github.com/fj/8393399
The raw source is here:
https://gist.github.com/fj/8393399/raw/7d4acd14db21dd0c7d802c7aee3000d8bffeeff2/gistfile1.cs https://gist.github.com/fj/8393399/raw/7d4acd14db21dd0c7d802...
- kenferry 13y agoThey 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.
- Kluny 13y agoIsn'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.
- Scaevolus 13y agoPlus they're benchmarking C# against Python. Python is generally 50-100x slower than C++, while C# is <2x slower. (based on computer languages shootout)
- WizzleKake 13y ago> 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 http://imgur.com/CjXRHBC Grumble.
- jxf 13y agoTry using the raw link I posted afterwards. That'll give you as much room as your browser window has.
- pyduan 13y agoIt 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.
- IanCal 13y agoIn 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).
- pygy_ 13y agoThey 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.