compress.txt

来自「著名压缩算法的实现」· 文本 代码 · 共 1,091 行 · 第 1/4 页

	|                        |
  1 bit '1'                 1 bit '0'
+ 7 bits giving           + 7 bits giving
  the number (-2)           the number (-1)
  of repetitions            of non repetition
+ repeated byte           + n non repeated bytes
	|                        |
 1xxxxxxx,yyyyyyyy        0xxxxxxx,n bytes
[-----------------]      [----------------]

Example:

Sequence of bytes to encode | Coded values | Differences with compression
			    |              |         (unit: byte)
-------------------------------------------------------------------------
       255,15,              |  1,255,15,   |            -1
       255,255,             |    128,255,  |             0
	15,15,              |    128,15,   |             0
     255,255,255,           |   129,255,   |            +1
       15,15,15,            |    129,15,   |            +1
   255,255,255,255,         |   130,255,   |            +2
     15,15,15,15            |    130,15    |            +2

See codecs source codes: codrle1.c and dcodrle1.c

*** Second RLE scheme ***

In the second scheme of RLE compression you look for the less frequent byte
in the source to compress and use it as an header for all compressed block.

In the best cases, the occurrence of this byte is zero in the data to compress.

Two possible schemes, firstly with handling frames with only one byte,
secondly with handling frames with one byte *and* more. The first case is
the subject of this current compression scheme, the second is the subject
of next compression scheme.

For the frame of one byte, header byte is written in front of all repetition
with at least 4 bytes. It is then followed by the repetition number minus 1 and
the repeated byte.
Header byte, Occurrence number-1, repeated byte

If a byte don't repeat more than tree times, the three bytes are written without
changes in the destination stream (no header nor length, nor repetition in front
or after theses bytes).

An exception: If the header byte appears in the source one, two, three and up
times, it'll be respectively encoded as following:
- Header byte, 0
- Header byte, 1
- Header byte, 2
- Header byte, Occurrence number-1, Header byte

Example, let's take the previous example. A non frequent byte is zero-ASCII
because it never appears.

Sequence of bytes to encode | Coded values | Differences with compression
			    |              |         (unit: byte)
-------------------------------------------------------------------------
       255,15,              |    255,15,   |             0
       255,255,             |   255,255,   |             0
	15,15,              |     15,15,   |             0
     255,255,255,           | 255,255,255, |             0
       15,15,15,            |   15,15,15,  |             0
   255,255,255,255,         |   0,3,255,   |            -1
     15,15,15,15            |    0,3,15    |            -1

If the header would appear, we would see:

Sequence of bytes to encode | Coded values | Differences with compression
			    |              |         (unit: byte)
-------------------------------------------------------------------------
	  0,                |      0,0,    |            +1
	 255,               |      255,    |             0
	 0,0,               |      0,1,    |             0
	 15,                |      15,     |             0
	0,0,0,              |      0,2,    |            -1
	 255,               |      255,    |             0
       0,0,0,0              |     0,3,0    |            -1

See codecs source codes: codrle2.c and dcodrle2.c

*** Third RLE scheme ***

It's the same idea as the second scheme but we can encode frames with
more than one byte. So we have three cases:

- If it was the header byte, whatever is its occurrence, you encode it with:
Header byte,0,number of occurrence-1
- For frames which (repetition-1)*length>3, encode it as:
Header byte, Number of frame repetition-1, frame length-1,bytes of frame
- If no previous cases were detected, you write them as originally (no header,
nor length, nor repetition in front or after theses bytes).

Example based on the previous examples:

Sequence of bytes to encode |   Coded values   | Differences with compression
			    |                  |         (unit: byte)
-----------------------------------------------------------------------------
	   255,15,          |      255,15,     |             0
	   255,255,         |     255,255,     |             0
	    15,15,          |       15,15,     |             0
	 255,255,255,       |   255,255,255,   |             0
	   15,15,15,        |     15,15,15,    |             0
       255,255,255,255,     | 255,255,255,255, |             0
	 15,15,15,15,       |   15,15,15,15,   |             0
      16,17,18,16,17,18,    |16,17,18,16,17,18,|             0
     255,255,255,255,255,   |    0,4,0,255,    |            -1
       15,15,15,15,15,      |     0,4,0,15,    |            -1
 16,17,18,16,17,18,16,17,18,|  0,2,2,16,17,18, |            -3
  26,27,28,29,26,27,28,29   |0,1,3,26,27,28,29 |            -1

If the header (value 0) would be met, we would see:

Sequence of bytes to encode | Coded values  | Differences with compression
			    |               |         (unit: byte)
--------------------------------------------------------------------------
	  0,                |     0,0,0,    |            +2
	 255,               |      255,     |             0
	 0,0,               |     0,0,1,    |            +1
	  15,               |       15,     |             0
	0,0,0,              |     0,0,2,    |             0
	 255,               |      255,     |             0
       0,0,0,0              |     0,0,3     |            -1

See codecs source codes: codrle3.c and dcodrle3.c

*** Fourth RLE scheme ***

This last RLE algorithm better handles repetitions of any kind (one byte
and more) and non repetitions, including few non repetitions, and does not
read the source by twice as RLE type 3.

