Kompresia je proces zníženia počtu bitov potrebných na reprezentáciu dát.
Dekompresia je proces uvedenia dát do pôvodného stavu.
Kompresia zmenší množstvo dát potrebných na uloženie alebo prenos.
AAAAAAAAAABBBBBBCCCCCCCC
Obsahuje veľa opakovaní, preto sa dá dobre komprimovať.
Q7mK2pL9xR4aT8zW
Náhodné dáta sa komprimujú oveľa horšie.
Viac: Kompresia dát
Stratová a bezstratová
Vynechanie nepodstatných častí. Nie je možná dekompresia do pôvodnej podoby.
Zmena spôsobu zápisu informácie, Zníženie redundancie v dátach.
Je možné obnovenie do pôvodnej podoby.
| Typ | Príklady | Po dekompresii |
|---|---|---|
| Bezstratová | ZIP, PNG, FLAC | dáta sú úplne rovnaké |
| Stratová | JPEG, MP3, MPEG | dáta sú mierne zmenené |
Bezstratovú kompresiu použijeme napríklad pri zdrojovom kóde, dokumentoch alebo databázach.
pomer = komprimovaná veľkosť / pôvodná veľkosť
úspora = 1 - pomer
Príklad:
pôvodný súbor: 1000 B
komprimovaný súbor: 600 B
úspora: 40 %
Kompresia nemusí byť vždy úspešná. Pri krátkych alebo náhodných dátach môže výsledok narásť:
ABCD → 1A1B1C1D
Kompresor musí uložiť aj informáciu o opakovaní, takže pri malom vstupe môže réžia prevážiť úsporu.
Viac: Kompresia dát
RLE nahrádza súvislé opakovanie dvojicou (počet, znak).
AAAABBBAAC
4A 3B 2A 1C
Výsledok:
4A3B2A1C
Viac: Run-length encoding
RLE funguje dobre pri obrázkoch s veľkými jednofarebnými plochami alebo pri podobných opakujúcich sa dátach.
Pri dátach bez dlhých behov opakujúcich sa znakov môže byť výsledok väčší než originál.
Príklady použitia sa nachádzajú v jednoduchých obrazových a bitmapových formátoch.
Viac: Run-length encoding
def rle_encode(data: str) -> list[tuple[int, str]]:
if not data:
return []
result = []
count = 1
for current, previous in zip(data[1:], data):
if current == previous:
count += 1
else:
result.append((count, previous))
count = 1
result.append((count, data[-1]))
return result
Vysielač -- prenosový kanál --> Príjmač
Ako navrhnúť efektívnu komunikáciu z vysielača tak, aby jej príjmač porozumel?
Shannon:
Základný probmém komunikácie je schopnosť príjmača identifikovať dáta generované vysielačom cez prijatý signál v prenosovom kanáli.
Dáta sú množina prvkov (udalostí), ktoré sa môžu opakovať.
['prší','prší','prší','sneží','slnečno','sneží']
[1,1,2,3,2]
Je možné vypočítať pravdepodobnosť každého prvku. Pravdepodobnosť je priamo úmerná početnosti:
(prší) 1 : 2
(sneží) 2 : 2
(slnečno) 3 : 1
ostatné : nula
from collections import Counter
data = ['prší', 'prší', 'prší',
'sneží', 'slnečno', 'sneží']
freq = Counter(data)
print(freq)
Výstup:
Counter({
'prší': 3,
'sneží': 2,
'slnečno': 1
})
from collections import Counter
data = ['prší', 'prší', 'prší',
'sneží', 'slnečno', 'sneží']
freq = Counter(data)
n = len(data)
for symbol, count in freq.items():
print(symbol, count / n)
Výstup:
prší 0.5
sneží 0.333
slnečno 0.167
je miera prekvapenia, ktoré prináša symbol.
Entropiu merieme v bitoch na symbol.
Čím je symbol zriedkavejší, tým viac informácie nesie.
Štatisticky analyzujeme symboly vo výslednej správe,
Počet výskytov - frekvencia - pravdepodobnosť.
\(P (z) = C (z) / N\)
Minimálne množstvo bitov, potrebné na reprezentáciu celej množiny \(Z, z \in Z\).
\(S(Z) = - \sum_z P(z) \log_2 P(z)\)
symbol s pravdepodobnosťou \(1/2\) nesie 1 bit informácie, kým symbol s pravdepodobnosťou \(1/8\) nesie 3 bity. Zriedkavejší symbol prináša väčšie prekvapenie.
Pre množinu symbolov môžeme vypočítať Shannonovu entropiu:
from collections import Counter
from math import log2
data = ['prší', 'prší', 'prší',
'sneží', 'slnečno', 'sneží']
freq = Counter(data)
n = len(data)
entropy = 0
for count in freq.values():
p = count / n
entropy -= p * log2(p)
print(entropy)
#1.459 bitu na symbol
Množina vstupných symbolov v správe sa prepisuje na množinu výstupných symbolov.
Množina výstupných symbolov - kódový slovník
Spôsob zápisu množiny prvkov pomocou kódových symbolov.
[1,2,2,4,5,7,7,7]
[1,2,2,4,5,7,7,7]
Unikátny spôsob zápisu jedného prvku
ASCII Tabuľka: - osem bitové slová
Morzeova abeceda : - slová s premenlivou dĺžkou
Hľadanie optimálneho prefixového kódovania.
Optimálne kódovanie - Najčastejšie symboly by mali mať čo najkratšie kódy.
Prefixové kódovanie : Žiadne kódové slovo nie je prefixom iného kódového slova, nepotrebuje sa používať žiadny oddeľovací znak.
Správa bude stručná a jednoznačne čitateľná.
Vychádza z pravdepodobností symbolov a vytvára binárny strom, ktorý reprezentuje kódovanie.
Máme zdroj, ktorý generuje 4 nezávislé symboly s týmito pravdepodobnosťami:
| Symbol | Pravdepodobnosť | Kód | Dĺžka | \(p \times l\) |
|---|---|---|---|---|
| A | \(1/2\) | 0 | 1 | \(0.500\) |
| B | \(1/4\) | 10 | 2 | \(0.500\) |
| C | \(1/8\) | 110 | 3 | \(0.375\) |
| D | \(1/8\) | 111 | 3 | \(0.375\) |
| Súčet | 1 | — | — | 1.75 |
Stĺpec \(p \times l\) ukazuje, koľko bitov na symbol každý znak prinesie priemerne. Súčet sa rovná entropii (1.75 bitu).
Ak je kódovanie nasledovné:
A → 1B → 00C → 01Dekódujme bitový reťazec 00011. Čítame zľava doprava a pri každom liste začíname od koreňa:
00 → B01 → C1 → A1 → AVýsledkom je postupnosť BCAA. Kódy sú prefixové, preto vieme jednoznačne určiť, kde sa každý kód končí.
Pre text "MISSISSIPPI" (11 znakov) s početnosťami:
| Symbol | Početnosť | Pravdepodobnosť | Kód | Dĺžka | \(p \times l\) |
|---|---|---|---|---|---|
| M | 1 | 1/11 ≈ 0.091 | 111 | 3 | 0.273 |
| I | 4 | 4/11 ≈ 0.364 | 0 | 1 | 0.364 |
| S | 4 | 4/11 ≈ 0.364 | 10 | 2 | 0.727 |
| P | 2 | 2/11 ≈ 0.182 | 110 | 3 | 0.545 |
| Súčet | 11 | 1 | — | — | 1.909 |
Huffmanovo kódovanie dosahuje 3.83× kompresiu oproti ASCII.
| Porovnanie | Bitov |
|---|---|
| ASCII (8 bitov/znak) | 11 × 8 = 88 |
| Huffmanovo kódovanie | 23 |
| Entropia (dolná hranica) | 11 × 1.909 ≈ 21 |
0, choď do ľavého potomka.1, choď do pravého potomka.Huffmanov strom je prefixový (trie), takže dekódovanie je jednoznačné.
Príklad: Zostavte Huffmanov strom pre text "MISSISSIPPI":
| Symbol | Početnosť |
|---|---|
| M | 1 |
| I | 4 |
| S | 4 |
| P | 2 |
*
/ \
* I
/ \
* S
/ \
M P
class Node:
def __init__(self, freq, symbol=None,
left=None, right=None):
self.freq = freq
self.symbol = symbol
self.left = left
self.right = right
# Prekrytie metódy < umožňuje porovnávať uzly podľa frekvencie
def __lt__(self, other):
return self.freq < other.freq
Metóda __lt__ umožňuje ukladať uzly do prioritnej fronty.
from collections import Counter
text = "MISSISSIPPI"
# spočítame znaky a zotriedime podľa frekvencie
pool = sorted(
Node(freq, symbol)
for symbol, freq in Counter(text).items()
)
while len(pool) > 1:
# dva najmenšie uzly (už zoradené)
left, right = pool.pop(0), pool.pop(0)
parent = Node(
left.freq + right.freq,
left=left,
right=right
)
pool.append(parent)
# po pridaní nového uzla je potrebné znovu zotriediť frontu
# triedenie má typicky zložitosť n log(n)
pool.sort(key=lambda n: n.freq)
# Celý algoritmus má zložitosť n^2 log(n)
root = pool[0]
def build_codes(node, prefix="", codes=None):
if codes is None:
codes = {}
if node.symbol is not None:
codes[node.symbol] = prefix
return codes
build_codes(node.left, prefix + "0", codes)
build_codes(node.right, prefix + "1", codes)
return codes
Možný výstup:
I 0
S 10
P 110
M 1110
vyžaduje opakované triedenie poľa pri každom vložení alebo výbere.
O(log n).# zostavenie Huffumanovho stromu s použitím heapq
import heapq
class Node:
def __init__(self, freq, symbol=None,
left=None, right=None):
self.freq = freq
self.symbol = symbol
self.left = left
self.right = right
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(text):
freq = Counter(text)
heap = [Node(f, s) for s, f in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
parent = Node(left.freq + right.freq, left=left, right=right)
heapq.heappush(heap, parent)
return heap[0]
Prioritná fronta vracia vždy prvok s najvyššou (alebo najnižšou) prioritou.
Binárna kopa je efektívna dátová štruktúra na jej implementáciu:
O(log n), pohľad na minimum O(1).O(n), čo je lepšie ako O(n log n) pri implementácii pomocou binárneho stromu.Pri indexovaní od 0 platí pre uzol na pozícii i:
2 * i + 12 * i + 2(i - 1) // 2Vďaka tomu netreba v poli ukladať odkazy na rodičov ani potomkov.
V minimálnej kope má každý rodič hodnotu menšiu alebo rovnakú ako jeho potomkovia. Najmenší prvok je preto vždy v koreni.
Nezáleží na tom, či je menší prvok v ľavom alebo pravom podstrome, dôležité je, že je menší ako jeho rodič.
1
/ \
2 3
/ \
4 5
O(log n) Príklad na takmer úplný strom:
1
/ \
2 3
/ \ /
4 5 6
Takmer úplnný strom je efektívny na ukladanie do poľa, pretože v poli nemusíme uchovávať žiadne prázdne miesta, ani odkazy na rodičov alebo potomkov.
O(log n), pretože výška takmer úplného stromu je logaritmická.def heapify(arr, n, i):
smallest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr < arr[smallest]:
smallest = left
if right < n and arr < arr[smallest]:
smallest = right
if smallest != i:
arr[i], arr[smallest] = arr[smallest], arr[i]
heapify(arr, n, smallest)
Zložitosť je O(log n), pretože v najhoršom prípade sa musíme prejsť z koreňa až na list.
def build_heap(arr):
n = len(arr)
# V druhej polovici poľa sú listy, ktoré sú už kopovité.
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
Využijeme fakt, že výsledkom obnovenia kopovitosti je minimálny prvok na prvom mieste.
def heap_sort(arr):
n = len(arr)
build_heap(arr)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)