7 ms·
Spelling Corrector in 21 lines of Python
- timrobinson 16y agoI'm no Python expert, but I liked doing this in Haskell: http://www.partario.com/blog/2009/10/a-spelling-corrector-in-haskell.html http://www.partario.com/blog/2009/10/a-spelling-corrector-in... https://github.com/timrobinson/spell-correct/blob/master/Correct.hs https://github.com/timrobinson/spell-correct/blob/master/Cor...
- cormullion 16y agoliked your Haskell version. Makes me want to learn the language!
- rayval 16y agoInteresting that the shortest (and among the most readable) is the 15-line version written in old-school AWK: http://pacman.blog.br/wiki/index.php?title=Um_Corretor_Ortográfico_em_GAWK http://pacman.blog.br/wiki/index.php?title=Um_Corretor_Ortog... A surprise is that the Perl implementation weighs in at 63 lines. I would have expected much less. I expect a much shorter version is possible, relying on idiomatic constructs at the expense of readability.
- tedunangst 16y agoIf you run a2p on the awk, then remove some boilerplate and unformat as per the original, you end up with only about 18 lines of perl.
- abecedarius 16y agoI like awk (and used it a lot 15-20 years ago), but that code to my eye is oversqueezed and hard to read.
- joshu 16y agoThat's perl6, btw...
- SlyShy 16y agoIf anyone is interested in other applications of this technique, this is a Ruby library I wrote to do sentence tokenization: https://github.com/SlyShy/Tactful_Tokenizer https://github.com/SlyShy/Tactful_Tokenizer
- tgflynn 16y agoAnyone else having trouble parsing this list comprehension ? e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS
- marcinw 16y agoIn a traditional for loop fashion: def known_edits2(word): L = [] for e1 in edits1(word): for e2 in edits1(e1): if e2 in NWORDS: L.append(e2) return set(L)
- tgflynn 16y agoThanks for the clarification. I didn't realize that list comprehensions mapped so directly to nested loops, I was particularly confused by the variable name scoping rules.
- deleted 16y ago[deleted]
- cema 16y agoThe double "comprehension" loop is like a double nested "regular" loop here.
- prs 16y agoScrolling to the bottom of the article gives you a list of similar implementations in other languages. Very interesting to see how other have tackled this programming problem.
- gregschlom 16y agoI was somewhat amused to see that most other implementations take around 30 - 60 lines of code, except Java : 372. But the comparison may not be fair, as the Java author may have tweaked the algorithm or added new features
- freakwit 16y agoThere are two implementations listed for Java. The first is 35 LOC and the second is 372.
- veb 16y agoIn PHP, you can use the levenshtein() function. http://php.net/manual/en/function.levenshtein.php http://php.net/manual/en/function.levenshtein.php
- l0nwlf 16y agoLevenshtein Distance ( http://en.wikipedia.org/wiki/Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance ) is a standard algorithm taught in algorithm courses as a standard example of Dynamic Programming. Some discussion here : http://stackoverflow.com/questions/1564184/edit-distance-algorithm http://stackoverflow.com/questions/1564184/edit-distance-alg...
- cloudkj 16y agoLevenshtein/edit distance isn't too useful for spell checking though. Edit distance can yield you the absolute difference between two words, but your goal is to find the words that have the smallest such distance with the word in question. Simply calculating the edit distance between the word in question and all other dictionary words isn't good enough - you'll have to be a bit more clever.
- adamzochowski 16y agoLevenshtein is good for many languages. However, for English nothing beats soundex type algo. I believe major SQLs and php do soundex. Soundex is an old algorithm, century old, designed to find immigrants by their last name, no matter how they converted it from their native language to english. For example: if one came and had name Szczybliewski or had it Shcheeblevsky , then soundex should return close match. Metaphone is improved version of soundex (available in php). And if you are careful, you can find double-metaphone out there. Kind regards
- Terretta 16y agoI dropped by to say this. The examples in Future Work 2 would all have been resolved by checking results against Soundex, a simple check with significant improvement. There are two classes of errors: misspellings and typos. Edit distance (Levenshtein) is reasonable for typos, while the examples in Future Work 2 are misspellings. Another trivial improvement is to weight edit distance by typo distance.
- clvv 16y agoI have seen this one before somewhere, and what amazes me is that how you can solve problems without a hassle if you get the "trick" right. Another case I read was that Google use(at least used) two vectors(each consists of many 0s and 1s, which in turn represent whether the web page has the keyword or not) to represent web pages, and calculate the angle between the vectors to figure out the similarity(a value) between web pages.
- l0nwlf 16y agoYou are probably talking about Cosine similarity ( http://en.wikipedia.org/wiki/Cosine_similarity http://en.wikipedia.org/wiki/Cosine_similarity ) , a commonly used technique in the field of IR/NLP.
- maurits 16y agoThat would be the cosine metric then. I don't think it is that simple. The position (or dimension if you will) of a keyword in the data-vector is all important. So equal vectors in terms of the symbolic presence of a number of keywords will generate great cosine distances the moment the keywords are not in equal position.
- bad_user 16y agoThat wouldn't work well, because you need to take into account the relevance of a keyword for those web pages. Check out the Tf-Idf weight for getting an idea on how to do that: http://en.wikipedia.org/wiki/Tf%E2%80%93idf http://en.wikipedia.org/wiki/Tf%E2%80%93idf A useful trick based on the technique you describe: build vectors where each dimension represents a user in the system (1 means the user visited that web page); since people are interested in a narrow array of topics. Furthermore you can extend this to find similar users. Amazon does this to find similar or complementary products.
- tyler 16y agoIt sounds like you're conflating two techniques here. The first (as others have mentioned) is cosine similarity, which measures the angle between the vectors. However, the bit about 0s and 1s sounds like you're talking about locality-sensitive hashing (http://en.wikipedia.org/wiki/Locality_sensitive_hashing http://en.wikipedia.org/wiki/Locality_sensitive_hashing). LSH is often used to estimate cosine similarity, as cosine similarity can be quite expensive to calculate. I know Google and others are using it for such.
- singular 16y agoI found it fascinating that you can actually implement something seemingly so magical in such a small amount of code. I'm down as 22 lines of C#, though to be fair I am cheating vastly and the lines are huge :) http://www.codegrunt.co.uk/2010/11/02/C-Sharp-Norvig-Spelling-Corrector.html http://www.codegrunt.co.uk/2010/11/02/C-Sharp-Norvig-Spellin... C# does offer some nice features to give you some succinctness but there's no getting away from the verboseness of a java-like language.