Compression scheme is:

		  First byte=Next byte?
			   /\
		      Yes /  \ No
			 /    \
		 1 bit '0'     1 bit '1'
		       /        \
		      /          \
       Count the                    Motif of several
       occurrences                  repeated  byte?
       of 1 repeated                ( 65 bytes repeated
       byte (maximum                257 times maxi)
       16449 times)                           /\
	    /\                               /  \
	   /  \                             /    \
	  /    \                           /      \
	 /      \                         /        \
  1 bit '0'       1 bit '1'        1 bit '0'          1 bit '1'
+ 6 bits        + 14 bits        + 6 bits of              |
giving the      giving the       the length      Number of non repetition
length (-2)     length (-66)     of the motif         (maximum 8224)
of the          of the           + 8 bits of               /\
repeated byte   repeated byte    the number (-2)     < 33 /  \ > 32
+ repeated byte + repeated byte  of repetition           /    \
    |                |           + bytes of the   1 bit '0'       1 bit '1'
    |                |           motif          + 5 bits of     + 13 bits
    |                |               |          the numer (-1)  of the
    |                |               |          of non          number (-33)
    |                |               |          repetition      of repetition
    |                |               |          + non           + non
    |                |               |          repeated        repeated
    |                |               |          bytes           bytes
    |                |               |             |               |
    |                |               |             |  111xxxxx,xxxxxxxx,n bytes
    |                |               |             | [-------------------------]
    |                |               |             |
    |                |               |      110xxxxx,n bytes
    |                |               |     [----------------]
    |                |               |
    |                |  10xxxxxx,yyyyyyyy,n bytes
    |                | [-------------------------]
    |                |
    |   01xxxxxx,xxxxxxxx,1 byte
    |  [------------------------]
    |
 00xxxxxx,1 byte
[---------------]

Example, same as previously:

Sequence of bytes to encode |         Coded values          | Differences with compression
			    |                               |         (unit: byte)
------------------------------------------------------------------------------------------
    255,15,255,255,15,15    |11000101b,255,15,255,255,15,15 |             +1
     255,255,255            |        00000001b,255,         |             -1
       15,15,15             |         00000001b,15,         |             -1
   255,255,255,255          |         00000010b,255,        |             -2
     15,15,15,15            |          00000010b,15,        |             -2
  16,17,18,16,17,18         |     10000001b,0,16,17,18,     |             -1
 255,255,255,255,255        |        00000011b,255,         |             -3
   15,15,15,15,15           |         00000011b,15,         |             -3
 16,17,18,16,17,18,16,17,18 |      10000001b,16,17,18,      |             -4
  26,27,28,29,26,27,28,29   |     10000010b,26,27,28,29     |             -2


+==========================================================+
|                   The Huffman encoding                   |
+==========================================================+

This method comes from the searcher who established the algorithm in 1952.
This method allows both a dynamic and static statistic schemes. A statistic
scheme works on the data occurrences. It is not as with RLE where you had
a consideration of the current occurrence of a frame but rather a consideration
of the global occurrences of each data in the input stream. In this last case,
frames can be any kinds of sequences you want. On the other hand, Huffman
static encoding appears in some compressers such as ARJ on PCs. This enforces
the encoder to consider every statistic as the same for all the data you have.
Of course, the results are not as good as if it were a dynamic encoding.
The static encoding is faster than the dynamic encoding but the dynamic encoding
will be adapted to the statistic of the bytes of the input stream and will
of course become more efficient by producing shortest output.

The main idea in Huffman encoding is to re-code every byte with regard to its
occurrence. The more frequent bytes in the data to compress will be encoded with
less than 8 bits and the others could need 8 bits see even more to be encoded.
You immediately see that the codes associated to the different bytes won't have
identical size. The Huffman method will actually require that the binary codes
have not a fixed size. We speak then about variable length codes.

The dynamical Huffman scheme needs the binary trees for the encoding. This
enables you to obtain the best codes, adapted to the source data.
The demonstration won't be given there. To help the neophyt, I will just explain
what is a binary tree.

A binary tree is special fashion to represent the data. A binary tree is
a structure with an associated value with two pointers. The term of binary has
been given because of the presence of two pointers. Because of some conventions,
one of the pointer is called left pointer and the second pointer is called right
pointer. Here is a visual representation of a binary tree.

     Value
      / \
     /   \
 Value    Value
  / \      / \
... ...  ... ...

One problem with a binary encoding is a prefix problem. A prefix is the first
part of the representation of a value, e.g. "h" and "he" are prefixes of "hello"
but not "el". To understand the problem, let's code the letters "A", "B", "C",
"D", and "E" respectively as 00b, 01b, 10b, 11b, and 100b. When you read
the binary sequence 00100100b, you are unable to say if this comes from "ACBA"
or "AEE". To avoid such situations, the codes must have a prefix property.
And the letter "E" mustn't begin with the sequence of an other code. With "A",
"B", "C", "D", and "E" respectively affected with 1b, 01b, 001b, 0001b, and
0000b, the sequence 1001011b will only be decoded as "ACBA".

 1      0
<-  /\  ->
   /  \
 "A"  /\
    "B" \
	/\
      "C" \
	  /\
       "D"  "E"

As you see, with this tree, an encoding will have the prefix property
if the bytes are at the end of each "branch" and you have no byte at the "node".
You also see that if you try to reach a character by the right pointer you add
a bit set to 0 and by the left pointer, you add a bit set to 1 to the current
code. The previous *bad* encoding provide the following bad tree:

       /\
      /  \
     /    \
    /\    /\
   /  \ "B" "A"
  /    \