Praktické cvičenie: Huffmanovo kódovanie textu

Cieľ

Implementujte jednoduchý Huffmanov kompresor pre textový reťazec.

Študent si precvičí:

• počítanie početností symbolov,
• prácu s prioritnou frontou cez heapq,
• konštrukciu binárneho Huffmanovho stromu,
• generovanie prefixových kódov,
• kódovanie a dekódovanie binárneho reťazca,
• porovnanie veľkosti oproti 8-bitovému ASCII zápisu.

Reprezentácia stromu

Pre automatické testovanie používajte túto reprezentáciu:

• prázdny strom: None,
• listový uzol: znak ako str, napr. "a",
• vnútorný uzol: dvojica (left, right).

Príklad stromu:

(("a", "b"), "c")

Tento strom môže znamenať kódy:

{
    "a": "00",
    "b": "01",
    "c": "1",
}

Vetve doľava priraďte bit "0" a vetve doprava bit "1".

Zadanie

Vytvorte súbor solution.py a implementujte funkcie:

def frequency_table(text):
    pass

def build_huffman_tree(frequencies):
    pass

def build_codes(tree):
    pass

def huffman_encode(text, codes):
    pass

def huffman_decode(bits, tree):
    pass

def compression_ratio(text, encoded_bits):
    pass

1. frequency_table(text)

Funkcia dostane textový reťazec a vráti slovník početností znakov.

Príklad:

frequency_table("banana")
# {"b": 1, "a": 3, "n": 2}

Prázdny vstup:

frequency_table("")
# {}

Môžete použiť collections.Counter, ale výsledok má byť obyčajný slovník alebo objekt kompatibilný so slovníkom.

2. build_huffman_tree(frequencies)

Funkcia dostane slovník početností a vráti Huffmanov strom.

Príklad vstupu:

{
    "a": 4,
    "b": 2,
    "c": 1,
    "d": 1,
}

Požiadavky:

• použite prioritnú frontu cez heapq,
• v každom kroku vyberte dva uzly s najmenšou početnosťou,
• nový vnútorný uzol má početnosť rovnú súčtu početností potomkov,
• ak je vstup prázdny, vráťte None,
• ak je vo vstupe iba jeden znak, strom je priamo tento znak.

Huffmanov strom nemusí byť pri rovnakých početnostiach jediný. Automatické testy preto nemajú kontrolovať presnú štruktúru stromu, ale vlastnosti výsledných kódov a správnosť dekódovania.

Odporúčaná položka v halde:

(frequency, order, tree)

Hodnota order je rastúce číslo, ktoré zabráni tomu, aby Python porovnával celé stromy pri zhodných početnostiach.

3. build_codes(tree)

Funkcia dostane Huffmanov strom a vráti slovník kódov.

Príklad:

tree = (("a", "b"), "c")

build_codes(tree)
# {"a": "00", "b": "01", "c": "1"}

Požiadavky:

• ľavá vetva pridáva bit "0",
• pravá vetva pridáva bit "1",
• kódy musia byť prefixové,
• pre strom s jedným znakom použite kód "0",
• pre None vráťte prázdny slovník.

4. huffman_encode(text, codes)

Funkcia zakóduje text podľa tabuľky Huffmanových kódov.

Príklad:

codes = {"a": "0", "b": "10", "n": "11"}

huffman_encode("banana", codes)
# "100110110"

Výsledkom je reťazec zložený iba zo znakov "0" a "1".

5. huffman_decode(bits, tree)

Funkcia dekóduje bitový reťazec pomocou Huffmanovho stromu.

Príklad:

tree = ("a", ("b", "n"))

huffman_decode("100110110", tree)
# "banana"

Požiadavky:

• prázdny bitový reťazec a prázdny strom vrátia "",
• pri strome s jedným znakom sa každý bit dekóduje ako tento znak,
• bežné dekódovanie prechádza strom podľa bitov a pri dosiahnutí listu pridá znak do výsledku.

6. compression_ratio(text, encoded_bits)

Funkcia porovná veľkosť Huffmanovho zápisu s jednoduchým 8-bitovým zápisom znakov.

Vráti číslo:

len(encoded_bits) / (len(text) * 8)

Príklad:

compression_ratio("aaaa", "0000")
# 0.125

Ak je vstupný text prázdny, vráťte 0.0.

Automatické hodnotenie

Automatické testy majú overovať:

