What algorithm gives suggestions in a spell checker?

by

There is good essay by Peter Norvig how to implement a spelling corrector. It’s basicly a brute force approach trying candidate strings with a given edit distance. (Here are some tips how you can improve the spelling corrector performance using a Bloom Filter and faster candidate hashing.)

The requirements for a spell checker are weaker. You have only to find out that a word is not in the dictionary. You can use a Bloom Filter to build a spell checker which consumes less memory. An ancient versions is decribed in Programming Pearls by Jon Bentley using 64kb for an english dictionary.

A BK-Tree is an alternative approach. A nice article is here.

Levenshstein distance is not exactly the right edit distance for a spell checker. It knows only insertion, deletion and substitution. Transposition is missing and produces 2 for a transposition of 1 character (it’s 1 delete and 1 insertion). Damerau–Levenshtein distance is the right edit distance.

More Related Contents:

  1. Getting the closest string match
  2. How can I pair socks from a pile efficiently?
  3. Unique (non-repeating) random numbers in O(1)?
  4. Converting a Uniform Distribution to a Normal Distribution
  5. Can hash tables really be O(1)?
  6. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  7. How do you detect Credit card type based on number?
  8. What distribution do you get from this broken random shuffle?
  9. Is there an O(n) integer sorting algorithm?
  10. Determine font color based on background color
  11. Nearest neighbors in high-dimensional data?
  12. How can I measure the similarity between two images? [closed]
  13. How to efficiently build a tree from a flat structure?
  14. Need help in mod 1000000007 questions
  15. Sum-subset with a fixed subset size
  16. What is a good Hash Function?
  17. Algorithm to generate a crossword [closed]
  18. Binary Search in Array
  19. Calculate largest inscribed rectangle in a rotated rectangle
  20. The Sieve of Atkin
  21. How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?
  22. How best to sum up lots of floating point numbers?
  23. 3 dimensional bin packing algorithms
  24. Find 2 numbers in an unsorted array equal to a given sum
  25. Algorithm to find the most common substrings in a string
  26. Optimizing Conway’s ‘Game of Life’
  27. “Rounding” colour values to the nearest of a small set of colours
  28. Convert light frequency to RGB?
  29. Best way to find a point on a circle closest to a given point
  30. Postfix notation to expression tree

Leave a Comment