Dalam ilmu komputer dan teori informasi, Huffman coding adalah sebuah tipe code yang optimal yang biasanya digunakan untuk lossless data compression. Algoritma Huffman Coding ditemukan oleh David A. Huffman pada saat ia masih seorang mahasiswa di MIT, ia menerbitkan karyanya pada tahun 1952 yang berjudul "A Method for the Construction of Minimum Redundancy Codes".
Hasil dari algoritma Huffman bisa dipandang sebagai sebuah tabel kode variabel-panjang untuk pengkodean simbol sumber (seperti sebuah karakter dalam sebuah file). Algoritme ini memperoleh dari tabel tersebut berdasarkan dari estimasi probabilitas atau frekuensi munculnya untuk setiap nilai yang mungkin dari simbol sumber. Seperti dalam metode pengkodean entropi lainnya, simbol yang lebih umum diwakili dengan bit yang lebih sedikit daripada simbol kurang umum.
| Karakter | Frekuensi | Kode |
|---|---|---|
| (spasi) | 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 |
Sejarah
Pada tahun 1951, David A. Huffman dan mahasiswa sekelasnya di teori informasi MIT diberikan pilihan untuk membuat makalah atau mengerjakan ujian akhir. Topik untuk makalah tersebut yang diberikan oleh profesor kelas itu, Robert M. Fano, adalah pencarian kode biner yang paling efisien. Huffman, yang tidak mampu untuk membuktikan kode mana yang paling efisien, hampir menyerah dan sudah mau memutuskan untuk mengambil ujian akhir-nya saja saat tiba-tiba ia terpikir sebuah ide untuk menggunakan algoritma pohon biner yang diurutkan berdasarkan frekuensi. Dengan cepat, ia langsung membuktikan kepada profesornya bahwa metode tersebut adalah metode yang paling efisien.
Referensi
- D.A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., September 1952, pp 1098–1102. Huffman's original article.
- Ken Huffman. Profile: David A. Huffman, Scientific American, September 1991, pp. 54–58
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 16.3, pp. 385–392.