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

How to write a spelling corrector (2016)

norvig.com

Post reply on HN
Print view View original

31–40 of 87 posts

Re: How to write a spelling corrector (2016)

#31

Post by falsedan »

The unit tests worry me:

    assert len(WORDS) == 32192
    assert sum(WORDS.values()) == 1115504
    assert WORDS.most_common(10) == [
     ('the', 79808),
     ('of', 40024),
     ('and', 38311),
     ('to', 28765),
     ('in', 22020),
     ('a', 21124),
     ('that', 12512),
     ('he', 12401),
     ('was', 11410),
     ('it', 10681)]
    assert WORDS['the'] == 79808
Those aren't testing the file open, or Counter, or read, but instead are tightly-coupling the tests to the exact corpus. The code really should have not hard-coded the corpus, and the tests should have supplied a smaller corpus of known length where each word's frequency+probability was obvious from inspection.

There's another overfitted test just before this:

    assert Counter(words('This is a test. 123; A TEST this is.')) == (
           Counter({'123': 1, 'a': 2, 'is': 2, 'test': 2, 'this': 2}))
What is this verifying? We know how a Counter works, we don't need to test it; and the previous test already established the correctness of words().

I see a lot of junior engineers following this style of tightly-coupled, overfitted tests, and seen how a few years of growth can lead to tens of thousands of tests whose primary value is to provide Amazon with a predictable stream of AWS revenue (as we run all th tests) & make the engineer feel better for writing tests.

Re: How to write a spelling corrector (2016)

#32

Post by lb1lf »

I know a spelling corrector is not the same thing as a spelling checker, but this is too good an opportunity to pass to promote Martha Snow's hilarious poem 'Spell Chequer':

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.

Re: How to write a spelling corrector (2016)

#33

Post by wolfgarbe »

apendleton wrote: post #6

While doing a bunch of research on exactly this problem space recently for a project, I stumbled onto this improvement on the Norvig corrector idea http://blog.faroo.com/2012/06/07/improved-edit-distance-base... that's one of those things that's so deceptively simple you kick yourself for not thinking of it: it turns out you can model the same "generate all the variations" effect but generating only the deletes, rath…

Here is the link to the SymSpell Github repository: https://github.com/wolfgarbe/SymSpell

An here a benchmark between Norvig's spelling corrector, BK-tree and SymSpell: https://towardsdatascience.com/symspell-vs-bk-tree-100x-fast...

Re: How to write a spelling corrector (2016)

#34

Post by cdancette »

falsedan wrote: post #31

The unit tests worry me: assert len(WORDS) == 32192 assert sum(WORDS.values()) == 1115504 assert WORDS.most_common(10) == [ ('the', 79808), ('of', 40024), ('and', 38311), ('to', 28765), ('in', 22020), ('a', 21124), ('that', 12512), ('he', 12401), ('was', 11410), ('it', 10681)] assert WORDS['the'] == 79808 Those aren't testing the file open, or Counter, or read, but instead are tightly-coupling the tests to the exact…

This code is not written for production, it's just written to make you understand how the basic of this technology works. So I would say the unit tests have the exact same purpose: make the reader understand what the functions are doing (and not a real unit testing).

Since you speak of value, the value Peter Norvig is trying to provide is making readers understand the principles, he's not trying to provide some monetary value. So I don't think your criticisms apply here, those tests fit the purpose very well.

Re: How to write a spelling corrector (2016)

#35

Post by rietta »

shdon wrote: post #25

Spelling correction rather than spell checking and suggestions really bugs me. As soon as you have a somewhat international audience (and given that this is the internet - you probably do) or have any non-English content, automatic correction can be an actively user-hostile "feature". Especially on search engines, sometimes I am searching for words in another language, mixed-language results, or even doing an intenti…

Not only there. Automatic word replacement is my absolute least favorite iOS mobile feature. I cannot tell you how many times I painstakingly, painfully thumb typed exactly what I meant just to have it changed out from under me. And I have gone back to see nonsense messages where I know I didn't type what was sent. Very frustrating.

Re: How to write a spelling corrector (2016)

#36

Post by slfnflctd »

chmike wrote: post #15

