Our capability of doing simple spellcheckers has maybe improved, but our standards have risen as well. Back then it might have been amazing, nowadays it's boring and every program has it, even my Firefox browser does.
A spellchecker is only a limited solution to the task of proofreading. I've never used the grammarly product, but at least from the ads it seems it can catch many things that human proofreaders would catch. There might still be domain-specific things that requires humans.
But the grammarly product has way more logic behind it than just using a simple table of words. No idea if it's parametric or uses an ML language model, or maybe a combination, but the feature set wouldn't be possible with just a table.
So instead of a lone employee being tasked to write a spellcheker, you suddenly have an entire industry focused on NLP. That's how the growth of the computing industry looks like :).
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.)
Their google search spellchecker is good, but it's ironic that their android / keyboard spell checker is quite literally the worst I have ever used. Years in and it's maybe 5% as accurate as aspell.
I dunno, really. It is much better than Word on English, but it is laughable when I jumble several languages on a single document, and doesn't handle some laguages that relies on code-switching. At least Word knows its boundaries.
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.
Well, yes, it has to work that way to handle searches for new companies that chose their name based on some non-word with an available domain. If someone types "nvidea" they probably mean "nvidia", and Google doesn't handle that with a dictionary. Same for the handles of social media celebrities.
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?
Not all spellcheckers suggest it wrong, but almost all that rely on statistics, will get it wrong: hoofdaannemer (or hoofdanything), will occur far less than hoofd or aannemer.
This, I fear, is forming our language use. As people rely on tech, they'll follow the suggestions and wrong use of space will turn an actual problem.
This exactly. I've often wondered if the default spell checkers that come with phones nowadays are slowly changing the language itself. If Google doesn't fix these issues in the nearish future, an entire generation will grow up with a device that tells them the spelling they learnt in school is wrong.
And with so many people just accepting Google's anti-compound spelling as correct, many people will be mostly exposed to a version of their language with more spaces, and it'll start to "feel" right to them.
That's true, although in effect, you can 'just' see it as a creative way to meta-optimize google to translate neologisms to do your bidding (hopefully ethical, in fact, it's a very effective way to intentionally cause effects). For example, I think people have had huge type understanding entropy, energy, power, transmission, information, etc with all of the neologisms that people have coined (or converted into fiat currency, or concentrations of power or information, or net 0 carbon obligations vPPAs like google has).
But I gotta say, isn't it a bit exergy-poverty potentiating and lack of laser focus on how fundamental heat transference actually works, both in vivo (important for targeted medicine), in silico (needed to improve the probability of quantum error rate and controllability of decoherence) and in environment (especially with the carbon cycle). This has frequently lead to anti-trust issues in the past, and maybe too much regulatory capture.
The funny thing is that you can metabolize google (and the generalized polyad business pattern pathogen) with hydromel of work to be stolen by outputting work over a distributed work stealing queue (for example, outputting stuff into a private distributed peer to peer distributed version of git, like the laconically named https://fossil-scm.org/home/doc/trunk/www/index.wiki). You can in fact, intentionally skew (or ideate euler or complex-dims of spinor space) words to bias things (this would be traditionally a stein encoding over a homogenous linear space), by analyzing the ROC curve of a virtualized Google flattened to VC-dims, then pushforwarding societal pathologies (can be interpreted as a failure to recognize tragedy of the commons, or failure to invest, spend time on, or be incentivized to think about the over-commercalization of the www, which was certainly not the original intent @ CERN etc. Since google has become over reliant on combinatorial algorithms and things that relate to some encoding of numbers, you can re-discreetly digitalize many logarithms that encode to transcode network-theoretic online modulated wavetrains of datums of infos to be "lifted" up into their internal servers, especially due to the implications of the CCPA and GDPR, it's still fairly trivial to abstractly reinterpret '0' as transience using more raw logical prims or much more complicated physical models but shouldn't come to a surprise are much more stable fundamentally when you are modeling things in the digital world. Probably any one set of services (or people) that have too much digital service providing digital presence may quixotically have destabilizing disequilibria of effects. Not that I think google hasn't immensely positive world good over the long run, they've just spread themselves too thin, when one entity becomes "the truth" but might not have everyone's interests aligned (in a semantic meaningful way), it's very much prone to abuse, especially when people become the products in an unethical fashion. Not too dissimilar to that of Facebook.
I feel it's more statistics based than true spellchecking? At least I often feel that it wants to rewrite my sentences to something completely different because what I'm searching/writing is uncommon but similar to a more common word.
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, noting how often each one occurs in this particular piece of text. It then goes through the text again calculating an index of peculiarity for each word on the basis of the trigrams it contains. Given pkxie, for instance, it would probably find that this was the only word in the text containing pkx and kxi (and possibly xie too), so it would rate it highly peculiar. The word fairy, by contrast, would get a low rating since fai, air and iry probably all occur elsewhere, perhaps quite often, in the passage being analysed. Having completed its analysis, it draws the user's attention to any words with a high peculiarity index. Like the previous method, it would fail to spot a high proportion of ordinary spelling errors, but it is quite good at spotting typing errors, which it was designed for. An advantage that it has over all dictionary-based methods is that it is not tied to English; it will work on passages of, say, French, German or Greek.
A while ago, I was considering building a text editor that ran SQL for a very specific purpose at work. I mused about adding a syntax checker/suggested. I wonder if the above approach might be a better approach to a look up table.
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).
I have abbrev mode i Emacs for that. No more "teh" instead of the. I found most of them went away when I switched to Dvorak, since most of my errors like that are when the letters are in one hand. "teh" however became the all time high. 4000 corrections this year according to abbrev mode. And English isn't even the language I write the most.
If you just want to fix typos then it seems to me that Damerau-Levenshtein distance would be the best approach - a DL distance of 1 from a dictionary word is a high likelihood of a transposition or a missing or extra character.
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)
I've thought of a variation on that, if you're spell checking a large text file. Create an index of all the unique words in the file, along with how many each appears. Any unique words with a count of 1 are likely to be misspelled.
It'd probably be better to look for words with small Levenshtein distance that look like a case of typo, because people tend to miss-spell some words repeatedly, especially in larger texts.
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.
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 :-/
> 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 :-/
We all make mistakes and it’s okay, there is no shame in it! Let the computer fill in the gaps for you so you can use your brain for other things :) I shamelessly use a spell checker in my IDE and it has been a very positive experience, highly recommend!
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.
You might think that's grammar checking but the boundary is not clear and in any case, any language processing application starts with tokenizing and deciding what counts as words and on what basis.
What is a word even ? Is "CIA" a word ? What about "C.I.A." ? What about C (as in the language) ? What about c (as in the speed of light) ? 2,4-Dinitrophenylhydrazine ?
How does the spellchecker handle dashes and apostrophes ? What about proper nouns ?
The feature creep is irrelevant to the article. In 1984, a spell checker could be just a list of words and would still be a major engineering challenge.
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 had probably been programming for less than a year at that stage, and only in the afternoons after I got back from school.
It read the whole document into memory (not the English dictionary, which was too big) in a tree structure. Pointing out that I could use a binary tree and teaching me how to use pointers was my brother's contribution. Then it read through an on-disk copy of the English dictionary. It wasn't a complete dictionary, so I didn't do any compression on the storage, and then asked the user (my sister) to review each word that wasn't in the dictionary, sending any issues out to the printer with a line number and the word in bold.
So if a kid with very little experience could do it, professionals would have had little trouble back then.
Writing a spell-checker on the computer we had before that though (the ZX-spectrum with 16KB of RAM and the only bulk storage being a cassette tape)... that would have been hard. We've definitely progressed since then.
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.
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.
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 bells, a near-duplicate of something else, etc.) and the proper idiom is "put through the wringer" (since a wringer is/was a device to squeeze water out of a wet mop or wet laundry. Squeezing someone through a pair of rollers is particularly evocative.)
Although you do see "nerve-wracking" or "wracking" (i.e. wrecking) one's brain, the more traditional "racking" (literally to torture by stretching on a medieval rack) seems more appropriate (although the term "nervous wreck" is common.) Shakespeare may have exploited the pun of "wrack" vs. "rack," so perhaps we can also.
"Security breaches" and "security breeches" sound alike but have somewhat dissimilar meanings. Network and system administrators might consider donning the latter in preparation for the former.
This isn't in any way a criticism, but I found it really amusing that your post contained almost exactly the error you were describing ("hat") before correction.
Yes, at least for Levenshtein-style edits (substitution, insertion, deletion).
Although, I suppose a spell checker algorithm would be O(mnd) where d is the size of the dictionary, because it needs to compute O(mn) edit distance for each of the dictionary words.
Yes. Up until last two sections is prompt, then I let GPT-3 fill in the responses.
Non-standard English: Please provide me with a short brief of the design youre looking four and some examples or previous projects youve done would be helpful.
Standard American English: Please provide me with a short brief of the design you’re looking for and some examples or previous projects you’ve done would be helpful.
Non-standard English: If Im stressed out about something, I tent to have a problem falling asleep.
Standard American English: If I’m stressed out about something, I tend to have a problem falling asleep.
Non-standard English: There are plenty off fun things too do in the summer when you are able two go outside.
Standard American English: There are plenty of fun things to do in the summer when you are able to go outside.
Non-standard English: She didnt go to hte market.
Standard American English: She didn't go to the market.
Non-standard English: The database sever was updated.
Standard American English: The database server was updated.
Non-standard English: The next procedure is to sever the artery.
Standard American English: The next procedure is to sever the artery.
(In case you're wondering, if I provide 'server' as the input for the second case, it replaces it with 'serve'. Which is reasonable. I tried changing the wording to coax it into placing sever but didn't have much luck)
Indeed, I think most linguistic tasks could benefit from the neural (transformer) approach, even a tiny spellchecker. The combination of semi-regular rules, semantics and logic makes a highly effective "manual" solution too expensive to obtain (in terms of research and programming time).
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.
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.
To be fair, Hunspell was written specifically for Hungarian because it's such a difficult language to handle efficiently in a spell checker. It just happens to also work for other languages.
If you only need English, the complexity of Hunspell is not required.
I still haven't found a decent Hungarian spell checker, they get confused by rare words that have the same letters as a very common word, but different accents.
E.g.: The word "és" means "and", which makes it much more common than "es", which is the word root for "fall" and is rarely used without a suffix like "esett" or "estek".
I'm yet to see a spellchecker that's smart enough to fix "something es something" but not "le es".
First of all it's a verb with -ik ending so you can't write "es", the root lexical word is "esik".
Second you never use anything like "le es" because generaly you always have to
use the verb and prefix together ("leesett", "leesik" etc.) unless you use a commanding form ("ess le") or a modal verb ("le akart esni, "le fog esni" etc.)
"le es" is strictly wrong because it's the wrong verb (should be "esik") and you have to write together ("leesik") so obviously a spellchecker picks that up.
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.
Exactly. It's a very important argument against calling it a solved problem. I believe the problem with hunspell is that it's very hard to get into fixing it (it's good, but it's not perfect) and spylls makes it feasible again
If french is one of your language, state of the art has been Druide's Antidote for more than 20 years. And it has had a Linux version available for almost 15 years, too.
I would argue that it's not a hard engineering problem. It's just a problem that should be solved. Linguists made a lot of formalizations about language. There are rules, there are known lists of exceptions, there are dictionaries. You just have to implement those things carefully with lots of edge-cases, implement it for every language, but it's just mundane engineering work, nothing that requires breakthrough.
Currently spell checking just checks words from a dictionary. Its 1% of work. Or even less.
Microsoft Word used to have awesome spell checking, grammar checking, etc back in 2000 for Russian language. It seems to be degraded since then. But the fact is, this problem was solved. It checked for spelling, for grammar, for punctuation. I would expect that kind of functionality working in every OS textbox by now.
>You just have to implement those things carefully with lots of edge-cases,
Say hello to homophones, ambiguous phrases and double meaning.
In Spanish a lot of verbs share the singular first and third persons. "Estaba" can mean "I was" or "He/she was.". Or "fuimos", (we were); but also "we went".
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. [...] That's progress.
I was curious -- This Python script consumes 9.5 MB of RAM on my Mac, which is a whole lot of 1980s-era PCs. Sure, in most cases this one decision to use a terse but unoptimized data structure won't matter much on a modern computer, but it adds up!
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.
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."
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.
152 comments
[ 2.9 ms ] story [ 228 ms ] threadA spellchecker is only a limited solution to the task of proofreading. I've never used the grammarly product, but at least from the ads it seems it can catch many things that human proofreaders would catch. There might still be domain-specific things that requires humans.
But the grammarly product has way more logic behind it than just using a simple table of words. No idea if it's parametric or uses an ML language model, or maybe a combination, but the feature set wouldn't be possible with just a table.
So instead of a lone employee being tasked to write a spellcheker, you suddenly have an entire industry focused on NLP. That's how the growth of the computing industry looks like :).
Word/Outlook 2016 now have EXTENSIVE but DEFAULT OFF grammar and sentence styling assistance.
File > Options > Editor Options > Proofing > Writing Style.
Ref: https://twitter.com/SwiftOnSecurity/status/97440857301385216...
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.
Out of curiosity, what is your native language, Dutch? Can you give an example of something that Google’s spell checker screws up?
* hoofdaannemer - hoofd aannemer : main contracter - person who takes heads
* wegomlegging - weg om legging : road closure, a road around a legging(pants)
* dagverse vis - dag verse vis : catch of the day - goodbye, fresh fish
This twitter has many such errors in the wild.
https://mobile.twitter.com/spatiegebruik
Not all spellcheckers suggest it wrong, but almost all that rely on statistics, will get it wrong: hoofdaannemer (or hoofdanything), will occur far less than hoofd or aannemer.
This, I fear, is forming our language use. As people rely on tech, they'll follow the suggestions and wrong use of space will turn an actual problem.
Edit: formatting.
And with so many people just accepting Google's anti-compound spelling as correct, many people will be mostly exposed to a version of their language with more spaces, and it'll start to "feel" right to them.
But I gotta say, isn't it a bit exergy-poverty potentiating and lack of laser focus on how fundamental heat transference actually works, both in vivo (important for targeted medicine), in silico (needed to improve the probability of quantum error rate and controllability of decoherence) and in environment (especially with the carbon cycle). This has frequently lead to anti-trust issues in the past, and maybe too much regulatory capture.
The funny thing is that you can metabolize google (and the generalized polyad business pattern pathogen) with hydromel of work to be stolen by outputting work over a distributed work stealing queue (for example, outputting stuff into a private distributed peer to peer distributed version of git, like the laconically named https://fossil-scm.org/home/doc/trunk/www/index.wiki). You can in fact, intentionally skew (or ideate euler or complex-dims of spinor space) words to bias things (this would be traditionally a stein encoding over a homogenous linear space), by analyzing the ROC curve of a virtualized Google flattened to VC-dims, then pushforwarding societal pathologies (can be interpreted as a failure to recognize tragedy of the commons, or failure to invest, spend time on, or be incentivized to think about the over-commercalization of the www, which was certainly not the original intent @ CERN etc. Since google has become over reliant on combinatorial algorithms and things that relate to some encoding of numbers, you can re-discreetly digitalize many logarithms that encode to transcode network-theoretic online modulated wavetrains of datums of infos to be "lifted" up into their internal servers, especially due to the implications of the CCPA and GDPR, it's still fairly trivial to abstractly reinterpret '0' as transience using more raw logical prims or much more complicated physical models but shouldn't come to a surprise are much more stable fundamentally when you are modeling things in the digital world. Probably any one set of services (or people) that have too much digital service providing digital presence may quixotically have destabilizing disequilibria of effects. Not that I think google hasn't immensely positive world good over the long run, they've just spread themselves too thin, when one entity becomes "the truth" but might not have everyone's interests aligned (in a semantic meaningful way), it's very much prone to abuse, especially when people become the products in an unethical fashion. Not too dissimilar to that of Facebook.
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, noting how often each one occurs in this particular piece of text. It then goes through the text again calculating an index of peculiarity for each word on the basis of the trigrams it contains. Given pkxie, for instance, it would probably find that this was the only word in the text containing pkx and kxi (and possibly xie too), so it would rate it highly peculiar. The word fairy, by contrast, would get a low rating since fai, air and iry probably all occur elsewhere, perhaps quite often, in the passage being analysed. Having completed its analysis, it draws the user's attention to any words with a high peculiarity index. Like the previous method, it would fail to spot a high proportion of ordinary spelling errors, but it is quite good at spotting typing errors, which it was designed for. An advantage that it has over all dictionary-based methods is that it is not tied to English; it will work on passages of, say, French, German or Greek.
(The Morris there is Bob Morris).
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).
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)
https://norvig.com/spell-correct.html
Edit: forgot the link https://github.com/dlang/dmd/blob/master/src/dmd/root/spelle...
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.
https://github.com/wolfgarbe/SymSpell
https://norvig.com/spell-correct.html
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 :-/
We all make mistakes and it’s okay, there is no shame in it! Let the computer fill in the gaps for you so you can use your brain for other things :) I shamelessly use a spell checker in my IDE and it has been a very positive experience, highly recommend!
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. You might think that's grammar checking but the boundary is not clear and in any case, any language processing application starts with tokenizing and deciding what counts as words and on what basis.
What is a word even ? Is "CIA" a word ? What about "C.I.A." ? What about C (as in the language) ? What about c (as in the speed of light) ? 2,4-Dinitrophenylhydrazine ? How does the spellchecker handle dashes and apostrophes ? What about proper nouns ?
Really, the example is poorly chosen.
That it can't even identify that it itself is a "spelling checker" illustrates the problem.
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 had probably been programming for less than a year at that stage, and only in the afternoons after I got back from school.
It read the whole document into memory (not the English dictionary, which was too big) in a tree structure. Pointing out that I could use a binary tree and teaching me how to use pointers was my brother's contribution. Then it read through an on-disk copy of the English dictionary. It wasn't a complete dictionary, so I didn't do any compression on the storage, and then asked the user (my sister) to review each word that wasn't in the dictionary, sending any issues out to the printer with a line number and the word in bold.
So if a kid with very little experience could do it, professionals would have had little trouble back then.
Writing a spell-checker on the computer we had before that though (the ZX-spectrum with 16KB of RAM and the only bulk storage being a cassette tape)... that would have been hard. We've definitely progressed since then.
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.
2015 https://news.ycombinator.com/item?id=10789019
2012 https://news.ycombinator.com/item?id=4640658
2012 https://news.ycombinator.com/item?id=3466388
Discussed at the time: https://news.ycombinator.com/item?id=212221
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 bells, a near-duplicate of something else, etc.) and the proper idiom is "put through the wringer" (since a wringer is/was a device to squeeze water out of a wet mop or wet laundry. Squeezing someone through a pair of rollers is particularly evocative.)
Although you do see "nerve-wracking" or "wracking" (i.e. wrecking) one's brain, the more traditional "racking" (literally to torture by stretching on a medieval rack) seems more appropriate (although the term "nervous wreck" is common.) Shakespeare may have exploited the pun of "wrack" vs. "rack," so perhaps we can also.
"Security breaches" and "security breeches" sound alike but have somewhat dissimilar meanings. Network and system administrators might consider donning the latter in preparation for the former.
Although, I suppose a spell checker algorithm would be O(mnd) where d is the size of the dictionary, because it needs to compute O(mn) edit distance for each of the dictionary words.
1: https://en.wikipedia.org/wiki/Levenshtein_automaton
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"?
Non-standard English: Please provide me with a short brief of the design youre looking four and some examples or previous projects youve done would be helpful. Standard American English: Please provide me with a short brief of the design you’re looking for and some examples or previous projects you’ve done would be helpful.
Non-standard English: If Im stressed out about something, I tent to have a problem falling asleep. Standard American English: If I’m stressed out about something, I tend to have a problem falling asleep.
Non-standard English: There are plenty off fun things too do in the summer when you are able two go outside. Standard American English: There are plenty of fun things to do in the summer when you are able to go outside.
Non-standard English: She didnt go to hte market. Standard American English: She didn't go to the market.
Non-standard English: The database sever was updated. Standard American English: The database server was updated.
Non-standard English: The next procedure is to sever the artery. Standard American English: The next procedure is to sever the artery.
(In case you're wondering, if I provide 'server' as the input for the second case, it replaces it with 'serve'. Which is reasonable. I tried changing the wording to coax it into placing sever but didn't have much luck)
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.
If you only need English, the complexity of Hunspell is not required.
I still haven't found a decent Hungarian spell checker, they get confused by rare words that have the same letters as a very common word, but different accents.
E.g.: The word "és" means "and", which makes it much more common than "es", which is the word root for "fall" and is rarely used without a suffix like "esett" or "estek".
I'm yet to see a spellchecker that's smart enough to fix "something es something" but not "le es".
First of all it's a verb with -ik ending so you can't write "es", the root lexical word is "esik".
Second you never use anything like "le es" because generaly you always have to use the verb and prefix together ("leesett", "leesik" etc.) unless you use a commanding form ("ess le") or a modal verb ("le akart esni, "le fog esni" etc.)
"le es" is strictly wrong because it's the wrong verb (should be "esik") and you have to write together ("leesik") so obviously a spellchecker picks that up.
But if you're right (seems like you are), then why do spell checkers not pick up on "es" as misspelled?
Mostly for numerals:
"I arrive with the train at 7" [as in 7 o'clock] = "A 7-es vonattal érkezem"
"M7 motorway" = "M7-es autópálya"
"50m² room" = "50m²-es szoba"
But it's also used with foreign names and full names.
> 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.
Currently spell checking just checks words from a dictionary. Its 1% of work. Or even less.
Microsoft Word used to have awesome spell checking, grammar checking, etc back in 2000 for Russian language. It seems to be degraded since then. But the fact is, this problem was solved. It checked for spelling, for grammar, for punctuation. I would expect that kind of functionality working in every OS textbox by now.
Say hello to homophones, ambiguous phrases and double meaning.
In Spanish a lot of verbs share the singular first and third persons. "Estaba" can mean "I was" or "He/she was.". Or "fuimos", (we were); but also "we went".
I was curious -- This Python script consumes 9.5 MB of RAM on my Mac, which is a whole lot of 1980s-era PCs. Sure, in most cases this one decision to use a terse but unoptimized data structure won't matter much on a modern computer, but it adds up!
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
By then it was fairly trivial.
"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
I rarely need any spellchecking on smartphone because most spelling errors have been eliminated at the point of word entry.
https://youtu.be/tc4ROCJYbm0
(Shell coding starts at 8:40)
https://youtu.be/XvDZLjaCJuw?t=828
Now that I think about it spellcheckers were pretty sh!te not that long ago...
https://itnext.io/string-similarity-the-basic-know-your-algo...