Programming - about archiving - algorithms that produce lossless compression.

__________________________________________

(C) N.B.
__________________________________________

       A little about methods
  data packaging.

   Only algorithms considered here
producing lossless compression, i.e. admitted
searching for the restoration of the original information
tions "byte to byte".

 Running -  This is the simplest of the methods
            packaging information. Presumably
assume that you have a line of text, and finally
This line is worth 40 spaces. There is a clear
redundancy of available information. Problem
The method of compressing this string is solved very simply
then - these 40 spaces ( 40 bytes) are compressed
in 3 bytes by packing them using the method
repeating characters (running). First
byte standing instead of 40 spaces in the compressed
line,in fact, it will be a test
scrap (the sequence was made up of spaces).
The second byte is a special "flag" byte.
which indicates that we should deploy
remove the previous byte in the line in sequence
efficiency when restoring a string. Tre-
this byte is the account byte (in our case it is
will be 40). As you can see for yourself,
just so that any time we have
sequence of more than 3 identical ones
characters, replace them with the procedure described above
research in order to obtain at the output
block of information is smaller in size, but up to
enabling information recovery using
running condition.
   Keeping everything said above true,
I will only add that in this method the main
The new problem is the choice of the one
th byte of the “flag”, since in real blocks
which information is typically used
all 256 byte options, and there is no possibility
have the 257th option - “checkbox”. On the first
this problem seems insoluble,
but there is a key to it that you will find,
after reading about coding with an algorithm
Huffman.

 LZW -  The history of this algorithm begins -
         since publication in May 1977.
J. Ziv (J. Ziv) and A. Lempel (A. Lem-
pel) articles in the journal "Information technology
rii" called "IEEE Trans".Lastly
Subsequently, this algorithm was modifiedTerry A.
Terry A. Welchand finally
version is reflected in the article "IEEE Compute" in
June 1984. This article described the sub-
details of the algorithm and some general tests
problems that may be encountered when
implementation. Later this algorithm received
name - LZW (Lempel - Ziv - Welch).
Algorithm LZW is an algorithm
the rhythm of encoding sequences is neo-
identical characters. Let's take, for example,
line "The TSortedCollection object is generated
from TCollection.". Analyzing this line, we
we can see that the word "Collection" rev-
is repeated twice. This word contains 10 characters
- 80 bit. And if we can replace this
word in the output file, in the second it will be included -
If you look at the link to the first inclusion, then
We obtain information compression. If we consider
create an input block of information of size not
more than 64K and limit the length of the encoding
my string is 256 characters, then given
byte "flag", we get that a string of 80 bit
replaced by 8+16+8 = 32 bits. Algorithm LZW
as if it “learns” during the process of file compression
la. If there are duplicate lines in
file, then they will be encoded in a table
tsu. The obvious advantage of the algorithm is
It turns out that there is no need to include
encoding table into a compressed file. Other
an important feature is that the compression
The algorithm LZW is a one-pass
operation as opposed to algorithmic
mu Huffman, which requires
two passes.

 Huffman - Firstit seems like creation
           smaller file from the used
running without sequence encoding
or byte repeat exceptions will be impossible
possible task. But let's force our se-
I would like to make some mental efforts and
understand the Huffman algorithm.Pot-
With not much time, we will gain
knowledge and additional disk space.
   Compressing the file using the Huffman algorithm
everything we have to do is necessary
I can read the entire file and calculate it,
how many times does each character appear?
superset ASCII. If we will
take into account all 256 characters, then for us it is not
there will be a difference in the compression of text or
another file.
   After calculating the frequency of occurrence of each
before the symbol, you need to look at the table
face ASCII codes, and generate an imaginary
arrangement between codes in descending order. That is,
without changing the location of each character
from a table in memory, sort the table
links to them in descending order. Every link
from the last table we will call it a “node”.  B
further (in the tree) we will later expand
place signs that will indicate
to this "node". For clarity, let's break down
look at an example:

   We have a file of length 100 bytes and have
6 differentsymbols in themselves. We are under
counted the occurrence of each character in
file and got the following:

 |-----------------|-----|-----|-----|-----|-----|-----|
 |     symbol |  A |  B |  C |  D |  E |  F |
 |-----------------|-----|-----|-----|-----|-----|-----|
 | number of occurrences |  10 |  20 |  30 |  5 |  25 |  10 |
 |-----------------|-----|-----|-----|-----|-----|-----|

   Now we take these numbers and we will call
list them by frequency of occurrence for each
symbol. Let's place the table as below.

 ----------------- ---- ---- ---- ---- ---- -----
 symbol C E B F A D
 ----------------- ---- ---- ---- ---- ---- -----
 number of occurrences 30 25 20 10 10 5
 ----------------- ---- ---- ---- ---- ---- -----

   We will take the characters from the last table
withlowest frequency. In our case, this is
D (5) and any character fromF or A (10),
you can take any of them, for example A.
 Let's form from nodes D and A a new "node",
the frequency of occurrence for which will be equal to
sum of frequenciesDandA :

Frequency 30 10 5 10 20 25
Character C A D F B E

 -- --
 -
 15 = 5 + 10
 --

   The number in the frame is the sum of the symbol frequencies D
