9 ms·
A Spellchecker Used To Be A Major Feat of Software Engineering
- Radim 15y agoI know it's HN folklore to claim "Trivial! Would do over a weekend!", but please... Doing a half-decent production spell checker is STILL a major feat. Same as "just crawling the web" (further down the discussion). Both require problem understanding and engineering you can't see and appreciate at a glance. And no, looking up individual words in some predefined dictionary doesn't qualify as half-decent spell checking, especially for non-English languages. Spelling correction is another step. "Their coming too sea if its reel."
- rcfox 15y agoMaybe it's not fair to cite the work of super heroes, but Peter Norvig wrote a spelling corrector in 21 lines of Python: http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html
- Radim 15y agoIt is fair, it is a first step in that direction :-) That corrector has no context though, so it will not correct misspelled words that happen to come out as other words (incl. the "Their coming too sea if its reel."). This is especially important on the web, where pretty much every conceivable word is "correct" (a name of a company or otherwise). False positives are costly, and context disambiguation critical. Let the fun begin.
- dextorious 15y agoYou keep using this word "spelling". I don't think it means what you think it means. This is GRAMMAR checking, or at least grammar-assisted spell checking. Very few, if any, shipping mainstream spelling correctors do that.
- Radim 15y agoPeople want their documents (or queries) free of spelling errors. That is their pain and that is the challenge. The example sentence has misspelled words, hence is within the domain of spell checking. This type of misspelled words are called "homonyms", which are one very common spelling problem. The academic terminology is uninteresting to most users, however. Or if you mean to posit that "spell checking really means looking up if a word exists in a static dictionary of English", then yes, that's easy and solved, no argument there.
- tincholio 15y ago> The example sentence has misspelled words, hence is within the domain of spell checking. No, it doesn't . It is grammatically incorrect, but all the words are spelled correctly. You're definitely talking about a grammar checker, not a spelling checker.
- Radim 15y agoI understand this is a mismatch in terminology. In your view, "spelling check" is applied to individual words, to see if they appear in a fixed dictionary (see my other comment about difficulties with choosing this "correct" dictionary in reality, though). I can imagine this view is inviting for programmers, because it's easy to implement, but I doubt anyone else finds useful a definition that says there are no misspellings in "Their coming too sea if its reel." In my view, "spell check" applies to utterances and roughly means "all words are spelled as per the norm of the language; I can send this document to my boss/customer and they won't laugh at my spelling." It is a more user-centric view, and more complex too, because it covers intent and norms, as opposed to the comforting lookup table for a few hand-picked strings. Modern spell checkers make heavy use of statistical analysis of large text corpora, to reasonably approximate context needed to model such intent. Once we agree on the terminology, I believe we are in agreement, so let's not split hairs. The "correctly spelled" sentence under question comes from the Wikipedia article on spell checking, by the way.
- 15y ago
- Radim 15y agoIncidentally, the linked article by Peter Norvig also mentions that adding context is the best way to improve spelling correction. If you think this claim is so controversial, explain yourself, don't just downvote please.
- SquareWheel 15y agoThat'd be a grammar checker, that's a whole 'nother beast. That should spell check just fine.
- plq 15y agospell checking for languages that sport a high rate of agglutination where you can't (feasibly) enumerate every possible form of a stem is still a major feat. languages like turkish, finnish and hungarian are prime examples of this.
- nandemo 15y agoThat's not the point of the article. He's not talking about writing a state-of-the-art spelling-and-grammar checker. > And no, looking up individual words in some predefined dictionary doesn't qualify as half-decent spell checking, Well, but the author is talking about that problem! Even if you don't consider that real spell-checking, his point still stands. Let's define crappy-spell-checking as "looking up individual words in some predefined dictionary"; that problem used to be hard and now it's very easy, as in, you could write one in 15 minutes using Python.
- Radim 15y agoOk, fair point -- I blame the misleading title :) I read the point of the article to compare "spell-checking then (80s) and now", whereas others read it more along the lines of "looking up static English words then and now". Your nickname sounds japanese, but I assume you're talking about English as well, with those 15 minutes.
- dangoldin 15y agoI know Bloom Filters came in handy for this sort of work but I'd love to see some other data structures and algorithms that were developed in the 80s to deal with limited memory.
- btn 15y agoJon Bentley's Progamming Pearls books are full of such insights into designing incredibly efficient data structures and algorithms.
- daantje 15y agoYes, and "Programming Pearls" has a nice chapter (13.8) on how doug mcilroy fit the spell dict into less than 64k ( http://code.google.com/p/unix-spell/ http://code.google.com/p/unix-spell/). That site also has a paper on the development of spell (http://unix-spell.googlecode.com/svn/trunk/McIlroy_spell_1982.pdf http://unix-spell.googlecode.com/svn/trunk/McIlroy_spell_198...).
- _sh 15y agoYou might like 'How to Fit a Large Program Into a Small Machine' (http://www.csd.uwo.ca/Infocom/Articles/small.html http://www.csd.uwo.ca/Infocom/Articles/small.html), where some of the founders of Infocom talk about the approaches they used to fit Zork (which required a massive 1MB of memory) onto microcomputer systems which had 32K and a floppy disk drive. See also the Digital Antiquarian's fascinating (and reasonably technical) blog on the origins of Infocom: http://www.filfre.net/tag/infocom/ http://www.filfre.net/tag/infocom/
- est 15y agovp-tree. Developed in the 90th.
- DanBC 15y agoMorris, Robert & Cherry, Lorinda L, 'Computer detection of typographical errors', IEEE Trans Professional Communication, vol. PC-18, no.1, pp54-64, March 1975. They do away with a dictionary.
- 15y ago
- RodgerTheGreat 15y agoProgress for computing, absolutely. Progress for software engineering? Questionable. Are the clever solutions applied in legacy spellcheckers obsolete simply because sufficient brute force is now available on everyday machines to solve everyday problems?
- boredguy8 15y agoThere are always questions on the edge of computational complexity. In 30 years: "Indexing all of the individual web pages in the world used to be a tough challenge. Network speeds were in the hundreds of megabits, and..."
- hyperbovine 15y agoI would be surprised if that analogy holds up. I have heard the Google guys state that the growth of the web easily outpaces advances in computing and bandwidth. The English language, not so much...
- boredguy8 15y agoYou're missing the point. "Growth of the language" wasn't the problem for spell-check, it was the size of the language combined with limited space. Computational breakthroughs solved that problem. The parent to my post implied that solving the 'space' problem in a different way (i.e. by having more space) somehow harmed software engineering, which it hasn't. Ergo, the suggestion that the web is outpacing computing and bandwidth all the more supports my point, since that problem will be persistent.
- adgar 15y ago> In 30 years: "Indexing all of the individual web pages in the world used to be a tough challenge." Eh, that needs qualification to make sense. Just crawling and trivially tokenizing the web counts as "indexing all the individual web pages" but that's never been such a monstrous task. Having results fresh to-the-day/hour/minute is a better example of something that will probably be looked at is child's play even though that's a very new, very computationally expensive development in search.
- Dn_Ab 15y agoInteresting. But maybe a better title would be: A Spellchecker Used To Require A Major Feat of Software Engineering. Some may say something is lost and resources wasted - taken for granted as we now brute force our way through such problems. Surely going backwards? but now we are, a million times a second; free to disambiguate a word's meaning, check its part of speech, figure out whether its a named entity or an address, figure out if it is a key topic in the document we are looking at and write basic sentences. I agree. That is progress.
- Evgeny 15y agoSome may say something is lost and resources wasted - taken for granted as we now brute force our way through such problems. Surely going backwards? I think it is progress: Yes, we can brute force today through the problems that were a feat a decade or two ago. But: Not having to solve those problems frees a lot of time. Time that can be spent on problems that are a major feat today.
- WalterBright 15y agoNow, if they could only fix OCR technology! I'm getting tired of "the" being scanned as "die".
- simcop2387 15y agoJust run it through google translate, German -> English. That'll fix "die" into "the", but it'll make some other things strange I bet.
- zacharyvoase 15y agoThis relates to Fred Brooks's 'No Silver Bullet': the 'accidental complexity' of coping with hardware constraints has given way to the 'essential complexity' of writing an algorithm to check someone's spelling.
- ADent 15y agoI had a decent spell checker on my Apple //c - 128K RAM (64K commonly usable) and had to fit on 140KB floppy. While slow it worked better than about 10 years of MS Word.
- erikb 15y agoIt seems the author of that article doesn't know that spell checking, translating and understanding text are actually major features of pretty new software, too. I don't know how the spellcheckers are for English, but in German they really suck since years. You can't just let MS Word autocorrect your text, because the spell checker will insert more errors than it can remove. So when I want to find out, how to spell a word correctly in German, I just use the Google search bar. Why? Because they consider spell checking a hard task TODAY! Spell checking is not about comparing a list of words to what the user wrote and tell him what didn't match. It's much more about understanding the users intention and helping him shaping that intention into an officially recognised grammar/spelling. Example: "then" is a correct word. But in the context of "Google's spell check is better then Word's" "then" is actually wrong. (Google also doesn't tell you about that mistake but the first search result actually contains a "than", which is recognised as what you actually meant) I hope I could make it clear, why I think it still is a major feature to have the best spell checker and I think, the title really should be revised.
- cbsmith 15y agoYes. This whole article struck me as the spell checking equivalent to "I can build Map Reduce in 5 lines of language N" meme that went around a while ago.
- dextorious 15y ago"""It seems the author of that article doesn't know that spell checking, translating and understanding text are actually major features of pretty new software, too. """ Actually it seems that everybody reading the article got the same WRONG impression. The author full well knows what it takes to do a i18n full-featured spell checker. That is BESIDE the point. What he says is that doing a basic (lame ass) spell-checker in the 80s used to be a MAJOR undertaking, and now, doing EXACTLY THE SAME is trivial. His point is not about spell-checking. It's about modern OS, language, CPU, HD and memory conveniences, vs what one had to deal with in the olden days.
- chime 15y agoWhile these specific challenges are trivial now because of increased memory and CPU, user expectations have increased too, requiring more advanced features which are not trivial to implement across different platforms. Users now expect good auto-suggestion when doing text entry on mobile platforms and laugh when it fails ( http://damnyouautocorrect.com/ http://damnyouautocorrect.com/ ). I just launched an iPad app to improve communication for speech-disabled users and nearly everyone I talked to wanted word-completion and next-word suggestion, even when offline. While it seems trivial for Google or a database backed server to provide real-time intelligent suggestions (e.g. suggest 5 words that follow: Harry), implementing such a feature on iPad took me over a month even though I knew exactly what I wanted to make and had all the necessary data beforehand. I had a list of 1 million words and phrases with frequency of usage (16mb of text data) and wanted to suggest 3-7 words in real-time as the user typed each letter. And implementing this on iPad required quite a bit of engineering and optimization.
- DanBC 15y agoIt's a shame that solutions like Bob Morris's no dictionary spell checker[1] are left languishing just because we all have fast computers. Getting better at a problem in one domain can spin off benefits in others. Spelling is part of language, and language is something that computers are really bad at. Brute force helps a bit with that (auto-correct; siri;) but better understanding would be cool. [1] (http://www.spellingsociety.org/journals/j20/spellchecking.php http://www.spellingsociety.org/journals/j20/spellchecking.ph...) Morris, Robert & Cherry, Lorinda L, 'Computer detection of typographical errors', IEEE Trans Professional Communication, vol. PC-18, no.1, pp54-64, March 1975.
- yason 15y agoOh, those were the times. What makes working in a finite, very limited set of resources so rewarding is that those limitations turn mere programming into art. You can't have art unless you constrain yourself somehow. Some people paint with dots only and some people express themselves in line art. If they allowed themselves any imaginable method that is applicable, they wouldn't be doing art. They could just take a photograph of a setting, and that photograph wouldn't say a thing to anyone. Endless bit-twiddling and struct packing may turn trivial methods into huge optimization-ridden hacks and not get you too far vertically but given only few resources, those hacks are required to turn the theoretic approach into a real application that you can actually do useful work with. Those hacks often exhibit ingenious thinking and many examples of that approach art—and the best definitely are. And any field where ingenious thinking is required will push the whole field forward. Similarly, for example, using a Python set as a rudimentary spell-checker is fast, easy, and convenient but it's no hack because it requires no hacking. It's like taking that photograph, or using a Ferrari to reverse from your garage out to the street and then driving it back. Which ingenious tricks are you required to accomplish that? None. The bleeding edge has simply moved and it must lie somewhere these days, of course. Maybe computer graphics—although it has always demonstrated the capability to lead the bleeding edge so there's actually no news there. The fact is that the bleeding edge is more scattered. Early on, every computer user could feel and sense the bleeding edge because it revolved around tasks so basic that you could actually measure with your own eyes. Similarly, even a newbie programmer would face the same limitations early on and learn about how others had done it. Now you can stash gigabytes of data into your heap without realizing that you did, and wonder why the computer felt sluggish for a few seconds. Or how would you compare two state of the art photorealistic, interactive real-time 3D graphics demos? There's so much going on beyond the curtains that it's difficult to evaluate the works without having extensive domain knowledge in most the technologies used. Findind the bleeding edge has become a field in itself.
- joemoon 15y agoI understand your general thesis, but your statements about art just seem completely off. > You can't have art unless you constrain yourself somehow. > They could just take a photograph of a setting, and that photograph wouldn't say a thing to anyone. While I realize that art is subjective, I'm very surprised that you would put these conditions around what you consider to be art. Especially since it seems to be a condemnation of a large subset of photography.
- mda 15y agoDesigning a high quality and compact spell checker for agglutinative languages like Turkish or Hungarian is definitely a non trivial and challenging problem.
- bozho 15y agoIt's not that easy today either. Loading a list of words in a hashtable will work for..Chinese (pinyin), but most languages have declensions and conjugation. And you want to validate both "cat" and "cats", both "walk", "walking" and "walked" and the word list normally wouldn't contain those. (haven't checked the English ones, but it certainly doesn't for languages with more complex inflection). Yes, you don't have the memory complications that are really hard, but you still need to think. Get a proper data-structure (Trie, for ex), and fill it with all forms of the words.
- deleted 15y ago[deleted]
- joejohnson 15y agoHow long was it until a grammar checker was able to be implemented with these space constraints?