Збільшення ентропії

• Як працює ZIP-бомба?
• Чому архівація архіву файлу не зменшує файл?
• Для чого потрібні бінарні дерева в програмуванні?

В цих задачах потрібно буде розібратись, як працює lossless компресія даних.

Екстра плюс, якщо будуть також написані unit-тести до алгоритмів!

(illustration by Daniel Hertzberg)

Біт стрінги

Мабуть, найперша задача з теорії інформації, це перетворити список байт у список біт.

b'ABCDE\x03' -> '010000010100001001000011010001000100010100000011'

Завдання

Перетворити рядок байт у рядок біт (по кодуванню ASCII). Не забути, що один байт перетворюється у 8 біт (не менше!).

І схожа задача, перетворити рядок біт у рядок байт:

'01101111011011010010110101101110011011110110110100101101011011100110111101101101' -> b'om-nom-nom'

Завдання

Перетворити рядок біт у рядок байт.

Тепер, коли ви легко перетворюється біти <-> байти, можна приступити до більш адаптивного перетворення.

В біт-рядку закодовано символи. Є розділювачі, і є символи. Закодовані вони таким чином:

1. Читаємо наступний біт:
   • якщо 0, то це біт розділювач, йдемо в пункт 1
   • якщо 1, то це кінцевий біт розділювач, ми закінчили читати розділювачі, і наступні 8 біт це і буде наш символ
   • після прочитання символу зберігаємо його у список
2. Коли біти закінчились, то це кінець програми

Наприклад, біт рядок:

'001010101001010100100101000101000101000001'

перетвориться у

b'TREA'

Якщо розділювачі писати бітами, то виглядатиме так:

b'001T1R01E0001A'

Завдання

Написати декодер бітового рядка у символьний

Біт дерева

Бінарне дерево –- це деревовидна структура даних, де у кожної ноди є рівно дві гілки. Наприклад,

# приклад дерева в Python
example_tree = ( (1, 2), (3, 4) )

є бінарним деревом, з трьома нодами (парами дужок) і чотирма листочками (кінцевими нодами). В цьому випадку, інформація кодується числами в листочках.

Потрібно закодувати дерево у біт рядок.

def encode_tree(tree):
    ...
    return '10011101...'

Для цього треба використати обхід дерева, де спочатку ми кодуємо ліву гілку, потім праву. Якщо нода, яку ми кодуємо, не листова, то записуємо її як 0, якщо листова –- то записуємо як 1 та дописуємо число з листочка як 8 біт.

Тобто, дерево вище перетвориться у рядок 001\x01 1\x02 01\x03 1\x04 (звісно, пробіли я поставив щоб зручніше читалось, насправді їх бути не повинно) (а також це записано у форматі біт-розділювачів з попереднього завдання).

Інший приклад, дерево

another_tree = ( ( (b'A', b'B'),  b'C'), (b'D', b'E') )

буде закодовано як (без пробілів, звісно)

0001A 1B 1C 01D 1E

або у повному форматі:

0001010000011010000101010000110101000100101000101

Завдання

Написати енкодер дерева з байтами-листочками у біт рядок.

Можливо ви помітили, що формат кодування з попереднього завдання дуже схожий на формат цього дерева. Саме так! Це один і той же формат.

Завдання

Написати декодер дерева з біт рядка.

Частотний аналіз

Нехай дано блок довжиною 410 байт:

data = b"""\
Nach dem stutzen des Rhabarberbarbarabarbarbarenbarts
geht der Rhabarberbarbarabarbarbarenbartbarbier
meist mit den Rhabarberbarbarabarbarbaren
in die Rhabarberbarbarabarbarbarenbartbarbierbierbar
zu Rhabarberbarbarabarbarbarenbartbarbierbierbarbarbel
um sie mit zur Rhabarberbarbarabar zu nehmen
um mit etwas Rhabarberbarbarabarbarbarenbartbarbierbier
von Rhabarberbarbaras herrlichem
Rhabarberkuchen zu essen\
"""

Видно, що багато тексту повторюється. Це означає, що ентропія блоку низька (кількість інформації на символ маленька), а отже, можна спробувати зменшити розмір блоку за рахунок збільшення ентропії (збільшити кількість інформації на символ).

Для цього потрібно побудувати спеціальний словник, і цю таблицю потрібно буде передавати разом з повідомленням.

Якщо вважати що 1 символ == 1 ASCII символ, то можна порахувати, який символ як часто зустрічається:

r: 76
a: 75
b: 73
e: 40
 : 25
h: 15
i: 15
...

І, відповідно, можна порахувати частоту зустрічання кожної букви, просто поділивши на кількість символів (таблиця X1):

