|
Toshkent axborot texnologiyalar universiteti
|
| Sana | 13.05.2024 | | Hajmi | 40,73 Kb. | | #229881 |
Bog'liq 1-Mustaqil ish 1, Документ Microsoft Office Word (2), Папка номеклатура, 1 чи ўринбосар иш режа КПЙ март ой, Конимех туман март ва апрел ойида иш ўрни, Algoritmlarni loyihalash fanidan 1-topshiriq, Algoritmlarni loyihalash fanidan 2-topshiriq, Малумот, 1-Mustaqil ish , 2-Mustaqil ish , Chaqiruv qog`ozi-380211102988 (1), Аҳоли бандлиги масаласи 06 05 2024 йил , Документ Microsoft Word (6) (2), Конимех тумани
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALAR UNIVERSITETI
Axborot va kodlash nazariyalari fanidan
1-Mustqail ish
Bajardi: Isakov R.B.
Guruh: 042-21 STo‘
Tekshirdi: Djabbarov Shuxrat Yuldashevich
Toshkent 2024
Mavzu: Siqish algoritmi asosida ma’lumotlarni siqish usullarining samaradorligini hisoblash
Reja:
1. Siqish algoritmi
2. Siqish dasturlari
LZ algoritmi asosida ma’lumotlarni siqish usullarining samaradorligini hisoblash.
Lempel – Ziva algoritmlarini iboralar bo’yicha arxivlovchi algoritmlar deyiladi, chunka ushbu algoritmlarda axborotdagi iboralar yoki xarflar birlashmasi uzidan olidinrok kaytarilgan xuddui shunday ibora yeki xarflar birlashmasi bilan almashtirishga asoslangan. Iboralar bo’yicha yo’qotishsiz arxivlovchi algoritmlarni ayrim adabiyotlarda jadval asosida arxivlovchi algoritmlar ham deyiladi. Ushbu algoritmlarni asoschilari Yakoba Ziva (Jakob Ziv) va Abraxam Lempel (Abraham Lempel) xisoblanadi. Iboralar buycha arxivlovchi algoritmlar dastlabkisi 1977 yilda paydo bo’ldi va ushbu algoritmnig nomi LZ77 deb nomlangan. Keyinchalik bir yildan so‘ng ushbu algoritmning modifikatsiyalangan varianti yaratildi va algoritm nomi LZ78 deb atala boshlandi.
Masalan ushbu axborotni kodlashtirish talab qilsin "aaabbabaabaaabab". Ushbu axborotni jadval 4.1 ko’rsatilganidek yettita mayda iboralarga (xarflar birlashmasi) bo’lamiz. Axborotdagi har bir xarf yoki iboralar (harflar birlashmasi) o’zidan oldin qaytarilgan iboralar (xarflar birlashmasi) va kushuv mavjud bo`lgan belgi bilan kodlanadi. Masalan, oxirgi uchta belgi 4 ("b") iborasi sifatida kodlshtiriladi. Jadval 4.1 LZ78 algoritmi yordamida "aaabbabaabaaabab" axborotni kodlashtirish natijalari keltirilgan.
|
Axborotni iboralarga bo’lish
|
a
|
aa
|
b
|
ba
|
baa
|
baaa
|
bab
| |
Raqamlarga ajratish
|
1
|
2
|
3
|
4
|
5
|
6
|
7
| |
Natija
|
(0,a)
|
(1,a)
|
(0,b)
|
(3,a)
|
(4,a)
|
(5,a)
|
(4,b)
|
Xozirgi kunga kelib LZ oilasiga mansub bo`lgan algoritmlar ichida eng samarali usullaridan biri bu LZSS algoritmi hisoblanadi. Ushbu algoritm 1982 yilda Storer va Jimanskilar tomonidan LZ77 algoritmini modifikatsiyalash natijasida paydo bo’ldi. Ushbu algoritm vositasida axboroni kodlashtirilsa siqish koeffitsientining qiymati bir necha marta katta. LZSS algoritmi vositasi axborotni kodlashtirshga misol sifatida quyidagi N=30 ta belgilar ketma-ketligini olamiz:
«АВААDDDDDBAABAACCCCEAFFFFDAAAA»
Ma'lumotlarni siqish, odatda kodlash usullaridan foydalangan holda ma'lum bir ma'lumotni saqlash yoki uzatish uchun zarur bo'lgan ma'lumotlar miqdorini kamaytirish jarayoni. Siqish raqamli texnologiyadan oldin paydo bo'lgan bo'lib, Morze kodida eng keng tarqalgan belgilarga eng qisqa kodlarni tayinlagan va ovoz uzatishda yuqori chastotalarni to'xtatuvchi telefoniyada ishlatilgan. Bugungi kunda, siqilmagan raqamli tasvir uchun 20 megabayt kerak bo'lganda, ma'lumotlarni siqish kompyuter disklarida raqamli ma'lumotlarni saqlash va uni aloqa tarmoqlari orqali uzatishda muhim ahamiyatga ega.
Axborot 0 va 1 lar yoki bitlar (ikkilik raqamlar) namunasi sifatida raqamli kodlangan. To'rt harfli alifbo ( a , e , r , t ) agar barcha belgilar bir xil ehtimolga ega bo'lsa, har bir belgi uchun ikkita bit kerak bo'ladi. "Kalamush choyda tort yedi" jumlasidagi barcha harflarni 2 × 18 = 36 bit bilan kodlash mumkin. Ushbu matnda a eng tez-tez uchraydi , t ikkinchi eng keng tarqalgan bo'lib, o'zgaruvchan uzunlikdagi ikkilik kodni tayinlash - a : 0, t : 10, r : 110, e : 111 - faqat 32 bitli siqilgan xabarga olib keladi . Ushbu kodlash muhim xususiyatga ega, chunki hech qanday kod boshqasining prefiksi emas. Ya'ni, harf kodlarini ajratish uchun qo'shimcha bitlar talab qilinmaydi: 010111 t e sifatida bir ma'noda dekodlanadi .
Ma'lumotlarni siqish yo'qotishsiz (aniq) yoki yo'qolgan (noaniq) bo'lishi mumkin. Yo'qotmasdan siqish asl ma'lumotni olish uchun qaytarilishi mumkin, yo'qolgan siqilish esa tafsilotlarni yo'qotadi yoki teskari o'zgartirilganda kichik xatolarga olib keladi. Yo'qotmasdan siqish matn uchun zarur, bunda har bir belgi muhim, yo'qotuvchi siqilish esa tasvirlar yoki ovoz uchun maqbul bo'lishi mumkin (telefoniyadagi chastota spektrining cheklanishi yo'qolgan siqilish misolidir).
Umumiy ma'lumotlar uchun eng keng tarqalgan uchta siqish dasturlari Zip (Windows operatsion tizimidan foydalanadigan kompyuterlarda), StuffIt (Apple kompyuterlarida) va gzip (UNIX bilan ishlaydigan kompyuterlarda); barchasi yo'qotishsiz siqishni ishlatadi.
Statik tasvirlarni siqishning keng tarqalgan formati, ayniqsa Internet orqali namoyish qilish uchun, GIF (grafik almashish formati) bo'lib, u ham yo'qotmaydi, bundan tashqari uning tasvirlari 256 rang bilan cheklangan. JPEG formatlash standarti (fotografik ekspertlar qo'shma guruhi) bilan ranglarning kengroq diapazoni ishlatilishi mumkin, u ham yo'qotishsiz, ham yo'qotuvchi usullardan foydalanadi, shuningdek, videolar uchun MPEG (harakatlanuvchi tasvirlar bo'yicha ekspertlar guruhi) standartlari.
Siqish dasturlari ishlashi uchun ular belgilar, so'zlar yoki boshqa elementlarning taqsimlanishini tavsiflovchi ma'lumotlar modeliga ega bo'lishi kerak, masalan, ingliz tilida alohida belgilarning paydo bo'lish chastotasi. Yuqoridagi to'rtta belgili alifboning oddiy misoli kabi qo'zg'almas modellar, ayniqsa, matn jadval ma'lumotlarini o'z ichiga olgan yoki maxsus lug'atdan foydalansa, bitta matnni unchalik yaxshi tavsiflamasligi mumkin. Bunday hollarda matnning o'zidan olingan adaptiv modellar ustun bo'lishi mumkin. Moslashuvchan modellar belgilar yoki so'zlarning taqsimlanishini ular hozirgacha qayta ishlaganlariga qarab baholaydi.
Moslashuvchan modellashtirishning muhim xususiyati shundan iboratki, agar siqish va dekompressiya dasturlari modelni shakllantirish uchun aynan bir xil qoidalardan va uning elementlariga tayinlangan bir xil kodlar jadvalidan foydalansa, modelning o'zi dekompressiya dasturiga yuborilishi shart emas. Misol uchun, agar siqishni dasturi uchinchi marta ko'rilganda keyingi mavjud kodni bersa, dekompressiya xuddi shu qoidaga amal qiladi va bu kodni ikkinchi marta paydo bo'lganidan keyin kutadi .
Kodlash alohida belgilar yoki so'zlar bilan ishlashi mumkin. Huffman kodlari statik modeldan foydalanadi va to'rt harfli alifboda ilgari tasvirlangan kodlarni yaratadi. Arifmetik kodlash belgilar qatorlarini haqiqiy sonlar diapazonlari sifatida kodlaydi va deyarli optimal kodlarga erishadi. Bu Huffman kodlashiga qaraganda sekinroq, lekin moslashuvchan modellar uchun mos keladi. Run-length encoding (RLE) takrorlanuvchi ma'lumotlar uchun yaxshi bo'lib, uni hisoblash va takroriy elementning bir nusxasi bilan almashtiradi.
Moslashuvchan lug'at usullari satrlar jadvalini tuzadi va keyin ularni qisqaroq kodlar bilan almashtiradi. Isroillik kompyuter olimlari Abraham Lempel va Jeykob Ziv tomonidan ixtiro qilingan Lempel-Ziv algoritmi matnning o'zidan lug'at sifatida foydalanadi va satrning keyinroq paydo bo'lgan joylarini oldingi va uning uzunligini ko'rsatadigan raqamlar bilan almashtiradi. Zip va gzip Lempel-Ziv algoritmining variatsiyalaridan foydalanadi.
Yo'qotilgan siqish tafsilotlarni olib tashlash orqali ushbu usullarni kengaytiradi. Xususan, raqamli tasvirlar kulrang shkala yoki rangli ma'lumotni ifodalovchi piksellardan iborat. Agar piksel qo'shnilaridan bir oz farq qilsa, uning qiymati ularniki bilan almashtirilishi mumkin, shundan so'ng "tekislangan" tasvirni RLE yordamida siqish mumkin.
Tasvirning katta qismini tekislash yaqqol ko'rinadigan bo'lsa-da, kichik tarqoq qismlarga yoyilganda o'zgarish unchalik sezilmaydi. Eng keng tarqalgan usul diskret kosinus konvertatsiyasidan foydalanadi, bu Furye konvertatsiyasi bilan bog'liq bo'lgan matematik formula bo'lib, tasvirni tasvir sifati uchun turli darajadagi muhimlikdagi alohida qismlarga ajratadi. Ushbu texnika, shuningdek, fraktal texnikalar mukammal siqish nisbatlariga erishishi mumkin. Yo'qotishsiz siqishning ishlashi uning siqilish darajasi bilan o'lchangan bo'lsa, yo'qotilgan siqilish ham u kiritgan xatolik asosida baholanadi. Xatoni hisoblashning matematik usullari mavjud, ammo xatolik o'lchovi ham ma'lumotlardan qanday foydalanishga bog'liq: yuqori chastotali ohanglarni bekor qilish, masalan, og'zaki yozuvlar uchun ozgina yo'qotishlarni keltirib chiqaradi, lekin musiqa uchun qabul qilinishi mumkin bo'lmagan buzilish.
Video tasvirlar faqat ketma-ket kadrlar orasidagi kichik farqlarni saqlash orqali siqilishi mumkin. MPEG-1 CD-ROMlar uchun videoni siqishda keng tarqalgan; shuningdek, musiqani siqish uchun ishlatiladigan MP3 formati uchun asosdir. MPEG-2 - bu DVD disklari ( qarang : ixcham disk: DVD) va ba'zi televizion tarmoq qurilmalari uchun ishlatiladigan yuqoriroq "efir" sifati formati . MPEG-4 "past tarmoqli kengligi" ilovalari uchun mo'ljallangan va World Wide Web (WWW) orqali video translyatsiya qilish uchun keng tarqalgan. (MPEG-3 MPEG-2 ga qo'shildi.) Videoni siqish minimal buzilish bilan 20 dan 1 gacha bo'lgan siqish nisbatlariga erishishi mumkin.
Siqish algoritmlari talab qiladigan vaqt va xotira va ular erishadigan siqilish o'rtasida mutanosiblik mavjud. Ingliz tilidagi matn odatda asl hajmining yarmi yoki uchdan bir qismiga siqilishi mumkin. Tasvirlar ko'pincha 10 dan 20 gacha yoki undan ko'p omillar bilan siqilishi mumkin. Kompyuterning saqlash hajmi va tarmoq tezligining o'sishiga qaramay, ma'lumotlarni siqish tobora kattaroq ma'lumotlar to'plamini saqlash va uzatish uchun muhim vosita bo'lib qolmoqda. Shuningdek, axborot nazariyasiga qarang : Ma'lumotlarni siqish; telekommunikatsiya: manba kodlash.
|
| |
