Kompresia a Huffmanovo kódovanie

Compression

Data compression is the process of reducing the number of bits used to represent data. Data compression entails two processes: in one process the data is compressed, or encoded, to reduce its size; in a second process it is uncompressed, or decoded, to return it to its original state.

Kompresia

Stratová a bezstratová

Stratová kompresia

Vynechanie nepodstatných častí. Nie je možná dekompresia do pôvodnej podoby.

  • kompresia audia
  • kompresia videa

Bezstratová kompresia

Zmena spôsobu zápisu informácie, Zníženie redundancie v dátach.

Je možné obnovenie do pôvodnej podoby.

  • šifrovaný prenos.
  • archivovanie súborov.

Bezstratová kompresia

Premenlivá dĺžka kódového slova:: Kóduje často opakujúce sa sekvencie s menším počtom bitov Fixná dĺžka kódového slova:: Kóduje dáta ako tokeny

Problém komunikácie

Vysielač -- prenosový kanál --> Príjmač

Ako navrhnúť efektívnu komunikáciu z vysielača tak, aby jej príjmač porozumel?

Fundamental problem of communication

[quote, Shannon]

fundamental problem of communication" is for the receiver to be able to identify what data was generated by the source, based on the signal it receives through the channel.

Teória informácií

Dáta sú množina prvkov (udalostí), ktoré sa môžu opakovať.

['prší','prší','prší','sneží','slnečno','sneží']

[1,1,2,3,2]

Teória informácií

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

Množina vstupných symbolov v správe sa prepisuje na množinu výstupných symbolov.

Množina výstupnjných symbolov - kódový slovník

Kódovanie

Spôsob zápisu množiny prvkov pomocou kódových symbolov.

[1,2,2,4,5,7,7,7]
  • Ako by sme zapísali v binárnom kóde túto množinu čo najefektívnejšie?
  • Koľko bitov budeme potrebovať?

Kódovanie

[1,2,2,4,5,7,7,7]
  • ASCII kódovanie potrebuje 8 bitov na jeden znak
  • Mohli by sme sa dohodnúť na nejakom inom kódovaní?

Kódové slovo

  • Unikátny spôsob zápisu jedného prvku

ASCII Tabuľka

  • osem bitové slová

Morzeova abeceda

  • slová s premenlivou dĺžkou

Optimálne kódovanie

Najčastejšie symboly by mali mať čo najkratšie kódy.

Koľko symbolov potrebujem?

Ak nbudem tú istú spprávu kódovať rôznymi kódovými tabuľkami

Entropia

Štatisticky analyzujeme symboily vo výslednej správe,

Počet výskytov - frekvencia - pravdepodobnosť.

\(P (z) = C (z) / N\)

Z pravdepodobnosti vypočítame entropiu

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)\)

Kompresia

Hľadanie optimálnej sady kódových slov.

Zníženie počtu bitov potrebných na reprezentáciu dát.

Entropia:: Teoreticky maximálna kompresia.

Prefixové kódovanie

Žiadne kódové slovo nie je prefixom iného kódového slova.

Huffmanovo kódovanie

Hľadanie optimálneho prefixového kódovania.

Huffmanov strom

  • Všetky symboly sa dajú zoradiť do binárneho stromu podľa ich binárneho kódu.
  • Cesta k uzlu je jeho binárny kód.

Huffmanov strom

Huffmanov strom

Huffmanovo kódovanie

  • Vstup:: Množina symbolov a ich váhy (početnosti).
  • Výstup:: Množina binárnych kódov pre každý symbol usporiadaná v Huffmanovom strome.

Tvorba Huffmanovho stromu

  1. Zostav tabuľku početností symbolov
  2. Symbol a početnosť premeň na uzol binárneho stromu a ulož do prioritnej fronty.

Tvorba Huffmanovho stromu

  1. Ak je vo fronte dosť prvkov, vytvor nový uzol. vyber dva najmenej početné prvky a tie budú potomkami nového uzla.. Početnosť nového uzla bude súčet početností potomkov.
  2. Ak nie je vo fronte dosť prvkov, zvyšný uzol je koreňom binárneho Hufmanovho stromu.

Huffmanovo kódovanie

Každému symbolu sa priradí jeho Huffmanov kód.

Huffmanovo dekódovanie

  • Vstup:: Binárny reťazec a Hufmannov strom.
  • Výstup:: Postupnosť symbolov

Zhrnutie: Ako súvisí kompresia a údajové štruktúry a algoritmy

  • Hufmanov strom je binárny strom
  • binárna kopa sa využíva pri zostavení Hufmannovho stromu.

Dobré miesto na doplnenie Pythonu je pri entropii, počítaní početností a hlavne pri konštrukcii Huffmanovho stromu. Môžeš medzi existujúce slidy vložiť napríklad tieto:

Výpočet početností symbolov v Pythone

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
})

Výpočet pravdepodobností

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

Výpočet entropie

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)

Výstup:

1.459 bitu na symbol

Prioritná fronta v Pythone

Modul heapq implementuje binárnu kopu.

import heapq

heap = [5, 2, 8, 1]

heapq.heapify(heap)

print(heapq.heappop(heap))
print(heapq.heappop(heap))

Výstup:

1
2

Uzol Huffmanovho stromu

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

Metóda __lt__ umožňuje ukladať uzly do prioritnej fronty.

Vytvorenie Huffmanovho stromu

import heapq
from collections import Counter

text = "MISSISSIPPI"

heap = []

for symbol, freq in Counter(text).items():
    heap.append(Node(freq, symbol))

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)

root = heap[0]

Generovanie Huffmanových kódov

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

Použitie:

codes = build_codes(root)

for symbol, code in codes.items():
    print(symbol, code)

Možný výstup:

I 0
S 10
P 110
M 1110
...

Kódovanie textu

text = "MISSISSIPPI"

encoded = "".join(
    codes[ch]
    for ch in text
)

print(encoded)

Porovnanie veľkosti

ASCII:

ascii_bits = len(text) * 8
print(ascii_bits)

Huffman:

huffman_bits = len(encoded)
print(huffman_bits)

Kompresný pomer:

print(
    ascii_bits / huffman_bits
)

Kompletný príklad

from collections import Counter
import heapq

text = "MISSISSIPPI"

# spočítanie početností
freq = Counter(text)

# vytvorenie haldy
heap = [
    Node(count, symbol)
    for symbol, count in freq.items()
]

heapq.heapify(heap)

# zostavenie stromu
while len(heap) > 1:
    left = heapq.heappop(heap)
    right = heapq.heappop(heap)

    heapq.heappush(
        heap,
        Node(left.freq + right.freq,
             left=left,
             right=right)
    )

root = heap[0]

# vytvorenie kódov
codes = build_codes(root)

print(codes)
Reload?