Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-12-05 16:44:13.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	huffman.in, huffman.out	Sursă	Arhiva Educationala
Autor	Arhiva Educationala	Adăugată de	Gavrila Vlad •GavrilaVlad
Timp execuţie pe test	0.5 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Coduri Huffman

Se dă un alfabet A 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).

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ă L.

Date de intrare

Fişierul de intrare huffman.in va conţine pe prima linie numărul natural N. Pe următoarele N linii se vor afla elementele şirului V, în ordine crescătoare.

Date de ieşire

În fişierul de ieşire huffman.out se va afişa pe prima linie lungimea minima L a textului T'. Pe următoarele N linii se vor afişa 2 numere naturale caracterizând elementele şirului B: lungimea fiecărui cod şi reprezentarea sa în baza 10.

Restricţii

1 ≤ N ≤ 1 000 000.
1 ≤ V_k ≤ 100 000 000.
1 ≤ L ≤ 10¹⁸.
B_i ≤ 10¹⁸, 1 ≤ i ≤ N.
Soluţia nu este unică; poate fi afişată orice soluţie ce duce la o lungime L minimă.

Exemplu

huffman.in	huffman.out
7 1 2 2 5 5 9 10	86 4 2 4 3 3 0 3 6 3 7 2 1 2 2

Explicaţie

Caracterelor le-au fost atribuite codurile astfel:

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

Lungimea totală a textului T' este 86.

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 valoarile 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.

Etape de rezolvare

O soluţie în care căutarea celor 2 noduri de cost minim se face liniar are o complexitate O(N²) ş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 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 obţine 100 de puncte.