Vaqt murakkabligi
Eng yaxshi: O(n)
O'rtacha: O(n · W)
Eng yomon: O(n · W)
LZ77 — 1977-yilda Abraham Lempel va Jacob Ziv tomonidan ixtiro qilingan lug‘atga asoslangan siqish algoritmi. U qat’iy kodlar lug‘ati o‘rniga yaqinda uchragan ma’lumotlardan iborat siljuvchi oynani dinamik lug‘at sifatida ishlatadi.
Ishlash tartibi:
1. Qidiruv buferini (allaqachon kodlangan oyna) va oldindan ko‘rish buferini saqlab turadi
2. Oldindan ko‘rish buferidagi oynada ham mavjud bo‘lgan eng uzun prefiksni topadi
3. Uchlik qiymatni chiqaradi (offset, length, next):
- offset — moslik boshlanadigan joygacha orqaga qancha masofa borligi
- length — nusxalanadigan belgilar soni
- next — moslikdan keyin keladigan oddiy belgi (yoki fayl oxirida, EOF da, bo‘sh qiymat)
4. Oynani length + 1 miqdoriga oldinga siljitadi va jarayonni takrorlaydi
Nima uchun ishlaydi:
Takrorlanuvchi iboralar (so‘zlar, naqshlar, qism satrlar) matn va tuzilgan ma’lumotlarda ko‘p uchraydi. Oynadagi oldingi ma’lumotga murojaat qilish uzun ketma-ketlikni qisqa havola bilan ifodalash imkonini beradi. Uchliklar oqimi bir ma’noli dekodlanadi: avval offset bo‘yicha ma’lumot nusxalanadi, so‘ng oddiy belgi qo‘shiladi.
Vaqt murakkabligi:
Eng yaxshi: O(n) — siljuvchi xeshlar yoki ilg‘or moslik qidirish algoritmlari bilan
O‘rtacha: O(n · W) — sodda qidiruvda (W = oyna hajmi)
Eng yomon: O(n · W)
Xotira murakkabligi: O(W) — oyna uchun
Xususiyatlari:
- Siljuvchi oynadan foydalanadigan yo‘qotishsiz lug‘at usuli
- DEFLATE algoritmining asosi (gzip, ZIP, PNG); u LZ77 va Huffman kodlashni birlashtiradi
- Oyna hajmi siqish darajasi, xotira sarfi va qidiruv xarajatlari o‘rtasidagi muvozanatni belgilaydi
- Takrorlanuvchi qism satrlarni yaxshi siqadi; sof tasodifiy ma’lumotlar esa siqilmaydi
LZ77 «yaqindagi takrorlarni izlash» g‘oyasini kundalik hayotda ishlatiladigan ko‘plab yo‘qotishsiz arxivlash formatlarining amaliy asosiga aylantirdi.
O'xshash algoritmlar
Ko'p beriladigan savollar
- LZ77 nima?
- LZ77 — 1977-yilda Abraham Lempel va Jacob Ziv tomonidan ixtiro qilingan lug‘atga asoslangan siqish algoritmi. U qat’iy kodlar lug‘ati o‘rniga yaqinda uchragan ma’lumotlardan iborat siljuvchi oynani dinamik lug‘at sifatida ishlatadi.
- LZ77 murakkabligi qanday?
- Vaqt (o'rtacha): O(n · W) — sodda qidiruvda (W = oyna hajmi) · Xotira: O(W)
- Ushbu LZ77 vizualizatori kimlar uchun?
- LZ77 vizualizatsiyasi "Siqish" kategoriyasida o'rta darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- LZ77 ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Siqish) quyidagilarni ko'rishingiz mumkin: Run-Length Encoding, LZW, Huffman Coding. Har biri interaktiv vizualizatsiyaga ega.