Cvičení 11: Objekty, Halda, Asociativní pole, Stromy

Třídy pro komplexní čísla:

• Třída obsahuje dvě proměnné real a imag
• Konstruktor (metoda _init_) nastavuje tyto proměnné defaultně na 0
• Pro přímý výpis funkcí print je vhodné definovat metodu _repr_, která vrací string
• Pozor: init a repr má v názvu dvě podtržítka!!!

class Complex:
    def __init__(self, real=0, imag=0):
        self.real = real
        self.imag = imag
 
    def amplitude(self):
        return self.real*self.real + self.imag*self.imag
 
    def add(self, rhs):
        self.real += rhs.real
        self.imag += rhs.imag
 
    def sub(self, rhs):
        self.real -= rhs.real
        self.imag -= rhs.imag
 
    def __repr__(self):
        sign = "+";
        if (self.imag < 0):
            sign = "-";
        return str(self.real) + sign + str(abs(self.imag)) + "i"
 
    def mul(self, rhs):
        r = self.real*rhs.real - self.imag*rhs.imag;
        i = self.real*rhs.imag + self.imag*rhs.real;
        self.real = r
        self.imag = i 
 
if __name__=="__main__":
    a = Complex()
    print("a=",a)
 
    b = Complex(1,-1)
    print("b=",b)
 
    a.add(b)
    print("a=",a)
 
    a.mul(b)
    print("a=",a)
 
    print("|a|=",a.amplitude())
    print("|b|=",b.amplitude())

Binární halda je binární stromová datová struktura. Je tvořena uzly, které mají max. dva potomky (levý a pravý potomek) (odtud přídavné jméno binární), pričemž potomek je opět uzel. Její důležitou vlastností je, že:

• hodnota každého uzlu je rovna nebo menší než hodnoty jejich potomků.
• Pokud je tato vlastnost splněna tak platí, že prvek v tzv. kořenu stromu obsahuje nejmenší prvek mezi všemi prvky.
• V tomto cvičení budeme předpokládat tuto variantu.
• Takové haldě se někdy říká min-halda.

Binární haldu lze samozřejmě realizovat i s opačnou vlastností:

• hodnota každého uzlu je rovna nebo větší než hodnoty jejich potomků.
• Pokud je tato vlastnost splněna tak platí, že prvek v tzv. kořenu stromu obsahuje největší prvek mezi všemi prvky.
• Takové haldě se říká max-halda.

Použití binární haldy:

• Pro realizaci prioritní fronty, v důsledku toho např. pro hledání cest v grafech, mapách, plánování pohybu robotů

Předpokládejme, že máme existující binární haldu. Při vyjmutí prvky stačí vzít prvek v kořeni stromu, neboť ten již z definice obsahuje nejmenší hodnotu mezi všemi uzly. Po odebrání prvku je ale nutné zbylé prvky přeskupit a určit nový kořen haldy. Postup je:

• Vyjmout prvek z kořene haldy ( prvek s nejmenší hodnotou )
• Vzít poslední prvek v poslední úrovni a přesunout na pozici kořene.
• Nyní je třeba nahrat prvky v haldě tak, aby byla splněna vlastnost min-haldy. Jelikož budeme začínat od kořene a procházet strom směrem dolu, říká se tomuto postupu tzv. bubble-down.

• Předpokládejme, že jsme v uzlu $U$.
• Porovnáme hodnotu $U$, $U$.left a $U$.right. Pokud je splěna vlastnost min-haldy (tj. hodnota $U$ je menší nebo rovna hodnotám jejích potomků), končíme.
• Pokud ne, vybereme toho potomka, který je menší než $U$. Vyměníme hodnotu $U$ s tímto potomek.
• Pokračujeme bubble-down z tohoto potomka.
• Algoritmus končí, pokud už jsme narazili na uzel bez potomka.

Předpokládejme, že máme existující binární haldu. Vložení prvku se provede takto:

• Vložíme prvek na poslední nejpravější místo v poslední úrovni.
• Porovnáme hodnotu tohoto prvku s jeho rodičem. Pokud je splněna vlastnost haldy (tj. u min-haldy: hodnota prvku je větší nebo rovna hodnotě jeho rodiče), pak končíme.
• Pokud ne, vyměníme hodnotu prvku za hodnotu rodiče a opakujeme tento postup od změněného rodiče.

Tento algoritmus se nazývá bubble-up, jelikož při něm procházíme haldu ze spodní úrovně nahoru.

Nejjednodušší realizací binární haldy je implementaci na poli. Použijeme jednoduchý trik:

• Nechť uzel má v poli index $i$.
• Jeho levý potomek má v poli index $2i+1$.
• Jeho pravý potomek má v poli index $2i+2$.

• Jaký je index rodiče, pokud má potomek index v poli $i$?

# Implementace haldy
#
# http://interactivepython.org/runestone/static/pythonds/Trees/BinaryHeapImplementation.html
# Jan Kybic, 2016
 
class MinHeap:
  """ binarni halda __init__ konstruktor """
  def __init__(self):
     self.heap = [] # indexujeme od nuly
 
  def bubble_up(self,i):
    """ probubla prvek i nahoru, zajisti splneni podminek haldy """
    while i>0:
      j=(i-1)//2 # index rodice
      if self.heap[i] >= self.heap[j]:
        break
      self.heap[j],self.heap[i]=self.heap[i],self.heap[j]
      i = j
 
  def insert(self,k):
    """ vloz prvek do haldy """    
    self.heap+=[k]
    self.bubble_up(len(self.heap)-1)
 
  def peek(self):
    """ vrati nejmensi prvek """
    return self.heap[0]
 
  def size(self):
    """ vrati pocet prvku v halde """
    return len(self.heap)
 
  def is_empty(self):
    """ je halda prazdna? """
    return self.size()==0 
 
  def bubble_down(self,i):
     """ probublej prvek dolu """
     n=self.size()
     while 2*i+1 < n:
        j=2*i+1 # zjisti index mensiho syna
        if j+1 < n and self.heap[j] > self.heap[j+1]:
          j+=1
        if self.heap[i]>self.heap[j]:
          self.heap[i],self.heap[j]=self.heap[j],self.heap[i]
        i=j
 
  def pop(self):
    """ odebere nejmensi prvek a uprav haldu """
    element=self.heap[0]
    self.heap[0]=self.heap[-1]
    self.heap.pop() # smaz posledni prvek
    self.bubble_down(0)
    return element

Implementujte metody pro odebrání prvku na pozici i z binární haldy:

• Metodu pojmenujte delete(i)
• metoda dále smaže tento prvek z haldy
• ošetřete tuto metodu tak, aby ji bylo možné volat i na prázdnou haldu, případně pokud je i větší než velikost haldy

Pomocí této funkce smažte z haldy vytvořené z pole všechna sudá čísla (Nejdříve haldu vytvořte se všemi čísly a pak smažte všechna sudá čísla z haldy):

pole=[10,21,7,11,31,6,1,-11,31,42,-12,80,25,-7,-12,9,14]

• Upravte implementaci haldy tak, aby byla realizována min-halda s kartami ve formátu cvičení 8 příklad 1.
• Vytvořte hladu z následujících karet:

cards = [[0, 'Q'], [2, '6'], [1, 'K'], 
         [1, '8'], [2, '10'], [2, '4'], 
         [3, '4'], [0, '4'], [1, '3'], 
         [2, '5'], [0, 'K'], [3, 'A'], 
         [1, 'J'], [0, '3'], [0, '9']]

• V cvičení 8 jsme pro porovnání karet využívali funkci index a dvojího porovnání (nejdříve barvu a pak hodnotu). Nyní definujte pořadí pomocí asociativního pole a operací sčítání a násobení.

• Využijte následující asociativní pole k převodu římského čísla na dekadické číslo:

conv={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}

• Převeďte na číslo např. MCMXCIX

Uložení načtených dat do ' Dot ' souboru, který lze pak vykreslit do png nástrojem dot z balíku nástrojů Graphviz:

dot -Tpng family.dot  > family.png

Příklad family.dot:

digraph G {
Jana[ color=red];
Jana->Martin [label="child"];
Jana->Robert [label="child"];
Jana->Jan[color=blue; penwidth=4];
Jan[ color=green];
Jan->Petra [label="child"];
Jan->Uxana [label="child"];
Jan->Jana[color=blue; penwidth=4];
Martin[ color=green];
Martin->Jiri [label="child"];
Martin->Rudolf [label="child"];
Martin->Jana [style=dashed];
...
}

• Napište program adam7.py, který podle algoritmu adam7 vykreslí černobílý obrázek přenášený po síti (kódování Adam7 je využito ve formátu obrázků png ).

• Program čte ze standardního vstupu dvě řádky:
  • první řádka obsahuje dvě čísla oddělená mezerou, počet sloupců a počet řádků obrázku
    • všechny rozměry obrázků budou dělitelné 8
  • druhá řádka obsahuje pole čísel s hodnotou 0 nebo 1 oddělené mezerou
    • zaslaná data mohou být neúplná data o informaci o barvě obrázku
    • data jsou od začátku uspořádaná podle algoritmu Adam7
    • pokud je dat méně než je rozměr obrázku (sloupce*řádky) tak je potřeba doplnit informaci o barvě pixelů podle:
      • 1) barvy nejbližšího definovaného pixelu vlevo
      • 2) pokud na řádce není žádný definovaný pixel pak podle barvy nejbližšího definovaného nebo doplněného pixelu nad zkoumaným pixelem
