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

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)