Vaqt murakkabligi
Eng yaxshi: O(n)
O'rtacha: O(n)
Eng yomon: O(n)
LZW (Lempel–Ziv–Welch) — bu 1984-yilda Terri Uelch tomonidan e’lon qilingan, lug‘atga asoslangan adaptiv siqish algoritmi. Kodlovchi va dekodlovchi ma’lumotlar oqimi asosida bir xil lug‘atni ishlash jarayonida yaratadi — alohida lug‘atni uzatish talab qilinmaydi.
Qanday ishlaydi:
1. Lug‘atni bittadan belgidan iborat barcha satrlar bilan boshlash
2. Joriy w iborasini saqlab borish (dastlab bo‘sh)
3. Har bir keyingi c belgisi uchun:
- Agar w+c lug‘atda mavjud bo‘lsa, w = w+c deb belgilash
- Aks holda, w uchun kodni chiqarish, w+c ni lug‘atga qo‘shish va w = c deb belgilash
4. Oxirgi belgidan so‘ng qolgan w iborasi uchun kodni chiqarish
Nima uchun ishlaydi:
Takrorlanadigan iboralar qisqa butun sonli kodlarga ega bo‘ladi. Uzunroq iboralar lug‘atga avtomatik ravishda qo‘shilib boradi. Dekodlovchi kodlovchining amallarini takrorlaydi: qabul qilingan har bir kod satrga aylantiriladi va hali uchramagan keyingi ibora xuddi shu qoida asosida lug‘atga qo‘shiladi. Shu tariqa ikkala tomon hamohang ishlaydi.
Vaqt murakkabligi:
Eng yaxshi: O(n)
O‘rtacha: O(n)
Eng yomon: O(n), xesh-lug‘atdan foydalanilganda
Xotira murakkabligi: O(d), bu yerda d — lug‘atdagi yozuvlar soni
Xususiyatlari:
- Yo‘qotishsiz adaptiv lug‘at kodlashi
- Tarixan GIF va Unix compress formatlarida ishlatilgan
- Oldindan chastotalarni tahlil qilishni talab qilmaydi
- Oqimli formatlarda lug‘atning o‘sishini cheklash mumkin (kod uzunligini belgilangan qiymatda saqlash orqali)
LZW o‘sib boruvchi kodlar jadvali takrorlanuvchi tuzilmalarni manba ma’lumotlari uchun alohida model talab qilmasdan, qisqaroq butun sonli kodlarga qanday aylantirishini ko‘rsatadi.
O'xshash algoritmlar
Ko'p beriladigan savollar
- LZW nima?
- LZW (Lempel–Ziv–Welch) — bu 1984-yilda Terri Uelch tomonidan e’lon qilingan, lug‘atga asoslangan adaptiv siqish algoritmi. Kodlovchi va dekodlovchi ma’lumotlar oqimi asosida bir xil lug‘atni ishlash jarayonida yaratadi — alohida lug‘atni uzatish talab qilinmaydi.
- LZW murakkabligi qanday?
- Vaqt (o'rtacha): O(n) · Xotira: O(d)
- Ushbu LZW vizualizatori kimlar uchun?
- LZW vizualizatsiyasi "Siqish" kategoriyasida o'rta darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- LZW ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Siqish) quyidagilarni ko'rishingiz mumkin: Run-Length Encoding, LZ77, Huffman Coding. Har biri interaktiv vizualizatsiyaga ega.