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

41–50 of 154 posts

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

#41

Post by SulfurHexaFluri »

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 understanding the mapping between how a word sounds like and what it actually is even when they share very few letters in common.

An easy example of what I mean is if the input is "shivon" and the spell checker is able to correct this to "Siobhán" because it knows this is how users try to spell it when they have no idea. A simple algorithm isn't able to do this because there are no logical rules of english to follow here, you would likely need a massive amount of user data to train on to solve this test case.

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

#43

Post by jiggawatts »

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

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

#44

Post by Loranubi »

adamjb wrote: post #6

If you haven't seen it already you should check out Peter Norvig's 20-odd line toy spell checker, written over the course of a flight. https://norvig.com/spell-correct.html

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.

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

#45

Post by sabalaba »

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)

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

#46

Post by oneearedrabbit »

Const-me wrote: post #15

A good spell checker is still a hard engineering problem, despite the hardware progress. Just a hash map ain't gonna work. The only reason spell checking is perceived as a solved problem is availability of libraries. Here's an open source example https://github.com/hunspell/hunspell way above 10k lines of code. I speak 4 languages, and in my experience what's in Microsoft Office is the best one I used so far.

I suppose, it is worth giving a shout-out to a recent Hunspell port to Python by Zverok: https://github.com/zverok/spylls, this description from Github sums it up nicely:

> Hunspell is a long-living, complicated, almost undocumented piece of software, and it was our feeling that the significant part of human knowledge is somehow "locked" in a form of a large C++ project. That's how Spylls was born: as an attempt to "unlock" it, via well-structured and well-documented implementation in a high-level language.

It's incredible how much work has been done (along with documenting algorithms!) in this one-man project.

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

#47

Post by bombastry »

WalterBright wrote: post #11
adamjb wrote: post #6

If you haven't seen it already you should check out Peter Norvig's 20-odd line toy spell checker, written over the course of a flight. https://norvig.com/spell-correct.html

Here's D's spell checker, tests included! Edit: forgot the link https://github.com/dlang/dmd/blob/master/src/dmd/root/spelle...

I believe that this may be the missing link (or equivalent):

https://github.com/dlang/dmd/blob/master/src/dmd/root/spelle...

This is a spell-checker in the D reference compiler that detects typos in identifiers and suggests potential corrections for those typos.

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

#50

Post by jeroenhd »

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 often suggest splitting up words and sometimes even does it transparently, which can give entirely wrong results because suddenly Google matches words across a sentence instead of specific compound words. It's kind of frustrating to have to resort to quotation marks for some single-word search terms.

I get the feeling Google's spell checker doesn't check spelling, it just tweaks the input until it manages to find more results. Not quite the same, because a lot of "fixes" often have entirely different meanings in my experience.

Post reply on HN