Nagu eespool mainitud, on andmete krüpteerimiseks ettevalmistamise üks olulisi ülesandeid nende liiasuse vähendamine ja kasutatava keele statistiliste mustrite joondamine. Osaline liiasuse kõrvaldamine saavutatakse andmete tihendamisega.

Teabe tihendamine on algse sõnumi teisendamine ühest koodisüsteemist teise, mille tulemusena sõnumi suurus. Info tihendamiseks loodud algoritmid võib jagada kahte suurde rühma: need, mis rakendavad kadudeta pakkimist (pöörduv pakkimine) ja need, mis rakendavad kadudeta pakkimist (pöördumatu tihendamine).

Pööratav kompressioon tähendab absoluutselt täpset andmete taastamist pärast dekodeerimist ja seda saab kasutada mis tahes teabe tihendamiseks. See viib alati väljundinfovoo mahu vähenemiseni, muutmata selle infosisu, st kaotamata infostruktuuri. Veelgi enam, väljundvoost on rekonstrueerimis- või dekompressioonialgoritmi abil võimalik saada sisend ja taastamisprotsessi nimetatakse dekompressiooniks või dekompressiooniks ning alles pärast dekompressiooniprotsessi on andmed sobivad töötlemiseks vastavalt selle sisemisele. vormingus. Kadudeta pakkimist kasutatakse teksti, käivitatavate failide, kvaliteetse heli ja graafika jaoks.

Pöördumatu kokkusurumine tavaliselt on sellel palju suurem tihendusaste kui kadudeta kodeerimisel, kuid lubab dekodeeritud andmetel mõningaid kõrvalekaldeid originaalist. Praktikas on palju praktilisi probleeme, mille puhul algse teabe täpse taastamise nõude järgimine pärast dekompressiooni ei ole kohustuslik. Eelkõige puudutab see multimeediumiteabe tihendamist: heli-, foto- või videokujutisi. Näiteks on laialdaselt kasutusel JPEG ja MPEG multimeediumivormingud, mis kasutavad pöördumatut tihendamist. Pöördumatut tihendamist ei kasutata tavaliselt koos krüptograafilise krüptimisega, kuna krüptosüsteemi põhinõue on, et dekrüpteeritud andmed oleksid identsed algse andmetega. Kuid multimeediatehnoloogiate kasutamisel tihendatakse digitaalsel kujul esitatud andmed sageli pöördumatult enne krüptosüsteemi krüpteerimiseks esitamist. Pärast tarbijale teabe edastamist ja dekrüpteerimist kasutatakse multimeediumifaile tihendatud kujul (st neid ei taastata).

Vaatame lähemalt mõningaid kõige levinumaid pöörduva andmete tihendamise meetodeid.

Tuntuim lihtne lähenemine ja algoritm teabe pöörduval viisil kokkusurumiseks on järjestuste seeria kodeerimine (Run Length Encoding – RLE). Selle lähenemisviisi meetodite põhiolemus on asendada ahelad või korduvate baitide seeriad ühe kodeeriva täitebaidiga ja nende korduste arvu loenduriga. Kõigi sarnaste meetodite probleem seisneb ainult selles, et teha kindlaks, kuidas lahtipakkimisalgoritm suudab eristada kodeeritud seeriat saadud baidivoo muudest kodeerimata baitjadadest. Probleemi lahendus saavutatakse tavaliselt märgiste paigutamisega kodeeritud ahelate algusesse. Sellised märgid võivad olla kodeeritud seeria esimese baidi iseloomulikud bitiväärtused, kodeeritud seeria esimese baidi väärtused. RLE-meetodi miinuseks on üsna madal tihendusaste või väikese seeriate arvu ja, mis veelgi hullem, väikese arvu korduvate baitide arvuga failide kodeerimise hind.

Teabe ühtse kodeerimise korral eraldatakse ühe sõnumi kohta sama arv bitte, olenemata selle esinemise tõenäosusest. Samas on loogiline eeldada, et edastatavate sõnumite kogupikkus väheneb, kui sageli esinevad sõnumid kodeeritakse lühikeste koodisõnadega, harvaesinevad aga pikemate koodisõnadega. Probleemid, mis sel juhul tekivad, on seotud kasutusvajadusega muutuva koodsõna pikkusega koodid. Selliste koodide koostamiseks on palju lähenemisviise.

Ühed praktikas laialdaselt kasutatavad on sõnaraamatumeetodid, mille peamisteks esindajateks on Zivi ja Lempeli perekonna algoritmid. Nende põhiidee seisneb selles, et sisendvoo fragmendid ("fraasid") asendatakse osutiga kohale, kus need tekstis varem esinesid. Kirjanduses nimetatakse selliseid algoritme algoritmideks LZ kompressioon.

See meetod kohandub kiiresti teksti struktuuriga ja suudab kodeerida lühikesi funktsioonisõnu, kuna need esinevad selles väga sageli. Uusi sõnu ja fraase saab moodustada ka varem kohatud sõnade osadest. Tihendatud teksti dekodeerimine toimub otse - kursor asendatakse lihtsalt sõnastikust valmis fraasiga, millele see osutab. Praktikas saavutab LZ meetod hea tihenduse, selle oluliseks omaduseks on dekoodri väga kiire töö.

Teine lähenemisviis teabe tihendamiseks on Huffmani kood, mille kodeerija ja dekoodri riistvaraline teostus on üsna lihtne. Algoritmi idee on järgmine: teades sõnumis sümbolite ilmumise tõenäosust, saame kirjeldada täisarvust bittide arvust koosnevate muutuva pikkusega koodide koostamise protseduuri. Tähemärkidele omistatakse suurema tõenäosusega lühemad koodid, harvemini esinevatele tähemärkidele aga pikemad koodid. Tänu sellele saavutatakse koodisõna keskmise pikkuse vähenemine ja suurem tihendamise efektiivsus. Huffmani koodidel on unikaalne eesliide (koodsõna algus), mis võimaldab neid üheselt dekodeerida, hoolimata nende muutuvast pikkusest.

