Data Compression

[Jerome Kaidor <jerryk@best.com>]

Hello,

   A week or so ago, somebody on this list was talkign about needing fast
data compression - I think, in regard to the FAA flight data CD-ROM. 
Comment was made that Gzip was too slow, and faster results were obtained
with a compression library.

   A few years ago, I had need of a very fast compressor to integrate into a
networking application.  I rolled my own.  The idea was simple:  I took
an industry standard compression algorithm - in my case, it was dynamically
modelled dictionary compression a-la gzip ( but without gzip's second step
of Huffman-encoding the output ).  I then transformed the algorithm into a
state machine, which allowed it to work on incoming data while the packets
were coming in.

   When you use a compressor like gzip, you tell it:

  "Here is a file, or data area for you to compress.  Here's where it
starts, here's how long it is.  Put the compressed version over there.  Come
back when you're through."

   Whereas with my compressor, you'd say:

   "I want you to start creating some compressed data for me."
             ( compressor returns a 'handle' for use in subsequent calls )
   "Here's a kilobyte"
   "Here's five hundred thirty  three more bytes"
   "Here's another byte"
   "Here's another hundred bytes"
             .
             .
             .   
   "OK, there's no more bytes.  Finish it up!"

   This approach has two main advantages:  first, you never have to store
the complete uncompressed file anywhere!  Each packet ( or sector, or
read()) can be compressed as it comes in.  Which can save your computer
from going into swap.  Second, the time spent compressing is partially
( or maybe wholly ) subsumed into the I/O time.  In other words, the
computer can be compressing while the network is networking, or the disk
is disking :-).

   I'm sure similar things are done by MNP5 modems.

                      - Jerry Kaidor ( jerry@tr2.com )
-
Archives of linux-aviation: http://mail.nl.linux.org/lists/linux-aviation/
To unsubscribe: send the command "unsubscribe linux-aviation" in the body
of a mail message to <Majordomo@mail.nl.linux.org>.