5

I am using the levenshtein distance to recognize keywords despite typos, but i am wondering until which value the typo is still a typo or should be considered a different word. I am only comparing the input with certain keywords, so i dont need to use grammar or context at all.

For example, the words "cat" and "bat" have a levenshtein distance of 1, which could very well be a typo, but "cut" and "bat" have a distance of 2 and are probably not what the user wanted to say.

EDIT: At which point does the UX suffer from keywords being recognized despite the user not meaning to type them. For example the key word "service" might be recognized from "srrvice" or "Servce", but should not be recognized from "Servant", 3 typos is a bit much. But where do i draw the line? Is "Servufe" still expected to be recognized as "service" or would the user be rather disrupted by my application recognizing that.

I thought of maybe allowing 1 levenshtein "point" for every 4 or so letters the input consists of, because the longer a word the more typos could be done, but i'm not sure if thats a valid assessment.

I couldn't find anything on that topic in the net, so, how many typos should be allowed for a word to be recognized?

  • I'm not sure if this question wouldn't be better suited over on the English Language Stack Exchange or somewhere else but my instinct is that you would need to apply some grammar recognition to understand the context of the word to distinguish if the user was trying to say "I hit the ball with a bat" or "the cat was purring". Then you could vary the distance according to context. – Andrew Martin Aug 23 '18 at 8:22
  • It's actually about keywords being recognized. And i felt that spelling stuff wrong is more a user thing than a language thing. – WhiteMaple Aug 23 '18 at 8:24
  • I understand why this may seem like a UX issue but the UX issue is really "The system needs to be able to check spelling accurately" - everything else is about implementation of that spelling check. Maybe try over at datascience.stackexchange.com where they're more likely to have a data-handling related answer for you. – Andrew Martin Aug 23 '18 at 8:33
  • I quess my question wasn't specific enough, i'm gonna edit it a bit – WhiteMaple Aug 23 '18 at 8:37
  • Would it make sense to let the user search on a word that isn't one of your known keywords (i.e. is it a "free text" search, and the keywords list is just "to be helpful" for common terms, or is it more of a "tag" search where the keyword list a closed list of the only search terms that will give results)? – TripeHound Aug 23 '18 at 10:44
2

An edit distance of one or two will be sufficient for the great majority of user typos (...but there is a lot to be said about this subject)

Algorithm wise a typo is only a typo when the typed word does not correspond to any word in the local dictionary or does not fit the current grammar context. I believe your question is: "when should I do an autocorrection?" This is an active area of research in Natural Language Processing and does not have one obvious answer. There are good articles on the subject, for example this one. The author even proposes a first approach:

We’ll start by forming a rudimentary, but seemingly powerful spelling corrector. Here’s our algorithm.

  1. Check if the error word is valid English, if so return it, otherwise proceed.
  2. Find the word at 1 edit distance of the error word and that occurs most in the corpus and return it, if none can be found then proceed.
  3. Find the valid word within 2 edit distance of the error word and that occurs most in the corpus and return it, if none can be found then proceed.
  4. The spelling corrector has failed, return the error word.

We are making a couple of assumptions. First, we assume that if a word is in our corpus then it’s not an error. Next, we’re assuming that edit distance is the only factor affecting the error model. Finally, we assume that errors will only occur within 1 or 2 edit distance. This is not a bad assumption, as approximately 75% of errors are within 1 edit distance and nearly all of them are within 2 edit distance (based on training data of errors you’ll see later).

In this case the author considers every error above distance 2 a true error. In his second attempt he adds a probabilistic engine to improve its results (further improved in a third attempt). I won't transcribe his methodology here since its extensive but it's well worth reading.


Some general purpose commentary about this subject

You did not specify which type of UI or software you are trying to build. However common uses for string metrics are:

It's not the string metrics that disrupt, but the UI built to inform the user of an unknown word or context. This UI depends on objective. For example Command Line Completion (also known as Tab Completion) is an extremely useful use of a single key to loop through all compatible choices regarding what the user has already typed and all files inside the "current folder" (the typical "local dictionary" for a command line).