Klassikalise Huffmani koodi sünteesimise protseduur eeldab a priori teabe olemasolu sõnumiallika statistiliste omaduste kohta. Teisisõnu peab arendaja teadma teatud sümbolite esinemise tõenäosusi, millest sõnumeid moodustatakse. Vaatame Huffmani koodi sünteesi lihtsa näite abil.

p(S1)=0,2, p(S2)=0,15, p(S3)=0,55, p(S4)=0,1. Sorteerime sümbolid esinemise tõenäosuse kahanevas järjekorras ja esitame need tabelina (joon. 14.3, a).

Koodi sünteesi protseduur koosneb kolmest põhietapist. Esimeses etapis ahendatakse tabeli read: kaks rida, mis vastavad kõige väiksema esinemistõenäosusega tähemärkidele, asendatakse ühega, mille esinemissagedus on täistõenäosus, misjärel järjestatakse tabel uuesti. Konvolutsioon jätkub seni, kuni tabelisse jääb ainult üks rida, mille kogutõenäosus on võrdne ühega (joonis 14.3, b).

Riis.

14.3.

Riis.

14.4.

Puu juure moodustab viimases veerus asuv üksus. Vaadeldavas näites moodustatakse see ühik tõenäosustest 0,55 ja 0,45, mis on kujutatud kahe juurega seotud puusõlmena. Esimene neist vastab sümbolile S 3 ja seega selle sõlme edasist hargnemist ei toimu.

Teine sõlm, mis on märgistatud tõenäosusega 0,45, ühendub kahe kolmanda taseme sõlmega tõenäosustega 0,25 ja 0,2. Tõenäosus 0,2 vastab sümbolile S 1 ja tõenäosus 0,25 moodustub omakorda sümboli S 2 ilmumise tõenäosustest 0,15 ja sümboli S 4 ilmumise tõenäosusest 0,1.

Koodipuu üksikuid sõlmi ühendavad servad on nummerdatud 0 ja 1 (näiteks vasakpoolsed servad on 0 ja paremad servad 1). Kolmandas, viimases etapis koostatakse tabel, milles võrreldakse lähtesümboleid ja vastavaid Huffmani koodisõnu. Need koodsõnad moodustatakse numbrite lugemisel, mis tähistavad servi, mis moodustavad tee puu juurest vastava sümbolini. Vaadeldava näite puhul on Huffmani kood parempoolses tabelis näidatud kujul (joonis 14.4, b). Klassikalisel Huffmani algoritmil on aga üks oluline puudus. Tihendatud sõnumi sisu rekonstrueerimiseks peab dekooder teadma sagedustabelit, mida kodeerija kasutas. Järelikult suureneb tihendatud sõnumi pikkus sagedustabeli pikkuse võrra, mis tuleb enne andmeid saata, mis võib tühistada kõik jõupingutused sõnumi tihendamiseks. seisneb sisendvoo vaatamises ja kogutud statistika põhjal kodeeringu konstrueerimises. Selleks on vaja faili läbida kaks korda – üks statistilise teabe vaatamiseks ja kogumiseks, teine ​​kodeerimiseks. Staatilises Huffmani kodeerimises seostatakse sisendsümbolid (erineva pikkusega bitiahelad) samuti muutuva pikkusega bitiahelatega - nende koodidega. Iga sümboli koodi pikkus on võrdeline selle sageduse binaarlogaritmiga, mis on võetud vastupidise märgiga. Ja kõigi erinevate sümbolite kogum moodustab voolu tähestiku.

On veel üks meetod - adaptiivne või dünaamiline Huffmani kodeerimine. Selle üldpõhimõte on kodeerimisskeemi muutmine sõltuvalt sisendvoo muudatuste olemusest. Sellel lähenemisviisil on ühekäiguline algoritm ja see ei nõua selgesõnaliselt kasutatava kodeeringu kohta teabe salvestamist. Adaptiivne kodeerimine võib pakkuda suuremat tihendusastet kui staatiline kodeerimine, kuna sisendvoo sageduste muutusi võetakse rohkem arvesse. Adaptiivse Huffmani kodeerimise kasutamisel on algoritmi keeruliseks vajadus kohandada pidevalt põhitähestiku puu- ja märgikoode vastavalt sisendvoo muutuvale statistikale.

Huffmani meetodid tagavad üsna suure kiiruse ja mõõdukalt hea tihenduskvaliteedi. Huffmani kodeerimisel on aga minimaalne liiasus, eeldusel, et iga märk on kodeeritud märgikoodi tähestikus kahest bitist koosneva eraldi stringina – (0, 1) . Selle meetodi peamiseks puuduseks on tihendusastme sõltuvus sümboli tõenäosuste lähedusest 2-le teatud negatiivsel määral, mis tuleneb asjaolust, et iga sümbol on kodeeritud täisarvu bittidega.

Pakub hoopis teistsugust lahendust aritmeetiline kodeerimine. See meetod põhineb ideel teisendada sisendvoog üheks ujukomaarvuks. Aritmeetiline kodeerimine on meetod, mis võimaldab sisendtähestiku märke kadudeta pakkida, eeldusel, et nende märkide sagedusjaotus on teada.

Eeldatav nõutav sümbolite jada, kui see on aritmeetilise kodeerimisega tihendatud, loetakse mingiks intervalli kahendmurruks )