Архівація файлів та створення архіватора текстових файлів (стр. 2 из 2)

Давайте розглянемо ще один приклад файлу, власне дерево якого має вигляд більш складний, ніж в попередньому випадку.

Буває так, що частоти окремих символів однакові або майже однакові, це призводить до того, що такі символи кодуються одним і тим же числом біт. Однак алгоритм побудови дерева від цього незмінюєтся:

ddddddaaaaaabbbbbbccccdffffffffffdddd{37 byte, end of file}

В двійковому вигляді файл буде мати вигляд такий:

01100100 01100100 01100100 01100100 01100100 01100100 01100001 01100001 01100001 01100001 01100001 01100001 01100010 01100010 01100010 01100010 01100010 01100010 01100011 01100011 01100011 01100011 01100100 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100100 01100100 01100100 01100100{296 bit, end of file}

Розпишемо частоти кожного з символів:

a - 6

b - 6

c - 4

d - 11

f - 10

Весь файл займає 37 байт. Кожен з символів в початковому файлі кодується згідно таблиці ASCII вісьмома бітами. Поглянемо, як будуть кодуватись ці символи в стиснутому файлі. Для цього побудуємо відповідне дерево (не забуваємо сортувати отриманий набір):

1. {(d,11), (f,10), (a,6), (b,6), (c,4)};

2. {(d,11), (f,10), (вершина #1, 10), (a,6)} (зауважте, що сортування по спаданню частот є обов'язковим!);

3. {(вершина #2, 16), (d,11), (f,10)};

4. {(вершина #3, 21), (вершина #2, 16)};

5. {(вершина #4, 37)}

Аналізуючи отримане дерево, розпишемо, як буде кодуватися кожен з символів після стиснення:

a - "11"

b - "100"

c - "101"

d - "00"

f - "01".

В двійковому вигляді файл буде мати такий вигляд:

00000000 00001111 11111111 10010010 01001001 00101101 10110100 01010101 01010101 01010000 0000хххх{88 bit, end of file}

Стиснутий файл зайняв 11 байт (останні чотири біта хххх записуються будь-які, тому що весь файл насправді вміщується в 84 біта, що не кратно восьми). Коефіцієнт стиснення при такому кодуванні дорівнює 3,5.

Список використаних джерел

1) Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. Диалог-МИФИ, 2003 г. 384 стр.

2) Сэломон Д. Сжатие данных, изображений и звука: Перевод с английского. Техносфера. 2004г.

Додатки

Малюнок №1:

Малюнок №2: