17 ms·

A spellchecker used to be a major feat of software engineering (2008)

314 points by rrampage 4y ago

deleted 4y ago
[deleted]
bediger4000 4y ago
He's got a point: increase in minimum memory and increase in CPU performance means that superior programming isn't always necessary. People regularly produce for fun what used to be a masters thesis level of work these days. I'll cite that YouTube video of someone making a reaction wheel system that can get an inverted Lego pendulum to stand up, and stay up under perturbations. The Lego part isn't the main work. The main work is software, a PID controller of the reaction wheel. Something else has happened. There's enough people who know enough that the knowledge is just sloshing around, waiting for others to do cool things with it.
- simcop2387 4y ago
  > He's got a point: increase in minimum memory and increase in CPU performance means that superior programming isn't always necessary. Fun part about this is that it might actually make it slower! Between cache misses, pre-fetchers and branch mispredictions the more naive search may make things significantly more predictable for the out of order execution on modern processors that the result is actually faster when you don't try to be clever with some of this. You still have to benchmark and not do things completely wacky but it's kind of interesting how things have changed because of the scale of the pieces.
  - BoorishBears 4y ago
    A good example from Bjarne Stroustrup https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo
taeric 4y ago
The really mind blowing thing about that 2 meg dictionary, is that it can completely fit in cache for many computers nowadays. Just mind blowing that the optimized linear scan search today is competitive with faster methods from yesteryear. (Heck, the unoptimized scan is probably more than competitive.) This does have me curious how big the ZDD for the dictionary would be. https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram#ZDDs_as_dictionaries https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagr...
- diceduckmonk 4y ago
  It will even fit within 5mb of browser local storage.
  - hawski 4y ago
    That is nice, but the browser storage limit is more arbitrary, cache size is limited by hardware.
