Seperti yang dinyatakan di atas, salah satu tugas penting penyediaan awal data untuk penyulitan adalah untuk mengurangkan redundansinya dan menyelaraskan corak statistik bahasa yang digunakan. Penghapusan separa redundansi dicapai dengan pemampatan data.

Pemampatan maklumat ialah proses menukar mesej asal daripada satu sistem kod kepada sistem kod yang lain, akibatnya saiz mesej. Algoritma yang direka untuk pemampatan maklumat boleh dibahagikan kepada dua kumpulan besar: mereka yang melaksanakan pemampatan tanpa kehilangan (mampatan boleh balik) dan mereka yang melaksanakan mampatan lossy (mampatan tidak boleh balik).

Mampatan boleh balik membayangkan pemulihan data yang sangat tepat selepas penyahkodan dan boleh digunakan untuk memampatkan sebarang maklumat. Ia sentiasa membawa kepada penurunan dalam jumlah aliran maklumat keluaran tanpa mengubah kandungan maklumatnya, iaitu, tanpa kehilangan struktur maklumat. Lebih-lebih lagi, dari aliran keluaran, menggunakan algoritma pembinaan semula atau penyahmampatan, adalah mungkin untuk mendapatkan input, dan proses pemulihan dipanggil penyahmampatan atau penyahmampatan, dan hanya selepas proses penyahmampatan data yang sesuai untuk diproses mengikut dalamannya. format. Mampatan tanpa rugi digunakan untuk teks, fail boleh laku, audio dan grafik berkualiti tinggi.

Mampatan tidak dapat dipulihkan biasanya mempunyai nisbah mampatan yang jauh lebih tinggi daripada pengekodan tanpa kerugian, tetapi membenarkan beberapa sisihan data yang dinyahkod daripada yang asal. Dalam amalan, terdapat pelbagai masalah praktikal di mana pematuhan terhadap keperluan pemulihan tepat maklumat asal selepas penyahmampatan adalah tidak wajib. Ini, khususnya, terpakai kepada pemampatan maklumat multimedia: imej bunyi, foto atau video. Sebagai contoh, format multimedia JPEG dan MPEG, yang menggunakan pemampatan tidak boleh balik, digunakan secara meluas. Mampatan tidak boleh balik biasanya tidak digunakan bersama dengan penyulitan kriptografi, kerana keperluan utama untuk sistem kriptografi ialah data yang dinyahsulit adalah sama dengan yang asal. Walau bagaimanapun, apabila menggunakan teknologi multimedia, data digital selalunya dimampatkan secara tidak boleh balik sebelum diserahkan kepada sistem kriptografi untuk penyulitan. Selepas maklumat dihantar kepada pengguna dan dinyahsulit, fail multimedia digunakan dalam bentuk termampat (iaitu, ia tidak dipulihkan).

Mari kita lihat dengan lebih dekat beberapa kaedah yang paling biasa bagi pemampatan data boleh balik.

Pendekatan dan algoritma mudah yang paling terkenal untuk memampatkan maklumat dengan cara boleh balik ialah pengekodan satu siri jujukan (Run Length Encoding - RLE). Intipati kaedah dalam pendekatan ini adalah untuk menggantikan rantai atau siri bait berulang dengan satu bait pengisi pengekodan dan pembilang untuk bilangan ulangan mereka. Masalah dengan semua kaedah yang serupa hanyalah untuk menentukan cara algoritma penyahmampatan boleh membezakan siri yang dikodkan daripada jujukan bait yang tidak dikodkan yang lain dalam aliran bait yang terhasil. Penyelesaian kepada masalah biasanya dicapai dengan meletakkan tanda pada permulaan rantai berkod. Tanda sedemikian boleh menjadi nilai bit ciri dalam bait pertama siri berkod, nilai bait pertama siri berkod. Kelemahan kaedah RLE ialah nisbah mampatan yang agak rendah atau kos pengekodan fail dengan bilangan siri yang kecil dan, lebih teruk lagi, dengan sebilangan kecil bait berulang dalam siri.