and A. Now we are again looking for two characters with
the lowest frequencies of occurrence. Exclude-
tea from viewing D and A  and looking
instead of them, a new “node” with a total frequency
that occurrence. Lowest frequency now
at F and a new "node". Let's do the operation again
node merging:

Frequency 30 10 5 10 20 25
Character C A D F B E


 ?--
 - 15
 -

 ?--
 ---- 25 - = 10 + 15
 --

   Consider the table again for the following:
two characters ( B and E ). We continue
this mode until the entire “tree” is formed
vano, i.e. until it all comes down to one thing
node.

Frequency 30 10 5 10 20 25
Character C A D F B E


 ?--
 - 15
 -

 ?-- ?-- -
 ---- 25 - - 45 -
 - -
?--
 ---- 55 ------
 -
 ------------
 --- Root (100) ---
 ------------

   Now that our tree is created, we
can encode the file. We must always
start from the root ( Root ). Coding first
symbol (tree leaf С), we trace
up the tree all the turns of the branches, and,
if we make a left turn, we remember
0th bit, and similarly 1st bit for the right
turn. So for C, we will go left to
55 (and remember 0), then left again (0)
to the symbol itself. Huffman code for our
symbol C - 00. For the next character (A)
we get -left, right, left, left,
which results in the sequence 0100.
Doing the above for all characters
we get:

           C = 00 (2 bits)
 A = 0100 (4 bits)
 D = 0101 (4 bits)
 F = 011 (3 bits)
 B = 10 (2 bits)
 E = 11 (2 bits)

   Each character was originally represented
8 bits (one byte), etc. we reduce
sewed the number of bits needed to represent
of each symbol, we therefore
reduced the size of the output file. Compression
works out as follows:

 ---------- ---------------- ------------------- --------------
The frequency of the originally compressed bits is reduced by
 ---------- ---------------- ------------------- --------------
 C 30 30 x 8 = 240 30 x 2 = 60      180     
  A 10      10 x 8 =  80      10 x 3 = 30           50     
  D 5        5 x 8 =  40       5 x 4 = 20           20       F 10      10 x 8 =  80      10 x 4 = 40           40     
  B 20      20 x 8 = 160      20 x 2 = 40          120     
  E 25      25 x 8 = 200      25 x 2 = 50          150     
-----------------------------------------------------------

   Первоначальный размер файла: 100 байт -
800 бит;
   Размер сжатого файла:30 байт - 240 бит;

   240 - 30% из 800, так что мы сжали этот
файл на 70%.

   Все это довольно хорошо,но неприятность
находится в том факте,что для восстановле-
ния первоначальногоfile we must have
decoding tree, since trees will
are different for different files. Therefore,
we must save the tree along with the file
scrap This eventually turns into an increase
output file sizes.
   In our compression technique and each node
there are 4 bytes of pointer, so complete
a table for 256 bytes will be approximately
1 KB length.

   The table in our example has 5 nodes
plus 6 peaks (where our symbolic
ly), a total of 11. 4 bytes 11 times - 44. If
we will add after a small amount of buy-
com to save node space and some
other statistics - our table will be used -
approximately 50 bytes of length.
   By adding to 30 bytes of compressed information
50  bytes of the table - we get that the total
the length of the archive file will increase to 80 bytes.
Considering that the original file length is
the example under consideration was 100 bytes - we
received 20% information compression.
   Not bad. What we really are
plumper - broadcastcharacter ASCII on-
boron into our new set, which requires less
number of characters compared to standard
nom.
   What can we gain along the way?
   Let's consider the maximum we can
get for various bit combinations -
tions in the optimal tree, which is
asymmetrical.
   We get that we can only have:
 4 - 2 digit codes;
 8 - 3 digit codes;
 16 - 4-bit codes;
 32 - 5 digit codes;
 64 - 6-bit codes;
 128 - 7-bit codes;

   Two more 8-bit codes are required.

 4 - 2 digit codes;
 8 - 3 digit codes;
 16 - 4-bit codes;
 32 - 5 digit codes;
 64 - 6-bit codes;
 128 - 7-bit codes;
 --------
 254

   So, we have a total of 256 different
combinations that can be used to encode a byte.
Of these combinations, only 2 are equal in length
8 bits.
   If we add up the number of bits that this
represent, then in the end we get 1554 bit
or 195 bytes. So, at the maximum, we squeezed
256 bytes to 195 or 33%, thus max.
the most idealized Huffman can
achieve compression of 33%, when used
at the byte level.
   All these calculations were made for not
prefix codes Huffman, i.e. codes, which
which cannot be identified unambiguously.
For example, code A - 01011 and code B - 0101. Ec-
will we receive these codes bit by bit, then
having received bits 0101, we will not be able to tell
what code we received - A or B, because next
the next bit can be the beginning of the next bit
general code, and a continuation of the previous one.
   It must be added that the key to post-
The formation of prefix codes is served by the usual bi-
narny tree, and, if you carefully consider-
Take the previous example with building a tree
va, you can make sure that all the obtained co-
Yes there are prefixes.
   And the last note - the Hough algorithm
fman requires reading the input file twice,
counting the frequencies of symbols once
and another time, producing, directly,
coding.

P.S. About the “key” that gives way to the algorithm
     Running. After reading the overview information
     about Huffman coding, think about
     because on our binary tree we can
     maybe 257 leaves.
------------------------------------------