Implementace databázových systémů/HuffmanSandbox

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

kódujeme zprávu "aa bb"

0. začneme stromem s jedním speciálním vrcholem

?(0)

1. kódujeme první znak zprávy a, vypíšeme kód spec.uzlu ? (prázdný řetězec) následovaný definicí znaku a, vložíme do stromu a aktualizujeme frekvence ve stromu

  • Input: aa bb
  • Output: a
  • OutBin: 000
  (1)
 0/ \1
?(0) a(1)

2. kódujeme další a, pouze vypíšeme jeho kód a aktualizujeme frekvence ve stromu

  • Input: aa bb
  • Output: a1
  • OutBin: 0001
  (2)
 0/ \1
?(0) a(2)

3. kódujeme "mezeru", vypíšeme kód spec.uzlu ? (0) a definici znaku "mezera", vložíme do stromu a aktualizujeme frekvence ve stromu (žádné výměny nejsou potřeba)

  • Input: aa_bb
  • Output: a10_
  • OutBin: 00010001
    (3)
   0/ \1
  (1) a(2)
 0/ \1
?(0) _(1)

4. kódujeme b, vypíšeme kód ? (00) a definici b, vložíme do stromu a aktualizujeme frekvence ve stromu (žádné výměny nejsou potřeba)

  • Input: aa bb
  • Output: a10 00b
  • OutBin: 0001000100010
      (4)
     0/ \1
    (2) a(2)
   0/ \1
  (1) _(1)
 0/ \1
?(0) b(1)

5. kódujeme další b, vypíšeme kód b a aktualizujeme frekvence ve stromu -> porušíme sourozeneckou vlastnost, musíme prohodit uzly na úrovni před kořenem a dokončíme aktualizaci frekvencí

  • Input: aa bb
  • Output: a10 00b001
  • OutBin: 0001000100010001
      (4)
     0/ \1
    (2) a(2)
   0/ \1
  (1) _(1)
 0/ \1
?(0) b(2)

      (4)
     0/ \1
    (3) a(2)
   0/ \1
  (1) b(2)
 0/ \1
?(0) _(1)

      (5)
     0/ \1
   a(2) (3)
       0/ \1
     (1) b(2)
    0/ \1
  ?(0) _(1)