|
-rasm Lenpel va Ziv algaritmlar
|
| bet | 3/18 | | Sana | 06.07.2023 | | Hajmi | 8.41 Mb. | | #76409 |
Bog'liq Algoritmlar nazariyasi fanidan mavzu arxivlash algoritmi 1626543488910695 (1), Bajarish kerak, LAFVIN iBot Programming Education Robot Car, Арх cложных веб приложени Laravel ПЕРЕВОД 2020, Raqamli qurilmalarni loyihalashga kirish, Psixodiagnostika va eksperimental psixologiya (Z.Nishanova va b.), Elektromagnit maydon, Kompyuter arxitekturasi 1-amaliy ish, webb mustaqil ish, 11-sinf-adabiyot-2, MB Mustaqil ish, Презентация (1), Bekchanov, 5-maruza1.1-rasm Lenpel va Ziv algaritmlar
Internetda ma'lumotlarni siqish keng tarqalib ketgan va Lempel va Ziv algoritmlari (LZ algoritmlari) ixtiro qilinganidan so'ng, avvalgi siqishni misollarini keltirish mumkin. Morz 1838-yilda o'z kodini ixtiro qilib, ingliz tilida "e" va "t" harflarini eng qisqa tartibda (mos ravishda nuqta va tire) aqlli ravishda tayinladi. 1949 yilda asosiy freymlar paydo bo'lishidan ko'p o'tmay, Shannon-Fano algoritmi ixtiro qilindi, u blokda paydo bo'lishi ehtimoliga qarab ma'lumotlar blokidagi belgilarga kodlar qo'ydi. Blokda belgi paydo bo'lishi ehtimoli kod uzunligiga teskari proportsional edi, bu esa ma'lumotlarning namoyishini siqib chiqarishga imkon berdi. Devid Xuffman Robert Fano bilan birga sinfda talaba bo'lgan va akademik ishchi sifatida ikkilamchi ma'lumotlarni kodlash usulini izlashni tanlagan. Natijada u Shannon-Fano algoritmini takomillashtirishga muvaffaq bo'ldi. Shannon-Fano va Xuffman algoritmlarining oldingi versiyalari oldindan belgilangan kodlardan foydalangan. Keyinchalik buning uchun ular siqish uchun mo'ljallangan ma'lumotlar asosida dinamik ravishda yaratilgan kodlardan foydalanishni boshladilar. 1977-yilda Lempel va Ziv dinamik ravishda yaratilgan lug'atdan foydalanishga asoslangan LZ77 algoritmini nashr etdilar (u "toymasin oyna" deb ham ataladi). 78-yilda ular birinchi bo'lib ma'lumotlarni tahlil qiladigan va lug'at yaratadigan LZ78 algoritmini nashr etdilar, uni dinamik ravishda yaratish o'rniga. LZ77 va LZ78 algoritmlari katta shuhrat qozondi va tuzatuvchilar to'lqinini keltirib chiqardi, ulardan DEFLATE, LZMA va LZX shu kungacha saqlanib qoldi. Eng mashhur algoritmlar LZ77-ga asoslanadi, chunki LZ78 ning LZ78 hosilasi 1984-yilda Unisys tomonidan patentlangan, shundan so'ng ular hamma va barchani, shu jumladan GIF tasvirlaridan foydalanishni ham o'rgana boshlagan. Bu vaqtda, UNIX-da, LZC deb nomlangan LZW algoritmining o'zgarishi ishlatilgan va huquqlar sababli, ulardan foydalanish minimallashtirilishi kerak edi. DEFLATE algoritmi (gzip) va Burroughs-Wheeler transformatsiyasi, BWT (bzip2) afzal ko'rildi. Yaxshi, chunki bu algoritmlar deyarli har doim siqilishda LZW-dan ustun turadi. 2003-yilga kelib, patentning amal qilish muddati tugadi, ammo poezd allaqachon chiqib ketgan va LZW algoritmi saqlangan, ehtimol faqat GIF fayllarida. LZ77-ga asoslangan algoritmlar dominant hisoblanadi. 1993-yilda yana bir patent jangi bo'ldi - Stac Electronics o'zining LZS algoritmini Microsoft tomonidan MS-DOS 6.0 bilan jihozlangan disklarni siqish dasturida ishlatganligini aniqladi. Stac Electronics sudga murojaat qildi va ular sudda g'alaba qozonishga muvaffaq bo'lishdi, natijada ular 100 million dollardan ko'proq pul olishdi.
Har doim ko'payib boradigan ma'lumotlarni saqlash uchun yirik korporatsiyalar siqishni algoritmlaridan foydalangan, ammo algoritmlarning haqiqiy tarqalishi 80-yillarning oxirlarida Internet paydo bo'lishi bilan ro'y bergan. Kanalning sig'imi juda tor edi. Tarmoq orqali uzatiladigan ma'lumotlarni siqish uchun ZIP, GIF va PNG formatlari ixtiro qilindi. Tom Xenderson 1985 yilda birinchi tijoratda muvaffaqiyatli ARC arxivini ixtiro qildi va chiqardi (System Enhancement Associates). ARC BBS foydalanuvchilari orasida mashhur bo'lgan u birinchilardan bo'lib bir nechta fayllarni arxivga siqib chiqara oldi, qo'shimcha ravishda uning manbalari ham ochiq edi. ARC o'zgartirilgan LZW algoritmidan foydalangan. Phil Katz, ARC-ning mashhurligidan ilhomlanib, PKARC-ni shareware dasturida chiqardi, bu esa Assembler-da qayta yozish orqali siqishni algoritmlarini yaxshilagan. Biroq, uni Xenderson sudga bergan va sudlangan. PKARC ARC-ni shunchalik ochiqchasiga nusxalashtirdiki, ba'zan hatto yozuvlarni manba kodiga sharhlarda takrorlashardi. Ammo Phil Katz xafa bo'lmadi va 1989 yilda arxivni katta o'zgartirdi va PKZIPni ozod qildi. LZW algoritmining patenti tufayli unga hujum qilingandan so'ng, u asosiy algoritmni IMPLODE deb nomlangan yangi bilan o'zgartirdi. 1993-yilda format yana PKZIP 2.0 bilan almashtirildi va uning o'rnini DEFLATE egalladi. Yangi xususiyatlardan biri arxivni hajmlarga bo'lish funktsiyasi edi. Ushbu versiya yoshi ulug' bo'lishiga qaramay, hanuzgacha keng qo'llaniladi. Grafika almashinuvi formati (GIF) CompuServe tomonidan 1987-yilda yaratilgan. Ma'lumki, format formatsiz tasvirni siqishni qo'llab-quvvatlaydi va 256 rang palitrasi bilan cheklangan. Unisysning barcha harakatlariga qaramay, u ushbu formatni tarqatishni to'xtata olmadi. Bu hali ham mashhur, ayniqsa animatsiya yordami bilan bog'liq. Patent bilan bog'liq muammolardan xursand bo'lgan CompuServe 1994-yilda Portativ Network Grafika (PNG) formatini ishga tushirdi. ZIP singari u yangi trendli DEFLATE algoritmidan foydalangan. DEFLATE Katz tomonidan patentlangan bo'lsa ham, u hech qanday da'vo qilmadi. Endi bu eng mashhur siqishni algoritmi. PNG va ZIP-dan tashqari, u gzip, HTTP, SSL va boshqa ma'lumotlarni uzatish texnologiyalarida qo'llaniladi. Afsuski, Fil Katz DEFLATE g'alabasiga erishmadi, u 2000-yilda 37 yoshida alkogolizmdan vafot etdi.
ZIP 90-yillarning o'rtalariga qadar o'zgarmasdan davom etdi, ammo 1993-yilda oddiy rus dahosi Yevgeniy Roshal o'zining shaxsiy formati va RAR algoritmi bilan chiqdi. Uning so'nggi versiyalari PPM va LZSS algoritmlariga asoslangan. Endi ZIP - bu formatlarning eng keng tarqalgani, RAR - yaqin vaqtgacha Internetda past qonuniy tarkibni tarqatish uchun standart bo'lgan (o'tkazuvchanligi oshganligi sababli, fayllar ko'pincha arxivlanmasdan tarqatiladi) va 7zip maqbul ish vaqti uchun eng yaxshi siqishni formati sifatida ishlatiladi. UNIX dunyosida tar + gzip to'plami ishlatiladi (gzip arxivchi va tar bir nechta fayllarni bittaga birlashtiradi, chunki gzip qanday qilishni bilmaydi). 1996 yilda BWT ochiq kodli bzip2 algoritmining versiyasi paydo bo'ldi va tezda mashhurlikka erishdi. 1999 yilda 7z formatli 7-zip dasturi paydo bo'ldi. Siqilishda u RAR bilan raqobatlashadi, uning afzalligi ochiqlik, shuningdek bzip2, LZMA, LZMA2 va PPMd algoritmlarini tanlash imkoniyatidir. 2002-yilda yana bir arxivchi - PAQ paydo bo'ldi. Muallif Mett Mahoni "kontekstual aralashtirish" deb nomlangan usuldan foydalangan holda PPM algoritmining takomillashtirilgan versiyasidan foydalangan. Belgilarning paydo bo'lishi chastotasi bo'yicha bashorat qilishni yaxshilash uchun bir nechta statistik modellardan foydalanish imkonini beradi.
|
| |