enter image description here

Word processors rely on far more complex dictionaries (see for example Hunspell) to correct words. They usually also have systems to let the user update the software with a new word (so that it does not cause an error next time it's used). See, for example, this wikipedia description about the use (or not) of a dictionary:

Traditional disambiguation works by referencing a dictionary of commonly used words, though Eatoni offers a dictionaryless disambiguation system.

In dictionary-based systems, as the user presses the number buttons, an algorithm searches the dictionary for a list of possible words that match the keypress combination, and offers up the most probable choice. The user can then confirm the selection and move on, or use a key to cycle through the possible combinations.

A non-dictionary system constructs words and other sequences of letters from the statistics of word parts. To attempt predictions of the intended result of keystrokes not yet entered, disambiguation may be combined with a word completion facility.

Either system (disambiguation or predictive) may include a user database, which can be further classified as a "learning" system when words or phrases are entered into the user database without direct user intervention. The user database is for storing words or phrases which are not well disambiguated by the pre-supplied database. Some disambiguation systems further attempt to correct spelling, format text or perform other automatic rewrites, with the risky effect of either enhancing or frustrating user efforts to enter text.

That being said I recommend that you build a list of probable choices (ranking them with Levenshtein distance) and only correct the word when it does not exist in the local dictionary. Provide an option to update the local dictionary with user words (see for example how Office Word does it, or Android long press).

Notice that dictionary learning capabilities do not have to be activated by a deliberate action of the user. Let me quote an interesting article on the subject:

In its most basic form, keyboard prediction uses text that you enter over time to build a custom, local "dictionary" of words and phrases that you've typed repeatedly. It then "scores" those words by the probability you'll use or need it again. For example, if you type in "lifehacker" and your keyboard has never seen you use it before, it'll offer to correct it to another phrase that it thinks is more likely (no, I don’t mean “lifejacket”). You have three options: You can accept one of their corrections, you can ignore the word and leave it as is, or you can add it to your personal dictionary so it won't bother you when you type it again.

If you accept a correction, obviously the keyboard will continue to assume the word is wrong, and offer corrections in the future. If you add it to your dictionary, the keyboard "learns" the word immediately, and will offer it up the next time you enter a spelling pattern that's close to those keys, or use similar words before and after the phrase but misspell "lifehacker." Things get interesting if you ignore the word—good predictive keyboards even use your lack of action to learn from your typing habits. The first or second time you ignore the word, it'll assume it's not a misspelling, but not a word you use often enough to be presented with in similar usage patterns. If you ignore it a third or fourth time (how many times depends on the specific keyboard), your keyboard will mark it as a future probable choice, and start presenting you with it when you type similar words or sentences.

  • While i'm not trying to autocorrect an input, but rather check an already sent input for keywords, this answer still fulfills the question, suggesting one or two edits as the only valid number of corrections. It should answer most of the later users finding this question, accepted! – WhiteMaple Oct 23 '18 at 6:12
  • 1
    Also, i'm gonna change the title, yours is much more fitting. – WhiteMaple Oct 23 '18 at 6:13
0

Not a direct answer for you but I hope this insight helps.

I would consider looking at the layout of a keyboard, for each character there are a possible number of errors, or typos, that can be made based on the surrounding keys. Typo's generally occur when a user accidentally presses a surrounding key, otherwise, it's a spelling mistake.

Giving the user a few options to choose from (like mobile phones) can eliminate incorrect suggestions by the system as you may come across anomalies. For example, I wanted to type cheese but I make a typo and type chesse. Does the system auto-correct to this to chess or to cheese? This helps where the system fails to understand the context of the sentence.

  • Good answer, but my question wasn't specific enough. My application is planned to be used multilingual, so there will be different keyboard layouts and such. I am only wondering how far i should go with letting typos pass without disturbing the user. – WhiteMaple Aug 23 '18 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.