Dengan pengekodan seragam maklumat, bilangan bit yang sama diperuntukkan kepada mesej, tanpa mengira kebarangkalian kejadiannya. Pada masa yang sama, adalah logik untuk mengandaikan bahawa jumlah panjang mesej yang dihantar akan berkurangan jika mesej yang kerap berlaku dikodkan dengan perkataan kod pendek, dan mesej yang jarang berlaku dengan yang lebih panjang. Masalah yang timbul dalam kes ini adalah berkaitan dengan keperluan untuk digunakan kod dengan panjang kata kod berubah-ubah. Terdapat banyak pendekatan untuk membina kod tersebut.

Salah satu yang digunakan secara meluas dalam amalan ialah kaedah kamus, wakil utamanya termasuk algoritma keluarga Ziv dan Lempel. Idea asas mereka ialah serpihan aliran input ("frasa") digantikan dengan penuding ke tempat di mana ia sebelum ini muncul dalam teks. Dalam literatur, algoritma tersebut dirujuk sebagai algoritma Mampatan LZ.

Kaedah ini cepat menyesuaikan diri dengan struktur teks dan boleh mengekod perkataan fungsi pendek, kerana ia sering muncul di dalamnya. Perkataan dan frasa baharu juga boleh dibentuk daripada bahagian perkataan yang ditemui sebelum ini. Penyahkodan teks termampat dijalankan secara langsung - penunjuk hanya digantikan dengan frasa siap pakai dari kamus yang ditunjukkannya. Dalam amalan, kaedah LZ mencapai pemampatan yang baik; sifat pentingnya ialah operasi penyahkod yang sangat pantas.

Satu lagi pendekatan untuk memampatkan maklumat ialah Kod Huffman, pengekod dan penyahkod yang mempunyai pelaksanaan perkakasan yang agak mudah. Idea algoritma adalah seperti berikut: mengetahui kebarangkalian simbol yang muncul dalam mesej, adalah mungkin untuk menerangkan prosedur untuk membina kod pembolehubah panjang yang terdiri daripada nombor integer bit. Aksara lebih berkemungkinan diberikan kod yang lebih pendek, manakala aksara yang kurang kerap diberikan kod yang lebih panjang. Disebabkan ini, pengurangan dalam purata panjang kata kod dan kecekapan pemampatan yang lebih besar dicapai. Kod Huffman mempunyai awalan unik (permulaan perkataan kod), yang membolehkannya dinyahkod dengan jelas, walaupun panjangnya berubah-ubah.

Prosedur untuk mensintesis kod Huffman klasik menganggap kehadiran maklumat apriori tentang ciri statistik sumber mesej. Dalam erti kata lain, pembangun mesti mengetahui kebarangkalian berlakunya simbol tertentu dari mana mesej terbentuk. Mari kita lihat sintesis kod Huffman menggunakan contoh mudah.

p(S 1)=0.2, p(S 2)=0.15, p(S 3)=0.55, p(S 4)=0.1. Mari kita susun simbol dalam tertib menurun kebarangkalian kejadian dan bentangkannya dalam bentuk jadual (Rajah 14.3, a).

Prosedur sintesis kod terdiri daripada tiga peringkat utama. Pada peringkat pertama, baris jadual diruntuhkan: dua baris sepadan dengan aksara dengan kebarangkalian paling rendah kejadian digantikan dengan satu dengan jumlah kebarangkalian, selepas itu jadual disusun semula semula. Konvolusi berterusan sehingga hanya tinggal satu baris dalam jadual dengan jumlah kebarangkalian sama dengan satu (Rajah 14.3, b).

nasi. 14.3.

Pada peringkat kedua, pokok kod dibina menggunakan jadual yang runtuh (Rajah 14.4, a). Pokok itu dibina bermula dari lajur terakhir jadual.

Akar pokok dibentuk oleh unit yang terletak di lajur terakhir. Dalam contoh yang sedang dipertimbangkan, unit ini terbentuk daripada kebarangkalian 0.55 dan 0.45, digambarkan sebagai dua nod pokok yang dikaitkan dengan akar. Yang pertama daripada mereka sepadan dengan simbol S 3 dan, dengan itu, cawangan selanjutnya nod ini tidak berlaku.

