Vaqt murakkabligi
Eng yaxshi: O(n)
O'rtacha: O(n)
Eng yomon: O(n)
Run-Length Encoding (RLE) — bu ma’lumotlarni yo‘qotishsiz siqishning oddiy algoritmi. U bir xil belgining ketma-ket takrorlanishlarini bitta (belgi, soni) juftligi bilan almashtiradi.
Algoritm qanday ishlaydi:
1. Kiruvchi ma’lumotlarni chapdan o‘ngga qarab ko‘rib chiqish
2. Yangi belgi paydo bo‘lganda, yangi ketma-ketlikni boshlash
3. Keyingi belgilar bir xil ekan, ularni sanashni davom ettirish
4. (Belgi, soni) juftligini chiqarish va ketma-ketlikdan keyingi qismni qayta ishlash
Nima uchun bu ishlaydi:
Bir xil qiymatlarning uzun ketma-ketliklarini oddiy usulda saqlash ko‘p joy egallaydi. Ularning uzunligini bir marta kodlash ortiqcha takrorlanishni bartaraf etadi. Dekodlash esa buning teskarisi: har bir juftlik belgi nusxalarining ko‘rsatilgan soniga kengaytiriladi.
Vaqt murakkabligi:
Eng yaxshi holat: O(n)
O‘rtacha holat: O(n)
Eng yomon holat: O(n)
Xotira murakkabligi: O(k), bu yerda k — ketma-ketliklar soni
Xususiyatlari:
- Belgilar va ularning soni yo‘qotishsiz saqlansa, siqish ham yo‘qotishsiz bo‘ladi
- Siyrak bitmaplar, ikonlar va oddiy grafikalar uchun juda samarali (BMP RLE, PCX, faks tasvirlari)
- Uzun takroriy ketma-ketliklar bo‘lmagan ma’lumotlar hajmini oshirishi mumkin (masalan, ABABAB kabi navbatma-navbat keladigan belgilar)
- Ko‘pincha Huffman yoki arifmetik kodlashdan oldingi birinchi bosqich sifatida ishlatiladi
RLE — hozirgacha o‘rgatiladigan eng qadimgi ma’lumotlarni siqish usullaridan biri. Uni amalga oshirish va vizualizatsiya qilish oson, shuningdek, murakkabroq formatlarning tarkibiy qismi hisoblanadi.
O'xshash algoritmlar
Ko'p beriladigan savollar
- Ketma-ket takrorlanish uzunligini kodlash (Run-Length Encoding) nima?
- Run-Length Encoding (RLE) — bu ma’lumotlarni yo‘qotishsiz siqishning oddiy algoritmi. U bir xil belgining ketma-ket takrorlanishlarini bitta (belgi, soni) juftligi bilan almashtiradi.
- Ketma-ket takrorlanish uzunligini kodlash (Run-Length Encoding) murakkabligi qanday?
- Vaqt (o'rtacha): O(n) · Xotira: O(k)
- Ushbu Ketma-ket takrorlanish uzunligini kodlash (Run-Length Encoding) vizualizatori kimlar uchun?
- Ketma-ket takrorlanish uzunligini kodlash (Run-Length Encoding) vizualizatsiyasi "Siqish" kategoriyasida boshlang'ich darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Ketma-ket takrorlanish uzunligini kodlash (Run-Length Encoding) ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Siqish) quyidagilarni ko'rishingiz mumkin: LZ77, LZW, Huffman Coding. Har biri interaktiv vizualizatsiyaga ega.