Studoši

možete podijeliti zadatak/pitanja s blica od danas?

[obrisani korisnik]

Danas je prvi labos u 12 objavim kad krene

Sta ulazi u ovaj labos?
Dinamičko programiranje, kompresijski algoritmi i nasumični algoritmi?

zmaj
problem naprtnjače, Huffmanovo kodiranje i LZ77.

Zadatak Vam je implementirati Huffmanov enkoder koristeći prioritetni red. Numerička tolerancija je . U postupku izgradnje stabla, lijevo dijete uvijek neka bude ono manje, a desno neka bude veće (pogledajte napomenu 1). Ovo će osigurati jednoznačnost koda. Testiranje se provodi nad odabranim i slučajno generiranim primjerima. Svi testovi se provode nad kodnom tablicom.

Već Vam je složena većina koda, ali morate ispravno dovršiti slijedeće:

metodu lt unutar klase Node na način da ispravno uspoređuje čvorove stabla. U usporedbama brojeva sa pomičnim zarezom, pazite na numeričku preciznost! Ovu metodu koristi prioritetni red za određivanje redoslijeda čvorova.
metodu Huffman_tree na način da izgradi valjano Huffmanovo stablo
Mjesta gdje trebate unijeti kod su označena sa TODO. Za prioritetni red se preporuča korištenje heapq iz pythonove standardne programske knjižnice koja koristi min-heap za održavanje reda.

Ostatak koda riješava probleme izgradnje kodne tablice i enkodiranja.

Kod
U prostor za odgovore zalijepite CIJELI kod (popunjen, naravno).

import heapq

TOL_DEC = 3
TOLERANCE = 10**-TOL_DEC


class Node:
    """Node in a Huffman tree
    """

    def __init__(self, prob, symbol, left=None, right=None):
        self.prob = prob  # probability of symbol
        self.symbol = symbol
        self.left = left
        self.right = right

        # incoming tree direction to node (0/1) - root has ''
        self.code = ''

    def __lt__(self, other: 'Node') -> bool:
        """enables comparisons between objects

        Args:
            other (Node): other object in comparison

        Returns:
            bool: True if self is LESS THAN other,
                  False otherwise
        """
        # TODO: ovdje dodajte svoj kod za usporedbu. Pazite na numeričku toleranciju!
        pass


def Huffman_tree(symbol_with_probs: dict) -> Node:
    """Builds Huffman tree

    Args:
        symbol_with_probs (dict): dictionary symbol-probability that describes the problem

    Returns:
        Node: root of the built Huffman tree
    """
    symbols = symbol_with_probs.keys()
    nodes_queue = []

    # TODO: ovdje dovršite izgradnju stabla
    # HINT: spajanje dva stringa s1 i s2 u sortirani se moze postici sa: ''.join(sorted(s1+s2))
    # HINT: za rad sa prioritetnim redom vam mogu zatrebati metode heapq.heappop i heapq.heappush

    return nodes_queue[0]


####################### IT'S BETTER NOT TO MODIFY THE CODE BELOW ##############


def calculate_codes(node: Node, val: str = '', codes=dict()) -> dict:
    # calculates codewords for Huffman subtree starting from node

    newVal = val + str(node.code)

    if(node.left):
        calculate_codes(node.left, newVal, codes)
    if(node.right):
        calculate_codes(node.right, newVal, codes)

    if(not node.left and not node.right):
        codes[node.symbol] = newVal

    return codes


def Huffman_encode(data: str, coding: dict) -> str:
    # encodes
    encoding_output = []
    for c in data:
        encoding_output.append(coding[c])
    string = ''.join([str(item) for item in encoding_output])
    return string


def Huffman_decode(encoded_data: str, huffman_tree: Node) -> str:
    tree_head = huffman_tree
    decoded_output = []
    for x in encoded_data:
        if x == '1':
            huffman_tree = huffman_tree.right
        elif x == '0':
            huffman_tree = huffman_tree.left
        # check if leaf
        if huffman_tree.left is None and huffman_tree.right is None:
            decoded_output.append(huffman_tree.symbol)
            huffman_tree = tree_head

    string = ''.join([str(item) for item in decoded_output])
    return string


def roundToDecimals(num: float, decimals: int) -> float:
    """Rounds number to significant decimals

    Args:
        num (float): number to round
        decimals (int): number of significant decimals

    Returns:
        float: rounded number
    """
    return round(num*10**decimals)/10**decimals