• Výstup - program vytiskne mezeru pro číslo 0 nebo znak '*' pro číslo 1 pro každý pixel obrázku, vždy jednu řádku obrázku na jeden řádek standardního výstupu bez mezer mezi tištěnými znaky.
• Váš program adam7.py odevzdejte do odevzdávacího systému jako HW10.

Vstup (1/16 dat)

24 24
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0

                        
                        
                        
                        
                ****    
                ****    
                ****    
                ****    
                        
                        
                        
                        
    ****            ****
    ****            ****
    ****            ****
    ****            ****
****            ****    
****            ****    
****            ****    
****            ****    
****                    
****                    
****                    
****                    

Vstup (1/8 dat):

24 24
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0

  **          **        
  **          **        
  **          **        
  **          **        
  **  **        **      
  **  **        **      
  **  **        **      
  **  **        **      
  **  **              **
  **  **              **
  **  **              **
  **  **              **
    **            ****  
    **            ****  
    **            ****  
    **            ****  
**              **      
**              **      
**              **      
**              **      
**            **        
**            **        
**            **        
**            **        

Vstup (1/4 dat):

24 24
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0

  **          **        
  **          **        
**  **  **        **    
**  **  **        **    
  **  **        **      
  **  **        **      
    **  **    **        
    **  **    **        
  **  **              **
  **  **              **
                  **    
                  **    
    **            ****  
    **            ****  
    ****              **
    ****              **
**              **      
**              **      
  **      ****  **      
  **      ****  **      
**            **        
**            **        
      **          **    
      **          **    

Vstup (1/2 dat):

24 24
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0

  *    *   *  *    *    
  *    *   *  *    *    
*   *   *  * *    *     
*   *   *  * *    *     
  *   *  * * *  *    *  
  *   *  * * *  *    *  
    *   **    **   *    
    *   **    **   *    
  **  *          *   ** 
  **  *          *   ** 
     *            *     
     *            *     
   ***            ***   
   ***            ***   
   ** *          *    **
   ** *          *    **
*    * *        *  *    
*    * *        *  *    
  **      ****  *    *  
  **      ****  *    *  
*      *   *  *  *     *
*      *   *  *  *     *
      *    *   *  *     
      *    *   *  *     

Vstup (cela data):

24 24
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0

  *    *   *  *    *    
   *   *   *  *    *    
*   *   *  * *    *     
 *   *  *  * *   *    **
  *   *  * * *  *    *  
   *   *  ****  *   *   
    *   **    **   *    
**   * *        * *    *
  **  *          *   ** 
    * *          * **   
     *            *     
***  *            *     
   ***            ***   
     *            *  *  
   ** *          *    **
 **   *          **     
*    * *        *  *    
    *   **    **    *   
  **      ****  *    *  
 *      *  *  *  *    * 
*      *   *  *  *     *
      *    *   *  *     
      *    *   *  *     
     *     *   *   *    

Vstup (1/4 data):

24 8
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

      **                
      **                
  ******                
  ******                
  ******                
  ******                
      **                
      **                

Vstup (1/2 data):

24 8
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1

      **           * * *
      **           * * *
  *****          * * *  
  *****          * * *  
  *****          * * *  
  *****          * * *  
      **           * * *
      **           * * *

Vstup (cela data):

24 8
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

      **           * * *
    ****          * * * 
  *****          * * *  
************************
  *****          * * *  
    ****          * * * 
      **           * * *
                        

Úkolem je implementovat kompresi obrázku pomocí algoritmu LZ77.

• Program lz77.py buď kóduje, nebo dekóduje v závislosti na zadaném obsahu vstupu
  • Kódování:
    • Vstupní data obsahují pouze znaky ' ' a '*' a čtou se ze standardního vstupu - pro načítání použijte smyčku

      for line in sys.stdin:

    • Nejdříve vstupní data překódujete do Nibble (půl bajt), každý nibble je reprezentován jedním hexadecimálním znakem (tj. čísla od '0' do '9' a písmena od 'A' do 'F')
    • Algoritmus lz77 bude pracovat nad celým obrázkem, začne s prázdným bufferem.
    • Velikost bufferu pro najití opakující se sekvence bude 16 hexadecimálních znaků, maximální délka opakující se sekvence bude 5. Základní jednotka pro vyhledávání opakujících se sekvencí je nibble, jedna hexadecimální hodnota.
    • Výstup je bitový řetězec vytištěný v hexadecimálním formátu
    • Pokud v bufferu nebude nalezena sekvence, pak se na výstup:
      • zapíše bit s hodnotou 0
      • a 4 bity daného hexadecimálního znaku (v pořadí od MSB k LSB)
    • Pokud v bufferu bude nalezena sekvence o délce více než jeden znak, pak se zakóduje následujícím způsobem:
      • zapíše se bit s hodnotu 1
      • a zapíší se 4 bity kódující (offset) od začátku bufferu (v pořadí od MSB k LSB)
      • a zapíší se 2 bity kódující délku sekvence zmenšenou o 2 (length-2) (v pořadí MSB, LSB)
      • pokud je sekvencí o stejné délce více, vybere se ta s nejmenším offsetem
    • Obrázek se na hexadecimální hodnoty převádí tak, že MSB (most significant bit) je vlevo a LSB (least significant bit) je vpravo.
      • Počet sloupců obrázku je vždy dělitelný 4
      • Příklad převodu řetězce na hexa hodnoty probíhá následovně:

