home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 15 / CDACTUAL15.iso / cdactual / program / basic / QB_RLE.ZIP / RLE.DOC < prev   
Encoding:
Text File  |  1991-03-07  |  4.1 KB  |  72 lines
  1. I've seen quite a few messages in this text compression thread but for
  2. some reason I missed the original message.  I have a couple of simple
  3. RLE routines to pass along which can be very effective in certain
  4. rather limited circumstances.  I've seen mention of a bit packing
  5. scheme that you seem to be considering for compression purposes.  You
  6. should check out the books PROGRAMMING PEARLS and MORE PROGRAMMING
  7. PEARLS by Jon Bently.  One of these books contains a discussion of bit
  8. packing, and both contain a great many ideas worth thinking about.
  9.  
  10.    Program Name    RLE.BAS
  11.    Author          Kenneth G. White
  12.    Date            9/3/90
  13.    Language        QuickBasic 4.x / PDS 7.x
  14.    Purpose         RLE Data Compression Functions
  15.  
  16.    I recently had a chance to write a couple of Run Length Encoding
  17.    data compression functions, and I thought they might be of use or
  18.    amusement to someone else.  This compression method is among the
  19.    most simple, and works by reducing redundant character sequences to
  20.    a single character code and a character count code.  As a result,
  21.    any file with a large number of repeating characters can be reduced
  22.    in size by a meaningful amount.  The downside is that you must
  23.    uncompress your data before use, and, if there are no repeating
  24.    character sequences, the output file could be double the size of
  25.    the input file.  This makes your compression utility into an
  26.    expansion utility.  Fun, but not very useful.
  27.  
  28.    The functions in RLE.BAS are not designed to be a general purpose
  29.    compression tool, so keep your current utilities at the ready.
  30.    There are however, situations that come up in programming where
  31.    some amount of data compression could be useful.  Character based
  32.    screen displays and other forms of text loaded separately into a
  33.    program come to mind as possible candidates for this type of
  34.    compression.  The main limiting factor in using compressed data
  35.    within a program is the speed with which it can be uncompressed.
  36.    I've tried to make these routines as fast as possible within the
  37.    limits of Basic.
  38.  
  39.    The functions are designed to deal with character codes 0-255 as
  40.    input which makes them very flexible but slows them down a bit.
  41.    This increased flexibility can also carry a high price in terms of
  42.    compressed output size.  A compression marker is used to signal the
  43.    start of a code/count sequence in the compressed output, and this
  44.    code requires special handling if it is allowed in the input
  45.    stream.  Encoding an input stream in which every other character is
  46.    a compression marker will cause the output size to be double the
  47.    input size.  A file which contains no compression markers, or which
  48.    has sequences of three or more compression markers at a time, has a
  49.    worst case output size equal to the input size.  In certain cases,
  50.    changing the compression marker code can have a very large effect
  51.    on the output size.  Additionally, if you are sure that the input
  52.    data will never include this marker character, then the special
  53.    processing code used to deal with this possibility can be removed.
  54.    Allowing the entire character set as input seemed to be a fair
  55.    trade-off in terms of flexibility, but this is just a personal
  56.    preference on my part.
  57.  
  58.    I tried these functions on various text files which contained
  59.    formatted  documents ,BBS messages, text screens, and random
  60.    character sequences.  The compression varied between 8% and 65%,
  61.    with the best compression coming from ascii text screens and
  62.    formatted documents.   I would think somewhere between 10% and 20%
  63.    might be about the best you could hope for in most ascii files.
  64.    Interestingly, while BBS message files and the like, were
  65.    compressed in the neighborhood or 10-15%, a text file containing NL
  66.    player stats was reduced in size by 51%.  Formatted program screens
  67.    consisting of standard text and border characters can generally be
  68.    compressed by as much as 65% in my tests.   This seems to the most
  69.    practical area for application of these functions.
  70.  
  71.  
  72.