Vaqt murakkabligi
O(n · W)
DEFLATE — gzip, ZIP va PNG formatlari ichida ishlatiladigan ma'lumotlarni yo'qotishsiz siqish algoritmi. Bu bitta usul emas, balki ushbu saytda alohida o'rganish mumkin bo'lgan ikkita g'oyani birlashtiruvchi jarayon: LZ77 lug'at orqali mosliklarni qidirish va Huffman kodlash.
Qanday ishlaydi:
1. LZ77 skanerlash — siljiydigan oyna ichida takrorlanuvchi matn qismlarini topish va (siljish, uzunlik, keyingi belgi) tokenlarini yaratish
2. Belgilar oqimi — ushbu tokenlarni belgilar ketma-ketligiga aylantirish (moslik belgilari + literallar)
3. Huffman kodlash — ko'proq uchraydigan belgilar uchun qisqaroq bit kodlarini yaratish
4. Bitlar oqimi — har bir belgini uning kodi bilan almashtirish; so'ng gzip oqimga sarlavha va nazorat summasini qo'shadi
Nima uchun ishlaydi:
LZ77 «bu iborani avval aytganman» ko'rinishidagi takrorlanishlarni yo'q qiladi. Huffman esa «ayrim belgilar kam uchraydi» ko'rinishidagi ortiqchalikni kamaytiradi. Ular birgalikda ham takrorlanuvchi tuzilmani, ham belgilar chastotasidagi notekislikni siqadi. Odatdagi matnlar va veb-resurslarda bu usullarni alohida qo'llashdan ancha samaraliroq.
Vaqt murakkabligi:
Asosan mosliklarni qidirishga bog'liq: sodda usulda O(n · W), haqiqiy gzip'da hash zanjirlari va kechiktirilgan moslashtirish yordamida ancha tezroq
Huffman bosqichi: O(k log k), bu yerda k — blokdagi turli belgilar soni
Xotira murakkabligi: O(W + k) — siljiydigan oyna va kod jadvallari uchun
Xususiyatlari:
- Bloklar asosida ishlaydigan, ma'lumotlarni yo'qotishsiz siqish algoritmi (RFC 1951)
- gzip (RFC 1952), zlib, ZIP va PNG IDAT formatlarida ishlatiladi
- Haqiqiy implementatsiyalarda statik yoki dinamik Huffman daraxtlari hamda alohida masofa kodlari ishlatiladi — ushbu sahifa RFC'ning barcha tafsilotlarini emas, balki umumiy jarayonni tushuntiradi
- Eslab qolish uchun qulay model: avval lug'at, keyin entropik kodlash
Agar faqat bitta jumlani eslab qolsangiz: gzip asosan DEFLATE'dan iborat, DEFLATE esa LZ77 orqali Huffman kodlashga uzatiladigan ma'lumotlar jarayonidir.
O'xshash algoritmlar
Ko'p beriladigan savollar
- DEFLATE nima?
- DEFLATE — gzip, ZIP va PNG formatlari ichida ishlatiladigan ma'lumotlarni yo'qotishsiz siqish algoritmi. Bu bitta usul emas, balki ushbu saytda alohida o'rganish mumkin bo'lgan ikkita g'oyani birlashtiruvchi jarayon: LZ77 lug'at orqali mosliklarni qidirish va Huffman kodlash.
- DEFLATE murakkabligi qanday?
- Xotira: O(W + k)
- Ushbu DEFLATE vizualizatori kimlar uchun?
- DEFLATE vizualizatsiyasi "Siqish" kategoriyasida yuqori darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- DEFLATE ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Siqish) quyidagilarni ko'rishingiz mumkin: Run-Length Encoding, LZ77, LZW. Har biri interaktiv vizualizatsiyaga ega.