What I would like to know is why the spelling correction suggestion of Apple iOS are so bad. Why can they get along with this ? I used to disable it. It can't even make a suggestion when there is only one missing character.

I turned off Autocorrect in short order when I had an iPhone for this reason (and others). Now, my Android speech recognition - which seems to be getting worse lately - pulls completely incorrect spelling from thin air constantly, sometimes not even giving me the proper spelling in the 'correction' drop-down list.

I'm tempted to wonder whether speech-to-text is actually saving me enough time after all the fixing I need to do now to be worth it. It's more than a little frustrating.

Re: How to write a spelling corrector (2016)

#37

Post by crispyporkbites »

rietta wrote: post #35
shdon wrote: post #25

Spelling correction rather than spell checking and suggestions really bugs me. As soon as you have a somewhat international audience (and given that this is the internet - you probably do) or have any non-English content, automatic correction can be an actively user-hostile "feature". Especially on search engines, sometimes I am searching for words in another language, mixed-language results, or even doing an intenti…

Not only there. Automatic word replacement is my absolute least favorite iOS mobile feature. I cannot tell you how many times I painstakingly, painfully thumb typed exactly what I meant just to have it changed out from under me. And I have gone back to see nonsense messages where I know I didn't type what was sent. Very frustrating.

I think this could be corrected if the spell corrector factored in the time taken to write the word out. If the user takes longer than average to write the word they are probably deliberately spelling it out, compared to just mashing the screen to get the words through.

Re: How to write a spelling corrector (2016)

#38

Post by madacoo »

lb1lf wrote: post #32

I know a spelling corrector is not the same thing as a spelling checker, but this is too good an opportunity to pass to promote Martha Snow's hilarious poem 'Spell Chequer': 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…

Thanks for sharing this.

I found it difficult to parse the initial couple of lines because I was constantly attempting to read by attaching meaning to the spellings: "Eye halve" is a bit frightening in that sense. But then I realised I can read the text as sounds and almost ignore the spellings. Listening to what the sounds made in my head allowed for a much faster pace of comprehension because I didn't have to keep correcting myself.

This poem demonstrated for me that it is possible to read and listen simultaneously, and that I don't usually do that. It seems that it would probably add to the experience of other poems to read them in this manner.

Re: How to write a spelling corrector (2016)

#39

Post by FranOntanaya »

shdon wrote: post #25

Spelling correction rather than spell checking and suggestions really bugs me. As soon as you have a somewhat international audience (and given that this is the internet - you probably do) or have any non-English content, automatic correction can be an actively user-hostile "feature". Especially on search engines, sometimes I am searching for words in another language, mixed-language results, or even doing an intenti…

I almost added autocorrection to a translation pipeline once. Curated a subset of unambiguous safe cases to reduce the manual workload. I parked it away because I didn't see a way to reliably convey this was just lowering the number of manual corrections needed.

A bad part about user-end autocorrection is that the end user is looking only at the case they have in front, not the overall average — if they have a case where it worked very well, they'll start overly trusting it and failing at producing good results. If they have a case where it wasn't useful, they'll be annoyed by it and feel they are doing more than they should. In all cases someone is going to be unhappy.

If I can't expect all ends to understand the value I'd mostly just look for pipelines where a-c could be an internal process and there was no need for the data provider and end user to be aware that it's happening. But then, ascertaining this is a problem on its own.

Re: How to write a spelling corrector (2016)

#40

Post by rietta »

crispyporkbites wrote: post #37
rietta wrote: post #35

Earlier quoted context omitted.

Not only there. Automatic word replacement is my absolute least favorite iOS mobile feature. I cannot tell you how many times I painstakingly, painfully thumb typed exactly what I meant just to have it changed out from under me. And I have gone back to see nonsense messages where I know I didn't type what was sent. Very frustrating.

I think this could be corrected if the spell corrector factored in the time taken to write the word out. If the user takes longer than average to write the word they are probably deliberately spelling it out, compared to just mashing the screen to get the words through.

Agreed. I am a touch typist on a regular computer. I literally hate writing on the phone. I find it an utterly odious process. So much for user friendliness from my point of view.
Post reply on HN