10 ms·
A spellchecker used to be a major feat of software engineering (2008)
- gnabgib 1y ago(2008) Popular in: 2023 (314 points, 180 comments) https://news.ycombinator.com/item?id=34971924 https://news.ycombinator.com/item?id=34971924 2020 (363 points, 143 comments) https://news.ycombinator.com/item?id=25296900 https://news.ycombinator.com/item?id=25296900 2012 (94+156 points, 70+61 comments) https://news.ycombinator.com/item?id=4640658 https://news.ycombinator.com/item?id=4640658 https://news.ycombinator.com/item?id=3466388 https://news.ycombinator.com/item?id=3466388
- dang 1y agoThanks! Macroexpanded: A spellchecker used to be a major feat of software engineering (2008) - https://news.ycombinator.com/item?id=34971924 https://news.ycombinator.com/item?id=34971924 - Feb 2023 (180 comments) 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)
- regnull 1y ago[flagged]
- svelle 1y agoAfter having used the IntelliJ/PyCharm spellchecker for German quite extensively I can only attest to this. It's so much more than just checking is a word is spelled correctly. On the other hand, I did use Grammarly for a while and ultimately became annoyed at its tendency to keep "re-adjusting" sentences after it had already fixed them, so there is a fine line to walk.
- unstatusthequo 1y agoFast forward to now, and autocorrect in draft Teams messages appears to be the unbreakable barrier.
- AlphaAndOmega0 1y agoI'd have liked more explanation of the actual solutions that programmers used at the time.
- Someone 1y agoFor the basic word list, possibly tries (https://en.wikipedia.org/wiki/Trie https://en.wikipedia.org/wiki/Trie), DAGs (https://en.wikipedia.org/wiki/Directed_acyclic_graph#Data_compression https://en.wikipedia.org/wiki/Directed_acyclic_graph#Data_co...), or Bloom filter (https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter)
- tetraodonpuffer 1y agoaccording to https://en.wikipedia.org/wiki/Ispell https://en.wikipedia.org/wiki/Ispell ispell (1971) already used Levenshtein Distance (although from the article it is not stated if this already existed in the original version, or if it was added in later years).
- Someone 1y agoLevenshtein distance up to 1, according to that article. If you have a hierarchical structure (trie or a DAG; in some sense, a DAG is a trie, but stored more efficiently, with the disadvantage that adding or removing words is hard) with valid words, it is not hard to check what words satisfy that. If you only do the inexact search after looking for the exact word and finding it missing I think it also won’t be too slow when given ‘normal’ text to spell-check.
- bazzargh 1y agoThe limit given in the article is 360KB (on floppy). At that size, you can't use Tries, you need lossy compression. A Bloom filter can get you 1 in 359 false positives with the size of word list given https://hur.st/bloomfilter/?n=234936&p=&m=360KB&k= https://hur.st/bloomfilter/?n=234936&p=&m=360KB&k= The error rate goes up to 1 in 66 for 256KB (in memory only);
- 1y ago
- knicholes 1y agoI loved what Peter Norvig did with this. It's not just a spell checker, but a spelling corrector. https://norvig.com/spell-correct.html https://norvig.com/spell-correct.html
- soperj 1y ago"why should they know about something so far __outisde__ their specialty?" Should have used it on his spell-correct article.
- thimabi 1y agoGiven that spellcheckers are mostly stable tech, I wonder why Google’s spellchecker in Gmail, or even in Chrome in “enhanced” mode, is so bad. Even Microsoft Word, being a local app and everything, manages to work better than Google’s cloud-based offerings. That’s surely evidence that progress is far from being linear.
- devmor 1y agoThere have been some very specific issues I and others have noticed that lead me to believe the backend for Google’s cloud based spellchecker has changed from a traditional language model to some more generalized LLM-based system. It’s gotten distinctly more terrible a couple of times in the last few years.
- chilipepperhott 1y agoChecking if a word is spelled correctly is easy. It is providing high-quality suggestions that is hard.
- DJBunnies 1y agoHaving written a spellcheck, maybe 20 years ago for school, this is accurate.
- Finnucane 1y agoAs a copyeditor/proofreader, the number of times over the years I've had to fix the low-quality (i.e, wrong) suggestions is quite large. ("he had a small plague on his desk" remains a favorite.)
- KineticLensman 1y agoOne of my favourites was 'rouge elephant'.
- cratermoon 1y agoI have a spelling checker It came with my PC It highlights for my review Mistakes I cannot sea. I ran this poem thru it I'm sure your pleased to no Its letter perfect in it's weigh My checker told me sew. https://www.thoughtco.com/spell-checker-poem-by-mark-eckman-1692348 https://www.thoughtco.com/spell-checker-poem-by-mark-eckman-...
- aidenn0 1y ago"He looked in the [car's] grove department" is still my favorite.
- bluGill 1y agoEven that is hard since there are many words where a mispelling is a valid different word.
- catwhatcat 1y agoA recent article from PCGamer adding some more details: https://www.pcgamer.com/software/implementing-a-spellchecker-on-64-kb-of-ram-back-in-the-1970s-led-to-a-compression-algorithm-thats-technically-unbeaten-and-part-of-it-is-still-in-use-today/ https://www.pcgamer.com/software/implementing-a-spellchecker...
- jimt1234 1y agoCan confirm. The first time I saw an automatic spellchecker was probably with WordStar around 1989, and it blew me away. How can the computer know all the words? That's insane! Sounds lame, but it's true. It was a different world.
- torium 1y agoSince you're old enough, here's a question for you. Do you remember if at the time the first spellcheckers were invented, people were negative on spellcheckers, because that would mean that soon people would stop learning how to spell and just general dumbing down? It seems that anything that helps people gets this reaction these days. On the one hand, the argument 100% resonates with me. On the other hand, spelling isn't really the end, is it? It's just a means to an end, so what's wrong with making the mean easier? Did people worry that you'd stop knowing how to plant potatoes when trading was invented? EDIT: The example doesn't make sense because agriculture is newer than trading, but you got the idea.
- _fqqr 1y ago“The careless, the inept, the spelling disabled will be able to survive in a world of words by relying on computers to conceal their own weaknesses.” https://www.washingtonpost.com/archive/opinions/1985/06/02/the-invasion-of-the-spelling-people/6283df4f-3d2b-4584-a5ed-3c34adc1baca/ https://www.washingtonpost.com/archive/opinions/1985/06/02/t...
- runako 1y agoNot as much with spellcheckers because even when they started to get popular, it was apparent that many people cannot spell English. So it was very natural. People pushed back on the grammar checks when they landed in Word. Before that, people pushed back on calculators in secondary schools. This was a huge point of contention all classes except trigonometry, and calculators were definitely not allowed in the SAT/ACT.
- kergonath 1y ago> People pushed back on the grammar checks when they landed in Word. Word’s grammar checker has improved quite a lot. But I absolutely hate the style checker and its useless advice. Yes, I know how the passive voice works and yes, it is appropriate in this sentence. Also, it’s not really a problem in English but Word still can’t do spaces properly so it wants to put normal spaces everywhere and it’s fucking ugly. I wish it would spend as much time fixing inappropriate breaking spaces (in English as well).
- DevX101 1y agoIt still is? Few engineers could build a good spell checker without external libraries, giving a database of valid words.
- justin66 1y agoIt takes a PhD to develop that. (ahem)
- adrianN 1y agoThe existence of external libraries is part of the point.
- kccqzy 1y agoI was actually asked to build a spell checker in an interview. I immediately thought of Peter Norvig's article on spell corrector (https://norvig.com/spell-correct.html https://norvig.com/spell-correct.html) and proceeded to explain. It turned out that the interviewer really wanted a spell checker not spell corrector: the program will only point out words not in the set of known words. I failed that interview by overengineering.
- dehrmann 1y ago> I failed that interview by overengineering. Almost. You needed to clarify what the interviewer was asking and discover requirements. As much as HN likes to hate on coding interviews requiring specific algorithm knowledge, determining requirements is very much part of the job, and engineers have a tendency to build what they want to build, not what the customer wants.
- elzbardico 1y agoI don't care about people who like to overengineer things, as long as they are humble and have awareness of this tendency. Sometimes you need the extra power and creativity. If they are affable and don't take critics personally, they usually get in with the program easily.
- 1y ago
- benoau 1y agoIIRC none of the popular text-based games of the 80s and early 90s incorporated even basic support for spelling mistakes, best-case scenario they had one or two synonyms baked-in and even that was uncommon!
- yndoendo 1y agoIt is 2025 and the best spell checker is a search engine. Numerous time an application will not provide the correct word. Only solution is to try the word in a search engine and try using in a sentence if that fails. In my opinion, this is where ML/AL local model, no internet required, would be the most beneficial today. Even had to use a search engine with, "thoughts and opi" because I forgot how to spell opinion before posting this. In application spell checker was 100% useless with assisting me.
- athrowaway3z 1y agoI've had a related idea for a while now. Instead of how LLMs operate by taking the current text and taking the most likely next token, you take your full text and use an LLM to find the likeliness/rank of each token. I'd imagine this creates a heatmap that shows which parts are the most 'surprising'. You wouldn't catch all misspelling, but it could be very useful information to find what flows and what doesn't - or perhaps explicitly go looking for something out of the norm to capture attention.
- paol 1y agoI would like this too. This approach would also fix the most common failure mode of spelling checkers: typos that are accidentally valid words. I constantly type "form" instead of "from" for example and spelling checkers don't help at all. Even a simple LLM could easily notice out of place words like that. And LLMs also could easily go further and do grammar and style checking.
- NitpickLawyer 1y agoI've seen this in a UI. They went a step further and you could select a word (well token but anyway) and "regenerate" from that point by selecting another word from the token distribution. Pretty neat. Had the heatmaps that you mentioned, based on probabilities returned by the LLM. This should also be pretty cheap (just one pass through the LLM).
- deleted 1y ago[deleted]
- keiferski 1y agoIs there a reason why Apple's iPhone spellcheck is often really poor, significantly worse than both LLMs and just...human eyes? I often find myself butchering the spelling of a word in a way where the correct answer is obvious to human eyes (probably because of "typoglycemia" [1]) and an AI LLM immediately understands what I meant to say, but Apple's spellcheck has "No Guesses Found." Does anyone else have this experience? 1. https://www.dictionary.com/e/typoglycemia/ https://www.dictionary.com/e/typoglycemia/
- dlivingston 1y agoI run into this all the time. I've just given up on the built-in spell checker and search the word in Google now.
- nicce 1y agoBit off-topic - macOS has excellent built-in dictionary. Just select the word in any app, press Ctrl+Command+D and it opens it. It even guesses most incorrect words correctly. Also translation available if it exist for current keyboard locales. E.g. > No entries for "typoglycemia", did you mean "hypoglycemia"?
- bee_rider 1y agoThese user activated dictionaries tend to be excellent (even in vim, a pretty barebones system, I tend to get fantastic guesses from the machine). Actually, come to think of it, the problem must be a bit easier than on smartphones, right? Real keyboard input is very precise. Smartphone keyboards already guess what word you were trying to spell, so they are influencing the typos in the direction of likely words… cannibalizing the very guess list that the dictionary uses!
- paradox460 1y agoAlfred ties into it nicely too, you can type `spell someword` and the completions below have the various spellings of words, fuzzy matched. Select one and the word goes onto your clipboard
- qmr 1y ago
- bikeshaving 1y agoOne wild thing about the AI era is that tasks which once required specialized NLP expertise—rhyming/meter detection, grammar correction, sentiment analysis—can now be done by weak LLMs. Same APIs, different prompts. I’m surprised more people aren’t exploiting this.
- tgv 1y agoSentiment analysis by small models is quite bad. I haven't tried grammar correction, but I imagine it will perform better in English than in e.g. German.
- real_marcfawzi 1y agoi can't help but make funny connection between "warm" making them less reliable/consistent and the temperature setting....
- deleted 1y ago[deleted]
- numpad0 1y agoIt's also a key enabler to CJK typing on computers. CJK scripts never map to keyboards well, so instead of actually typing, approximate representations are typed in and regularized into written forms using similar technologies as spell checkers. It's a neat thing if you speak one of the languages, sort of interesting that a similar tool haven't been integrated into English keyboards.
- grishka 1y agoDoesn't Chinese input usually work by typing Latin codes for characters? Korean characters represent syllables made up of shapes representing individual sounds, those fit on a keyboard just fine. And I'm not sure about Japanese, there they may use something like spell checkers to map kana to kanji. Another interesting challenge with CJK languages was just displaying them. You need higher-resolution graphics and a much bigger character ROM to even consider that.
- numpad0 1y agoIIUC there are ambiguity problems in Chinese and Korean, just less than there are for Japanese. Korean input has no end-of-character marks and multi-character entry could be split different ways, Chinese has bunch of homonyms-in-Latin, and Japanese is a huge mess(like always, if I think about it...)
- paradox460 1y agoRomanization systems for Chinese vary, but all have the issue that a single "word" in the romanized system can map to dozens, if not hundreds, of actual "words" in the target language. Pinyin is sort of the standard for romanization, although other systems exist, as well as inputs that aren't based on romanization (bopomofo). Take the pinyin `fei`. Just looking at the tones that can be on this word, it can mean at least 4 words (my dictionary app couldn't find any neutral tone words). In reality, its at least dozens, each with different contextual meanings.
- pcrh 1y agoThis is a history Chinese keyboards before word processors, and even as they were first introduced: https://spectrum.ieee.org/chinese-keyboard https://spectrum.ieee.org/chinese-keyboard Very interesting! It was certainly a different technological challenge... Also discussed here: https://news.ycombinator.com/item?id=40537464 https://news.ycombinator.com/item?id=40537464
- 77pt77 1y agoPlease add 2008 to the title.
- YesThatTom2 1y agoMy Commodore 64 had a spellchecker. It was a separate program. I had to save my file, exit my word processor program, switch floppies to the spell checker program, wait for it to load, and all I got was a list of misspelled words… no suggested corrections. Thinking back, how the heck did they do spell checking algorithms on a 6502? That’s a bit of code I’d like to see reverse engineered!
- tomatocracy 1y agoSpellMaster for the (6502-based) BBC Micro was seriously impressive given the space limitations. It did both spell checking and correction (and had an anagram finder as a bonus), had integration with several different wordprocessors, check as you type functionality, AND its own integrated editor on top of that. The built in dictionary had a claimed 58k words (with a claimed checking speed of 10k words per minute). All of this was somehow squeezed into 128k (as a ROM on a carrier board with a hardware bank switching mechanism paging in 16K at once).
- zkmon 1y agoI have used WordStar in 1993. But I don't remember anyone really using the spell checker or feeling a need for it those days. Work was slow and we had enough eyes and time to catch the spelling mistakes. When we were upgraded to MS Word on Windows 3.1, we were astonished to see that it has a feature to preview the document before printing. But somehow WordSatr still looked more fluid and faster than GUI-based word processors.
- rkagerer 1y agoThis article ends too soon! Show me the techniques and solutions those clever programmers of old came up with. Did I miss a link somewhere to subsequent posts?
- canucker2016 1y agosee https://news.ycombinator.com/item?id=44880979 https://news.ycombinator.com/item?id=44880979
- rkagerer 1y agoThanks!
- ethan_smith 1y agoEarly spellcheckers often used Bloom filters to efficiently store dictionaries in minimal memory - a probabilistic data structure that could determine if a word was "definitely not" or "possibly" in the dictionary using just a few bits per word.
- neuroelectron 1y agoI used a document editor in DOS with spellcheck. It was quite fast too. I don't remember what it was called but it featured formatting characters such as character returns and paragraphs. It had good printer support. I think it was called Easy Print and it was only a couple of dollars.
- IAmNotACellist 1y agoPff, now Microsoft Word probably sends your document to an AI every second and asks it to send back a PNG that highlights every misspelled word, and it overlays that underneath your text.
- hilbert42 1y ago"A Spellchecker Used to Be a Major Feat of Software Engineering" It still is. The spell checker on my Android phone is a PIA. It's too dumb to correct many typos, there's no way of highlighting wrongly used but correct words such a 'fro' and 'for', etc. There's no automatic or user defined substitution such as correcting 'rhe' with 'the' and yet keep the words highlighted until a final revision. Wordpossessor spellers have no way of tagging certain words that one may or may not wish to use depending on context. A classic example that's caught me out past the draft and found its way into the final document without me noticing it is 'pubic' for 'public'. Why doesn't my speller highlight such words in red and ask whether I actually meant to use this word? Moreover, spellers are not all of the same level of accuracy, for example Microsoft Word's speller is much better than LibrOffice's much to my annoyance as LibreOffice is my main (preferred) WP. Nor is there a method of collecting misspelled words or typos and tagging them as spelling errors or typos for the purpose of helping one's spelling or typing. It'd be nice to have a list of my misspelled words together with their correct spelling, that way I could become a better speller. Also, spellers could be integrated with full dictionaries—highlight the word and press F1 for its meaning, etc. There are no dictionary formats that are both universal and smart, that is that would allow for easy amalgamation between dictionaries and yet could contain user defined words and other user metadata which would be distinguished from the general corpus of words when crossed or amalgamated. For example, a smart dictionary format could contain metadata that would allow a dictionary and thesaurus to coexist in the same word list, similarly so different dictionaries, technical, medical etc. All up, spellercheckers are still a damn mess. They need urgent attention.
- efitz 1y agoHaving a dictionary is a prerequisite but is only a small part of the spell check problem. Plus, plain text word lists are slow to parse in the 80s; better going with a Trie or some other exotic tree structure that is naturally compressed but O(log(n)) instead of O(n) to traverse. The computer has to figure out whether the word is in the dictionary, but it also has to figure out a suggestion for what to change it to. And even after just that, we already have a bug- homonym mistakes- homonyms are in the dictionary but they’re misspelled (that was intentional btw). How misspelled is another problem. We’ve had Levenshtein et al algorithms for a long time, but how different can you get? A really badly misspelled word might not have any good replacement candidates within your edit distance limit. There are also optimizations like frequently mistyped words (acn-> can), acronyms, etc. It was never just about size.
- dhosek 1y agoThe way growth in memory availability changes the scope of problems is really quite astonishing. I cut my teeth writing code for Apple ][ computers with theoretically up to 128K of RAM, but in practice much closer to 40K for most use cases, but it does make me much more conscious of memory and CPU usage than younger devs who never faced these sorts of constraints. Thinking of the example given about being able to just load the word list into memory, I did something of that ilk when my son’s fifth grade class read a book which had a concept of dollar words: You assign a value to each letter, a=1, b=2, … z=26, add up the value and try to get exactly 100. It was pretty trivial to write a program that read the word list and produced the complete list of dollar words (although I didn’t share that with my son, I did give him access to the word list and challenged him to write the program himself). At the moment, I’m building up a Spanish rhyming dictionary by using a Spanish word list, reversing the words and sorting the reversed list to find the groups of words that are most likely to rhyme, which was something that 30 years ago would have been a challenge on my desktop computer but now is a brief script that I’m just as likely to manage through perl 1-liners and shell pipes as not.
- dingaling 1y agoPity they can't correct themselves to "spelling checker". Would you ask someone to "check my spell"? Not unless you're a wizard, I suppose.
- blast 1y agoWhat became of James Hague? What did he do after he stopped blogging?
- abhijeetpbodas 1y agoRelatedly: "How Unix Spell Ran in 64kB RAM"- https://news.ycombinator.com/item?id=42752604 https://news.ycombinator.com/item?id=42752604
- Theofrastus 1y agoI'd say it still is. I wouldn't even know how to begin if I were to write one.
- PeterStuer 1y agoIn a long forgotten time this used to be called AI.