At 9:20 AM +1000 2/9/00, Stephen Best wrote:
>As you've observed, the first is to discard unused space by storing all
>strings as zero delimited or pascal strings (length byte first) and packing
>them together. The second is to compress each string itself. You could use
>something like Huffman encoding (see any book on data compression) but this
>may not be fast enough if you want to sort/search the records.
As Joe Fitzpatrick pointed out, it's generally a good idea _not_ to compress your
"keys". This includes anything displayed in a list or table and anything used for
searching or sorting. I think people overestimate the cost of Huffman decoding. It can
be written quite efficiently using tables. Flytrap uses Huffman, along with several
other techniques, to compress music. It decompresses as it plays and still has plenty
of CPU left over for other things (including sleeping :).
My biggest concern is implementing an efficient Find through compressed data. We
didn't have to do this for Flytrap and didn't get around to doing it for BeamBooks.
The obvious approach is to decompress into a buffer and then search the buffer, but
this can be quite slow. If you make a special version of the decompression routine
that includes the search, it can be quite fast. Another approach is to compress words.
Then you can compress the pattern string and search for that. The case of the word
would have to be stored in a different place since the search should be case
insensitive. The compression level won't be nearly as good.
If anyone is interested in the details, I'd be happy to discuss it off the list.
-
Danny Epstein - Applied Thought
No Palm is an Island - try BeamBooks
http://www.appliedthought.com/beambooks
--
For information on using the Palm Developer Forums, or to unsubscribe, please see
http://www.palm.com/devzone/mailinglists.html
