Live data from Hacker News

How to Write a Spelling Corrector

norvig.com

51–60 of 133 posts

Re: How to Write a Spelling Corrector

#51

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

An open source grammar project written by CMU with LGPL license and links to current and future research: http://www.abisource.com/projects/link-grammar

Re: How to Write a Spelling Corrector

#52
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.

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!

Re: How to Write a Spelling Corrector

#53
post #21
post #7

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

What is the application where typos in a document are acceptable?

Classified 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

Re: How to Write a Spelling Corrector

#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 compelled to write about what they ate for breakfast and other insignificant topics before they get to an adequate level.

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.

Re: How to Write a Spelling Corrector

#57

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…

It's funny, I was given this as a lab assignment around when the article came out. In fact, we were shown the article. We had an hour, maybe two, for the lab and had to re-implement it in C++. At this point I already had 3-4 years of experience with C++ but found the task ABSOLUTELY daunting. Looking at it now it seems simple, but I'll never forget trying to figure out how this works for the first time with the two hours I was given. Even if a solution is simple, understanding it can be hard, especially if it seems like it should be hard.

Re: How to Write a Spelling Corrector

#58
post #42

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

Have you tried hunspell?

https://hunspell.github.io/

Re: How to Write a Spelling Corrector

#59

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, you could learn so much just looking at how he defines functions.. see this for example:

    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)
from http://nbviewer.jupyter.org/url/norvig.com/ipython/How%20to%...

Re: How to Write a Spelling Corrector

#60
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…

Ohh I completely agree with you. But what I was mostly reacting to is the idea that the way to propel these kids into the 21st century is to simply teach them some basic coding syntax and leave it at that. Even the new AP CS curriculum seems to take a step back from "hard cs" by adding lots of content not directly related to solving cs problems. All that I really meant is that the true value in coding comes in using it to express solutions to problems, whereas teachers and schools that I've seen try to implement "coding" seem to think that if these kids just memorize syntax they have some great advantage in life.

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.

Post reply on HN