• správnu tabuľku početností,
• správne generovanie kódov pre pevne daný strom,
• prefixovosť kódov,
• zakódovanie a dekódovanie bez straty informácie,
• optimálnu dĺžku pre malý vstup so známou distribúciou,
• spracovanie prázdneho vstupu a vstupu s jedným symbolom.

Testy

import pytest

from solution import (
    frequency_table,
    build_huffman_tree,
    build_codes,
    huffman_encode,
    huffman_decode,
    compression_ratio,
)

def is_prefix_free(codes):
    values = list(codes.values())

    for i, code in enumerate(values):
        for j, other in enumerate(values):
            if i != j and other.startswith(code):
                return False

    return True

def test_frequency_table():
    assert frequency_table("banana") == {"b": 1, "a": 3, "n": 2}
    assert frequency_table("") == {}

def test_build_codes_for_known_tree():
    tree = (("a", "b"), "c")

    assert build_codes(tree) == {
        "a": "00",
        "b": "01",
        "c": "1",
    }

def test_empty_input():
    frequencies = frequency_table("")
    tree = build_huffman_tree(frequencies)
    codes = build_codes(tree)

    assert tree is None
    assert codes == {}
    assert huffman_encode("", codes) == ""
    assert huffman_decode("", tree) == ""
    assert compression_ratio("", "") == 0.0

def test_single_symbol_input():
    text = "aaaaaa"

    frequencies = frequency_table(text)
    tree = build_huffman_tree(frequencies)
    codes = build_codes(tree)
    encoded = huffman_encode(text, codes)

    assert tree == "a"
    assert codes == {"a": "0"}
    assert encoded == "000000"
    assert huffman_decode(encoded, tree) == text

def test_roundtrip_and_prefix_property():
    text = "this is an example for huffman encoding"

    frequencies = frequency_table(text)
    tree = build_huffman_tree(frequencies)
    codes = build_codes(tree)
    encoded = huffman_encode(text, codes)

    assert set(codes) == set(frequencies)
    assert is_prefix_free(codes)
    assert set(encoded) <= {"0", "1"}
    assert huffman_decode(encoded, tree) == text

def test_encoded_length_for_known_distribution():
    text = "aaaabbcd"

    frequencies = frequency_table(text)
    tree = build_huffman_tree(frequencies)
    codes = build_codes(tree)
    encoded = huffman_encode(text, codes)

    assert is_prefix_free(codes)
    assert huffman_decode(encoded, tree) == text
    assert len(encoded) == 14

def test_compression_ratio():
    assert compression_ratio("aaaa", "0000") == pytest.approx(0.125)
    assert compression_ratio("banana", "100110110") == pytest.approx(9 / 48)

Skryté testy

Skryté testy môžu overovať:

• text s medzerami a interpunkciou,
• text s veľkými a malými písmenami,
• viac znakov s rovnakou početnosťou,
• dlhší text s tisíckami znakov,
• neexistenciu prefixových konfliktov,
• to, že huffman_decode(huffman_encode(text, codes), tree) == text.

Odporúčaná stratégia riešenia

• frequency_table: použite Counter alebo ručné počítanie cez slovník.
• build_huffman_tree: použite heapq; do haldy ukladajte početnosť, poradie a strom.
• build_codes: použite rekurzívny prechod stromu a postupne skladajte bity.
• huffman_encode: spojte kódy jednotlivých znakov cez "".join(...).
• huffman_decode: prechádzajte strom podľa bitov, po dosiahnutí listu sa vráťte do koreňa.
• compression_ratio: porovnajte počet Huffmanových bitov s len(text) * 8.

Hodnotenie

Časť	Body
frequency_table	2
build_huffman_tree	5
build_codes	4
huffman_encode	2
huffman_decode	3
compression_ratio	1
Spracovanie prázdneho vstupu a jedného symbolu	2
Čitateľnosť kódu a vhodné použitie heapq	1

Spolu: 20 bodov.

Bonus

Pridajte funkciu:

def huffman_compress(text):
    pass

Funkcia vráti trojicu:

(encoded_bits, tree, codes)

Príklad:

encoded_bits, tree, codes = huffman_compress("banana")

assert huffman_decode(encoded_bits, tree) == "banana"

Ako ďalší bonus môžete pridať serializáciu stromu do reťazca, aby sa dal zakódovaný text uložiť spolu so stromom.

Previous Post Next Post