Nod kedua, dilabelkan dengan kebarangkalian 0.45, menyambung kepada dua nod peringkat ketiga, dengan kebarangkalian 0.25 dan 0.2. Kebarangkalian 0.2 sepadan dengan simbol S 1 , dan kebarangkalian 0.25, seterusnya, terbentuk daripada kebarangkalian 0.15 kemunculan simbol S 2 dan 0.1 kemunculan simbol S 4 .

Tepi yang menyambungkan nod individu pepohon kod diberi nombor 0 dan 1 (contohnya, tepi kiri ialah 0 dan tepi kanan ialah 1). Pada peringkat ketiga, akhir, jadual dibina di mana simbol sumber dan perkataan kod kod Huffman yang sepadan dibandingkan. Kata kod ini dibentuk dengan membaca nombor yang menandakan tepi yang membentuk laluan dari akar pokok ke simbol yang sepadan. Untuk contoh yang sedang dipertimbangkan, kod Huffman akan mengambil bentuk yang ditunjukkan dalam jadual di sebelah kanan (Rajah 14.4, b).

Walau bagaimanapun, algoritma Huffman klasik mempunyai satu kelemahan yang ketara. Untuk membina semula kandungan mesej termampat, penyahkod mesti mengetahui jadual kekerapan yang digunakan oleh pengekod. Akibatnya, panjang mesej dimampatkan ditambah dengan panjang jadual kekerapan yang mesti dihantar lebih awal daripada data, yang boleh menafikan semua usaha untuk memampatkan mesej.

Satu lagi varian pengekodan Huffman statik terdiri daripada melihat aliran input dan membina pengekodan berdasarkan statistik yang dikumpul. Ini memerlukan dua laluan melalui fail - satu untuk melihat dan mengumpul maklumat statistik, yang kedua untuk pengekodan. Dalam pengekodan Huffman statik, simbol input (rantaian bit pelbagai panjang) dikaitkan dengan rantai bit juga panjang berubah - kodnya. Panjang kod setiap simbol dianggap berkadar dengan logaritma perduaan kekerapannya, diambil dengan tanda bertentangan. Dan jumlah set semua simbol berbeza yang ditemui membentuk abjad aliran.

Terdapat kaedah lain - adaptif atau pengekodan Huffman dinamik. Prinsip amnya adalah untuk menukar skema pengekodan bergantung pada sifat perubahan dalam aliran input. Pendekatan ini mempunyai algoritma satu laluan dan tidak memerlukan menyimpan maklumat tentang pengekodan yang digunakan secara eksplisit. Pengekodan penyesuaian boleh memberikan nisbah mampatan yang lebih tinggi daripada pengekodan statik, kerana perubahan dalam frekuensi aliran input lebih diambil kira sepenuhnya. Apabila menggunakan pengekodan Huffman adaptif, komplikasi algoritma adalah keperluan untuk sentiasa melaraskan kod pokok dan aksara abjad utama mengikut perubahan statistik aliran input.

Kaedah Huffman memberikan kualiti mampatan berkelajuan tinggi dan sederhana baik. Walau bagaimanapun, pengekodan Huffman mempunyai redundansi minimum dengan syarat setiap aksara dikodkan dalam abjad kod aksara sebagai rentetan berasingan dua bit - (0, 1) . Kelemahan utama kaedah ini ialah pergantungan tahap pemampatan pada kedekatan kebarangkalian simbol kepada 2 ke tahap negatif tertentu, yang disebabkan oleh fakta bahawa setiap simbol dikodkan dengan nombor integer bit.

Menawarkan penyelesaian yang sama sekali berbeza pengekodan aritmetik. Kaedah ini adalah berdasarkan idea untuk menukar aliran input kepada nombor titik terapung tunggal. Pengekodan aritmetik ialah kaedah yang membolehkan aksara abjad input dibungkus tanpa kehilangan, dengan syarat taburan kekerapan aksara ini diketahui.

Urutan simbol yang diperlukan yang dijangka apabila dimampatkan oleh pengekodan aritmetik dianggap sebagai beberapa pecahan binari daripada selang )