jrumbut 4y ago
A good one still is. When I got my most recent phone (Galaxy 22, but I jumped several versions in the upgrade so I don't know when the change happened), the spellcheck engine regressed massively from previous editions. I'd be so curious to hear what the change was. It's absolutely awful to use!
- benj111 4y ago
  Is it not based on your history? I know the suggestions seem to be. If so and it's stored locally it could just be that it's having to start again from scratch?
  - progmetaldev 4y ago
    It definitely does make use of your history.
  - jrumbut 4y ago
    It used to be very clearly based on history, so every time I restarted my phone I'd get the classic "duck" correction. Now I couldn't tell you what it's doing, but it doesn't appear to be using history. For instance, the same technical terms get autocorrected again and again.
deleted 4y ago
[deleted]
mdip 4y ago
This reminded me of a Mr Wizard's World episode I watched in the 80s: https://www.youtube.com/watch?v=pdz_8AjIgfA https://www.youtube.com/watch?v=pdz_8AjIgfA In it he demos the UI of a word processor of that era on a green screen monitor. As I had a CGA screen/PC at the time word processing was pretty novel to me ... in white and black, but most of my friends did not own computers and those that did had Commodore 64s[0]. [0] I sat jealous despite sitting before a $3,000 8088 w/FPU, 10MB HDD and 640k of RAM that took 2 minutes before it started booting from the hard drive (I learned to count in powers of two up to 640 that way).
PaulHoule 4y ago
I dunno, there was an article in Creative Computing magazine circa 1984 about how to code one up in BASIC that required a little creativity but made it look pretty easy. If you sort the words in the document it is pretty quick to check them against a dictionary on disk. Turbo Lighting, though, took advantage of the comparably large memory of the IBM PC to do something that really blew people away https://books.google.com/books?id=MC8EAAAAMBAJ&pg=PA7&lpg=PA7&dq=turbo+lightning+borland&source=bl&ots=xO6qUGfCFQ&sig=ACfU3U1i3tpDfjD6NaefKC_HEVwEpNBvhA&hl=en&sa=X&ved=2ahUKEwin8aCn67j9AhWIkIkEHS70ArEQ6AF6BAgyEAM#v=onepage&q=turbo%20lightning%20borland&f=false https://books.google.com/books?id=MC8EAAAAMBAJ&pg=PA7&lpg=PA...
- tbensky 4y ago
  I remember using Turbo Lightning. It was incredible. You type a word in some DOS program, and when you hit the spacebar, a beep would sound if the word was spelled wrong. Back then Peter Norton was all the rage, so if you typed "Norton" TL would beep and suggest spellings like "notion, nothing, etc." to correct Norton. The suggestions felt so AIish and futuristic to me. Wow a "suggestion" for how to spell something? If you selected a replacement, it would stuff the keyboard buffer with backspaces, to erase the word, and retype the correction. Borland made incredible software back then. Great times.
VLM 4y ago
Three other things to think about: 1980s memory models especially dos-era PC was a nightmare but you could at great effort work around it. The C / unix memory model is actually quite luxurious compared to programming on dos 3.3. In the old days non-English support was pretty complicated. Now you rely on the OS to support UTF-8 and call it good, more or less. Was a bigger problem 'back in the day'. In the old days you'd run a spell checker as a batch process, possibly not even part of the editor itself. The point I'm making is WRT speed, now a days speed doesn't matter, not because processors are faster (although they are, software always expands faster than hardware) but because we have integrated app with threading, so instead of saving this into a file, then exiting my browser and running a separate spell check app then exit and start the browser again and load this file back into it, the browser simply has a thread doing spell checking "on the fly". So in the old days it was VERY important WRT labor costs to spell check a 10000 word essay as fast as possible, and on a 8 mhz XT that was a trick indeed. But today my multi core multi ghz desktop merely needs to spell check on the fly as I'm typing and I can't be faster than 100 wpm or so. My desktop had "like one second or so" to decide that ghz and mhz are not words and put red squigglies under them whereas in the old days you'd have to spell check like 1000 words/second to keep the users happy. So simple ineffective code survives in 2023 because it can lean on the OS, its not just that hardware is faster or larger.
irrational 4y ago
Based on so many titles, posts, comments I see everywhere, the major feat now is getting people to use the spellchecker.
Finnucane 4y ago
I spent some years working as a freelance proofreader and copyeditor, and came to regard writers' use of spellcheckers as basically a guarantee of my future employment.
jandrese 4y ago
It still blows my mind that when growing up I had a Commodore 64 word processor with spell check. To run the spell checker you had to hit the button to start the spell checker and then turn the floppy upside down while it ran through the document. This means you had to store in a measly 64kb not only the code for the spell checker, the entire contents of the document, KERNAL overhead, and enough data for the spell checker to run. Remember that the Commodore 64 had an incredibly slow disk drive (300bps) and the disks only supported 160kb of data. Any scheme that required a lot of disk access would be terribly slow. Yet somehow it worked and wasn't outrageously slow. I suspect the program was unloading big chunks of its own program to aggressively reuse the memory space but even then it seems like magic.
- ghaff 4y ago
  It's pretty amazing between now and then. Way back when I wrote a DOS file manager that fit in 32K of assembly language. As I recall, at one point I upgraded it to use two different 64K segments when running by putting the code and in-memory information about the files in different segments.
- zimpenfish 4y ago
  See also ZX Spectrum Scrabble[1] with an 11k word dictionary (and game code) in ~41kb[2], loaded from tape - no swapping / reading / etc. [1] https://spectrumcomputing.co.uk/zxsr.php?id=4375 https://spectrumcomputing.co.uk/zxsr.php?id=4375 [2] 48k - 6.75k for the screen.
- reaperducer 4y ago
  There were several spell checkers for the TRS-80 model 100, which maxed out at 32K of RAM. More typically, it has 24K, because the weird RAM chips were so expensive. Plus, few people had floor drives for the 100 —you had to operate from a cassette tape.
  - jgtrosh 4y ago
    I was going to point out my Panasonic W1030 word processor as probably even more impressive since it's not even really a PC. But then I found specs and its dictionary uses 384kB [1]. Then again it's from the latter 80s, maybe previous word processors attempted more constrained spellcheckers. [1]: https://archive.org/details/kx-w1000-service-manual/KX-W1000%20Service%20Manual_300dpi/page/n31 https://archive.org/details/kx-w1000-service-manual/KX-W1000...
knodi123 4y ago
I read an article where a software engineer was about to go on a long plane flight, so he downloaded a file of all english words and tried to write a spell checker during his flight, with no internet access, just as an exercise. And when he landed, he had finished, and his algorithm was beautiful, simple, elegant, easy to understand, and never something I'd have come up with in a million years. It was actually a little depressing - it made me realize that some people just have a "something" that I'm not going to get through hard work or whatnot. *edit: ah, found it. https://norvig.com/spell-correct.html https://norvig.com/spell-correct.html
- andersource 4y ago
  To be fair, Peter Norvig [0] isn't just another software engineer, he's a hardcore CS researcher, co-authored the most popular (pre-DL) AI textbook, was head of NASA's Computational Sciences Division, etc. [0] https://en.wikipedia.org/wiki/Peter_Norvig https://en.wikipedia.org/wiki/Peter_Norvig
  - e_i_pi_2 4y ago
    I think what they're saying is that some people are Peter Norvig and got lucky, and other people won't get there with any amount of study or practice. He's definitely not an average engineer, and as a result most people shouldn't expect to have the same level of ability I had the same thought - read the URL and then said "Oh well that's Peter Norvig he's just weird in a cool way"
    - some_furry 4y ago
      My aspiration as a programmer and security engineer is to one day be regarded as "just weird in a cool way". Until that day comes, I keep working at it.
      - e_i_pi_2 4y ago
        That's also how I live my life haha, much less stress about people judging you if you can write it off as "yeah but I'm cool in other ways"
pcj-github 4y ago
Actually there's way more to it than loading /usr/share/dict/words into a perl hashtable and calling it done. A good spellchecker from scratch is still a massive engineering effort in 2023.
lxe 4y ago
There are still "hard" problems to solve when it comes to spellchecking. For example predictive text and correct typo detection. Notice what suggestions the Firefox and chrome spellcheckers give you versus what happens when you use google or mobile phone autocorrect. There are still differences in spellchecking speed, quality, and UX.
encoderer 4y ago
This reminds me of an article on the JoS blog where Joel describes how hard/impossible it is to do real-time spell checking on the web with red underlines on the typos. It really is mind blowing for those of us who remember spacer.gif and are still hacking today. The web has really grown up.
twodave 4y ago
Now it’s just a major pain in my butt. At least the ones on phones. Half the time they replace a legitimate word with the one they thought I actually meant. They’re almost always wrong.
wirthjason 4y ago
Perhaps that’s a good thing. There’s so much computing hardware these days that some things are basic “free”. Liberating (but also scary) implication is that we’re limited more by our ideas than the hardware, so go out there and create something cool, there’s little stopping you other than the ideas in your head.
Leherenn 4y ago
It's still pretty bad in some fairly common languages like French. For instance "'" really trips spellchecker, as well as some tense (subjunctive). For instance "que je n'embête".
LAC-Tech 4y ago
Dadgum/Prog21 must be one of my favourite blogs of all time. Hugely influential on me. It's a shame he doesn't post anymore.
Xeoncross 4y ago
If you think this is great and/or immediately thought of using a trie to reduce storage costs, then let me introduce you to https://blog.burntsushi.net/transducers/ https://blog.burntsushi.net/transducers/ which pushes storage reuse over the edge to almost competing with compression like gzip while still allowing you to consider edit distance while finding possible alternatives. typeaheads/autocomplete and spellchecking both need this so worth a read.
- denvaar 4y ago
  Also recommend "Compact Data Structures" by Gonzalo Navarro if you're into compression and data structures.
- ccooffee 4y ago
  Great article, thanks for sharing!
- polytely 4y ago
  Great stuff, I never deal with stuff like this in my day job and was pleasantly surprised at how easy it was to follow what was going on, which means the author did a great job.
  - Xeoncross 4y ago
    Yes, sad that we don't get to work on actual algorithms/leetcode-like problems in the job. Instead it's just hundreds of cocoapods, gems, npm packages, and build tools to make a contact form or profile page.
    - Cthulhu_ 4y ago
      Honestly sometimes it feels like it takes more time to untangle the web of build tooling and libraries than it does to write code. After months of setting up a new app, I've finally written a component in the past week. It's just a list item, icon, text and a chevron, but to get to that point took ages. I just hope it was worth it. Probably not, I fully expect this code to be thrown away again in favor of whichever consultant comes next and/or because a designer says so within five years or so. At least I get paid monthly I guess.
bluGill 4y ago
As a person with dysgraphia I can assure you that it still is a major feet. The algorithms are fast, but they still do a bad job of turning the semi-random sequence of letters I come up with into real words.
- deleted 4y ago
  [deleted]
- rvbissell 4y ago
  > dysgraphia > feet Indeed.
mthoms 4y ago
Mildly funny anecdote: An early version of WordPerfect spell check insisted on turning the company name "Unisys" into "anuses". That was a good laugh.
dang 4y ago
It used to be a popular submission topic too (still is, and used to as well): A spellchecker used to be a major feat of software engineering (2008) - https://news.ycombinator.com/item?id=25296900 https://news.ycombinator.com/item?id=25296900 - Dec 2020 (143 comments) A Spellchecker Used to Be a Major Feat of Software Engineering (2008) - https://news.ycombinator.com/item?id=10789019 https://news.ycombinator.com/item?id=10789019 - Dec 2015 (29 comments) A Spellchecker Used to Be a Major Feat of Software Engineering - https://news.ycombinator.com/item?id=4640658 https://news.ycombinator.com/item?id=4640658 - Oct 2012 (70 comments) A Spellchecker Used To Be A Major Feat of Software Engineering - https://news.ycombinator.com/item?id=3466388 https://news.ycombinator.com/item?id=3466388 - Jan 2012 (61 comments) A Spellchecker Used to Be a Major Feat of Software Engineering - https://news.ycombinator.com/item?id=212221 https://news.ycombinator.com/item?id=212221 - June 2008 (22 comments)
- Willish42 4y ago
  Pretty funny how the oldest one has the same top comment as this submission (https://norvig.com/spell-correct.html https://norvig.com/spell-correct.html), 15 years later
mcguire 4y ago
From Jon Bently, the history of Unix spell checking. [PDF] https://dl.acm.org/doi/pdf/10.1145/3532.315102 https://dl.acm.org/doi/pdf/10.1145/3532.315102
kens 4y ago
It's kind of amazing how many hard computer problems from the olden days were solved by having more memory. When I got started in computer graphics, there was a lot of research work on how to render images a scanline at a time, since that's all the memory you had. Once you could get enough memory to hold the entire image, you could use a Z-buffer and rendering became kind of trivial. Another example is the post on HN yesterday about old videogames and how they used a bunch of different hacks such as sprites and tiles because there wasn't enough memory for the whole screen. https://nicole.express/2023/yes-popeye-the-sailor-man.html https://nicole.express/2023/yes-popeye-the-sailor-man.html
BashiBazouk 4y ago
And still is for most. I'm a horrible speller, but fairly consistent in my mistakes. Usually I use the wrong vowel with a similar sound in the middle of a word. It's amazing how few spell checkers can handle that. The google search bar is the undisputed king in spell checking in my experience. Microsoft word, even from way back, has been good. Thunderbird from about a decade ago was the most infuriatingly bad spellchecker I have ever encountered. I always recognize the correct spelling when I see it. So, in Thunderbird it would commonly refuse to suggest the word I was looking for but would often give me the "un" version of that word. I mean, come on. I can get the first letter right 9,999 times out of 10,000 and that is probably a gross underestimation. And the few I would get wrong are a handful of edge cases...
- eastbound 4y ago
  Now be French like me and have words spelled with an E en English and A in French (I recommend/je recommande), and try telling Google that, despite them forcing themselves to guess that you are French despite having set the browser to English, the Google Settings, the OS, and using a VPN to ensure to get all ads and search results in English, you really, really want to be recommended the English spelling of words so that you don’t do en/an mistakes ever again…
  - rtpg 4y ago
    Duck Duck Go (and perhaps other like Bing) have a nice feature to let you just... choose a country. Especially helpful when language != country.
Daub 4y ago
I am dyslexic and my spelling is completely garbage without spellcheck. Even so, Spellcheck cannot recognize many of my misspellings. I have always wondered if there is a way to recognize the word I am trying to spell by its shape (form) and length.
voberoi 4y ago
Here's a play-by-play of a software engineer at Atari building a spellchecker for VAX mainframes in the 80's: https://atariemailarchive.org/thread/on-building-a-spellchecker-in-the-80-s-21 https://atariemailarchive.org/thread/on-building-a-spellchec... It's a game of problem whack-a-mole in this email thread!
jiggawatts 4y ago
The “current hotness” for spellcheck would be to use a large language model (LLM) like GPT-3 that can use several paragraphs of context to disambiguate between alternatives. However usefully accurate LLMs are still too big to work locally in a laptop or PC, so once again we’re back to having to liberally apply black magic to squeeze the models into something an integrated GPU can run in its “tiny” VRAM that’s actually gigabytes in size. The more things change, the more they stay the same. PS: Spell check is a trivially solved problem for most languages, but not all! Hungarian is notoriously difficult, and there are ongoing projects to improve this: https://en.m.wikipedia.org/wiki/Hunspell https://en.m.wikipedia.org/wiki/Hunspell
- aflag 4y ago
  While it sounds in theory LLMs could work for spell checking, was that ever attempted in practice?
crawdog 4y ago
Word processors in the 70s had this as well. I remember the CPT 8100 having this as a selling point in their literature. There was no inline correction. Run the program, correct your issues then continue! Anyone else remember Shift+F7? Bring out your Wordperfect templates.
thangalin 4y ago
In some ways, I think computational linguistics has missed a mark. We have dictionaries, lexicons, grammar engines, spell checkers, pluralization rules, tries, quotation disambiguation, sentiment analyzers, word segmentation, and more. You'd think we could roll all these into a unified, standard definition format. My KeenWrite editor, for instance, uses: * https://github.com/DaveJarvis/KeenSpell https://github.com/DaveJarvis/KeenSpell (spell check, lexicon) * https://github.com/DaveJarvis/KeenQuotes https://github.com/DaveJarvis/KeenQuotes (curls straight quotes) * https://github.com/DaveJarvis/KeenWrite/blob/main/R/pluralize.R https://github.com/DaveJarvis/KeenWrite/blob/main/R/pluraliz... (pluralization) * https://lucene.apache.org/ https://lucene.apache.org/ (word segmentation) I was looking at integrating LanguageTool[0] for grammar and realized that it has partial functionality for KeenQuotes (lexing and tokenization), duplicates the SymSpell algorithm used by KeenSpell, and because it offers grammar corrections it likely can pluralize words, as well. Unifying those for English alone would be a massive undertaking. At present, KeenWrite parses prose in multiple, redundant passes. While this works, I think it'd be great to start with a basic lexer/tokenizer that can emit tokens at blazing speeds[1], which feeds into higher-level abstractions. [0]: https://github.com/languagetool-org/languagetool https://github.com/languagetool-org/languagetool [1]: https://github.com/DaveJarvis/KeenQuotes/blob/main/src/main/java/com/whitemagicsoftware/keenquotes/lex/Lexer.java https://github.com/DaveJarvis/KeenQuotes/blob/main/src/main/...
earlyam 4y ago
Random story. I was a young kid in the 90's and my dad took me by the biggest house I'd seen at that point in my life for some work party or something. Really nice landscaping, etc. It was clear the owner had A Lot Of Money. I asked him afterwards how the guy got so rich and he told me that he wrote Microsoft's spellchecker.
lb1lf 4y ago
No one posted Martha Snow's epic poem yet? 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.
- deleted 4y ago
  [deleted]
- pornel 4y ago
  For the record, ChatGPT can actually correct spelling of this (or it has seen spoilers somewhere…)
  - nathan_f77 4y ago
    This is very impressive. I ran it through ChatGPT and got the following response. The only mistake it made is "really" instead of "rarely". ------ > Correct the spelling: 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. > I have corrected the spelling errors in the poem: "I have a spelling checker It came with my PC It plainly marks for my review Mistakes I cannot see. I strike a key and type a word And wait for it to say Whether I am wrong or right It shows me straight away. As soon as a mistake is made It knows before too long And I can put the error right It's really ever wrong. I have run this poem through it I am sure you're pleased to know It's letter perfect all the way My checker told me so."
    - yccs27 4y ago
      There's dozens of websites with the corrected poem out there, hard to know if ChatGPT just 'remembered' it.
smithmayowa 4y ago
Spellcheckers still blow my mind and Gmail's autocomplete(still the best out there imo), I still marvel when they work even though I know how they work and have used them for a while.
vbezhenar 4y ago
Yet in 2022 spell checking is still not good, at least when it comes to ordinary software. It checks with dictionaries, it seems that recently Google Chrome became a little bit better at it, but still I can completely write gibberish random with order words of and it wud no car as long as separate words are present in the dictionary. And that's while there's AI which generates awesome texts around. I don't know English well, but one single thing that immensely helps me memorizing English is instant feedback when I'm writing texts with errors. I bet that good spell checker in Chrome would do much more to the world than many English courses (also helps with any other language, of course, but English is special as it's world's lingua franca nowadays).
- jltsiren 4y ago
  It feels like spell checking was better in the 2000s than it is today. It probably wasn't, but it didn't feel so annoying because it was not that prevalent. With the spellcheckers Google and Apple are using, it's rare that I can write a full paragraph of Finnish without them flagging something incorrectly. Whatever methods they are using, they seem to be incapable of handling cases, conjugation, and compound words. Which is ironic, since early Finnish spellcheckers were surprisingly good. There was a lot of research on those topics in Finland in the 80s and 90s, and early spellcheckers took advantage of that.
- kevincox 4y ago
  I think Chrome uses a Google service by default. FWIW I have found Google Search's spell checker fantastic. (At least for English) It seems to have a better concept of sound similarity or something that means it almost always guesses the word I mean (extra impressive because on Google Search it only shows you one suggestion). I frequently find myself in a situation where Firefox's (local) checker can't figure out what word I meant so I put it into Google Search and it nearly always knows what I meant.
armchairhacker 4y ago
...but a really good grammar checker is still, to this day, a major feat. Even Grammarly can't write sentences for you as good as a native speaker. ChatGPT and language models can, but ironically, they still require way more memory than fits on a desktop. Simple cases like conjugation can certainly be handled but there is a lot of nuance to make a sentence "flow".
- deleted 4y ago
  [deleted]
aaron695 4y ago
[dead]
hnfong 4y ago
You can still try your skillz here: https://open.kattis.com/problems/dictionary https://open.kattis.com/problems/dictionary It's probably easy mode compared with the original constraints in the article, but the problem is still somewhat challenging. It took me a sleepless night to get it right.
deleted 4y ago
[deleted]
tabtab 4y ago
I remember that the early CPM edition of WordStar didn't have an interactive spell-checker, but you could run it in batch mode and get a report. One way to implement that is to store say a paragraph or more of your document at a time in RAM, then do a sequential read of the dictionary file on disk, compare to the stored paragraph words, and save any non-finds to the misspell report. Saving the position could allow one to bring the editor back up and have the misspelled words highlighted, which is what WordStar did as I remember it.
deleted 4y ago
[deleted]
afitnerd 4y ago
In 1988, I had a friend in my computer science program who got some local notoriety when he made a spell checker for DOS. It was a terminate and stay resident program and it used a tiny bit of the available 640K of RAM. We were all pretty amazed by it. He got some seed money to start a business and then was crushed like a year later when it was just built into wordstar.

314 points by rrampage 4y ago

deleted 4y ago

[deleted]

He's got a point: increase in minimum memory and increase in CPU performance means that superior programming isn't always necessary. People regularly produce for fun what used to be a masters thesis level of work these days. I'll cite that YouTube video of someone making a reaction wheel system that can get an inverted Lego pendulum to stand up, and stay up under perturbations. The Lego part isn't the main work. The main work is software, a PID controller of the reaction wheel. Something else has happened. There's enough people who know enough that the knowledge is just sloshing around, waiting for others to do cool things with it.

simcop2387 4y ago
> He's got a point: increase in minimum memory and increase in CPU performance means that superior programming isn't always necessary. Fun part about this is that it might actually make it slower! Between cache misses, pre-fetchers and branch mispredictions the more naive search may make things significantly more predictable for the out of order execution on modern processors that the result is actually faster when you don't try to be clever with some of this. You still have to benchmark and not do things completely wacky but it's kind of interesting how things have changed because of the scale of the pieces.
- BoorishBears 4y ago
  A good example from Bjarne Stroustrup https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo

taeric 4y ago

The really mind blowing thing about that 2 meg dictionary, is that it can completely fit in cache for many computers nowadays. Just mind blowing that the optimized linear scan search today is competitive with faster methods from yesteryear. (Heck, the unoptimized scan is probably more than competitive.) This does have me curious how big the ZDD for the dictionary would be. https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram#ZDDs_as_dictionaries https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagr...

diceduckmonk 4y ago
It will even fit within 5mb of browser local storage.
- hawski 4y ago
  That is nice, but the browser storage limit is more arbitrary, cache size is limited by hardware.

jrumbut 4y ago

A good one still is. When I got my most recent phone (Galaxy 22, but I jumped several versions in the upgrade so I don't know when the change happened), the spellcheck engine regressed massively from previous editions. I'd be so curious to hear what the change was. It's absolutely awful to use!

benj111 4y ago
Is it not based on your history? I know the suggestions seem to be. If so and it's stored locally it could just be that it's having to start again from scratch?
- progmetaldev 4y ago
  It definitely does make use of your history.
- jrumbut 4y ago
  It used to be very clearly based on history, so every time I restarted my phone I'd get the classic "duck" correction. Now I couldn't tell you what it's doing, but it doesn't appear to be using history. For instance, the same technical terms get autocorrected again and again.

deleted 4y ago

[deleted]

mdip 4y ago

This reminded me of a Mr Wizard's World episode I watched in the 80s: https://www.youtube.com/watch?v=pdz_8AjIgfA https://www.youtube.com/watch?v=pdz_8AjIgfA In it he demos the UI of a word processor of that era on a green screen monitor. As I had a CGA screen/PC at the time word processing was pretty novel to me ... in white and black, but most of my friends did not own computers and those that did had Commodore 64s[0]. [0] I sat jealous despite sitting before a $3,000 8088 w/FPU, 10MB HDD and 640k of RAM that took 2 minutes before it started booting from the hard drive (I learned to count in powers of two up to 640 that way).

PaulHoule 4y ago

I dunno, there was an article in Creative Computing magazine circa 1984 about how to code one up in BASIC that required a little creativity but made it look pretty easy. If you sort the words in the document it is pretty quick to check them against a dictionary on disk. Turbo Lighting, though, took advantage of the comparably large memory of the IBM PC to do something that really blew people away https://books.google.com/books?id=MC8EAAAAMBAJ&pg=PA7&lpg=PA7&dq=turbo+lightning+borland&source=bl&ots=xO6qUGfCFQ&sig=ACfU3U1i3tpDfjD6NaefKC_HEVwEpNBvhA&hl=en&sa=X&ved=2ahUKEwin8aCn67j9AhWIkIkEHS70ArEQ6AF6BAgyEAM#v=onepage&q=turbo%20lightning%20borland&f=false https://books.google.com/books?id=MC8EAAAAMBAJ&pg=PA7&lpg=PA...

tbensky 4y ago
I remember using Turbo Lightning. It was incredible. You type a word in some DOS program, and when you hit the spacebar, a beep would sound if the word was spelled wrong. Back then Peter Norton was all the rage, so if you typed "Norton" TL would beep and suggest spellings like "notion, nothing, etc." to correct Norton. The suggestions felt so AIish and futuristic to me. Wow a "suggestion" for how to spell something? If you selected a replacement, it would stuff the keyboard buffer with backspaces, to erase the word, and retype the correction. Borland made incredible software back then. Great times.

VLM 4y ago

Three other things to think about: 1980s memory models especially dos-era PC was a nightmare but you could at great effort work around it. The C / unix memory model is actually quite luxurious compared to programming on dos 3.3. In the old days non-English support was pretty complicated. Now you rely on the OS to support UTF-8 and call it good, more or less. Was a bigger problem 'back in the day'. In the old days you'd run a spell checker as a batch process, possibly not even part of the editor itself. The point I'm making is WRT speed, now a days speed doesn't matter, not because processors are faster (although they are, software always expands faster than hardware) but because we have integrated app with threading, so instead of saving this into a file, then exiting my browser and running a separate spell check app then exit and start the browser again and load this file back into it, the browser simply has a thread doing spell checking "on the fly". So in the old days it was VERY important WRT labor costs to spell check a 10000 word essay as fast as possible, and on a 8 mhz XT that was a trick indeed. But today my multi core multi ghz desktop merely needs to spell check on the fly as I'm typing and I can't be faster than 100 wpm or so. My desktop had "like one second or so" to decide that ghz and mhz are not words and put red squigglies under them whereas in the old days you'd have to spell check like 1000 words/second to keep the users happy. So simple ineffective code survives in 2023 because it can lean on the OS, its not just that hardware is faster or larger.

irrational 4y ago

Based on so many titles, posts, comments I see everywhere, the major feat now is getting people to use the spellchecker.

Finnucane 4y ago

I spent some years working as a freelance proofreader and copyeditor, and came to regard writers' use of spellcheckers as basically a guarantee of my future employment.

jandrese 4y ago

It still blows my mind that when growing up I had a Commodore 64 word processor with spell check. To run the spell checker you had to hit the button to start the spell checker and then turn the floppy upside down while it ran through the document. This means you had to store in a measly 64kb not only the code for the spell checker, the entire contents of the document, KERNAL overhead, and enough data for the spell checker to run. Remember that the Commodore 64 had an incredibly slow disk drive (300bps) and the disks only supported 160kb of data. Any scheme that required a lot of disk access would be terribly slow. Yet somehow it worked and wasn't outrageously slow. I suspect the program was unloading big chunks of its own program to aggressively reuse the memory space but even then it seems like magic.

ghaff 4y ago
It's pretty amazing between now and then. Way back when I wrote a DOS file manager that fit in 32K of assembly language. As I recall, at one point I upgraded it to use two different 64K segments when running by putting the code and in-memory information about the files in different segments.
zimpenfish 4y ago
See also ZX Spectrum Scrabble[1] with an 11k word dictionary (and game code) in ~41kb[2], loaded from tape - no swapping / reading / etc. [1] https://spectrumcomputing.co.uk/zxsr.php?id=4375 https://spectrumcomputing.co.uk/zxsr.php?id=4375 [2] 48k - 6.75k for the screen.
reaperducer 4y ago
There were several spell checkers for the TRS-80 model 100, which maxed out at 32K of RAM. More typically, it has 24K, because the weird RAM chips were so expensive. Plus, few people had floor drives for the 100 —you had to operate from a cassette tape.
- jgtrosh 4y ago
  I was going to point out my Panasonic W1030 word processor as probably even more impressive since it's not even really a PC. But then I found specs and its dictionary uses 384kB [1]. Then again it's from the latter 80s, maybe previous word processors attempted more constrained spellcheckers. [1]: https://archive.org/details/kx-w1000-service-manual/KX-W1000%20Service%20Manual_300dpi/page/n31 https://archive.org/details/kx-w1000-service-manual/KX-W1000...

knodi123 4y ago

I read an article where a software engineer was about to go on a long plane flight, so he downloaded a file of all english words and tried to write a spell checker during his flight, with no internet access, just as an exercise. And when he landed, he had finished, and his algorithm was beautiful, simple, elegant, easy to understand, and never something I'd have come up with in a million years. It was actually a little depressing - it made me realize that some people just have a "something" that I'm not going to get through hard work or whatnot. *edit: ah, found it. https://norvig.com/spell-correct.html https://norvig.com/spell-correct.html

andersource 4y ago
To be fair, Peter Norvig [0] isn't just another software engineer, he's a hardcore CS researcher, co-authored the most popular (pre-DL) AI textbook, was head of NASA's Computational Sciences Division, etc. [0] https://en.wikipedia.org/wiki/Peter_Norvig https://en.wikipedia.org/wiki/Peter_Norvig
- e_i_pi_2 4y ago
  I think what they're saying is that some people are Peter Norvig and got lucky, and other people won't get there with any amount of study or practice. He's definitely not an average engineer, and as a result most people shouldn't expect to have the same level of ability I had the same thought - read the URL and then said "Oh well that's Peter Norvig he's just weird in a cool way"
  - some_furry 4y ago
    My aspiration as a programmer and security engineer is to one day be regarded as "just weird in a cool way". Until that day comes, I keep working at it.
    - e_i_pi_2 4y ago
      That's also how I live my life haha, much less stress about people judging you if you can write it off as "yeah but I'm cool in other ways"

pcj-github 4y ago

Actually there's way more to it than loading /usr/share/dict/words into a perl hashtable and calling it done. A good spellchecker from scratch is still a massive engineering effort in 2023.

lxe 4y ago

There are still "hard" problems to solve when it comes to spellchecking. For example predictive text and correct typo detection. Notice what suggestions the Firefox and chrome spellcheckers give you versus what happens when you use google or mobile phone autocorrect. There are still differences in spellchecking speed, quality, and UX.

encoderer 4y ago

This reminds me of an article on the JoS blog where Joel describes how hard/impossible it is to do real-time spell checking on the web with red underlines on the typos. It really is mind blowing for those of us who remember spacer.gif and are still hacking today. The web has really grown up.

twodave 4y ago

Now it’s just a major pain in my butt. At least the ones on phones. Half the time they replace a legitimate word with the one they thought I actually meant. They’re almost always wrong.

wirthjason 4y ago

Perhaps that’s a good thing. There’s so much computing hardware these days that some things are basic “free”. Liberating (but also scary) implication is that we’re limited more by our ideas than the hardware, so go out there and create something cool, there’s little stopping you other than the ideas in your head.

Leherenn 4y ago

It's still pretty bad in some fairly common languages like French. For instance "'" really trips spellchecker, as well as some tense (subjunctive). For instance "que je n'embête".

LAC-Tech 4y ago

Dadgum/Prog21 must be one of my favourite blogs of all time. Hugely influential on me. It's a shame he doesn't post anymore.

Xeoncross 4y ago

If you think this is great and/or immediately thought of using a trie to reduce storage costs, then let me introduce you to https://blog.burntsushi.net/transducers/ https://blog.burntsushi.net/transducers/ which pushes storage reuse over the edge to almost competing with compression like gzip while still allowing you to consider edit distance while finding possible alternatives. typeaheads/autocomplete and spellchecking both need this so worth a read.

denvaar 4y ago
Also recommend "Compact Data Structures" by Gonzalo Navarro if you're into compression and data structures.
ccooffee 4y ago
Great article, thanks for sharing!
polytely 4y ago
Great stuff, I never deal with stuff like this in my day job and was pleasantly surprised at how easy it was to follow what was going on, which means the author did a great job.
- Xeoncross 4y ago
  Yes, sad that we don't get to work on actual algorithms/leetcode-like problems in the job. Instead it's just hundreds of cocoapods, gems, npm packages, and build tools to make a contact form or profile page.
  - Cthulhu_ 4y ago
    Honestly sometimes it feels like it takes more time to untangle the web of build tooling and libraries than it does to write code. After months of setting up a new app, I've finally written a component in the past week. It's just a list item, icon, text and a chevron, but to get to that point took ages. I just hope it was worth it. Probably not, I fully expect this code to be thrown away again in favor of whichever consultant comes next and/or because a designer says so within five years or so. At least I get paid monthly I guess.

bluGill 4y ago

As a person with dysgraphia I can assure you that it still is a major feet. The algorithms are fast, but they still do a bad job of turning the semi-random sequence of letters I come up with into real words.

deleted 4y ago
[deleted]
rvbissell 4y ago
> dysgraphia > feet Indeed.

mthoms 4y ago

Mildly funny anecdote: An early version of WordPerfect spell check insisted on turning the company name "Unisys" into "anuses". That was a good laugh.

dang 4y ago

It used to be a popular submission topic too (still is, and used to as well): A spellchecker used to be a major feat of software engineering (2008) - https://news.ycombinator.com/item?id=25296900 https://news.ycombinator.com/item?id=25296900 - Dec 2020 (143 comments) A Spellchecker Used to Be a Major Feat of Software Engineering (2008) - https://news.ycombinator.com/item?id=10789019 https://news.ycombinator.com/item?id=10789019 - Dec 2015 (29 comments) A Spellchecker Used to Be a Major Feat of Software Engineering - https://news.ycombinator.com/item?id=4640658 https://news.ycombinator.com/item?id=4640658 - Oct 2012 (70 comments) A Spellchecker Used To Be A Major Feat of Software Engineering - https://news.ycombinator.com/item?id=3466388 https://news.ycombinator.com/item?id=3466388 - Jan 2012 (61 comments) A Spellchecker Used to Be a Major Feat of Software Engineering - https://news.ycombinator.com/item?id=212221 https://news.ycombinator.com/item?id=212221 - June 2008 (22 comments)

Willish42 4y ago
Pretty funny how the oldest one has the same top comment as this submission (https://norvig.com/spell-correct.html https://norvig.com/spell-correct.html), 15 years later

mcguire 4y ago

From Jon Bently, the history of Unix spell checking. [PDF] https://dl.acm.org/doi/pdf/10.1145/3532.315102 https://dl.acm.org/doi/pdf/10.1145/3532.315102

kens 4y ago

It's kind of amazing how many hard computer problems from the olden days were solved by having more memory. When I got started in computer graphics, there was a lot of research work on how to render images a scanline at a time, since that's all the memory you had. Once you could get enough memory to hold the entire image, you could use a Z-buffer and rendering became kind of trivial. Another example is the post on HN yesterday about old videogames and how they used a bunch of different hacks such as sprites and tiles because there wasn't enough memory for the whole screen. https://nicole.express/2023/yes-popeye-the-sailor-man.html https://nicole.express/2023/yes-popeye-the-sailor-man.html

BashiBazouk 4y ago

And still is for most. I'm a horrible speller, but fairly consistent in my mistakes. Usually I use the wrong vowel with a similar sound in the middle of a word. It's amazing how few spell checkers can handle that. The google search bar is the undisputed king in spell checking in my experience. Microsoft word, even from way back, has been good. Thunderbird from about a decade ago was the most infuriatingly bad spellchecker I have ever encountered. I always recognize the correct spelling when I see it. So, in Thunderbird it would commonly refuse to suggest the word I was looking for but would often give me the "un" version of that word. I mean, come on. I can get the first letter right 9,999 times out of 10,000 and that is probably a gross underestimation. And the few I would get wrong are a handful of edge cases...

eastbound 4y ago
Now be French like me and have words spelled with an E en English and A in French (I recommend/je recommande), and try telling Google that, despite them forcing themselves to guess that you are French despite having set the browser to English, the Google Settings, the OS, and using a VPN to ensure to get all ads and search results in English, you really, really want to be recommended the English spelling of words so that you don’t do en/an mistakes ever again…
- rtpg 4y ago
  Duck Duck Go (and perhaps other like Bing) have a nice feature to let you just... choose a country. Especially helpful when language != country.

Daub 4y ago

I am dyslexic and my spelling is completely garbage without spellcheck. Even so, Spellcheck cannot recognize many of my misspellings. I have always wondered if there is a way to recognize the word I am trying to spell by its shape (form) and length.

voberoi 4y ago

Here's a play-by-play of a software engineer at Atari building a spellchecker for VAX mainframes in the 80's: https://atariemailarchive.org/thread/on-building-a-spellchecker-in-the-80-s-21 https://atariemailarchive.org/thread/on-building-a-spellchec... It's a game of problem whack-a-mole in this email thread!

jiggawatts 4y ago

The “current hotness” for spellcheck would be to use a large language model (LLM) like GPT-3 that can use several paragraphs of context to disambiguate between alternatives. However usefully accurate LLMs are still too big to work locally in a laptop or PC, so once again we’re back to having to liberally apply black magic to squeeze the models into something an integrated GPU can run in its “tiny” VRAM that’s actually gigabytes in size. The more things change, the more they stay the same. PS: Spell check is a trivially solved problem for most languages, but not all! Hungarian is notoriously difficult, and there are ongoing projects to improve this: https://en.m.wikipedia.org/wiki/Hunspell https://en.m.wikipedia.org/wiki/Hunspell

aflag 4y ago
While it sounds in theory LLMs could work for spell checking, was that ever attempted in practice?

crawdog 4y ago

Word processors in the 70s had this as well. I remember the CPT 8100 having this as a selling point in their literature. There was no inline correction. Run the program, correct your issues then continue! Anyone else remember Shift+F7? Bring out your Wordperfect templates.

thangalin 4y ago

In some ways, I think computational linguistics has missed a mark. We have dictionaries, lexicons, grammar engines, spell checkers, pluralization rules, tries, quotation disambiguation, sentiment analyzers, word segmentation, and more. You'd think we could roll all these into a unified, standard definition format. My KeenWrite editor, for instance, uses: * https://github.com/DaveJarvis/KeenSpell https://github.com/DaveJarvis/KeenSpell (spell check, lexicon) * https://github.com/DaveJarvis/KeenQuotes https://github.com/DaveJarvis/KeenQuotes (curls straight quotes) * https://github.com/DaveJarvis/KeenWrite/blob/main/R/pluralize.R https://github.com/DaveJarvis/KeenWrite/blob/main/R/pluraliz... (pluralization) * https://lucene.apache.org/ https://lucene.apache.org/ (word segmentation) I was looking at integrating LanguageTool[0] for grammar and realized that it has partial functionality for KeenQuotes (lexing and tokenization), duplicates the SymSpell algorithm used by KeenSpell, and because it offers grammar corrections it likely can pluralize words, as well. Unifying those for English alone would be a massive undertaking. At present, KeenWrite parses prose in multiple, redundant passes. While this works, I think it'd be great to start with a basic lexer/tokenizer that can emit tokens at blazing speeds[1], which feeds into higher-level abstractions. [0]: https://github.com/languagetool-org/languagetool https://github.com/languagetool-org/languagetool [1]: https://github.com/DaveJarvis/KeenQuotes/blob/main/src/main/java/com/whitemagicsoftware/keenquotes/lex/Lexer.java https://github.com/DaveJarvis/KeenQuotes/blob/main/src/main/...

earlyam 4y ago

Random story. I was a young kid in the 90's and my dad took me by the biggest house I'd seen at that point in my life for some work party or something. Really nice landscaping, etc. It was clear the owner had A Lot Of Money. I asked him afterwards how the guy got so rich and he told me that he wrote Microsoft's spellchecker.

lb1lf 4y ago

No one posted Martha Snow's epic poem yet? 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.

deleted 4y ago
[deleted]
pornel 4y ago
For the record, ChatGPT can actually correct spelling of this (or it has seen spoilers somewhere…)
- nathan_f77 4y ago
  This is very impressive. I ran it through ChatGPT and got the following response. The only mistake it made is "really" instead of "rarely". ------ > Correct the spelling: 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. > I have corrected the spelling errors in the poem: "I have a spelling checker It came with my PC It plainly marks for my review Mistakes I cannot see. I strike a key and type a word And wait for it to say Whether I am wrong or right It shows me straight away. As soon as a mistake is made It knows before too long And I can put the error right It's really ever wrong. I have run this poem through it I am sure you're pleased to know It's letter perfect all the way My checker told me so."
  - yccs27 4y ago
    There's dozens of websites with the corrected poem out there, hard to know if ChatGPT just 'remembered' it.

smithmayowa 4y ago

Spellcheckers still blow my mind and Gmail's autocomplete(still the best out there imo), I still marvel when they work even though I know how they work and have used them for a while.

vbezhenar 4y ago

Yet in 2022 spell checking is still not good, at least when it comes to ordinary software. It checks with dictionaries, it seems that recently Google Chrome became a little bit better at it, but still I can completely write gibberish random with order words of and it wud no car as long as separate words are present in the dictionary. And that's while there's AI which generates awesome texts around. I don't know English well, but one single thing that immensely helps me memorizing English is instant feedback when I'm writing texts with errors. I bet that good spell checker in Chrome would do much more to the world than many English courses (also helps with any other language, of course, but English is special as it's world's lingua franca nowadays).

jltsiren 4y ago
It feels like spell checking was better in the 2000s than it is today. It probably wasn't, but it didn't feel so annoying because it was not that prevalent. With the spellcheckers Google and Apple are using, it's rare that I can write a full paragraph of Finnish without them flagging something incorrectly. Whatever methods they are using, they seem to be incapable of handling cases, conjugation, and compound words. Which is ironic, since early Finnish spellcheckers were surprisingly good. There was a lot of research on those topics in Finland in the 80s and 90s, and early spellcheckers took advantage of that.
kevincox 4y ago
I think Chrome uses a Google service by default. FWIW I have found Google Search's spell checker fantastic. (At least for English) It seems to have a better concept of sound similarity or something that means it almost always guesses the word I mean (extra impressive because on Google Search it only shows you one suggestion). I frequently find myself in a situation where Firefox's (local) checker can't figure out what word I meant so I put it into Google Search and it nearly always knows what I meant.

armchairhacker 4y ago

...but a really good grammar checker is still, to this day, a major feat. Even Grammarly can't write sentences for you as good as a native speaker. ChatGPT and language models can, but ironically, they still require way more memory than fits on a desktop. Simple cases like conjugation can certainly be handled but there is a lot of nuance to make a sentence "flow".

deleted 4y ago
[deleted]

aaron695 4y ago

[dead]

hnfong 4y ago

You can still try your skillz here: https://open.kattis.com/problems/dictionary https://open.kattis.com/problems/dictionary It's probably easy mode compared with the original constraints in the article, but the problem is still somewhat challenging. It took me a sleepless night to get it right.

deleted 4y ago

[deleted]

tabtab 4y ago

I remember that the early CPM edition of WordStar didn't have an interactive spell-checker, but you could run it in batch mode and get a report. One way to implement that is to store say a paragraph or more of your document at a time in RAM, then do a sequential read of the dictionary file on disk, compare to the stored paragraph words, and save any non-finds to the misspell report. Saving the position could allow one to bring the editor back up and have the misspelled words highlighted, which is what WordStar did as I remember it.

deleted 4y ago

[deleted]

afitnerd 4y ago

In 1988, I had a friend in my computer science program who got some local notoriety when he made a spell checker for DOS. It was a terminate and stay resident program and it used a tiny bit of the available 640K of RAM. We were all pretty amazed by it. He got some seed money to start a business and then was crushed like a year later when it was just built into wordstar.