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

21–30 of 154 posts

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

#21

Post by powersnail »

DanBC wrote: post #5

Here's an article that people might be interested in. It gives a bit more detail: https://web.archive.org/web/20100706052342/http://www.spelli... I'm particularly interested in this one, and I'm curious about how useful something like this would be to use. > The second does not use a dictionary at all (Morris & Cherry 1975). Like the previous method, it divides the text into trigrams, but it creates a table of these,…

Consider that the most often typo I make is "ture" for "true", and "flase" for "false", I'd say this isn't going to catch some common mistakes.

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

#22

Post by bobbiechen »

Another great example of this is Key Word In Context [1], which is described in this paper [2] as being possible to implement in a week or two.

My professor (Josh Bloch, in his API design class at CMU) showed us this paper, then showed us his quick implementation using standard Java APIs in less time than the rest of the lecture.

[1] https://en.wikipedia.org/wiki/Key_Word_in_Context

[2] https://prl.ccs.neu.edu/img/p-tr-1971.pdf

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

#24

Post by mattkrause »

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…

Can't edit distance be computed in O(mn) time/space with dynamic programming?

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

#26

Post by emmanueloga_ »

The article on another thread [1] wrought up "Andy and Bils's Law":

"For every cycle a hardware engineer saves, a software engineer will add two instructions."

I thought of that reading last paragraph:

"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."

1: https://news.ycombinator.com/item?id=25285862

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

#28

Post by warent »

powersnail wrote: post #21
DanBC wrote: post #5

Here's an article that people might be interested in. It gives a bit more detail: https://web.archive.org/web/20100706052342/http://www.spelli... I'm particularly interested in this one, and I'm curious about how useful something like this would be to use. > The second does not use a dictionary at all (Morris & Cherry 1975). Like the previous method, it divides the text into trigrams, but it creates a table of these,…

Consider that the most often typo I make is "ture" for "true", and "flase" for "false", I'd say this isn't going to catch some common mistakes.

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

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

#29

Post by emmanueloga_ »

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 was thinking the same, I remember coming across [1] as a possible solution, but far from trivial!

1: https://en.wikipedia.org/wiki/Levenshtein_automaton

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

#30

Post by jka »

DanBC wrote: post #5

Here's an article that people might be interested in. It gives a bit more detail: https://web.archive.org/web/20100706052342/http://www.spelli... I'm particularly interested in this one, and I'm curious about how useful something like this would be to use. > The second does not use a dictionary at all (Morris & Cherry 1975). Like the previous method, it divides the text into trigrams, but it creates a table of these,…

Great reference. This highlights an interesting property of 'reasonably-solved' problems like spell checking and why they might be so much more straightforward now.

It's often not that we've developed groundbreaking algorithms that make solving the underlying problems intrinsically easier - the techniques we're using (like ngram modeling, in this case) may be the result of research work decades ago.

Instead the difference is that the fruit of that prior work has been implemented and made available in more accessible forms (libraries and source code) - and becomes easier to re-use, reason about, and modify thanks to abstraction and languages that have evolved to handle similar problems in a more expressible manner.

(upgrades in hardware and resources certainly help advancement too, but spell checking's probably a good example of a situation where an efficiently-designed implementation's likely to be noticeably more responsive, whether it's 1980 or 2020)

Post reply on HN