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

141–150 of 154 posts

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

#141

Post by [deleted] »

nenadst wrote: post #126
greenkey wrote: post #120

Earlier quoted context omitted.

That’s awesome! In comparison, here a quote from the OP’s blog entry: “Fast forward to today. A program to load /usr/share/dict/words into a hash table is 3-5 lines of Perl or Python, depending on how terse you mind being. Looking up a word in this hash table dictionary is a trivial expression, one built into the language. And that's it. Sure, you could come up with some ways to decrease the load time or reduce the m…

I always thought that we still use a trie or (to save memory) ternary search trees for that..

[deleted]

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

#142

Post by ape4 »

staplung wrote: post #68

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.

I made toy spell checker. My way of making suggestions was to take a misspelt word (ie not in the dictionary) and permute some letters - look up the new words - if it was in the dictionary - offer those as suggestions.

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

#143

Post by [deleted] »

RegW wrote: post #110

I wrote a spelling checker in the 1980's In my first job I worked for Tasman in Leeds and produced a Word Processor for IBM PC compatibles in 8086 assembler with some help, and then a spelling checker. For the spelling checker I did a whole load of analysis on a 70,000 word list from Collins and produced a list of tokens to represent common strings of letters. However, in the end I really had to cut the original word…

[deleted]

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

#144

Post by afiori »

Aachen wrote: post #111
Avamander wrote: post #92

Earlier quoted context omitted.

I wish it just struggled with the mix of multiple languages, it can't even handle my native one. A plural compound word in translative case with a clitic? I can only dream about it, it can't even do all the cases reliably.

What language is that? I guess what I'm wondering is how obscure it has to get (or perhaps how low the GDP of the people speaking a language has to be) before custom spell checking rules aren't considered worth it to bigcorps anymore. Though I'm also kinda interested in what this weird language thing is you're talking about.

Could be Italian, where there are words like `portatemelo` ~ `you bring that to me` that google routinely gets wrong.

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

#145

Post by RobAley »

darkwater wrote: post #127
RobAley wrote: post #124

Earlier quoted context omitted.

> Why don’t we Because we don't need to and we have much more interesting problems to take up our time.

But GP already solved the problem (at least for English and other Latin script languages). Why throw away those findings?

Implementation takes time. Keep it simple and move on.

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

#146

Post by afiori »

jiggawatts wrote: post #43
musicale wrote: post #14

Arguably detecting typographical (or transcription) errors is still non-trivial today since a) edit distance is NP complete and b) selecting the correct spelling often depends on grammar as well as semantic context. For example, consider the erroneous phrase "he was put through the ringer." Although "ringer" matches a spelling in the dictionary, it doesn't make sense semantically (a "ringer" being a device that rings…

I often make this mistake in technical documentation: "the database sever was updated". However, a surgeon might want to write "the next procedure is to sever the artery." I wonder if GPT-3 could be used to determine the "context" and determine the spelling correctness "weights"?

I don't think I ever made that specific mistake, but (as a non native speaker) I spent a couple minutes staring at your example and was about to write a comment asking what mistake you were talking about before I spotted the typo.

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

#147

Post by pbhjpbhj »

wolfgarbe wrote: post #102
MHard wrote: post #101

Earlier quoted context omitted.

That would be a grammar checker though. And there are many solutions available today to do that. Even open source solutions. Grammarly would be one example, language tool another. The ones I looked at work by encoding common spelling mistakes into a grammar (as in Chomsky grammar) and then running that over the text.

No, that's not grammar checking, but spelling mistakes that turn out to be real words! If you misspelled "college" as "collage", or you misspelled "three" as "tree" the word you typed incorrectly happens to be an actual word itself! Correcting these types of errors is called "real word spelling correction". Real-word spelling errors are words in a text that, although correctly spelled words in the dictionary, are not…

It's so weird that spellchecking isn't context sensitive: both locality and use.

Locality: The pair "buy Apple" must be vastly preferred, like millions of times more.

Use: I'm writing this and my swipe keyboard offers "spellcasting" when I want "spellchecking". The page I'm on is about spellchecking and the other word isn't one I've ever used until now. You can split these down in to prior-use and use-context, I guess: the former is most annoying, always having to correct in the same manner.

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

#148

Post by selfhoster11 »

warpech wrote: post #122
RegW wrote: post #110

I wrote a spelling checker in the 1980's In my first job I worked for Tasman in Leeds and produced a Word Processor for IBM PC compatibles in 8086 assembler with some help, and then a spelling checker. For the spelling checker I did a whole load of analysis on a 70,000 word list from Collins and produced a list of tokens to represent common strings of letters. However, in the end I really had to cut the original word…

Thanks for this nice detailed memory! How did you get the word list from Collins? Did they license it in a digital form?

They could have been non-copyrighted at the time. Database rights didn't apply in the UK until 1998, so I think it would be fine to have an intern type in just the words into the computer and not infringe on anything.

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

#149

Post by RegW »

warpech wrote: post #122
RegW wrote: post #110

I wrote a spelling checker in the 1980's In my first job I worked for Tasman in Leeds and produced a Word Processor for IBM PC compatibles in 8086 assembler with some help, and then a spelling checker. For the spelling checker I did a whole load of analysis on a 70,000 word list from Collins and produced a list of tokens to represent common strings of letters. However, in the end I really had to cut the original word…

Thanks for this nice detailed memory! How did you get the word list from Collins? Did they license it in a digital form?

The list was used with permission.

I don't know/remember the terms under which this happened. I do remember that when I was trimming it down I found the list contained the trademarks of a competitor. These were removed.

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

#150

Post by RegW »

nafey wrote: post #129
RegW wrote: post #110

I wrote a spelling checker in the 1980's In my first job I worked for Tasman in Leeds and produced a Word Processor for IBM PC compatibles in 8086 assembler with some help, and then a spelling checker. For the spelling checker I did a whole load of analysis on a 70,000 word list from Collins and produced a list of tokens to represent common strings of letters. However, in the end I really had to cut the original word…

Wouldn't using something like trie be useful here?

In the case of the ZX Spectrum +3 there wasn't enough disk or memory to hold the uncompressed word list, nevermind some form of tree structure.

The search method involved uncompressing each word (one at a time) until either the word was found or one that should follow it.

However, I did intend to use a binary search of the word list on the floppy. I arranged it so any zeroes in the list indicated the start of a word from which decompression could start. Under maximum compression there would be only 26 zero bytes in the list, but by selecting short words at regular intervals I could spinkle zeros throughout the list (approx 1 per block). A binary search could scan for the zeros, decompress the associated word and find the section that should contain the target word.

Tasman didn't go for this. They sorted all the words to be checked in memory, then opened the file and did a complete scan.

Post reply on HN