r: 18.5%
a: 18.3%
b: 17.8%
e: 9.8%
 : 6.1%
h: 3.7%
i: 3.7%
...

Але якщо вибирати в якості "символа" не 1 байт, а кілька то можна побудувати іншу таблицю (таблиця X2):

ba: 13.7%
ar: 13.7%
rb: 11.7%
er: 5.4%
ab: 3.9%
en: 2.9%
 R: 2.4%
...

Для того, щоб порівняти ці дві таблиці символів, потрібно порахувати ентропію. Ентропія рахується як сума добутків ймовірностей кожного символа в таблиці на їх двійкові логарифми (зі знаком мінус):

Наприклад, для першого випадку ми отримаємо:

H(X1) = -(0.185*(-2.432) + 0.183*(-2.451) + 0.178*(-2.49) + 
      + 0.098*(-3.358) + 0.061*(-4.036) + ...) = 3.53

А для другого –- H(X2) = 5.0. Видно, що у другому випадку ентропія більша, а отже кодування в такому словнику буде більш ефективним.

Завдання

Потрібно написати функцію, яка отримує на вхід блок даних, і для нього рахує, при якому фіксованому розмірі символа ми отримуємо максимальну ентропію. Повернути на вихід ентропію, розмір символа та таблицю частот.

Тепер, коли відома ентропія символів, можна приблизно оцінити, скільки потрібно біт на кодування оригінального блоку. Формула –- кількість символів у повідомленні помножити на ентропію:

NbitsX1 = H(X1) * len(data) = 3.53 * 410 = 1447.3 біт
NbitsX2 = H(X2) * len(data)/2 = 5.0 * 410/2 = 1025 біт

У випадку NbitsX2 ми ділимо на 2, бо нам потрібно 205 двобайтних символів для кодування оригінального блоку.

Власне "як саме" буде відбуватись це кодування ми розглянемо трохи пізніше. Там все не зовсім просто, формула вище вірна тільки в ідеальних випадках.

Завдання

Визначити, для якого розміру символа кількість біт для кодування блоку буде мінімальною.

Але, окрім біт на кодування, нам потрібно закодувати саму таблицю. В подальшому, для кодування цієї таблиці буде потрібно 2 біти на кожен елемент таблиці + сума довжин всіх ключів таблиці у байтах.

Наприклад, в таблиці X1 є 24 ключа по одному байту кожний, тобто, 2 біти * 24 + 24 байти = 240 біт = 30 байт.

В таблиці X2 є 65 ключів по два байти кожний, тобто, 2 біти * 65 + 65 * 2 байти = 1170 біт = 147 байт.

Деталі кодування таблиці також розглянемо окремо пізніше. Там все також не просто :)

Завдання

Враховуючи, що закодований блок = кодування таблиці символів + кодування блоку, визначити, при якій довжині символа довжина закодованого блоку буде мінімальна. Відношення довжини закодованого блоку до оригінальної довжини і буде коефіцієнтом компресії.

Декодування RLE

RLE (run-length encoding) –- це спеціальний метод представлення даних. Фактично, це узагальнення ідеї, що повтори символів ми можемо представити меншими зусиллями. Наприклад, рядок

aaaaaaaabbbbbbbbbbbb

можна представити як

8a12b

Але це якось просто, тому я опишу більш складний RLE. Вам потрібно буде зробити декомпресію послідовності RLE блоків.

Отже, формат блоку RLE виглядає так (одна буква –- один байт):

   L X ______________________ F
          довжина L байт

• L –- довжина літералу. Літерал –- це нестиснені дані, які копіюються при декомпресії без змін. Літерал починається після другого байту блоку і має довжину L байт. Може бути нулем, це означає що літералу в блоці немає взагалі
• X –- це число означає, яка довжина послідовності, яка має повторитись. Початок послідовності для повторення дивись у F. Якщо 0, це означає немає повтору
• F –- кількість байт, оффсет (зсув) назад, з якого починається повтор послідовності. Цей оффсет рахується не відносно блоку, а відносно результату декомпресії

Мабуть, найкраще пояснити як це все працює, буде на прикладах.

1. b'\x05\x00HELLO' –- L=5, X=0, значить читаємо 5 байт і копіюємо їх на вихід. Оскільки X=0, то жодних копіювань по оффсету. Результат: HELLO
2. b'\x05\x00HELLO\x01\x04 \x06' –- тут два блоки, перший такий же як в прикладі вище, другий \x01\x04 \x06.
   L=1, X=4. Це означає, що потрібно 1 байт (L=1) скопіювати на вихід, отже у нас виходить проміжний результат HELLO (в кінці пробіл), а потім считуємо F=6. Якщо відкатити індекс на 6 назад, то ми будемо бачити букву H, а довжина X=4 означає що треба взяти 4 символа, тобто, HELL. І це треба додати назад до результату, щоб вийшло HELLO HELL.
