Live data from Hacker News

How to Write a Spelling Corrector

norvig.com

111–120 of 133 posts

Re: How to Write a Spelling Corrector

#111

Although 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 anoth…

When i worked at iTunes they have a mega 'bad_words.txt' file. It was fun to read when bored.

Re: How to Write a Spelling Corrector

#112
post #91
post #89

Earlier quoted context omitted.

I 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 s…

> 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 pote…

I 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.

Re: How to Write a Spelling Corrector

#113

This 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…

Yes, 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.

Re: How to Write a Spelling Corrector

#114
I'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.

Re: How to Write a Spelling Corrector

#115
post #77

Is 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.

This is the very root of how modern spellcheckers work, but they add more layers, using language modelling.

Re: How to Write a Spelling Corrector

#116

Any article like this for grammar correction? I've been interested to know why grammar checking and corrections can't be more accurate.

"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.

Re: How to Write a Spelling Corrector

#117

His 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

Came 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 someth…

That was one of the phrases used in the program that taught me to touch type. Stuck with me for decades..and has been almost as useful to me as learning to touch type...

Re: How to Write a Spelling Corrector

#118

His 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

Came 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 someth…

That was one of the phrases used in the program that taught me to touch type. Stuck with me for decades..and has been almost as useful to me as learning to touch type...

Re: How to Write a Spelling Corrector

#119
post #55

I 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…

I agree that what Norvig demonstrates here and in all of his notebooks is an ideal of how we use programming to explore (nevermind implement ) concepts. But how do we get there without teaching people how to program, including syntax? I think everyone agrees that kids should be able to understand the themes of "A Modest Proposal" and perhaps even write with such depth, but they have to learn their ABCs and be compell…

Use languages with simple syntax and it's a non issue. There is no need for both a while and do loop in an intro coding course.

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.

Re: How to Write a Spelling Corrector

#120
post #65

I 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…

By that reasoning, we should not teach kids how to spell, or about punctuation, and just aim for them writing essays/stories/novels.

programming is already such an opaque concept before you learn it, kids entering the class won't even really know what programming is.

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.

Post reply on HN