Databases
StackOverflow2013
Postsdbo
POCompression Algorithm for Encoding Word Lists
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POCompression Algorithm for Encoding Word Lists
    primarykey
    data
    text
    <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>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USTall Jeff
    1. USTall Jeff
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POCompression Algorithm for Encoding Word Lists
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POCompression Algorithm for Encoding Word Lists
      1. USfrankodwyer
      1. VTFavorite
    3. VO
      singulars
      1. POCompression Algorithm for Encoding Word Lists
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload