home *** CD-ROM | disk | FTP | other *** search
/ Boot Disc 8 / boot-disc-1997-04.iso / PDA_Soft / Pilot / Apps / WordList.02 / readme.txt < prev    next >
Text File  |  1997-02-05  |  2KB  |  45 lines
  1.  
  2. This program allows you to search a highly compressed list of words.
  3. It can be used for looking up spellings and cheating at various word
  4. games.  Currently searches are specified by a substring (with '?' as a
  5. wildcard character) and/or a length.
  6.  
  7. I have encoded three dictionaries for this program.  The raw material
  8. came from ftp sites listed in the rec.puzzles.crosswords FAQ.
  9.  
  10. dictionary    words    raw size  .pdb size  ratio
  11. ----------   -------  ---------  ---------  -----
  12.  pocket       21,111    176,662    45,130    3.9
  13.   ospd        79,339    614,670   100,561    6.1
  14.  unabrd      235,544  2,492,342   516,428    4.8
  15.  
  16. Compression is performed in two steps.  First the beginning of each
  17. word is stripped off and replaced by a count of how many characters to
  18. copy from the beginning of the previous word.  Then the file is
  19. compressed using context-sensitive huffman codes (different codes are
  20. used depending on the previous character.)
  21.  
  22. To evaluate the performance of the context-sensitive huffman codes, I
  23. compressed the prefix-stripped ospd file using several other methods.
  24.  
  25.  program   size     comments
  26. --------  ------   ---------
  27.   ha      78253    PPM (arithmetic coding, variable length context)
  28.  bzip     79607    Burroughs-Wheeler
  29.  gzip     97409    LZ77 program, same algorithm as pkzip
  30.  lzo     132179    LZ77 library, used flags -m972 -b10000
  31.  
  32.  
  33. PPM and Burroughs-Wheeler aren't suitable for the Pilot because they
  34. need a lot of working memory. The lzo library by Markus Franz Xaver
  35. Johannes Oberhumer is attractive because it uses no memory and is very
  36. fast, but the compression isn't as good as the context-sensitive
  37. huffman codes that I used.  It seems to me that if you are going to
  38. start trading compression away for speed, then you should go all the
  39. way to the data structures described in the article below.  Searches
  40. could be hundreds of times faster while the dictionary would be less
  41. than twice as big.
  42.  
  43. Andrew Appel and Guy Jacobsen, "The World's Fastest Scrabble Program",
  44. Communications of the ACM, May 1988.
  45.