home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2563 < prev    next >
Encoding:
Internet Message Format  |  1992-09-02  |  2.9 KB
  1. Path: sparky!uunet!news.claremont.edu!lexcel!mtinews!mti!adrian
  2. From: adrian@mti.mti.com (Adrian McCarthy)
  3. Newsgroups: comp.programming
  4. Subject: Re: Spell checking routine
  5. Message-ID: <709@mtinews.mti.com>
  6. Date: 2 Sep 92 23:08:24 GMT
  7. References: <la5rkvINN9vr@aludra.usc.edu>
  8. Sender: news@mtinews.mti.com
  9. Organization: Micro Technology, Inc., Anaheim, CA
  10. Lines: 46
  11. Nntp-Posting-Host: mti
  12.  
  13. In article <la5rkvINN9vr@aludra.usc.edu> joseph@aludra.usc.edu (Jeff Lawson) writes:
  14. >I need a routine that will suggest words for a mispelled word from a
  15. >large dictionary.  I'd like something that could produce words with
  16. >totally different spellings, like WordPerfect's.  It doesn't really
  17. >matter what code it's written in, but C is preferable.  Thanks
  18.  
  19. One of my favorite techniques that I use in my toy spell checker is to use
  20. multiple hash indexes into the dictionary.  Each has index is generated with
  21. a different type of hash function.  The main hash function is the usual sort,
  22. designed for efficient lookup.
  23.  
  24. The additional hash functions are designed to cause words that are alike
  25. in some way to collide.  Thus, once you look up the incorrect word,
  26. you don't have to do any more work to guess at correct spellings; a list
  27. of guesses is already computed and stored as the collision list.  Precomputing
  28. the index when the dictionary is built means that guessing is blindingly fast.
  29.  
  30. For example, a hash function based on a Soundex-type of algorithm will
  31. automatically give you a list of words which sound like the word you tried to
  32. look up (within the limits of the Soundex algorithm).
  33.  
  34. I have another hash function which maps characters to the finger a touch typist
  35. would use.  This quickly finds mistakes where you used the right finger, but
  36. missed the key you aimed at.
  37.  
  38. Yet another hash function is bitmask of characters, so words that are anagrams
  39. of each other map to the same index.  This is very useful for quickly solving
  40. word-jumble puzzles or making a program to play Scrabble.  (It's also not too
  41. bad at finding transposed characters, but it tends to find a lot of other words
  42. as well.)
  43.  
  44. This technique has worked pretty well for me.  I've found it's quicker to
  45. try to sort a precomputed list of guesses based on similarity to the original
  46. word than to work the other direction.  Of course, there is a big space
  47. trade-off because the hash indexes may be large for a big dictionary.
  48.  
  49. Using the more traditional approach of generating guesses, it's pretty
  50. straightforward to transpose adjacent characters, delete characters, and
  51. substitute characters.  To quickly make reasonable guesses for inserting
  52. characters, compute the frequency of all of the trigraphs (3-letter
  53. combinations) in your dictionary.  Build a sparse 2-d table indexed by the
  54. first and last letter whose values are a sorted list of the most common
  55. interceding letters.  (If memory requirements are very limiting, you could
  56. try a simpler but similar approach using digraphs instead of trigraphs.)
  57.  
  58. Aid.  (adrian@lexcel.com)
  59.