84218421
**   * *
  C   5

• Výstupní bitový řetězec se převádí na hexadecimální hodnoty obdobně jako obrázek, tedy MSB je vlevo (dříve v řetězci) a LSB je vpravo (později v řetězci).
  • Pokud není délka řetězce dělitelná 4, doplní se na konec bitového řetězce 0. Tedy 11011 je haxadecimálně D8
  • Příklad převodu řetězce 11000101 na hexadecimální řetězec 'C5'

84218421
11000101
  C   5

• Příklad:

Vstupní obrázek šachovnice o velikosti 12×8 bitů:

  **  **  **
  **  **  **
**  **  **  
**  **  **  
  **  **  **
  **  **  **
**  **  **  
**  **  **  

333333CCCCCC333333CCCCCC

Tyto hexadecimální hodnoty se začnou převádět do bitového řetězce podle vyhledávání opakujících se částí v předchozích datech (první pole je buffer posledních maximálně 16 znaků, které již byly zpracovány, druhé pole je aktuálně zpracovávané znaky, jejich prefix hledáme v prvním poli, za bity je výsledek zpracování jednoho znaku, nebo prefixu):

[] [3, 3, 3, 3, 3] - bity 0 0011
[3] [3, 3, 3, 3, 3] - bity 0 0011
[3, 3] [3, 3, 3, 3, 12] - bity 1 0000 00  (offset 0 délka 2 - upravená na 0)
[3, 3, 3, 3] [3, 3, 12, 12, 12] - bity 1 0000 00 (offset 0 délka 2 - upravená na 0)
[3, 3, 3, 3, 3, 3] [12, 12, 12, 12, 12] - bity 0 1100
[3, 3, 3, 3, 3, 3, 12] [12, 12, 12, 12, 12] - bity 0 1100 
[3, 3, 3, 3, 3, 3, 12, 12] [12, 12, 12, 12, 3] - bity 1 0110 00 (offset 6 délka 2 - upravená na 0)
[3, 3, 3, 3, 3, 3, 12, 12, 12, 12] [12, 12, 3, 3, 3] - bity 1 0110 00 (offset 6 délka 2 - upravená na 0)
[3, 3, 3, 3, 3, 3, 12, 12, 12, 12, 12, 12] [3, 3, 3, 3, 3] - bity 1 0000 11 (offset 0 délka 5 - upravená na 3)
[3, 3, 3, 3, 3, 12, 12, 12, 12, 12, 12, 3, 3, 3, 3, 3] [3, 12, 12, 12, 12] - bity 1 0100 11 (offset 4 délka 5 - upravená na 3)
[12, 12, 12, 12, 12, 12, 3, 3, 3, 3, 3, 3, 12, 12, 12, 12] [12, 12] - bity 1 0000 00 (offset 0 délka 2 - upravená na 0)

18E040632C58874E00

• Dekódování
  • Dekódování probíhá, pokud první řádka vstupu obsahuje pouze hexadecimální znaky (znaky nejsou oddělené mezerou) a druhá řádka obsahuje počet sloupců zakódovaného obrázku
  • Celý obrázek je zakódován v jedné řádce vstupu, druhá řádka obsahuje informaci nutnou pro vykreslení obrázku
  • Hexadecimální řetězec si rozdělíte na bitový řetězec podle algoritmu kódování a dekódujete, tedy převedete na originální hexadecimální řetězec a ten zobrazíte pomocí znaků ' ' a '*'
  • Bitový řetězec začnete zpracovávat a pokud je zpracovávaný bit roven:
    • 0 přenesete následující 4 bity do výstupu
    • 1 načtete 4 bity posunutí a 2 bity délky, délku zvětšíte o 2 a na výstup si zkopírujete tolik nibble kolik je délka z offset již zpracovaných hexa hodnot

• K otestování správné činnosti můžete zkusit rozbalit následující řetězec, který jsme získali kompresí úvodního obrázku:

18E040632C58874E00
12

• Příklad spuštění dekomprese a získání obrázku krysy od Banksyho (odkaz na banksy.txt):

python3 lz77.py <banksy.txt