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…
How to Write a Spelling Corrector
111–120 of 133 posts
Re: How to Write a Spelling Corrector
#112Earlier 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…
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
#113This 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…
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
#114Sadly - 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
#115Is 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.
Re: How to Write a Spelling Corrector
#116Any article like this for grammar correction? 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
#117His 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…
Re: How to Write a Spelling Corrector
#118His 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…
Re: How to Write a Spelling Corrector
#119I 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…
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
#120I 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.
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.