---
tags: materials
---
# Збільшення ентропії
* Як працює ZIP-бомба?
* Чому архівація архіву файлу не зменшує файл?
* Для чого потрібні бінарні дерева в програмуванні?
В цих задачах потрібно буде розібратись, як працює **lossless компресія даних**.
Екстра плюс, якщо будуть також написані unit-тести до алгоритмів!
([illustration by Daniel Hertzberg](http://danielhertzberg.blogspot.com/2011/11/softmart-claude-shannon.html))
## Біт стрінги
Мабуть, найперша задача з теорії інформації, це перетворити список байт у список біт.
```
b'ABCDE\x03' -> '010000010100001001000011010001000100010100000011'
```
:::info
**Завдання**
Перетворити рядок байт у рядок біт (по кодуванню ASCII). Не забути, що один байт перетворюється у 8 біт (не менше!).
:::
І схожа задача, перетворити рядок біт у рядок байт:
```
'01101111011011010010110101101110011011110110110100101101011011100110111101101101' -> b'om-nom-nom'
```
:::info
**Завдання**
Перетворити рядок біт у рядок байт.
:::
Тепер, коли ви легко перетворюється біти <-> байти, можна приступити до більш адаптивного перетворення.
В біт-рядку закодовано символи. Є розділювачі, і є символи. Закодовані вони таким чином:
1. Читаємо наступний біт:
- якщо 0, то це біт розділювач, йдемо в пункт 1
- якщо 1, то це кінцевий біт розділювач, ми закінчили читати розділювачі, і наступні 8 біт це і буде наш символ
- після прочитання символу зберігаємо його у список
2. Коли біти закінчились, то це кінець програми
Наприклад, біт рядок:
```
'001010101001010100100101000101000101000001'
```
перетвориться у
```
b'TREA'
```
Якщо розділювачі писати бітами, то виглядатиме так:
```
b'001T1R01E0001A'
```
:::info
**Завдання**
Написати декодер бітового рядка у символьний
:::
## Біт дерева
Бінарне дерево --- це деревовидна структура даних, де у кожної ноди є рівно дві гілки. Наприклад,
```python=
# приклад дерева в Python
example_tree = ( (1, 2), (3, 4) )
```
є бінарним деревом, з трьома нодами (парами дужок) і чотирма листочками (кінцевими нодами). В цьому випадку, інформація кодується числами в листочках.
Потрібно закодувати дерево у біт рядок.
```python=
def encode_tree(tree):
...
return '10011101...'
```
Для цього треба використати обхід дерева, де спочатку ми кодуємо ліву гілку, потім праву. Якщо нода, яку ми кодуємо, не листова, то записуємо її як `0`, якщо листова --- то записуємо як `1` та дописуємо число з листочка як 8 біт.
Тобто, дерево вище перетвориться у рядок `001\x01 1\x02 01\x03 1\x04` (звісно, пробіли я поставив щоб зручніше читалось, насправді їх бути не повинно) (а також це записано у форматі біт-розділювачів з попереднього завдання).
Інший приклад, дерево
```python=
another_tree = ( ( (b'A', b'B'), b'C'), (b'D', b'E') )
```
буде закодовано як (без пробілів, звісно)
```
0001A 1B 1C 01D 1E
```
або у повному форматі:
```
0001010000011010000101010000110101000100101000101
```
:::info
**Завдання**
Написати енкодер дерева з байтами-листочками у біт рядок.
:::
Можливо ви помітили, що формат кодування з попереднього завдання дуже схожий на формат цього дерева. Саме так! Це один і той же формат.
:::info
**Завдання**
Написати декодер дерева з біт рядка.
:::
## Частотний аналіз
{%youtube gG62zay3kck %}
Нехай дано блок довжиною 410 байт:
```python
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`. Видно, що у другому випадку ентропія більша, а отже кодування в такому словнику буде більш ефективним.
:::info
**Завдання**
Потрібно написати функцію, яка отримує на вхід блок даних, і для нього рахує, при якому фіксованому розмірі символа ми отримуємо максимальну ентропію. Повернути на вихід ентропію, розмір символа та таблицю частот.
:::
Тепер, коли відома ентропія символів, можна приблизно оцінити, скільки потрібно біт на кодування оригінального блоку. Формула --- кількість символів у повідомленні помножити на ентропію:
```
NbitsX1 = H(X1) * len(data) = 3.53 * 410 = 1447.3 біт
NbitsX2 = H(X2) * len(data)/2 = 5.0 * 410/2 = 1025 біт
```
У випадку `NbitsX2` ми ділимо на 2, бо нам потрібно 205 двобайтних символів для кодування оригінального блоку.
:::warning
Власне "як саме" буде відбуватись це кодування ми розглянемо трохи пізніше. Там все не зовсім просто, формула вище вірна тільки в ідеальних випадках.
:::
:::info
**Завдання**
Визначити, для якого розміру символа кількість біт для кодування блоку буде мінімальною.
:::
Але, окрім біт на кодування, нам потрібно закодувати саму таблицю. В подальшому, для кодування цієї таблиці буде потрібно **2 біти** на кожен елемент таблиці + сума довжин всіх ключів таблиці **у байтах**.
Наприклад, в таблиці `X1` є 24 ключа по одному байту кожний, тобто, **2 біти** * 24 + 24 **байти** = 240 **біт** = 30 **байт**.
В таблиці `X2` є 65 ключів по два байти кожний, тобто, **2 біти** * 65 + 65 * 2 **байти** = 1170 **біт** = 147 **байт**.
:::warning
Деталі кодування таблиці також розглянемо окремо пізніше. Там все також не просто :)
:::
:::info
**Завдання**
Враховуючи, що закодований блок = кодування таблиці символів + кодування блоку, визначити, при якій довжині символа довжина закодованого блоку буде мінімальна. Відношення довжини закодованого блоку до оригінальної довжини і буде коефіцієнтом компресії.
:::
## Декодування 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 байт.
:::warning
Це RLE кодування --- це спрощена версія формату LZ4, найшвидшого методу декомпресії.
:::
:::info
**Завдання**
Написати декодер 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
```
В такому випадку, різні символи кодуються різними довжинами біт рядків. І, що головне, при декодування символів не буде двозначностей!
:::info
**Завдання**
Маючи бінарне дерево, отримати таблицю біт-кодувань для кожного листового символа дерева.
:::
Чудово, тепер маючи набір символів виду `DAADDBDADDD` можна буде перетворити його у набір біт `1 000 000 1 1 001 1 000 1 1 1` (пробіли розставлені тільки для зручності читання). Але як його декодувати назад?
Щоб декодувати цей біт рядок назад, потрібно читати один біт, і
- якщо це біт 0, то дивитись на ліву гілку дерева
- якщо це біт 1, то дивитись на праву гілку дерева
Якщо ми потрапляємо на лист дерева, то BINGO! Ми знайшли наш символ, можна додавати його до результату і починати зчитування наступного символу.
А якщо потрапляємо на ноду дерева, то читаємо наступний біт, і так поки не дійдемо до листка.
:::info
**Завдання**
Зробити зчитування наступного символа з біт рядка, використовуючи бінарне дерево для декодування.
:::
Тепер, коли всі ці алгоритми реалізовано, цікаво яке ж дерево потрібно вибрати для кодування конкретного повідомлення. І тут якраз потрібен нам алгоритм Хафмана.
Дерево будується так:
1. Отримуємо частотну таблицю для всіх символів
2. Сортуємо таблицю по частоті зустрічання символів
3. Беремо два найменш частих елементів цієї таблиці, робимо з них ноду (один елемент --- ліва гілка, інший --- права гілка), і замінюємо ті символи в таблиці на ноду. Частота цієї ноди буде сумою частот елементів
4. Переходимо в пункт 2 і продовжуємо доки дерево не побудується повністю.
Як приклад, можна взяти [дерево з Вікіпедії](https://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding#Huffman_coding).
- на першому кроці елементи D та E об'єднуються в одну ноду, тому-що це найрідкісніші елементи в таблиці. Частота цієї ноди установлюється як сума D та E
- на другому кроці об'єднуються уже B та C, тому-що тепер саме вони найрідкісніші елементи.
- на третьому кроці об'єднуються ноди з попередніх пунктів, бо кожна з них не дотягує до частоти елементу A.
- на четвертому кроці дерево замикається.
:::info
**Завдання**
Маючи таблицю частот символів, побудувати відповідне бінарне дерево Хафмана.
:::
## Кодування RLE
:::danger
TODO
:::
## Формат
:::danger
TODO
:::
Sign in with Wallet
Connect another wallet