title: Compression Algorithm for Encoding Word Lists
body: <p>I'm am looking for specific suggestions or references to an algorithm and/or data structures for encoding a list of words into what would effectively would turn out to be a spell checking dictionary. The objectives of this scheme would result in a very high compression ratio of the raw word list into the encoded form. The only output requirement I have on the encoded dictionary is that any proposed target word can be tested for existence against the original word list in a relatively efficient manner. For example, the application might want to check 10,000 words against a 100,000 word dictionary. It is <strong><em>not</em></strong> a requirement for the encoded dictionary form to be able to be [easily] converted back into the original word list form - a binary yes/no result is all that is needed for each word tested against the resulting dictionary.</p>
  
  <p>I am assuming the encoding scheme, to improve compression ratio, would take advantage of known structures in a given language such as singular and plural forms, possessive forms, contractions, etc. I am specifically interested in encoding mainly English words, but to be clear, the scheme must be able to encode any and all ASCII text "words".</p>
  
  <p>The particular application I have in mind you can assume is for embedded devices where non-volatile storage space is at a premium and the dictionary would be a randomly accessible read-only memory area.</p>
  
  <p><strong><em>EDIT</em></strong>: To sum up the requirements of the dictionary:</p>
  
  <ul>
  <li>zero false positives</li>
  <li>zero false negatives</li>
  <li>very high compression ratio</li>
  <li>no need for decompression</li>
  </ul>