����� �� �����.


������ ���������.

������ ����������: ����� ���������.

������ �� ��������� ��������

 Huffman - ������� ������� ��� �������� ����� �������  �������� �� 
��������� ���  ���������  ������������������� ��� ���������� ������� ������
�����  �����������  �������. ��  �������  �� �������� ���� ������� ���������
����������  ������  �  ������  �������� �������� ( Huffman ). ������� �� ���
����� ������� �� ���������� ������ � �������������� ����� �� ������.
      ������  ����  �� ��������� �������� ������ ��� �� ������ ������� - ���
����������  ���������  ����  ���������  � ���������� ������� ��� �����������
������  ������  ��  ������������  ������  ASCII. ���� �� ����� ��������� ���
256 ��������, ��  ���  ��� �� ����� ������� � ������ ���������� � EXE �����.

     ����  ��������  �������  ���������  
������� �������, ���������� �����������
�������  �����  ASCII  �  ������������  ������  ����������  �����  ������ ��
��������. ��  ����  ��  �����  ���������������  ������� ������� �� ������� �
������  �������������  �������  ������  �� ��� �� ��������. ������ ������ ��
��������� ������� ������� "�����".  � ���������� ( � ������ ) �� ����� �����
���������  ���������  �������  �����  ���������  �� ���� "����". ��� �������
������� ���������� ������:
      ��  �����  ����  �������  �  100 ���� � ������� 6 ��������� �������� �
���� . ��  ����������  ���������  �������  ��  ��������  �  ����  � ��������
��������� :
        |-----------------|-----|-----|-----|-----|-----|-----|
        |     c�����      |  A  |  B  |  C  |  D  |  E  |  F  |
        |-----------------|-----|-----|-----|-----|-----|-----|
        | ����� ��������� |  10 |  20 |  30 |  5  |  25 |  10 |
        |-----------------|-----|-----|-----|-----|-----|-----|
     ������  ��  �����  ���  �����  � ����� �������� �� �������� ���������
��� ������� �������. ��������� ������� ��� ����.
        |-----------------|-----|-----|-----|-----|-----|-----|
        |     c�����      |  C  |  E  |  B  |  F  |  A  |  D  |
        |-----------------|-----|-----|-----|-----|-----|-----|
        | ����� ��������� |  30 |  25 |  20 |  10 |  10 |  5  |
        |-----------------|-----|-----|-----|-----|-----|-----|
     �� ������� �� ��������� �������  ������� � ���������� ��������. � �����
������  ���  D (5) � ����� ���� ������ �� F ��� A (10), ����� ����� ����� ��
��� �������� A.
    ���������� �� "�����" D � A ����� "����", ������� ��������� ��� ��������
����� ����� ����� ������ D � A :

   �������         30    10     5     10     20     25
   �������          C     A     D      F      B      E
                          |     |
                          |--|--|
                            ||-|
                            |15|  = 5 + 10
                            |--|
     �����  �  ����� - ����� ������ �������� D � A. ������ �� ����� ���� ���
������� � ������  ������� ��������� ���������. �������� �� ��������� D � A �
������������  ������  ��� ����� "����" � ��������� �������� ���������. �����
������  �������  ������  � F � ������ "����". ����� ������� �������� �������
����� :

   �������         30    10     5     10     20     25
   �������          C     A     D      F      B      E
                          |     |      |
                          |     |      |
                          | |--||      |
                          |-|15||      |
                            ||-|       |
                             |         |
                             |    |--| |
                             |----|25|-| = 10 + 15
                                  |--|
     ������������� ������� ����� ��� ��������� ���� �������� ( B � E ).
�� ���������� � ���� ����� ���� ��� "������" �� ������������, �.�. ���� ���
�� �������� � ������ ����.

   �������         30    10     5     10     20     25
   �������          C     A     D      F      B      E
                    |     |     |      |      |      |
                    |     |     |      |      |      |
                    |     | |--||      |      |      |
                    |     |-|15||      |      |      |
                    |       ||-|       |      |      |
                    |        |         |      |      |
                    |        |    |--| |      | |--| |
                    |        |----|25|-|      |-|45|-|
                    |             ||-|          ||-|
                    |    |--|      |             |
                    |----|55|------|             |
                         |-||                    |
                           |   |------------|    |
                           |---| Root (100) |----|
                               |------------|

     ������ ����� ���� ������ �������, �� ����� ���������� ���� . �� ������
