How to Write a Spelling Corrector
norvig.com
norvig.com
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!
I wish I could say that in my time of teaching, I've met people who could just get these things without actually writing code. But I think for most non-geniuses, including myself, it's all too abstract until you know how to concretely write code yourself.
I'll give you a perfect example. I was asked to evaluate this Scratch course for middle schoolers just as they were about to present their final projects. One of the kids did a basic pong-like game with human-controlled characters. The ball would move all over the place, seemingly randomly. The game didn't seem to make any sense to the kids who played it. But, the administration felt that this was an incredible success.
I later learned that he had produced the game by mostly following along a step-by-step tutorial introduced in class. And I also learned that the reason the ball moved erratically was that the kid had absolutely no concept of how to deal with the angles, much less identify what portion of the character the ball had struck!
To me, THAT would have been the real learning! What an opportunity to have taken that kid outside and kick a soccer ball (this was in Brazil) outside and explore some intuition about how it rebounded on the wall; what a chance to see if he could not come up with a way to grok a solution to figuring out to detect where in the character the ball had hit since this didn't come out-of-the-box in Scratch.
In other words, I don't mind that they learn the syntax. But there's a reason why firms outsource a lot of "coding" to South Asian countries for pennies on the dollar. Knowing the syntax is cheap. Stimulating kids to think about problems, developing a routine and passion about solving them, that's where the real pot of gold is.
For control: foreach, while, Switch, Function
Datatypes: List, enum, Strings, signed 64 bit int, 64 floating point.
Would need a small standard library with IO.
Yes, I avoided the 'if' because Switch works and get's people thinking in less binary terms. Same with skipping arrays.
def pdist(counter):
"Make a probability distribution, given evidence from a Counter."
N = sum(counter.values())
return lambda x: counter[x]/N
P = pdist(COUNTS)
Spelling and punctuation details can come later. If the kids start out being wrong all the time, they just quit.
How about "if you want your citizens to fund a space program, don't gather the workforce to build a spaceship but teach them to yearn for the vastness and potential of the void."
if you start with a single-minded focus on syntax, as most do, the kid's mental model of programming becomes "programming is done by entering premade code words that someone made up. if i want to do something, i need to find the premade code word that does that thing".
as opposed to, "programming is about blobs of information and what i do with them - changing their shape, organizing them, picking certain things from them, taking stuff away from them. if i want to solve a complicated problem, i won't start typing, i'll start thinking about how i'd make a machine that makes the blob i want. the best way to make a machine like that is usually out of smaller machines that live inside it. i'd figure out what the smallest machines i need are, and i'd make those, and then use those to make the bigger machines, until i'm done."
if kids were started with a functional, problem-solving oriented approach like that, you'd create very capable programmers much faster. this applies to introductory CS classes in college. i went into my first CS class knowing absolutely nothing about programming beyond CSS/HTML - i was a math / mech eng major at the time. i think it was the third class where they had us write a program in C that did some non-trivial dynamic allocation. they never told us things like what the heap or the stack are, or the concept of a memory leak, what happens if you dereference a null pointer, etc, etc. i never got that program to stop segfaulting. i came very close to failing that class and was told, because of that, i probably shouldn't continue with CS. i taught myself computer science instead and now i know that i'm not stupid or unsuited to programming - my introductory CS education was shit.
(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.)
I'm thinking of books like Think Python and How to Design Programs.
And the actual coding is a Visual Basic forms and a bit of html/javascript.
Very little in the way of what I would call proper coding: data structures, algorithms.
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.
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.
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.
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.
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.
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.
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?
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.
(it's pretty subtle to catch all of the often-scatological jokes in there)
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).
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.
But... but programmers on HN told me that tries are just useless pieces of trivia used to fail people in interviews, and if you need them a library is just going to do it for you in the most efficient possible way.
Although he does seem to be using doc strings incorrectly
return set(w for w in words if w in WORDS)
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.
return {w for w in words if w in WORDS}
return words & WORDS
return words.intersection(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.
var varX = (boolean) ? 'X' : 'Y'
varX = 'X' if boolean else 'Y'
# And is chainable in a more natural way than C*:
varX = 'X' if boolean else 'Y' if other else 'Z'(He also switched from manually implementing counting behavior with a Dict to a Counter, added the P function which replaces an inline dict lookup, similarly added the candidates function, changed the somewhat awkward known_edits2 function to just edits2, and reorded some things.)
[] http://web.archive.org/web/20160408180602/http://norvig.com/...
edit: small edits
>>> import spell
>>> spell.correction('ducking')
'fucking'
>>>
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.941176470588I 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-base...
I implemented it here for fun in common lisp. Excuse the ugly code. https://github.com/RyanRiddle/lispell
Does anyone know which parts are new in August 2016? I've read this before and it isn't sticking out to me.
https://web.archive.org/web/*/http://norvig.com/spell-correc...
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)http://blog.databasepatterns.com/2014/08/postgresql-spelling...
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?
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.
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.
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.
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.
Finnish is probably even worse because of it's conjugation.