[HN Gopher] How to Write a Spelling Corrector (2007)
___________________________________________________________________
How to Write a Spelling Corrector (2007)
Author : graderjs
Score : 87 points
Date : 2022-03-06 06:05 UTC (16 hours ago)
(HTM) web link (www.norvig.com)
(TXT) w3m dump (www.norvig.com)
| isaacimagine wrote:
| What's cool is that it's now possible to use large language
| models to predict the probability of a given word, which doesn't
| only take into account the probability of a word appearing in a
| corpus, but also the probability in the context of the _exact
| sentence you 're writing_. This makes the spell checker more
| robust, and even able to correct small grammatical errors.
| There's a lot of interesting research on how people tend to
| misspell words, and even more research on how to correct based on
| these patterns. Interesting read, this subjet is--on the whole--
| very fun to dive into.
| mromanuk wrote:
| I would love to do that for an iOS keyboard, without a backend.
| I've built my own spell corrector going though the rabbit hole
| of tries and many other structures. iOS keyboards are
| constrained to 40Mb of RAM, I presume it's still too big to use
| a language model without a backend. Would be really cool to
| finally achieve a smarter prediction in-device, though.
| Gigachad wrote:
| This would be a massive improvement. It's frustrating when an
| extremely obscure word is the same as a common misspelling but
| spell check is no use since technically it is a word.
| razhab wrote:
| I'd be really curious to know how long it actually took Norvig to
| write the spell checker. It seems like such a simple idea and
| piece of code _after_ you 've read it but he suggests it took him
| a transcontinental flight worth of time.
|
| That, to me, is surprising in a potentially interesting way.
| Knowing that an expert like Norvig might still take hours to
| write such a seemingly simple program suggests the problem is
| harder than it appears in retrospect.
| ghusbands wrote:
| In general, with any project you can find online, you can find
| people claiming they would have done it faster. It's more
| tiresome than it is interesting.
|
| The program is simple once you know its shape, but there may
| have been quite some time spent in consideration of how it
| should work or the details of the edit distance. Also, most
| programmers overestimate how fast they can write something, and
| there are plenty of claims that studies show that programmers
| average only ten lines a day of code.
|
| It doesn't mean the problem is necessarily hard or that it
| needed to be for it to take time. And flights can be tiring and
| distracting.
| samwillis wrote:
| I have been on HN a long time, I remember reading this back in
| 2008 and learning from it. It's been posted a lot but that's an
| indication of an important educational resource:
| https://hn.algolia.com/?query=How%20to%20Write%20a%20Spellin...
|
| Amusingly half the comments from the first time it was posted
| (2007) are about how the post is a dupe...
| https://news.ycombinator.com/item?id=42587
|
| Another brilliant one is PGs "a plan for Spam":
| http://www.paulgraham.com/spam.html
| melony wrote:
| This is the same generative model used for optimal Wordle
| prediction.
| [deleted]
| ghusbands wrote:
| If you use a trie with suffix-sharing in a suitably dense array,
| and alter your edit-distance algorithm to use it directly, you
| can easily get two to three orders of magnitude faster, which
| could let you use this on a server for many clients.
|
| (My old team used that technique, though not in Python, many
| years ago. In modern times, for web clients, I'd export the work
| to the browser - a full dictionary in the above form is something
| maybe 200KB, if I remember correctly.)
| simulo wrote:
| It is a great piece of code to study as a beginner. It is easy to
| understand, non-trivial and has an easy-to-relate-to purpose.
| Norvig's implementation is in python, but he links to variants in
| many different languages at the bottom of the post.
| noneeeed wrote:
| I find spelling correction systems interesting because I
| frequently seem to confuse them. There is something about the way
| I misspell that causes them issues. I am often only two letters
| out, but I get no suggestions. My misspelling tend to involve
| flipping vowels, a for o for example.
|
| I should start taking notes to see if I can work out a pattern.
| bArray wrote:
| Better yet, it should learn from your manual corrections and
| the patterns you commonly mistake.
|
| One thing I do that confuses them is putting in extra letters I
| think should probably be in there. Like 'pherosious' instead of
| 'ferocious' (Firefox recommends 'heterosporous' - because
| that's closer!).
| ghusbands wrote:
| When I worked on a spelling corrector around 2007, it was
| trivial to get better suggestions than Word and other software.
| If you have examples, I'd be interested to see how well our
| spelling corrector does, compared to Aspell and Word and such.
| Maybe it would be worth finding it and releasing it.
|
| The only novel thing our algorithm contained was a trie-
| traversal algorithm that found all words approximately within a
| particular edit distance of the source word in one pass. It
| separately found words with similar sound and scored by a
| heuristic of both, but that's fairly standard.
|
| It was also clear that Google was doing something far more
| impressive on their servers, as it came up with spelling
| corrections that others didn't and would even suggest
| corrections that took into account the rest of the search. It's
| a shame that they've never (to my knowledge) released that
| technology for others to use. It's possible, of course, that
| the underlying text model is too large to easily share.
___________________________________________________________________
(page generated 2022-03-06 23:02 UTC)