|
������ ����������: ����� ���������.
������ �� ��������� ��������
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.
| |