Pengodean Huffman
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.
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.