������ ���������  �� ����� ( Root ) . ������� ������ ������ (���� ������ �)
�� ������������  ����� �� ������ ��� �������� ������ � ���� �� ������ �����
�������, �� ���������� 0-� ���, � ���������� 1-� ���  ��� ������� ��������.
��� ��� C, �� ����� ���� ����� � 55 ( � �������� 0 ), ����� ����� ����� (0)
� ������  ������� . ���  �������� ��� ������ ������� C - 00. ��� ����������
������� ( � )  �  ���  ���������� - ����,�����,����,���� , ��� ���������� �
������������������ 0100. ��������  ���� ��������� ��� ���� �������� �������

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

     ������ ������ ���������� ������������� 8-� ������ ( ���� ���� ), � ���
��� �� ��������� ����� ����� ����������� ��� ������������� ������� �������,
�� �������������  ���������  ������  ���������  ����� . ������  �����������
��������� ������� :
       |----------|----------------|-------------------|--------------|
       | �������  |  ������������� |  ����������� ���� | ��������� �� |
       |----------|----------------|-------------------|--------------|
       |  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%.

    ���  ��� �������� ������, �� ������������ ��������� � ��� �����, ��� ���
�������������� ��������������� �����, ��  ������  ����� ������������ ������,
��� ��� ������� ����� �������� ��� ������ ������ .  ������������� ��  ������
���������  ������  ������  �  ������ . ��� ������������ � ����� � ����������
�������� ��������� ����� .
    �  �����  ��������  ������  �  ������  ���� ��������� 4 ����� ���������,
�� �����, ������ ������� ��� 256 ���� ����� �������������� 1 �����  �������.
.
    ������� � �����  �������  �����  5 ����� ���� 6 ������ ( ��� � ���������
����  �������  ) , ����� 11 . 4  �����  11  ��� - 44 . ���� �� ������� �����
���������  ����������  ������  ���  ���������� ����� ���� � ��������� ������
���������� - ����  �������  ����� �������������� 50 ������ ������.
    �������  �  30 ������ ������ ����������, 50 ������ ������� ��������, ���
�����  ������   ���������   �����   ��������  ��  80  ���� .  �������� , ���
��������������  ������  �����  �  ��������������� ������� ���� 100 ���� - ��
�������� 20% ������ ����������.
    �� ����� . ��  ���  ��  ������������� ��������� - ���������� �����������
ASCII  ������  �  ���  �����  �����  ���������  ������� ���������� ������ ��
��������� � �����������.
    ��� �� ����� �������� �� ���� ���� ?
    ����������  ��������  ������  ��  ����� �������� ��� ��������� ���������
��������� � ����������� ������, ������� �������� ��������������.
    �� ������� ��� ����� ����� ������ :
                 4 - 2 ��������� ����;
                 8 - 3 ��������� �����;
                16 - 4 ��������� �����;
                32 - 5 ��������� �����;
                64 - 6 ��������� �����;
               128 - 7 ��������� �����;

     ���������� ��� ��� 8 ��������� ����.
                 4 - 2 ��������� ����;
                 8 - 3 ��������� �����;
                16 - 4 ��������� �����;
                32 - 5 ��������� �����;
                64 - 6 ��������� �����;
               128 - 7 ��������� �����;
             --------
               254

     ����  ��  �����  ����  ��   256  ���������  ����������  ��������  �����
����������  ���� .  ��  ����  ����������  ����  2  ��  ������ ����� 8 �����.
����  ��  ������  �����  ����� �������  ��� ������������, �� � ����� �������
1554 ��� ��� 195 ������. ���  � ��������� , �� ����� 256 ���� � 195 ��� 33%,
�����  �������  �����������  ���������������� Huffman ����� ��������� ������
� 33% ����� ������������ �� ������ ����� .
     ���  ���  ��������  ������������� ��� �� ���������� ����� �������� �.�.
�����, �������  ������ ���������������� ����������. �������� ��� A - 01011 �
��� B - 0101 . ���� �� ����� �������� ��� ���� �������, �� ������� ���� 0101
��  ��  ������ ������� ����� ��� �� �������� A ��� B , ��� ��� ��������� ���
�����  ����  ���  �������  ����������  ����, ��� � ������������ �����������.
     ����������  ��������,  ���  ������ � ���������� ���������� ����� ������
�������  ��������  ������  �  ���� ����������� ����������� ���������� ������
�  �����������  ������ ,  �����  �������� ,  ���  ���  ����������  ����  ���
����������.
     ����  ���������  ���������� - ��������  �������� ������� ������ �������
����  ������ , ����  ���  ������  �������  ���������  �������� , ������  ���
��������� ��������������� �����������.


� ����� - ���������� �� ������e.





����� �� ��������, � ���������� � ���������.

SpyLOG