3. Цей приклад розіб'ю на кілька рядків (рядок на блок), але реально вони мають йти підряд:
   ​​​​\x08\x03Rhabarber\x06
   ​​​​\x00\x03\x03
   ​​​​\x00\x06\x06
   ​​​​\x0A\x00barenbarts
   

   • після 1-го блоку у нас результат Rhabarberbar
   • після 2-го блоку у нас результат Rhabarberbarbar
   • після 3-го блоку у нас результат Rhabarberbarbarbarbar
   • після 4-го блоку у нас результат Rhabarberbarbarbarbarbarenbarts
     Результат має довжину 31 байт, а RLE блоки сумарно мають довжину 30 байт.

Це RLE кодування –- це спрощена версія формату LZ4, найшвидшого методу декомпресії.

Завдання

Написати декодер RLE.

Дерево Хафмана

Основна ідея ентропійного кодування –- це ті символи, які зустрічаються частіше, закодувати меншою кількістю біт, а ті символи, які зустрічаються рідше –- більшою кількістю біт.

Девід Хафман, будучи студентом, випадково знайшов оптимальний спосіб визначення, які саме повинні бути ці кодування.

Його алгоритм в загальному виглядає так:

1. Побудувати бінарне дерево, де листочками будуть символи.
2. При обході дерева ліва нода кодується як 0, а права як 1
3. Шлях до символа і буде його бінарним кодом.

Пункт 1 тут ключовий, але спершу розглянемо наступні пункти.

Наприклад, у дерева ( (1, 2), (3, 4) ) будуть такі відповідності символів до біт рядків:

\x01  ->  00
\x02  ->  01
\x03  ->  10
\x04  ->  11

Не дивно, що всі символи мають однакову довжину, бо всі вони знаходяться на одному рівні в дереві. Але як щодо такого дерева: ( ( (b'A', b'B'), b'C'), b'D' )?

A   ->  000
B   ->  001
C   ->  01
D   ->  1

В такому випадку, різні символи кодуються різними довжинами біт рядків. І, що головне, при декодування символів не буде двозначностей!

Завдання

Маючи бінарне дерево, отримати таблицю біт-кодувань для кожного листового символа дерева.

Чудово, тепер маючи набір символів виду DAADDBDADDD можна буде перетворити його у набір біт 1 000 000 1 1 001 1 000 1 1 1 (пробіли розставлені тільки для зручності читання). Але як його декодувати назад?

Щоб декодувати цей біт рядок назад, потрібно читати один біт, і

• якщо це біт 0, то дивитись на ліву гілку дерева
• якщо це біт 1, то дивитись на праву гілку дерева

Якщо ми потрапляємо на лист дерева, то BINGO! Ми знайшли наш символ, можна додавати його до результату і починати зчитування наступного символу.

А якщо потрапляємо на ноду дерева, то читаємо наступний біт, і так поки не дійдемо до листка.

Завдання

Зробити зчитування наступного символа з біт рядка, використовуючи бінарне дерево для декодування.

Тепер, коли всі ці алгоритми реалізовано, цікаво яке ж дерево потрібно вибрати для кодування конкретного повідомлення. І тут якраз потрібен нам алгоритм Хафмана.

Дерево будується так:

1. Отримуємо частотну таблицю для всіх символів
2. Сортуємо таблицю по частоті зустрічання символів
3. Беремо два найменш частих елементів цієї таблиці, робимо з них ноду (один елемент –- ліва гілка, інший –- права гілка), і замінюємо ті символи в таблиці на ноду. Частота цієї ноди буде сумою частот елементів
4. Переходимо в пункт 2 і продовжуємо доки дерево не побудується повністю.

Як приклад, можна взяти дерево з Вікіпедії.

• на першому кроці елементи D та E об'єднуються в одну ноду, тому-що це найрідкісніші елементи в таблиці. Частота цієї ноди установлюється як сума D та E
• на другому кроці об'єднуються уже B та C, тому-що тепер саме вони найрідкісніші елементи.
• на третьому кроці об'єднуються ноди з попередніх пунктів, бо кожна з них не дотягує до частоти елементу A.
• на четвертому кроці дерево замикається.

Завдання

Маючи таблицю частот символів, побудувати відповідне бінарне дерево Хафмана.

Кодування RLE

TODO

Формат

TODO