Лабораторная работа: Сжатие данных по алгоритму Хаффмана
Цель
Освоить принципы алгоритмов сжатия данных в телекоммуникационных протоколах.
Теория
Сжимая файл по алгоритму Хаффмана, первое, что мы должны сделать - это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ. После подсчета частоты вхождения каждого символа, необходимо упорядочить таблицу символов в порядке убывания частоты вхождения.
Допустим, мы имеем файл длиной в 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, и отсортируем полученные узлы вновь в порядке убывания:
Частота0
Символа C B E A D F
| |
|--|--|
||-|
|15| = 5 + 10
|--|
Номер в рамке - сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения, исключая из просмотра символы D и A, и рассматривая вместо них новый "узел" с суммарной частотой вхождения. Самая низкая частота теперь у F и нового "узла". Снова сделаем операцию слияния узлов:
Частота0
Символа C E B A D F
| | |
| | |
| |--|| |
|-|15|| |
||-| |
| |
| |--| |
|----|25|-| = 10 + 15
|--|
и сортируем таблицу в порядке убывания частот ( в нашем примере положим, что Е следует после составного символа (ADF) с частотой 25, хотя можно сделать и наоборот):
Частота0
Символа C A D F E B
| | |
| | |
| |--|| |
|-|15|| |
||-| |
| |
| |--| |
|----|25|-| = 10 + 15
|--|
Рассматриваем таблицу снова для следующих двух символов (B и E). Объединяем их в составной символ с частотой 45.
Частота5
Символа C A D F B E
| | | | |
| | | | |
| |--|| | | |
|-|15|| | | |
||-| | | |
| | | |
| |--| | | |--| |
|----|25|-| |-|45|-|
|--| |--|
Сортируем таблицу в порядке убывания частот:
Частота0
Символа B E C A D F
| | | | |
| | | | |
| | | |--|| |
| | |-|15|| |
| | ||-| |
| | | |
| |--| | | |--| |
|-|45|-| |----|25|-|
|--| |--|
Мы продолжаем в этот режим пока все "дерево" не сформировано, т. е. пока все не сведется к одному узлу (Root).
Частота5
Символа C A D F B E
| | | | | |
| | | | | |
| | |--|| | | |
| |-|15|| | | |
| ||-| | | |
| | | | |
| | |--| | | |--| |
| |----|25|-| |-|45|-|
| ||-| ||-|
| |--| | |
|----|55|------| |
|-|| |
| |-| |
|---| Root (100) |----|
|-|
Теперь, когда наше дерево создано, мы можем кодировать файл. Мы должны всегда начинать из корня (Root). Кодируя первый символ (лист дерева – С), мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 (и запомним 0), затем снова влево (0) к самому символу. Код Хаффмана для нашего символа C - 00. Для следующего символа ( А ) у нас получается - лево, право, лево, лево, что дает последовательность 0100. Выполнив выше сказанное для всех символов, получим:
C =бита )
A = 0бита )
D = 0бита )
F = бита )
B =бита )
E =бита )
Коды Хаффмана сопоставляют наиболее часто встречающимся символам коды наименьшей длины. Кроме того, коды Хаффмана являются префиксными, то есть код никакого символа не является началом кода какого-либо другого символа, что позволяет однозначно восстановить закодированную последовательность символов из потока битов кода при наличии таблицы кодов.
Примечание.
Существуют альтернативные алгоритмы получения кодов Хаффмана.
Требования
В данной лабораторной работе необходимо закодировать указанную символьную последовательность по алгоритму Хаффмана. Работа выполняется в письменном или электронном виде с приведением:
1) таблицы распределения частот символов
2) конечного и всех промежуточных деревьев
3) таблицы кодов Хаффмана для символов входной последовательности
4) представление символьной последовательности в кодах Хаффмана
Вариант | Последовательность |
1 | abracadabraerebraabra |
2 | barbaradaraberabara |
3 | fereperegerafaberepe |
4 | gerapergeaferapobera |
5 | ronoponoponuporobop |
6 | mopogonoponoponogo |
7 | igerabegeraoperagigero |
8 | hubramubragubragabra |
9 | lumalagalapumalamaga |
10 | parampapambaramlalam |
11 | brupruhrububupuruhh |
12 | ludegoberomodegobelu |
13 | hhhjdalllkdjhfssskld |
14 | qnemrbrennmqmenbrqmwe |
15 | fiopgpofogiihofpgoihio |
16 | tztuyxuyctzxucyzxctyz |
17 | kaskdjdaijjjdjdkasks |
18 | uuiwiwoowowoiweuquuq |
19 | nmnnnsndiidiidsisall |
20 | jjjfdisisdijjjsjsiia |
