12 ms·
How to Write a Spelling Corrector
- abecedarius 10y agoThe code's been updated to more modern Python and to not try to smooth the probabilities. (Also it computes probabilities instead of frequencies now, though that shouldn't affect the result.)
- lb1lf 10y agoSpell chequer Martha Snow Eye halve a spelling chequer It came with my pea sea It plainly marques four my revue Miss steaks eye kin knot sea. Eye strike a quay and type a word And weight four it two say Weather eye am wrong oar write It shows me strait a weigh. As soon as a mist ache is maid It nose bee fore two long And eye can put the error rite It's rare lea ever wrong. Eye have run this poem threw it I am shore your pleased two no It's letter perfect awl the weigh My chequer tolled me sew.
- bradbeattie 10y agoIs this where you start considering ngrams probabilities? Curious as to the best approach to this, as it's clear we can all read the above.
- agd 10y agoIn a way, I'm surprised I can read this so easily. Do our brains read by converting text to sounds, and then parsing the sounds?
- nkrisc 10y agoAs a native English speaker, I found my self reading it and then having to back-track by a few words to say them aloud in my head to discern the intended meaning as it was the sound of the words that was important, not the meaning of the word shape. The second time I read it through it was much easier.
- schoen 10y agoKind of a controversial issue whether this is always the case, but it's at least commonly or typically the case for many readers: https://en.wikipedia.org/wiki/Subvocalization https://en.wikipedia.org/wiki/Subvocalization
- lb1lf 10y agoI was pondering the same thing; also, I wonder whether not being a native English speaker makes it easier or harder to read it - English is my third language and I found I could read it without any problems. I think I've read somewhere that reading is basically done by the brain registering the first and last few letters in a word, then just checking whether the ones in the middle are more or less what you expect and where you'd expect them. (In other words - if the start and/or end of a word is altered, your reading speed and comprehension should take a nosedive compared to just messing with the letters in the middle) If there is some truth to that, it would go a long way towards explaining why we can read it with as little trouble as we do.
- BinaryIdiot 10y agoHonestly it took me a minute before my brain started to be able to read it a lot better. At least it was very slow because everything is so wrong. So I don't know how common either of our experiences are but I am your contrary :)
- dsr_ 10y agoEarly reading is taught that way. You may have heard of "Phonics" as an element of literacy? Full literacy in alphabetic-phonetic languages includes the steps of (1) no longer sounding out words aloud and (2) no longer sounding out most words in your head, but rather grasping the shape of the word immediately.
- fallous 10y agoIt's the jump from word-as-sound to word-as-symbol, which I think a lot of people never make, partially because it's not particularly useful in their lives. I suspect those involved in programming skew very much towards the word-as-symbol, but whether that is causative or correlative I can't say.
- lb1lf 10y agoI definitely belong to the word-as-symbol camp when reading in my native Norwegian. Besides, I am a programmer (A shoddy one in all but assembly language, though...) Interestingly, perhaps, is that I recently made the transition from word-as-sound to word-as-symbol in another language - morse code; that felt very odd while it was going on - I have parsed words character by character for a couple of decades, and suddenly, I found my decoding lagging further behind - I had started hearing words as units, rather than composites of characters. Funnily enough, it was through no conscious effort - just happened, over the course of a few hours.
- SamBam 10y agoI had to explicitly read it "aloud" in my head, in a way that I don't do when reading other text. I can generally read text very quickly without having to hear it in my head, and in this case it was impossible.
- fallous 10y agoI think many people do have brains that operate this way, probably because their understanding of language is grounded in conversation as a first experience. I suspect this is the reason you see confusion with "your, you're" and "there, their, they're." I don't parse language in quite that manner, and even in speaking I have a different "mouth feel" for those homonyms. This creates a modest inversion of the idea of spelling errors for me, in that people who truly do say homonyms in such a way that to my hearing it is exactly the same require me to parse for context.
- schoen 10y ago> I don't parse language in quite that manner, and even in speaking I have a different "mouth feel" for those homonyms. I believe in the (somewhat controversial) non-subvocalization-based text processing and even think I do it myself, but I'm wondering if you could describe more about the "mouth feel" issue. Do you mean that you believe that you pronounce them using different phonology (that another person would potentially be able to hear), that your muscles are doing something different but not in a way that makes an auditory difference, or simply that you're subjectively aware of the spelling while speaking but not necessarily in a way that makes a physically-observable difference? Or is it not quite clear which of these is the case? I think this is an interesting question in the philosophy of language and also in the psychology of reading. (I've thought about this myself but haven't studied the academic literature about it.) If your answer is the first one, I wonder if you'd be willing to make an audio recording of yourself pronouncing these words that might show what difference you experience. By the way, there are documented cases where spelling differences have created new pronunciation differences that didn't previously exist in the spoken language. Maybe something like that has been happening in your idiolect?
- khedoros 10y agoI have a similar feeling, when I pronounce a homonym/homophone. The word "mouth feel" resonates for me, although I suspect that sometimes it's just an awareness of the spelling of the word. Other times, I'll consciously choose to pronounce a word differently to try to disambiguate it. I'll say "aunt" as "ant"/"ont" (read those second as phonetically-spelled Californian American pronunciations) depending on the situation and flow of the sentence. "They're" is usually "They-er", "their" is sometimes "thur" (like "fur" with a /ð/), and "there" feels like it's pronounced the expected way. "To" might be "tə", but "two" and "too" never are. Of course, that's all when I'm paying close attention to what I say. I'm sure there are times that I go against those. Also, sorry for the mix of layman phonetic spelling and IPA.
- Tloewald 10y agoYou should read Feersum Endjinn
- smnscu 10y agoI thought you came up with it on the spot but it's a real thing. http://www.davidpbrown.co.uk/poetry/martha-snow.html http://www.davidpbrown.co.uk/poetry/martha-snow.html
- clentaminator 10y agoLove it. It also reminds me of the poem The Chaos, by Gerard Nolst Trenité: http://ncf.idallen.com/english.html http://ncf.idallen.com/english.html
- s-phi-nl 10y agoAlong similar lines, "The King's English" http://holyjoe.org/poetry/anonA.htm http://holyjoe.org/poetry/anonA.htm
- clentaminator 10y agoThanks for posting this. It's just as much of a tongue twister as The Chaos :)
- schoen 10y agoRelated: https://trialbysteam.com/2010/03/09/d-j-enright-the-typewriter-revolution/ https://trialbysteam.com/2010/03/09/d-j-enright-the-typewrit... (it's pretty subtle to catch all of the often-scatological jokes in there)
- votr 10y agoYou sound like a character from a Dickens novel.
- stronglikedan 10y agoHer spell checker works great, but it looks like she needs a grammar checker too.
- Grue3 10y agoThat poem could've been written about speech recognition software as well.
- mmanfrin 10y agoI had a surprisingly hard time reading this; but I don't subvocalize, and words are 'things' to me (for example, your/you're is read differently in my head and makes me very sensitive to that mistake).
- petercooper 10y agoI think it's cool how you can tell the writer's accent from this - something you can rarely do with written English. "halve" and "kin knot" sound nothing like "have" or "cannot" in my native accent, for example. Similarly, rhymes in Shakespeare's sonnets have been used to work out how Shakespeare spoke the same words, as we no longer pronounce the words the same way (and many of the rhymes have been broken).
- 1024core 10y agoThe last 9 times it was submitted: http://goo.gl/mVSi7W http://goo.gl/mVSi7W
- gist 10y agoI want to see someone do a post on how they analyzed all of the top stories on HN (ones that got more than "x" upvotes) and calculated the ones that could be resubmitted after "y" time period had gone by. For extra bonus points figure out if any particular hn handle has gone in and resubmitted old stories in the past by a similar technique and analysis.
- dvirsky 10y agoIn Go.
- colobas 10y agoI found it in a StackOverflow answer and found it worth sharing. Didn't bother checking if it had already been posted on hackernews.
- DanBC 10y agoNormally when people tell you something has been submitted before they're saying "you might find some of these earlier comments interesting too".
- scott_s 10y agoYou can also find that result by clicking on "past" under the submission.
- nxzero 10y agoReverse of the logic presented could be used to inject typos into a document per distributed copy of it to help identify anyone sharing documents online; basically each copy is unique to allow for attribution. Hash of each document could even be given to a third party and archived to provide if needed independent verification of the claim that the document and the document itself could be encrypted, loaded to another third party to log the IP and finger print of the download provide another independent verification of the exchange.
- ksk 10y agoWhat is the application where typos in a document are acceptable?
- jacalata 10y agoPre-publish review copies of a novel
- dsr_ 10y agoClassified reports. This technique is called the Canary Trap, with the name (but not the technique) coined by Tom Clancy. https://en.wikipedia.org/wiki/Canary_trap https://en.wikipedia.org/wiki/Canary_trap
- ksk 10y agoOkay, If you broaden it enough I'm sure you can find some use for almost everything. I was thinking of more of a mainstream application.
- deleted 10y ago[deleted]
- robryk 10y agoFor that purpose you'd want to add typos that would be "corrected" into the wrong word by a typical spellchecker or that are actually correct, but atypical in context, words. Otherwise passing the document through a spellchecker would remove the watermark.
- Halienja 10y agoNeat Code - expressing high-level concepts in such a concept manner.
- misiti3780 10y agoHis python code styling is really awesome. So concise. Probably inspired by all the LISP he wrote in the past. Although he does seem to be using doc strings incorrectly
- leblancfg 10y agoCame here to say this. I've combed through his pieces many times over just to glean the way he structures his code. Here, he got my head spinning for a minute with return set(w for w in words if w in WORDS) and made a mental note to use that idiom in the future. As for doc strings, well, this is just a toy piece of code after all. The main purpose for the code is to be read, instead of actually used. something something hobgoblin of little minds Edit: formatting.
- kough 10y agoYou can also use the set-comprehension syntax, which functions equivalently but looks slightly nicer: return {w for w in words if w in WORDS} could have also directly used the intersection operator on the sets: return words & WORDS or slightly more verbose, but maybe more clear for colleagues who don't regularly use sets in Python: return words.intersection(WORDS)
- abecedarius 10y ago> return words & WORDS Not quite. It'd have to be set(WORDS) instead of WORDS -- which'd be expensive. Or WORDS.keys(), which I'm not sure about -- I'd have to benchmark it.
- xapata 10y agoI wouldn't worry about the expense of set construction vs the expense of an n-squared algorithm.
- deleted 10y ago[deleted]
- 10y ago
- bsenftner 10y agoAlthough not a spell checker specifically, I wrote an offensive language filter for a chat system used by the National Hockey League for a period when they hosted communal chat rooms during televised games. The architecture I used is completely different from what is described here, but the goals are very similar. I had to handle any curse word in any language, including curses from one language translated into another language, as well as offensive phrases, and their translated equals, as well as offensive slang, and mispelt offensive slang translated from other languages. I ended up with an offense dictionary of about 700K words and phrases. This was back in '99, so my memory may not be 100% here, but I remember using Perfect Hash to generate a compiled hash table for the dictionary, and then a trie to organize the dictionary lookups. The entire system was about 150K of a downloaded exe to access the NHL simulcast chat, as all the offensive language filtering occurred on the client side. Chatting anything that could be offensive turned into a series of words with their interiors all asterisk '*', and it ran in something like 500 ms. Fun times. That company and project died with the dot com bust.
- Tloewald 10y agoInteresting. I had to write a badwords filter for a random name generator (for a procedural galaxy generator...) and it's quite a task just for English.
- bsenftner 10y agoIf you've not used a Trie https://en.wikipedia.org/wiki/Trie https://en.wikipedia.org/wiki/Trie I suggest checking them out. Very useful for fuzzy searching.
- majewsky 10y agoIndeed. I did a spell checker for a Haskell university course, and the trie was the recommended data structure. Makes it really easy to eliminate large chunks of the dictionary at once when edit distance gets too large during traversal.
- setheron 10y ago
- bpchaps 10y agoI love it. Spell checking was pretty relevant to some of my work recently and I needed to correct heavily typo'd address text from Chicago parking ticket data. It used difflib to recursively find similarly typo'd address until it finds a matching address within a list of correct addresses. Definitely a lot more to polish, but I'm kinda proud of the naive approach. https://github.com/red-bin/tyop_fixer https://github.com/red-bin/tyop_fixer coumbia,columbia,0.933333333333 argy,argyle,0.8 menomee,menomonee,0.875 newladn,newland,0.857142857143 boulevard way,boulevard,0.818181818182 sherwn,sherwin,0.923076923077 lawrencec,lawrence,0.941176470588
- evanjacobs 10y ago"why should they know about something so far outisde their specialty"
- jedberg 10y agoThe date on the top says February 2007 to August 2016. Does anyone know which parts are new in August 2016? I've read this before and it isn't sticking out to me.
- fancy_pantser 10y agoHere's the history, sorry there is no easy way to see diffs. https://web.archive.org/web/*/http://norvig.com/spell-correct.html https://web.archive.org/web/*/http://norvig.com/spell-correc...
- benhoyt 10y agoThe code has been updated stylistically, and I'm not sure what else has changed. Here's the old (Python 2.5) version from http://web.archive.org/web/20160110135619/http://norvig.com/spell-correct.html http://web.archive.org/web/20160110135619/http://norvig.com/...: import re, collections def words(text): return re.findall('[a-z]+', text.lower()) def train(features): model = collections.defaultdict(lambda: 1) for f in features: model[f] += 1 return model NWORDS = train(words(file('big.txt').read())) alphabet = 'abcdefghijklmnopqrstuvwxyz' def edits1(word): splits = [(word[:i], word[i:]) for i in range(len(word) + 1)] deletes = [a + b[1:] for a, b in splits if b] transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1] replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b] inserts = [a + c + b for a, b in splits for c in alphabet] return set(deletes + transposes + replaces + inserts) def known_edits2(word): return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS) def known(words): return set(w for w in words if w in NWORDS) def correct(word): candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word] return max(candidates, key=NWORDS.get)
- reachtarunhere 10y agoI read this in July. I am sure that the Future work section has been better explained. The main code is the same.
- deleted 10y ago[deleted]
- amelius 10y agoThey don't seem to address keyboard layouts.
- billconan 10y agothis is a good point I think. sometimes, people type wrong words, because certain keys are too close on the keyboard. another problem I found about the naive spelling corrector is, it doesn't take the pronunciation into account. certain wrong spelling looks different from the correct version by edit distance. but they sound similar.
- acdimalev 10y ago>>> import spell >>> spell.correction('ducking') 'fucking' >>> Yup, it works.
- Animats 10y agoThat's not how Google does it. Try spelling errors with Google Search. Google does multi-word spelling correction.
- majewsky 10y agoI guess that Google looks at each word individually. And what Google does is intriguingly simple: When they see someone do two similar searches from the same person, where the second search has way more results, they record the first search as "wrong spelling", and the second one as "correction".
- vpanghal 10y agoI wrote Rust version of spelling corrector sometime back to explore nitty gritty of language https://github.com/vpanghal/spellcorrector https://github.com/vpanghal/spellcorrector
- vcool07 10y agoIs there any C++ version of a decent spell checker ? Been looking for sometime (mainly out of curiosity), most are either amateur school projects or too academic/phd-ish....would love to go through a good open source C++ based spell checker that can be used in practise (with little modifications if required)
- vcool07 10y agoThanks for the suggestions, will check them out :)
- irremediable 10y agoWhat's wrong with Aspell? (Not saying you're wrong; just wondering what I've missed.)
- r-c-r 10y agoHave you tried hunspell? https://hunspell.github.io/ https://hunspell.github.io/
- abecedarius 10y agoYou could make a good start with the ideas from http://norvig.com/ngrams/ http://norvig.com/ngrams/ (a fancier corrector in the vein of the OP).
- WhitneyLand 10y agoAny article like this for grammar correction? I've been interested to know why grammar checking and corrections can't be more accurate.
- WhitneyLand 10y agoAn open source grammar project written by CMU with LGPL license and links to current and future research: http://www.abisource.com/projects/link-grammar http://www.abisource.com/projects/link-grammar
- Retra 10y agoEnglish text has an astonishing number of ambiguities and non-grammatical idioms.
- xapata 10y agoThe logic would be quite similar. The dataset would be much larger. For grammar, you'd need to go for trigrams at least, and likely 4-grams and 5-grams. Maybe much further for complex structures. To reduce the dimensionality you might start bucketing some words by part of speech.
- jomamaxx 10y ago"I've been interested to know why grammar checking and corrections can't be more accurate." It's because there is no such a thing as 'grammar' :) There is no such a thing as 'language' :) Ok, I misrepresented that a little - but there is no such thing as a 'word list of all the English words and proper names'. And there definitely no set of clear grammatical rules for English. For some languages - such as German - the rules are more precise, but even then. So what you end up with is a game of probability and a lot of risk of 'over-correction' (beta errors). Context matters a lot as well - multilingual speakers, casual typers. Go to a rap video on youtube and look at the comments. People are arguably not even writing English.
- elchief 10y agoI wrote one in PLV8 (Postgres) just for fun: http://blog.databasepatterns.com/2014/08/postgresql-spelling-correction-norvig-plv8.html http://blog.databasepatterns.com/2014/08/postgresql-spelling...
- ChicagoBoy11 10y agoI couldn't help but read this and think about all the "coding" initiatives I've seen in K-12 and shake my head. What Norvig is doing is what we should be teaching. He is tackling this seemingly REALLY hard problem by thinking about it methodically, translating some intuition into code, carefully constructing an argument about how to solve it, and ways that it could be extended. This is what actual engineers look like. Everything I've seen around "coding" though has become a masochistic exercise in teaching kids random syntax details and then calling them Coders and Geniuses and Computer Scientists when they successfully copy what the teacher showed them. When you read Norvig's code (big fan of his Sudoku one as well), you realize how the actual "code" is secondary in the sense that what it is really doing is expressing an idea. A very nunanced, elegant idea, but ultimately the product of doing some hard thinking and exploration on a problem domain. If we taught kids to just think about problems in this way, ohh what a world it would be!
- mack73 10y agoBut what you should realize is that the person who wrote this beautiful piece of code is someone who is at the peak of their career, a thinker, an artist, and that it must be ok to not ever rise to his level, because this is close to a master-piece. Few of these geniuses become professors, is just a guess, because no matter how quirky you are you always get a job somewhere.
- kragen 10y agoI think Norvig's actually improved substantially since he wrote this — he wasn't at the peak of his career! But yes, it's a masterpiece, and yes, it's okay to not ever rise to that level, because even if nothing you ever create is as worthwhile as this, it's still worthwhile. Hacking is fun! And sometimes very useful, too. (Also note that, despite appearances, this isn't the work of one man. Norvig didn't design Python and didn't invent the tabling technique for speeding up search; and Darius found a couple of bugs in the code. That doesn't mean it's not an authentic Norvig masterpiece.)
- mack73 10y ago
- yomritoyj 10y agoVersions in C, C++, Java, Haskell and Racket https://github.com/jmoy/norvig-spell https://github.com/jmoy/norvig-spell
- r-c-r 10y agoI added a spelling corrector to an application a while back. I tried a couple of libraries that implement these ideas. Problem is it can be slow for big words. I stumbled across this algorithm which is much faster if you allow some time to pre-process your dictionary. http://blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/ http://blog.faroo.com/2012/06/07/improved-edit-distance-base... I implemented it here for fun in common lisp. Excuse the ugly code. https://github.com/RyanRiddle/lispell https://github.com/RyanRiddle/lispell
- realworldview 10y agoCarefuly.
- tootie 10y agoIs this how modern spell checkers actually work? I assumed they would use a heuristic trying to match common misspellings to their frequent corrections. That or a combination of heuristic and Bayes.
- jomamaxx 10y agoThis is the very root of how modern spellcheckers work, but they add more layers, using language modelling.
- anonred 10y agoFor one, I'm fairly sure that modern spell checkers use n-gram language models rather than a 1-gram model to decrease perplexity. Disclaimer: I skimmed the article.
- Valkentino 10y agoIs it me or he's using the doc strings incorrectly?
- laxatives 10y agoNorvig's code is beautiful.
- WalterBright 10y agoThe D language compiler consults a simple spell corrector when encountering an unknown identifier. The dictionary is the list of names currently in scope. It's a nice improvement to the error message about an unknown identifier.
- 727374 10y agoIf people like this, also check out his course at Udacity - https://www.udacity.com/course/design-of-computer-programs--cs212 https://www.udacity.com/course/design-of-computer-programs--...
- gravypod 10y agoThis is really cool and I'm wondering if you could improve the ability of this by adding a markov chain/tree structure of most word usage patterns and doing contextual searching for your word. You wouldn't need your wordlist and your could compress and package this. The way this would work is by looking at the previous word, and the next word is available. It would find every word combination that looks like that and then do a Levenshtein distance for all of the words that come between these two items. Is this the way "big" spelling correction methods work or is it by other means?
- jomamaxx 10y agoYes, using language models is how it's done. Theoretically, it's not that hard, in practice, it's really hard. There is an online language modelling course from Stanford that you should check out if you want to take a stab.
- jomamaxx 10y agoI've done this before. Sadly - the problem is way harder. First - you get much better results by using language models, n-grams etc. to predict the likely hood of words given previous words. That can be hard. The really hard part comes down to language that people use. Colloquialisms, proper names, and mixed-languages ... make this stuff really, really hard. Getting it 'mostly right' is not hard. Getting it really good is very difficult and depends a lot on context. 'Srinivas' will not be in most people's dictionaries, but it's a common name in India. 'Le' and 'la' are words in french and some similar in Spanish - and a lot of writers jam these in all over the place. Over-correction and beta-errors become a huge problem. It's a really interesting premise and difficult for Engineers because it's purely probabilistic there is no way to build a perfect spellchecker unless you can agree 100% on what 'language' is, precisely ... and trust me there is no agreement on that. Not even close.
- mrweasel 10y agoWriting spell checkers is also hard in language that e.g. doesn't have spaces between composite nouns. In essence it makes it possible to make up a perfectly valid new word. We expect the spell checker to be able to recognise that word, because it knows the two words that the composite is made of. Finnish is probably even worse because of it's conjugation.
- anonfunction 10y agoI wrote a direct port in Golang with benchmark comparisons: https://github.com/montanaflynn/toy-spelling-corrector https://github.com/montanaflynn/toy-spelling-corrector
- taneq 10y agoThis is a beautiful example of pithy high-level coding. I feel compelled to mention, however, that the example word, 'thew', is in fact a(n archaic) English word: https://www.google.com.au/#q=thew https://www.google.com.au/#q=thew :P
- tranverfca 10y agoHi! I wet & wanna masturbate with you now. We will play? Im here - http://lynk5r.skhit.in/ http://lynk5r.skhit.in/