Kodlash jarayoni va uning usullari

Lug'at algoritmlari

  Lug'at algoritmlari ostida bo'lgan g'oya, asl sekans elementlarining zanjirlari kodlanganligi hisoblanadi. Ushbu kodlash asl navbati asosida olingan maxsus lug'atni ishlatadi.
  U erda algoritmlar so'z bir butun oila, lekin biz, eng ko'p ishlatiladigan algoritm qarash qiladi, uning ishlab chiquvchilar Lepel, Ziv va Welch nomidagi LZW, deb.
  Ushbu algoritmdagi lug'at algoritm ishlaydigan kodlash satrlari bilan to'ldirilgan jadvaldir. Siqilgan kodni dekodlashda lug'at avtomatik ravishda tiklanadi, shuning uchun lug'atlarni siqilgan kod bilan birga o'tkazish shart emas.
  Lug'at barcha yagona elementli zanjirlar bilan boshlanadi, ya'ni. Lug'atning birinchi qatorlari - bu kodlashni amalga oshiradigan alfavit. Siqilishda lug'atda yozilgan eng uzun zanjirning qidiruvi amalga oshiriladi. zanjir topiladi Har safar, u qo'shiladi, lug'atda ro'yxatdan emas, va chiqish allaqachon lug'at zanjirida qayd mos kodni siqilgan. nazariyasi, lug'at hajmi bo'yicha hech qanday cheklovlar bor, lekin amalda u oxir-oqibat topilmadi endi matnida bo'lgan zanjirlar uchrashib boshlaydi, chunki, hajmini cheklash mantiqiy. Bundan tashqari, jadvalning kattaligini yarmiga oshirsak, siqilgan kodlarni saqlash uchun qo'shimcha bit ajratishimiz kerak. Bunday holatlardan qochish uchun jadvalni barcha elementlarning birlamchi zanjirlari bilan boshlashini bildiruvchi maxsus kod kiritiladi.
  Keling, algoritm yordamida siqishni misolini ko'rib chiqaylik. Kuku kukushonkupkupalak kapushon ipini siqib chiqaramiz. Lug'at 32 ta pozitsiyani egallaydi, ya'ni har bir kodi 5 bitni tashkil etadi. Dastlab, lug'at quyidagi tarzda to'ldiriladi:

Bu jadval, axborotni siqib chiqaruvchi tomonning yonida bo'lgani kabi, va paketni chiqarib yuboradigan tomonning yonida ham. Keling, biz siqishni jarayoniga qaraymiz.

Jadval lug'atni to'ldirish jarayonini ko'rsatadi. Bu natijasida siqilgan kodi 105 bitni egallaydi, deb hisoblash oson, va (Biz nafaqa bir belgi kodlash 4 bit sharti bilan) original matn 116 bitni egallaydi.

  Aslida, kod hal qilish jarayoni kodi bevosita talqin qilish kamayadi, bu stol, kodlash, shuningdek boshlab yuborilgan bo'lishi muhim ahamiyatga ega. Endi hal qiluvchi algoritmni ko'rib chiqing.


I-bosqichda lug'atga qo'shilgan magistral faqat i + 1 da aniqlanishi mumkin. Shubhasiz, i-l-satr I + 1-satrining birinchi belgi bilan tugashi kerak. Shunday qilib. biz lug'atni qanday tiklashni bilib oldik. Bir-bir belgi, va S - - so'z muvofiq, CS lug'atda allaqachon Ba'zi qiziqish shakli c cScSc, kodlash majmuasini bir vaziyat. Birinchi qarashda dekoder bu vaziyatni hal qilish mumkin emas, deb tuyulishi mumkin, lekin aslida bu turdagi barcha chiziqlar har doim ular boshlash Shu ramzi bilan tugashi kerak.

Statistik kodlash algoritmlari

  Ushbu ketma-ketlikning algoritmlari ketma-ketlikning eng tez-tez elementlarini eng qisqa siqilgan kodga aylantiradi. Ya'ni. bir xil uzunlikdagi ketma-ketliklar turli uzunlikdagi siqilgan kodlar bilan kodlanadi. Bundan tashqari, ketma-ketlik qanchalik tez-tez bo'lsa, tegishli siqilgan kod shu qadar qisqa.

Huffman algoritmi

  Huffman algoritmi sizga prefiks kodlari yaratish imkonini beradi. Bu ikkilik daraxt bir yo'l prefix kodlari sifatida ko'rish mumkin: uning chap bola tugun o'tish kodi 0 bo'ladi va o'ng bolaga - 1. daraxt kodlangan ramzlari barglarini yorliq bo'lsa, biz ikki tomonlama, bir daraxt shaklida prefiks kodini bir fikr olish.
  Biz Huffman daraxtini qurish va Huffman kodlarini olish uchun algoritmni ta'riflaymiz.