I am trying to write a spellchecker, I have a huge wordlist (at least 500K, because of the nature of the language). The performance would suffer a lot if I got the lavenshtein distance of all of the words in the wordlist to the current word.

So I am trying to distribute the wordlist into buckets based on the characters in the word. This way, I only need to get the Levenshtein distance of the words in the specific bucket instead of the whole wordlist.

So I was wondering if there are any good Locality Sensitive hash algorithms for my problem? I have written a very simple algorithm that seems to work okay and the performance is at least 20X better. Although the accuracy suffers quite a bit.

Here is what I have come up with:

static string GetHash(string word)
{
    word = word.ToUpperInvariant();
    var lettersToTake = word.Length - (int)(word.Length * 0.70);

    var chars = word.GroupBy(c => c)
                    .OrderByDescending(c => c.Count())
                    .ThenBy(c => GetFrequency(c.Key))
                    .Take(lettersToTake)
                    .Select(g => g.Key)
                    .ToList();

    return new string(chars.ToArray());
}

Here are the steps of the algorithm:

  1. Capitalize all of the characters
  2. Order the characters in the word by the frequency of the letter in the word
  3. Then order the characters by the frequency of the word in the entire wordlist (GetFrequency)
  4. Take 30% of the characters in the word
  • 5
    It is ironic that you've mis-spelled "Levenshtein" by a single letter? – Eric Lippert Nov 27 at 19:00
  • 4
    Your intuition that a good hash will help is good. But there is a larger problem here. The best candidate for correcting a misspelling is not the word that is closest in edit distance. The best candidate is the word that the author most likely was trying to use, and that might be different. For example, adres should be corrected to address and not acres, even though acres has a shorter edit distance. – Eric Lippert Nov 27 at 19:11
  • 2
    See norvig.com/spell-correct.html for some thoughts on the design of this sort of program. – Eric Lippert Nov 27 at 19:16
  • @EricLippert hahaha it's a tricky word to spell. You are correct about what's the best candidate. However, I am trying to make a spell checker for a language that currently doesn't have any. So a simple spell checker is better than nothing. – Encrypt0r Nov 27 at 19:17
  • 1
    See stevehanov.ca/blog/index.php?id=114 for some thoughts on how to use a Trie to improve scalability. – Brian Nov 28 at 19:55

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.