Ovdje Vam je kod koji možete koristiti za testiranje

Kod za isprobavanje i testiranje
Ovaj kod nemojte kopirati u prostor za rješenje, već ga koristite lokalno u svojoj razvojnoj okolini.

symbols_with_probs={'A':0.13,'B':0.21,'C':0.39,'D':0.19,'E':0.08}
print('problem: ', symbols_with_probs)
tree=Huffman_tree(symbols_with_probs)
huffman_code = calculate_codes(tree)
print('encoding:',huffman_code)

data = 'DEBADE'
print('original text: ',data)

print('-------ENCODE--------')
enc=Huffman_encode(data,huffman_code)
print('data encoded: ',enc)

print('-------DECODE--------')
print('data decoded back: ',Huffman_decode(enc,tree))

""" # ispravan izlaz
problem:  {'A': 0.13, 'B': 0.21, 'C': 0.39, 'D': 0.19, 'E': 0.08}
encoding: {'D': '00', 'E': '010', 'A': '011', 'B': '10', 'C': '11'}
original text:  DEBADE
-------ENCODE--------
data encoded:  000101001100010
-------DECODE--------
data decoded back:  DEBADE
"""

Napomena 1
U postupku izgradnje kodne tablice, koristite sljedeći tie-breaker (razrješavanje situacija kada imate izjednačene usporedbe vjerojatnosti)…

Uvedimo imenovanje čvora u Huffmanovom stablu na sljedeći način:

ako je list, tada mu je ime njegov pripadni simbol
ako je unutarnji čvor, neka mu je ime uzlazno sortirana konkatenacija simbola njegovih listova. Npr. ako su u podstablu tog čvora listovi simbola ‘C’, ‘A’, ‘E’ onda će ime tog unutarnjeg čvora biti ‘ACE’.
Ako dva čvora imaju jednake vjerojatnosti, tada se manjim čvorom smatra onaj koji ima leksikografski manje ime. Primjer istinitih usporedbi su: ‘AB’ < ‘AC’ < ‘ACE’ te dodatno ‘BC’<‘E’.

NAPOMENA 2
Pazite na uvlačenja (indentacije) - koristite samo SPACE ili samo TAB
Možete koristiti print funkciju za ispis međurezultata
Edgar koristi Python verziju 3.8, tako da vam možda neke funkcionalnosti iz novijih (3.9+) ili starijih (2.x) verzija neće podržavati
Molimo da pišete svoj vlastiti kod. Kodove u skripti možete koristiti za orijentaciju. Edgar ima mogućnost otkrivanja plagijata i ta će mogućnost biti korištena na ovom zadatku.

djeno jesam ja lud ili im je createKnapsackTable kriv?

Rene Ja sam uspio s takvim napraviti. Izgleda da ima viska stupac koji bi odgovarao nijednom predmetu. Ustvari samo sluzi da bude pun nulama koliko sam skuzio

Cubi Aha, i koliko kužim obrnuto je nego u predavanjima tj. retci su predmeti a stupci su kapacitet…jer zašto bit konzistentan

Rene Naravno

Pitanja:

1. Složenost rješavanja problema naprtnjače kapaciteta C i broja predmeta N: O(N * C)
2. Huffmanovo kodiranje proizvodi optimalan binarni kod varijabilne duljine, da ili ne: DA
3. Koja je tvrdnja neispravna za LZ77
   a) Koristi operaciju kopiranja
   b) riječnički spremnik je u praksi dulji od unaprijednog spremnika
   c) provodi blokovsko enkodiranje
   d) koristi statični riječnik
4. Koja je ukupna složenost izgradnje Huffmanove kodne tablice iz ulaznog problema: O(n * log(n))

Cubi
Ja sam jos imao i ovo

jel ima ko kod huffmana da mu je original text == dekodirani tekst al edgar kaze da je kodna tablica kriva?

neunist.iva da, ali za 2 primjera “samo” (jedan nosi 30%)

neunist.iva ak si imala isti problem ovo ko ja, stvar je u onom slucaju kad se vjerojatnosti iste, ako usporedujes s == neces dobiti ispravno, moras npr. abs(self.prob - other.prob) < TOLERANCE koji je definiran u danom kodu

Zasto UVJEK ovi labosi moraju biti cancer. Najgori labosi na cjelom mom studiju, i to daleko.