Vaqt murakkabligi
Eng yaxshi: O(n log n)
O'rtacha: O(n log n)
Eng yomon: O(n log n)
Huffman kodlash — ma’lumotlarni yo‘qotishsiz siqish uchun mo‘ljallangan ochko‘z algoritm. U ko‘p uchraydigan belgilarga qisqaroq, kam uchraydigan belgilarga esa uzunroq ikkilik kodlarni tayinlaydi. Natijada ma’lumotlarni ifodalash uchun kerak bo‘ladigan umumiy bitlar soni kamayadi.
Qanday ishlaydi:
1. Har bir belgi necha marta uchrashini hisoblash
2. Har bir belgi uchun bittadan barg tugun yaratish va ularni minimal ustuvorlik navbatiga joylashtirish
3. Eng kichik chastotaga ega ikkita tugunni navbatdan olib, chastotalari yig‘indisiga teng qiymatli yangi ota tugun ostida birlashtirish
4. Bitta tugun qolganda, uni daraxtning ildizi sifatida ishlatish
5. Daraxt bo‘ylab yurib kodlarni tayinlash: chapga = 0, o‘ngga = 1
Nima uchun ishlaydi:
Hech bir kod boshqa kodning prefiksi bo‘lmaydi, shu sababli kodlangan bitlar oqimini bir ma’noda dekodlash mumkin. Ochko‘z birlashtirish berilgan chastotalar uchun optimal prefiks kodni kafolatlaydi.
Vaqt murakkabligi:
Eng yaxshi: O(n log n)
O‘rtacha: O(n log n)
Eng yomon: O(n log n)
Xotira murakkabligi: O(n)
Xususiyatlari:
- Yo‘qotishsiz: asl ma’lumotlar aynan avvalgi holatida tiklanadi
- Chastotalar taqsimoti ma’lum bo‘lganda prefiks kodlar orasida optimal hisoblanadi
- DEFLATE (ZIP, gzip, PNG), JPEG va MP3 formatlarida qo‘llaniladi
Ushbu algoritm 1952-yilda MIT talabasi bo‘lgan Devid A. Huffman tomonidan ixtiro qilingan. U hozirgi zamonaviy ma’lumotlarni siqish texnologiyalarining asosiy usullaridan biri bo‘lib qolmoqda.
O'xshash algoritmlar
Ko'p beriladigan savollar
- Huffman kodlash nima?
- Huffman kodlash — ma’lumotlarni yo‘qotishsiz siqish uchun mo‘ljallangan ochko‘z algoritm. U ko‘p uchraydigan belgilarga qisqaroq, kam uchraydigan belgilarga esa uzunroq ikkilik kodlarni tayinlaydi. Natijada ma’lumotlarni ifodalash uchun kerak bo‘ladigan umumiy bitlar soni kamayadi.
- Huffman kodlash murakkabligi qanday?
- Vaqt (o'rtacha): O(n log n) · Xotira: O(n)
- Ushbu Huffman kodlash vizualizatori kimlar uchun?
- Huffman kodlash vizualizatsiyasi "Siqish" kategoriyasida yuqori darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Huffman kodlash ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Siqish) quyidagilarni ko'rishingiz mumkin: Run-Length Encoding, LZ77, LZW. Har biri interaktiv vizualizatsiyaga ega.