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

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

prog21.dadgum.com

Post reply on HN
Print view View original

61–70 of 154 posts

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

#61

Post by solresol »

SulfurHexaFluri wrote: post #41
solresol wrote: post #10

I don't want to brag, but it wasn't that hard to write a spellchecker in 256KB in 1984. I was in primary school (age 11) and we had a Microbee at home with 64KB of RAM and a copy of Turbo Pascal. My sister is/was dyslexic so with a bit of help from my older brother (who would have been in first year of computer science at the time) I wrote a spellchecker for her. It think it might have been a Christmas present, so I…

A spell checker isn't something in a binary state of working or not working. Its something that has the almost impossible task of working out what the user wanted and not what they asked for. Maybe most of your problems are a single letter mistake or a keyboard slip up but where good spell checkers shine is they know what you want even when you are miles off. I find googles spell checking to be exceptional at underst…

Of course, I wouldn't dream of saying that spelchek.pas (as I think I called it because 11-year-old me thought that was hilarious) was state of the art at the time, nor would it be sufficient for any purpose today. But it solved the core of the problem: identifying words with a likely mis-spelling, which is all the original article was talking about.

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

#63

Post by [deleted] »

WalterBright wrote: post #8

I especially like the spellchecker added to the D compiler. The neato feature is the "dictionary" is the part of the symbol table that is in scope. In my usage it guesses right about 50-75% of the time. I've been considering adding one to my text editor. I found out I'm not as good a speller as I thought I was before spellcheckers :-/

[deleted]

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

#64

Post by lacker »

jeroenhd wrote: post #50
lacker wrote: post #3

Google's spell checker still is a major feat of software engineering ;-) It must handle every language, handle new words constantly being coined, have low enough latency and high enough throughput to run it on every web search. (Well, caching probably solves 2/3 of traffic.)

While it's not bad, it's not that great a universal tool either. My native language makes use of a lot of compound words and Google's spell checker often gets confused when I combine words according to the standard grammar. I can see and understand the technical limitations, but tools like Microsoft Word seem to do a much better job than Google's spell checker, even in things like Google Docs. Google search will ofte…

Yeah, exactly! - this is why building the perfect spell checker is still a challenging and interesting engineering problem, in 2020. The nature of misspelling varies from language to language, especially with non-letter-based languages like CJK, or with input methods that lead to different sorts of typos than a regular keyboard.

Out of curiosity, what is your native language, Dutch? Can you give an example of something that Google’s spell checker screws up?

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

#65

Post by lowbloodsugar »

vageli wrote: post #32
warent wrote: post #28

Earlier quoted context omitted.

From what they said above, it sounds like that's exactly the kind of thing it would catch unless you consistently wrote "ture" and "flase" many times in the same document

> From what they said above, it sounds like that's exactly the kind of thing it would catch unless you consistently wrote "ture" and "flase" many times in the same document The trigrams tur and ure are not that uncommon, nor fla or ase (though maybe they are less common in a programming context, by but even then it might depend on domain).

flag case future

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

#66

Post by thangalin »

pbreit wrote: post #52
Loranubi wrote: post #44

Earlier quoted context omitted.

It's a nice demo and a good tutorial if you are interested in spell checkers. But imo it did more bad than good. A lot of libraries started to implement it. But it's quite horrible in performance.

What is better?

SymSpell is about 1 million times faster than Norvig's algorithm.

https://github.com/wolfgarbe/SymSpell

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

#67

Post by Isamu »

One of the early implementations of Unix spell used a Bloom filter to compress the word list:

“Two different hashing methods have been implemented. The first, based on a simple superimposed code scheme first proposed by Bloom,9, 10 was supplied by D. M. Ritchie and succeeded in encoding a 25,000-word list into 50,000 bytes. A more elaborate method, in which values of a conventional hash func- tion are represented in a differential Huffman code, squeezed 30,000 words into 52,000 bytes. The stop list is handled by the same method in a different process.”

Doug McIlroy discussed the history of spell at Bell Labs here: https://www.cs.dartmouth.edu/~doug/spell.pdf

I remember emailing Doug to ask him about this and he was great, very helpful to me. Thanks Doug!

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

#68

Post by staplung »

Really, there are two components to a modern spell checker. First, identify the words that are misspelled. Second, offering (good) corrections. This article is really talking about how hard even the first task was when memory was scarce. Offering good suggestions is still non-trivial.

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

#69

Post by bluedino »

Typhon wrote: post #9

This is a rather bad article because it completely misses the real complexity of a spell checker. A spell checker is not simply a list of words, it's a way to check mistakes according to a standard and to point towards ways to fix these mistakes. This not reducible to a look-up in a hashtable. It requires taking into account some complicated things about the definition of a word and the context in which it is written…

Had you used any spellcheckers from that era?

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

#70

Post by abetlen »

sabalaba wrote: post #45

Interestingly enough, this video from the 1980s shows Brian Kernighan writing a one line spellchecker program in UNIX shell. Obviously, the computer that it’s running on is more powerful than a 256K PC. The point stands: some people are simply living in the future. https://youtu.be/tc4ROCJYbm0 (Shell coding starts at 8:40)

They really were. Here's a version of that video that includes Lorinda Cherry writing a talking calculator by piping together 3 unix commands.

https://youtu.be/XvDZLjaCJuw?t=828

Post reply on HN