== include(page="template/taskheader" task_id="huffman") ==
Codurile Huffman reprezintă o tehnică foarte eficientă pentru compactarea datelor, spaţiul economisit fiind adesea cuprins între $20%$ şi $90%$. Algoritmul greedy pentru realizarea acestei codificări înregistrează frecvenţele de apariţie ale fiecărui simbol dintr-un fişier text, după care utilizează o modalitate optimă pentru reprezentarea fiecărui simbol sub forma unui şir binar.
'Codurile Huffman':http://en.wikipedia.org/wiki/Huffman_coding reprezintă o tehnică foarte eficientă de compactare a datelor, spaţiul economisit fiind cuprins adesea între $20%$ şi $90%$. Algoritmul greedy pentru realizarea acestei codificări înregistrează frecvenţele de apariţie ale fiecărui simbol dintr-un fişier, după care utilizează o modalitate optimă pentru reprezentarea fiecărui simbol sub forma unui şir binar.
Astfel, se dă un alfabet $A = {a{~1~},a{~2~},...,a{~n~}}$ format din $n$ caractere. Numim cod binar un şir de cifre de $0$ şi $1$ de o lungime finită. Fie $B$ un şir de lungime $n$ de coduri binare cu proprietatea că niciun cod $b{~i~}$ nu este prefixul unui alt cod $b{~j~}$ $(i ≠ j)$.
Astfel, se dă o mulţime $A = {a{~1~},a{~2~},...,a{~n~}}$ formată din $n$ simboluri. Numim cod binar un şir de cifre de $0$ şi $1$ de o lungime finită. Fie $B$ un şir de lungime $n$ de coduri binare cu proprietatea că niciun cod $b{~i~}$ nu este prefixul unui alt cod $b{~j~}$ $(i ≠ j)$.
h2. Cerinţă
Ştiindu-se că într-un text $T$ caracterul $a{~i~}$ apare de $v{~i~}$ ori, să se determine un şir $B$ astfel încât înlocuind în textul $T$ fiecare caracter $a{~i~}$ cu codul $b{~i~}$ să se obţină un text $T'$ de lungime minimă $lg$.
Ştiindu-se că într-un text $T$ simbolul $a{~i~}$ apare de $v{~i~}$ ori, să se determine un şir $B$ astfel încât înlocuind în textul $T$ fiecare simbol $a{~i~}$ cu codul $b{~i~}$ să se obţină un text $T'$ de lungime minimă $lg$.
h2. Date de intrare
h2. Date de ieşire
În fişierul de ieşire $huffman.out$ se va afişa pe prima linie lungimea minimă $lg$ a textului $T'$. Pe următoarele $n$ linii se vor afişa câte două numere naturale caracterizând elementele şirului $B$: lungimea fiecărui cod şi reprezentarea sa în baza $10$.
În fişierul de ieşire $huffman.out$ se va afişa pe prima linie lungimea minimă $lg$ a textului $T'$. Pe linia $i$ din următoarele $n$ se vor afişa câte două numere naturale caracterizând elementele şirului $B$: lungimea fiecărui cod şi reprezentarea sa în baza $10$, $b{~i~}$, asociate codului $a{~i~}$.
h2. Restricţii
* $1 ≤ n ≤ 1 000 000$.
* $1 ≤ v{~i~} ≤ 100 000 000, 1 ≤ i ≤ n$.
* $1 ≤ v{~i~} ≤ 100 000 000$.
* $1 ≤ lg ≤ 10^18^$.
* $b{~i~} ≤ 10^18^, 1 ≤ i ≤ n$.
* $b{~i~} ≤ 10^18^, 1 ≤ i ≤ N$.
* Soluţia nu este unică; poate fi afişată orice soluţie ce duce la o lungime $lg$ minimă.
h2. Exemplu
table(example). |_. huffman.in |_. huffman.out |
| 7
| 16
1
1
1
1
1
1
2
2
5
5
9
10
| 86
2
2
2
2
3
4
4
7
| 135
5 18
5 7
5 24
5 19
5 6
5 25
4 6
4 11
4 2
4 3
4 7
4 8
4 10
4 13
3 0
3 6
3 2
3 7
2 1
2 2
|
h3. Explicaţie
!problema/huffman/Huffman_tree_2.svg 50%!
Pentru a materializa exemplul, am atribuit simboluri frecvenţelor date. Arborele Huffman obţinut se poate vedea în figura alăturată. _(Sursa 'wikipedia':http://en.wikipedia.org)_
Simbolurile, împreună cu frecvenţele şi codificările aferente se găsesc în lista următoare (simbol, frecvenţă, codul binar):
Caracterelor le-au fost atribuite codurile astfel:
!> problema/huffman?Huffman_tree_2.png 65%!
table(example). |_. Numar de apariţii |_. Lungime |_. Cod binar |_. Lungime totală |
| 1 | 4 | 0010 | 4 |
| 2 | 4 | 0011 | 8 |
| 2 | 3 | 000 | 6 |
| 5 | 3 | 110 | 15 |
| 5 | 3 | 111 | 15 |
| 9 | 2 | 01 | 18 |
| 10 | 2 | 10 | 20 |
* $space, 7, 111$
* $a, 4, 010$
* $e, 4, 000$
* $f, 3, 1101$
* $h, 2, 1010$
* $i, 2, 1000$
* $m, 2, 0111$
* $n, 2, 0010$
* $s, 2, 1011$
* $t, 2, 0110$
* $l, 1, 11001$
* $o, 1, 00110$
* $p, 1, 10011$
* $r, 1, 11000$
* $u, 1, 00111$
* $x, 1, 10010$
Lungimea totală a textului $T'$ este $86$.
Lungimea totală a textului $T'$ este $135$, valoare ce se obţine însumând valorile tuturor nodurilor interne, adică cele albastre.
h2. Soluţie
Problema se rezolvă printr-un algoritm greedy, codarea Huffman. Se pot considera cele $N$ caractere noduri într-un graf, având fiecare un cost egal cu numărul de apariţii al caracterului în textul $T$. La fiecare pas se creeaza un nod nou şi se duc de la acesta $2$ muchii către nodurile de cost minim care nu au fost încă unite, costul acestuia fiind egal cu suma costurilor celor $2$ fii. Pentru a putea reconstitui ulterior codurile, se asociaza celor $2$ muchii valorile $0$ şi $1$. Se va obţine un arbore binar cu $2*N-1$ noduri, suma costurilor nodurilor interne fiind egală cu lungimea textului $T'$.
Algoritmul se poate generaliza pentru coduri in baza $K$, selectand la fiecare pas cele mai mici K noduri pentru a le uni cu nodul nou creat. De asemenea, trebuie create caractere fictive cu $0$ aparitii, pentru ca numărul iniţial de noduri să fie de forma $X * (K-1) + 1$.
Problema se rezolvă printr-un algoritm greedy, 'codarea Huffman':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap17.htm. Se pot considera cele $n$ simboluri noduri într-un graf, având fiecare un cost egal cu numărul de apariţii al simbolului în textul $T$. La fiecare pas se creează un nod nou şi se duc de la acesta două muchii către nodurile cu costul minim care nu au fost încă unite, costul acestuia fiind egal cu suma costurilor celor doi fii. Pentru a putea reconstitui ulterior codurile, se asociaza celor două muchii valorile $0$, spre stânga, şi $1$, spre dreapta. Se va obţine un arbore binar cu $2*n-1$ noduri, suma costurilor nodurilor interne fiind egală cu lungimea textului $T'$.
Algoritmul se poate generaliza pentru coduri in baza $K$, selectând la fiecare pas cele mai mici $K$ noduri pentru a le uni cu nodul nou creat. De asemenea, trebuie create caractere fictive cu $0$ apariţii, pentru ca numărul iniţial de noduri să fie de forma $X * (K-1) + 1$.
h3. Etape de rezolvare
O 'soluţie':job_detail/370657?action=view-source în care căutarea celor $2$ noduri de cost minim se face liniar are o complexitate $O(N^2^)$ şi obţine $30$ de puncte. Folosind un heap pentru a extrage nodurile de cost minim, complexitatea scade la $O(N log{~2~} N)$. Această 'soluţie':job_detail/370924?action=view-source obţine $70$ de puncte. În cazul în care costurile nodurilor sunt date în ordine crescătoare, se pot ţine $2$ cozi, conţinând nodurile iniţiale, respectiv nodurile interne. Observând că nodurile sunt sortate crescător după cost, se pot extrage cele $2$ minime şi introduce nodul nou în $O(1)$. Această 'soluţie':job_detail/370923?action=view-source obţine $100$ de puncte.
O 'soluţie':job_detail/370657?action=view-source în care căutarea celor două noduri de cost minim se face liniar are o complexitate $O(N^2^)$ şi obţine $30$ de puncte. Folosind un 'heap':problema/heapuri pentru a extrage nodurile de cost minim, complexitatea scade la $O(N log{~2~} N)$. Această 'soluţie':job_detail/370924?action=view-source obţine $70$ de puncte. În cazul în care costurile nodurilor sunt date în ordine crescătoare, se pot ţine două cozi, conţinând nodurile iniţiale, respectiv nodurile interne. Observând că nodurile sunt sortate crescător după cost, se pot extrage cele două minime şi introduce nodul nou în $O(1)$. Această 'soluţie':job_detail/370923?action=view-source obţine $100$ de puncte.
h2. Probleme propuse
'Fence repair':http://acm.pku.edu.cn/JudgeOnline/problem?id=3253 - PKU
'Aviamachinations':http://acm.sgu.ru/problem.php?contest=0&problem=323 - SGU
'Hyperhuffman':http://acm.sgu.ru/problem.php?contest=0&problem=203 - SGU
'Scandura':problema/scandura
* 'Fence repair':http://acm.pku.edu.cn/JudgeOnline/problem?id=3253, pku
* 'Hyperhuffman':http://acm.sgu.ru/problem.php?contest=0&problem=203, sgu
* 'Scandura':problema/scandura
* 'K1':problema/k1
== include(page="template/taskfooter" task_id="huffman") ==
