CAP.1 NOŢIUNI DE CODARE A SURSELOR................................................................1
1.1 Noţiuni introductive.............................................................................................1
1.1.1 Terminologie..............................................................................................1
1.1.2 Modelul unui sistem de transmisie a informaţiei ...........................................2
1.2 Măsura informaţiei în semnale discrete.........................….....................................3
1.3 Codarea surselor pentru canale fără perturbaţii......................................................9
1.3.1 Coduri unic decodabile............................................................................10
1.3.2 Lungimea medie a unui cuvânt de cod......................................................12
1.3.3 Capacitatea, eficienţa şi redundanţa codului..............................................15
1.3.4 Coduri absolut optimale ..........................................................................17
1.3.5 Codarea simbol cu simbol........................................................................18
1.3.6 Codarea binară a lui Huffman...................................................................19
1.3.7 Procedeul de codare Huffman generalizat..................................................24
CAP.2 COMPRESII DE DATE..........................................................................................27
2.1 Compresia Shannon-Fano ..................................................................................27
2.2 Codarea aritmetica..............................................................................................28
2.3 Compresia prin substitutie....................................................................................28
2.3.1 Familia LZ78............................................................................................29
2.3.2 Familia LZ77............................................................................................30
2.4 Compresia Huffman............................................................................................31
2.4.1 Algoritmul Huffman...................................................................................32
2.4.2 Arbori binari – Huffman............................................................................32
2.4.2.1 Definitia arborilor binari optimi......................................................35
2.4.2.2 Constructia arborilor binari optimi.................................................36
2.4.2.3 Coduri Huffmann..........................................................................36
2.4.3 Coduri unic decodabile Huffman...............................................................38
CAP.3 COMPACTAREA DATELOR PRIN METODE HUFFMAN................................41
3.1 Compactarea datelor folosind arbori Huffman statici............................................41
3.1.1 Introducere...............................................................................................41
3.1.2 Compresia - o cerinţă permanentă ............................................................41
3.1.3 Algoritmul.................................................................................................42
3.1.3.1. Construirea arborelui Huffman......................................................42
3.1.3.2 Compresia....................................................................................44
3.1.3.3 Decompresia................................................................................45
3.1.3.4 Consideraţii finale.........................................................................45
3.2 Compactarea datelor folosind tehnica greedy......................................................47
3.2.1 Algoritmi greedy .....................................................................................47
3.2.2 Tehnica greedy........................................................................................47
3.2.3 Coduri Huffman prin metoda greedy........................................................49
3.2.4 Euristica greedy.......................................................................................51
CAP.4 PROGRAM...........................................................................................................53
Concluzii................................................................................................................77
Bibliografie........................................................................................................................79