Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to Write a Spelling Corrector

norvig.com

Post reply on HN
Print view View original

101–110 of 133 posts

Re: How to Write a Spelling Corrector

#101

Post by kragen »

mack73 wrote: post #86
kragen wrote: post #83

Earlier quoted context omitted.

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

Sir, btw, I need a rule that I can use intuitively when deciding on wether to concatenate two words and when to put a dash between them. Do you have one?

Sir, it depends entirely on how widely used the compound word in question is. Hyphenated compounds that become sufficiently familiar lose their hyphen.

Re: How to Write a Spelling Corrector

#102

Post by kough »

abecedarius wrote: post #62
kough wrote: post #44

Earlier quoted context omitted.

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

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

caught me, I hadn't read through the article, wasn't sure whether or not WORDS was a set or a dict. Like desdiv points out, this isn't a big deal, you can maintain an equivalent WORDS structure that is a set.

Re: How to Write a Spelling Corrector

#103

Post by sn9 »

ChicagoBoy11 wrote: post #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…

The resources are out there. It's more an issue of educators and policy-makers either not knowing they exist or not knowing that's what they need.

I'm thinking of books like Think Python and How to Design Programs.

Re: How to Write a Spelling Corrector

#104

Post by ChicagoBoy11 »

sn9 wrote: post #103
ChicagoBoy11 wrote: post #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…

The resources are out there. It's more an issue of educators and policy-makers either not knowing they exist or not knowing that's what they need. I'm thinking of books like Think Python and How to Design Programs .

HtDP is fantastic. I taught an after-school class with it and it went really well.

Re: How to Write a Spelling Corrector

#105

Post by xapata »

leblancfg wrote: post #96
xapata wrote: post #74

Earlier quoted context omitted.

Easy in the sense of more pleasant version control diffs.

Couldn't it cause issues with "object definition" code in REPLs and editors, and interfere with documentation generators, i.e. [Sphinx]( http://www.sphinx-doc.org/en/stable/ )?

I'd be surprised if so. Most of those tools rely on the built-in parser, which treats all string literals similarly.

Re: How to Write a Spelling Corrector

#106

Post by xapata »

WhitneyLand wrote: post #43

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

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

Re: How to Write a Spelling Corrector

#107

Post by gravypod »

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 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?

Re: How to Write a Spelling Corrector

#108

Post by reachtarunhere »

jedberg wrote: post #15

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

I read this in July. I am sure that the Future work section has been better explained. The main code is the same.

Re: How to Write a Spelling Corrector

#109

Post by riboflava »

imgabe wrote: post #99
danso wrote: post #55

Earlier quoted context omitted.

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…

The compiler/interpreter will correct your syntax. Explain it once and show where the documentation is, then let kids loose. There's no need to do a worksheet with 100 "spot the syntax error" problems or to have to write it out by hand on a piece of paper to learn it. That kind of pain is only going to teach kids that programming is a boring game of "find the missing semi-colon".

They're going to have to play that game anyway since the compiler/interpret won't spell out the exact issue every time. But they'll get through it anyway because their goal is something else rather than that game. A lot of learning comes from getting past stepping stones, but targeting a stepping stone as an explicit thing to learn and drill on is a poor plan.

Re: How to Write a Spelling Corrector

#110

Post by kevin_thibedeau »

misiti3780 wrote: post #45
leblancfg wrote: post #27

Earlier quoted context omitted.

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 is a great idiom. i remember the first time i saw it (possibly in is very essay), i thought it was awesome. I use it all over the place now. it is similiar to the javascript ternary operator [1], which I also find to be very useful var varX = (boolean) ? 'X' : 'Y' [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

This isn't the Python ternary which is:

  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'
Post reply on HN