There have been a few requests in the past for improvements to the spell checker. Currently MUSHclient uses a proprietary system purchased from Wintertree Software Inc.
I am contemplating moving to a custom system, which would potentially have a few advantages:
You could supply your own dictionaries (eg. in other languages, like French, Greek, German, etc.).
The behaviour could be customised more (eg. ignore the first word, like @aset or something like that).
Maybe auto-correct things (like 'teh' to 'the').
Maybe correct as-you-type.
It seems to me that spell checking isn't really rocket science, it shouldn't be too hard to do something that is at least as good as we currently have.
I guess the features which are probably needed to make this work are:
Possibly ignore lines which match an alias.
Break up entered text into "words". A word would probably be a sequence of letters and possibly numbers, probably including single quotes (eg. Nick's).
Discard certain words if required (eg. starting with caps, all caps, words with numbers in them, words with mixed case, words of all numbers).
Look up remaining words in a dictionary, possibly allowing for a "user dictionary" which can be added to.
Also check for doubled words (eg. "bird in the the hand").
If the word isn't found, possibly auto-correct if in a list (eg. 'teh' to 'the').
Otherwise display a dialog box with the "wrong" word displayed, and a list of suggested alternatives.
Allow manual correction, selecting from an alternative, or adding the word to a user dictionary.
I wonder what the correct treatment of case errors is? For instance, you enter "boston" but "Boston" is in the dictionary ...
(That being said, I would be happy to provide Nick with a C++ class I wrote that fully implements a character-based lexical trie; the work would then be to add all words displayed into that trie and then query it for words. It already takes care of things like asking for a list of words that start with a certain prefix, or even a list of words that match a (simple) regular expression.)
Would that be suitable for a spell checker? Would it take less storage than a simple table? I currently tested loading in thousands of words into a Lua table, it seems fast enough, but takes about 9 Mb of memory.
Yes, lexical tries are very, very good for anything, really, that needs to store a list of words.
My class also happens to have a built-in suggestion request method, which you might find helpful. :-)
Here are some memory statistics, as seen by 'top':
13723 david 18 0 26992 20m 896 S 0 1.0 0:01.07 trie
13748 david 17 0 8776 2612 896 S 0 0.1 0:00.10 trie
Recall that memory usage is in the 5th column (virtual memory i.e. total) and 6th column (resident memory).
In the big case (26mb) I loaded 127,142 words. In the small case (8k), I loaded the first 10,000 words of the big file -- all the words up to and including 'bewail'.
One reason we're seeing such a big memory savings is that tries are very good at compressing string with common prefixes. It would be a better test of memory usage to load 10,000 random words and see what the memory usage is. Nonetheless, I'm not sure how many thousand words you added in your case -- let's assume it was 10,000. That took 9 mb in a straight Lua table. Mine takes just over twice as much memory for 12 times as many words; one would assume that the Lua table size would increase more or less linearly as you add more and more words.
My only problem is that I need to keep suggested spellings. That is, for a given word I need to know "sound alike" words. Merely knowing "present or not" is not sufficient. Will the trie handle that? To put it another way, say someone enters "bote", we might suggest "boat", "bat", "bot", "boot" and so on.
I have an algorithm for the sound-alike stuff, and what I am currently doing is converting that (to, say, "BT") and then looking up that by key in the Lua table. Under BT in the table will be a sequential list of all the words that happen to sound like that. Now, if "boat" is in the list, then that counts as correct spelling. This also gives me a chance to match on, optionally, same or different case. If it isn't in the list, I immediately have all the sound-alikes.
Yes, it can do that. It uses edit distance as a measurement of proximity, which is not necessarily the best.
Here is what it gives for an edit distance of 1:
Suggested corrections for 'bote', e.d. = 1:
bate bite bode boite bole bone bore bot bota botel both bots bott byte cote dote mote note rote tote vote
The word 'boat' doesn't appear in that, which is unfortunate but that's what edit distance does. If we increase the max edit distance to 2, we get all kinds of words, many of which we don't want.
A smarter algorithm would assign a max 'cost', and then use some heuristic to determine which changes cost how much. For instance changing 'o' to 'i' might be cheap due to keyboard proximity. This would be a fair bit more complicated, though.
I have finished packaging the class and am releasing it now. I'll put a post in Prog:General with the link. :)
Some don't even start with "k" (but sound like "knife").
Maybe a trie per sound-alike sound.
The number of sound-alikes depends on the number of characters you store, for 4 characters I get 10181 unique sounds, but for 6 characters I get 23204 sounds.
This is from a dictionary of 76822 words. The whole thing loads from a straight text file, including computing the sound-alikes (itself implemented in C) in about a second.
Hmm. I wonder if this sound-alike notion could be adapted to the trie's notion of 'word distance'. Or, as you say, store a trie per sound-alike. Or, another idea, perhaps more efficient given the large number of sounds you have, would be to have a trie of sounds, and instead of a simple boolean indicating presence, you would use a pointer to another trie of words that sound alike. (And to really save memory you would want those tries to share string memory. My shared string library comes to mind...)
How do you map a given word to its "sound representation"? Do you compute that on the fly?
This is the documentation I have for the algorithm, and yes it is done on the fly. ...
/***************************************************************
Metaphone Algorithm
Created by Lawrence Philips (location unknown). Metaphone presented
in article in "Computer Language" December 1990 issue.
Converted from Pick BASIC, as demonstrated in article, to C by
Michael J. Kuhn (Baltimore, Maryland)
My original intention was to replace SOUNDEX with METAPHONE in
order to get lists of similar sounding names that were more precise.
SOUNDEX maps "William" and "Williams" to the same values. METAPHONE
as it turns out DOES THE SAME. There are going to be problems
that you need to resolve with your own set of data.
Basically, for my problem with S's I think that if
IF metaphone[strlen(metaphone)] == "S"
AND strlen(metaphone) >= 4 THEN
metaphone[strlen(metaphone)] = ""
You can add you own rules as required.
Also, Lawrence Philips suggests that for practical reasons only the
first 4 characters of the metaphone be used. This happens to be the
number of characters that Soundex produces. This is indeed practical
if you already have reserved exactly 4 characters in your database.
In addition an analysis of your data may show that names are split
into undesirable "metaphone groups" as the number of metaphone characters
increases.
*********** BEGIN METAPHONE RULES ***********
Lawrence Philips' RULES follow:
The 16 consonant sounds:
|--- ZERO represents "th"
|
B X S K J T F H L M N P R 0 W Y
Exceptions:
Beginning of word: "ae-", "gn", "kn-", "pn-", "wr-" ----> drop first letter
"Aebersold", "Gnagy", "Knuth", "Pniewski", "Wright"
Beginning of word: "x" ----> change to "s"
as in "Deng Xiaopeng"
Beginning of word: "wh-" ----> change to "w"
as in "Whalen"
Transformations:
B ----> B unless at the end of word after "m", as in "dumb", "McComb"
C ----> X (sh) if "-cia-" or "-ch-"
S if "-ci-", "-ce-", or "-cy-"
SILENT if "-sci-", "-sce-", or "-scy-"
K otherwise, including in "-sch-"
D ----> J if in "-dge-", "-dgy-", or "-dgi-"
T otherwise
F ----> F
G ----> SILENT if in "-gh-" and not at end or before a vowel
in "-gn" or "-gned"
in "-dge-" etc., as in above rule
J if before "i", or "e", or "y" if not double "gg"
K otherwise
H ----> SILENT if after vowel and no vowel follows
or after "-ch-", "-sh-", "-ph-", "-th-", "-gh-"
H otherwise
J ----> J
K ----> SILENT if after "c"
K otherwise
L ----> L
M ----> M
N ----> N
P ----> F if before "h"
P otherwise
Q ----> K
R ----> R
S ----> X (sh) if before "h" or in "-sio-" or "-sia-"
S otherwise
T ----> X (sh) if "-tia-" or "-tio-"
0 (th) if before "h"
silent if in "-tch-"
T otherwise
V ----> F
W ----> SILENT if not followed by a vowel
W if followed by a vowel
X ----> KS
Y ----> SILENT if not followed by a vowel
Y if followed by a vowel
Z ----> S
**************************************************************/
There is C code for that, I can post that if you want.
Now I immediately see a problem with this - the algorithm is obviously oriented around the English language. If it is used in a spell checker, then languages like French and German (and the rest) will have different rules for what is silent in what situation, and what consonants sound like each other.
I thought maybe a state machine? You are an expert on them are you not Ksilyan? Surely what is described above can be reduced to a fairly simple state machine? Then you could have one state table per language.
Yes, you are right about the problem with other languages. I'm somewhat curious how spell checkers handle this problem in general. Perhaps the dictionary files encode their language's notion of word similarity?
Quote: You are an expert on them are you not Ksilyan? Surely what is described above can be reduced to a fairly simple state machine? Then you could have one state table per language.
Well I'm not sure if I'm an "expert". :-) But yes it should be relatively simple to convert that to a state machine, as long as the rules have no ambiguity. (I'm assuming they don't.) This could probably be done using the lexing tool 'flex'. This sounds like a fun, relatively short project. I'll see if I have time to work on this this weekend.
One problem I see is that some languages, including English for that matter, have different rules for the same arrangements of letters. 'Knuth' is actually a good example. This documentation claims it's pronounced "Nooth" when in fact it's pronounced "Ka-Nooth". This is a common Stanford way to tell if somebody else is in fact familiar with Don Knuth personally. :-) (For reference's sake, my claim comes straight from Knuth himself: http://www-cs-faculty.stanford.edu/~knuth/faq.html)
French is even worse as the rules are not quite regular, even for relatively common words.
I wonder how word processors like Word, Open Office, or Thunderbird's built-in checker handle these things.
But, in any case, yes, if a language could have its sound-alike rules written out, then you could have one state machine per language, which would let you quickly convert a word to its phoneme. Then you could imagine a "reverse-checker" that would iterate over the trie, seeing which words could possibly correspond to that suggestion. Hopefully the rules given in the algorithm go both ways unambiguously. If that is the case then it would be fairly easy to walk the trie recursively and efficiently determine which branches could correspond to the given word.
Or maybe it can be done with a series of regexps. My testing indicates it probably can, however it may be slow. Also, regexps, continually applied to the whole string, probably have a different sense than looking forwards by letter.
That is a very interesting question, honestly I'm not so sure what to do about it.
What's nice about correct-as-you-type, or, at least, highlight-as-you-type, is that you know what words the checker thinks are bad but you don't have to deal with popup windows or anything of the sort. That way, I can type whatever I want, and if something isn't in the dictionary but I know it's correct, I can either add it (if I'm going to use it a lot) or just ignore it.
The other metaphone algorithm you gave looks like it gives better results, by the way. I'm happier with its list of suggestions for 'knife'.
I've been thinking about how to best use the algorithm in combination with tries to make a very efficient spell-checker, but I'm not sure yet. I suspect that the metaphone algorithm can be combined into the recursive walking of the trie. If I had the time, I'd have wanted to do more proper research into how the open source spell-checkers solve this problem...
I think that most people find actual 'correct as you type' annoying, save for a very limited list of things that always are errors. Like 'teh' for the', for example. I believe Word, for example, allows you to set it so it only autocorrects very common mistakes.
On the other hand, live _marking_ of potentially misspelled words (I think ICQ, for example, uses a red dashed underline for such words) is excellent, since it gets your attention.
Even better is if you then can right-click on the marked word to get a list of suggestions.
My experience in MUDs is you generally type everything in lower case, so maybe the problem goes away a bit. However the proper names are still an issue, maybe you quickly add them to the dictionary, or ignore-list.
Quote:
On the other hand, live _marking_ of potentially misspelled words (I think ICQ, for example, uses a red dashed underline for such words) is excellent
Well, live marking involves a spell check for every character as you type, which makes the burden of making it fast enough greater. A single check for a paragraph might accept a 0.5 second delay, but not for every character.
As for the marking, I'm not sure the edit box used for MUSHclient commands accepts stuff like red underlines, that potentially is another problem.
However I must admit that I was finding it hard to think of a nice way of spell checking without annoying dialog boxes getting in your way.
Yes, dialog boxes popping up would be an issue, I think. All the applications I have seen that do live checking do it as live marking of errors, not live offers to change via a dialog box.
Regarding the uppercase and lowercase issue, btw, it doesn't hold true for MUSHes that most everything is typed in lowercase.
I do, but that's an on demand spellchecker, not an automatic, live spell-checker. If boxes popped up automatically as I was typing and happened to get something wrong, it would be a problem. :)
Well, for simplicity, if the existing spellchecker was replaced by our own one (thus supporting multiple dictionaries for instance), then at the very least, having a spell-check on send, with dialog boxes, would be no worse than we currently have.
Though, I think it should probably be optional whether to have it automatically spell-check on send or whether it should be called up manually.
I wonder, though, how some of the other programs accomplish the live marking of misspelled words. ICQs input window, for example, seems very similar to that of MUSHclient, and it doesn't seem to slow things down.
Thunderbird also does highlight-as-you-type, and checks words only after a word-boundary character has been typed. A word-boundary character is something like a space, punctuation mark, new line, etc. It's quite fast.
I think that if there's a 0.5 second delay in checking spelling, something very wrong is happening. It should be very, very quick to see if a word is in the dictionary or not.
I did a quick test, and it took 5 seconds to load up 127k words, find suggestions for "bote", and then look up the word "transformation" a million times. If I change that to 10,000 lookups, it takes 1 second. (Interesting result, actually.) This is without optimization. If I turn on optimization, with -O3, it takes 2.8 seconds to do everything with one million words, and 0.6 seconds to do everything with ten thousand words. Recall that in both cases, I load up the entire dictionary of 127k words first.
So I think that we can get much better performance than 0.5s. :-)
I am not worried about the speed, as much as making a custom input box that allows words to be highlighted (eg. with a red squiggle) as you type.
The current edit control just doesn't allow that, and if it was changed to a rich-edit control, then that would have other ramifications (eg. if you pasted styled text into it).
I have a prototype going, I might release that for analysis. This is a straight "dialog box" one that pops up when you hit <enter> to send your text, similarly to the current one.
There are still some administrative issues, like the question about upper/lower case words. Also cases like this:
I want you to type 'east' now.
The problem is the single quotes. If they are considered part of the word, then we get an error that: east' is not in the dictionary.
However, if single quotes are not considered part of a word then something like this will raise an error:
Hold the gun at arm's length.
Given that "s" is not a word, it would accept "arm" but not "s".
Well the fix to that is to just ignore contractions, or have a separate contraction checker for words with an appostrophe in it, and have a check if the "word" (using term loosely here, to suggest characters separated by white space, or another punctuation character other than an apostrophe) begins and ends in an appostrophe, and if so then ignote it, as it is a quoted phrase.
I think a little logic workaround like that would work for the english language, but others, well lets just say 1 word on that 'Havok!'
- if quotation marks appear at the boundaries of words, ignore them.
- if quotation marks appear in the middle of a word, require that word to exist in the dictionary.
It's not sufficient to see if a single word is enclosed in quotation marks, because sometimes you have a quoted phrase that's longer than a word.
I find quite often that as I add somewhat unusual names to, say, OpenOffice's spell checker (e.g. Anscombe) it will not accept the possessive (e.g. Anscombe's) unless I add that too. However once I add Anscombe it will happily accept 'Anscombe', 'Anscombe, Anscombe' and so forth, so that I can use the name in a sentence or quoted sentence normally.
I think that this is a fairly safe rule, and much more preferable than simply throwing out contraction checking.
I got around it a bit by searching for the (Lua) regexp:
%a+'?%a+
That allows for a single imbedded quote. The disadvantage is that it won't match single-letter words. I suppose you could argue that single letter words are not exactly misspelt, so much as "noise" (oops, my finger hit the keyboard).
I mean, how many people say to themselves "I wonder how you spell the word 'I' (or 'A')"?
Also, in a MUD you might want words like N, S, E, W and so on.
There are other issues too. For example, the user dictionary.
Now, say there is a word the checker doesn't recognise, and you want it to (so you click "Add").
Currently the behaviour is to add it to the spell checker dictionary space, in the same way as existing words.
The significance of this is that it is also considered now as a "sound-alike" for other misspellings.
Here is an example. Say you type "ROFL" and you get a spell-check error. If you click "add" then "ROFL" is now in the dictionary. Now, if you type "ROFL" it is accepted, of course. But if you type "RFL" then one of the suggestions is now "ROFL" as that is now in the dictionary.
I'm not sure if that is a good thing or not. Possibly it is.
Auto-replacement
A feature that is not there at present is an "auto-replace" dictionary. Perhaps we could have a dictionary like this:
teh=the
attck=attack
If there was such a thing, then perhaps the spell checker can silently replace any words found, by the replacement.
Quote: Currently the behaviour is to add it to the spell checker dictionary space, in the same way as existing words.
Not entirely.. One thing that bugs the heck out of me is that most won't let you specify, in the cases of completely new worlds, what type of word it is. For example, you might want it to be smart enough to tell that 'ing' is a valid addon for 'frack', but not 'smurf' and more to the point, that 'smurf' is 's', not 'es' when plural, not to mention the simple fact that it is something that "should" be allowed to be plural. This always has bugged me about user dictionaries.
Then again, it could always be worse. They also started designing a non-proprietary spellchecker for the news reader I use, and somehow failed to add the, "No, I don't like any of those choices, but use this...", option. Nothing like mispelling a word, having the checker completely fail to find the "correct" spelling, then being stuck with "only" the wrong version or 10 unrelated choices, because the bloody spellchecker won't let you manually change the spelling to correct the mistake (or at least not in the dialog itself).
There are definitely some screwy problems with spellcheckers of all types, though the funiest has got to be the MS ones that are a) ignorant of MS product names and basic computer terms and b) missing other common, if 'maybe' slightly less used words. lol
For example, you might want it to be smart enough to tell that 'ing' is a valid addon for 'frack', but not 'smurf' ...
Well in my case you could just add the word "fracking" when required.
Quote:
"No, I don't like any of those choices, but use this...", option.
In my spellchecker you get around this by using "add" to add the word. Otherwise if you simply type a correction it rechecks it. For example, you type: "grp" and it gives an error. You correct it to "grup" and it still gives an error. You either Add grup to the dictionary, or keep going until you get the correct spelling (eg. "group").
Quote:
... though the funiest has got to be the MS ones ...
The thing I like about my spellchecker is that the dictionaries are under your control, and are human-readable. So, you can browse them and check that the words in them are what you expect.
Someone might like to make a "MUD dictionary" of common mudding terms and abbreviations (eg. LOL, ROFL etc.)
Quote: One thing that bugs the heck out of me is that most won't let you specify, in the cases of completely new worlds, what type of word it is. For example, you might want it to be smart enough to tell that 'ing' is a valid addon for 'frack', but not 'smurf' and more to the point, that 'smurf' is 's', not 'es' when plural, not to mention the simple fact that it is something that "should" be allowed to be plural. This always has bugged me about user dictionaries.
At this point you are no longer talking about a spell-checker, but about a linguistics model for the language. That's a whole different beast. Yes, it's annoying to have to add both the singular and plural forms of an unusual word, but I don't want the spell-checker playing guessing games about plurals, either. And if it's going to ask me, for every word I add, to define the word's linguistic properties, e.g. its plural form, that would probably be enough of a bother for me to want to just add the plural manually when I need to.
Nick, out of curiosity, are you using the tries in this new version? Or straight Lua tables?
I am using straight tables, because of my timings that showed, if I indexed by sound (thus getting thousands of tries) that there was no real space saving.
I have an experimental thesaurus going now. I found a open-source thesaurus file, and by reading that into a large Lua table, can look up synonyms, eg. for "garbage":
The thesaurus took 4 seconds to load, not too bad I suppose if you needed it badly enough.
Of course, for something like that, loading the whole thing into a database would probably be sensible, as it can just sit there until you need to look something up. Perhaps the same could be said for the spellchecker too, but that would get worked more heavily, it might be slow.
Yes, I need some sort of algorithm for "edit distance". Given a list of suggested words, it would be helpful to order them into the most likely ones first.
I also used the edit distance to omit words that were more than 4 away from the original, although you could change that number. That omits some of the more bizarre suggestions.
How does the new distance algorithm determine proximity? Looks like you're not using what is called 'edit distance', which is aka. Levenstein distance, I think. (It's where you add one point for a replacement, deletion or addition of letter.) That's the basic algorithm that the trie uses.
Quote: I am using straight tables, because of my timings that showed, if I indexed by sound (thus getting thousands of tries) that there was no real space saving.
Oh. The trie wasn't really supposed to be used by the thousands. Rather the idea was to have a single trie that contains a whole bunch of words. Admittedly this doesn't help you, unless the trie recursive walks incorporate whatever word distance algorithm you are using.
Also the original suggestion for the trie was for the auto-complete feature, for which all you really want is a compact way of representing a lot of words, which tries are (usually) pretty good at.
How does the new distance algorithm determine proximity? Looks like you're not using what is called 'edit distance', which is aka. Levenstein distance, I think.
Oh; well, you were getting results that looked pretty good, and in my experience, Levenshtein doesn't always give good results. :-)
As a note, the trie implements Levenshtein edit distance recursively, by using an intelligent walk of the tree, and so should be fairly fast. I'm not sure how you're getting the list of words, but you might want to compare speeds with the trie.
The first pass pulls out words that match the metaphone, the second pass effectively discards ones too far away in edit distance, then they are displayed in edit distance order.
Sorry to have questions on this old subject, but was this ever implemented? I'm horrid at spelling and if it could do some automatic changing for me, That would be GREAT!