Metoda e thjeshtë e kodimit ( KODIMI TË GJATESISË EKZEKUTOHET), i cili përdoret me sukses nga arkivuesit e njohur.
Kjo metodë bazohet në numërimin e gjatësisë së karaktereve të përsëritura në një rresht dhe shkrimin në skedarin e paketuar në vend të një sekuence të këtyre karaktereve, informacionin e llojit: numrin e karaktereve dhe vetë karakterin e përsëritur. Për shembull, ekziston një varg si " AAAAABBBCCCADDDEEL". Do të paketohet në një sekuencë si " 5A3B3CADDEEL". Siç shihet nga shembulli, sekuenca prej 5 shkronjash "A" ishte e paketuar në dy karaktere "5" dhe "A", dhe sekuencat "DD", "EE", "L" nuk ishin të paketuara fare. , pasi nuk ka asnjë përfitim nga zëvendësimi i këtyre karaktereve në një sekuencë të tipit "gjatësi"+"shkronjë".
Kur zbatohet paketimi i një skedari duke përdorur këtë metodë, lindin vështirësi të tilla si mënyra sesi shpaketuesi do të dallojë informacionin e kontrollit nga një skedar i paketuar nga të dhënat e papaketuara. Për shembull, si në rastin e diskutuar më sipër, a do ta dallojë paketuesi karakterin e kontrollit "5" nga një karakter i papaketuar me të njëjtin kod? Ekzistojnë dy mundësi për zgjidhjen e këtij problemi:
(Unë). Gjeni një simbol që shfaqet më pak se pjesa tjetër, ose që nuk shfaqet fare në skedarin e paketuar dhe përdorni atë si kontroll. Le ta quajmë një parashtesë për lehtësi në shpjegimin e mëposhtëm. Tani sekuenca "AAAAA" do të konvertohet nga paketuesi në prefiks (8 bit), "A" (8 bit), sasi (8 bit), pra 5 bajt do të zëvendësohen me tre. Nëse një bit me një kod prefiks ndeshet në skedarin burimor gjatë paketimit, atëherë dy bajt me kodin e prefiksit shkruhen në skedarin që rezulton dhe me këtë veçori shpaketuesi do të përcaktojë se ku është parashtesa një simbol dhe ku është kontrolli. informacion. Ndryshimet e kësaj metode janë të mundshme, për shembull:
1. Numri i të koduarve jo me tetë bit, por me tre, katër e kështu me radhë, që do të rrisë përqindjen e paketimit, por do të kufizojë gjatësinë maksimale të karaktereve të përsëritura që mund të paketohen në rastin e kodimit me tre bit. (nga 3 në 10, d.m.th. .000=3, ...,111=10), dhe nëse gjatësia është më shumë se 10 karaktere, atëherë paketoni dhjetë karaktere secili.
2. Një modifikim i dytë është i mundur, kur numri i karaktereve të përsëritura kodohet jo me tetë bit, por me tre bit, dhe gjatësia e karaktereve të përsëritura kufizohet në 265. Shtrohet pyetja se si të kodohen 256 gjatësi të ndryshme në 3 bit. Rezulton se është e mundur, por vetëm diapazoni është nga 3 në 9, nëse gjatësia e karaktereve të përsëritura është më shumë se 9, atëherë "111" në kodin binar shkruhet në tre bit, që është e barabartë me "7". Kjo do të thotë se gjatësia e vërtetë e sekuencës është në bajtin tjetër (8 bit janë ndarë për gjatësi nga 10 deri në 256 karaktere).
Ketu jane disa shembuj:
Kemi sekuenca:
a) "AAAAABBBBBBBBBBCCAAAAAAAAAAAAAAA"
b) "CBBBBBBBBBBEEEEEEEEEEEEA"
Le t'i paketojmë ato:
1. Me metodën RLE (kodimi në gjatësi - paketoni bajt të përsëritur).
a) Merrni parashtesën e barabartë me "D", marrim:
"D", "D", "A", 5, "D", "B", 10, "C", "D", "A", 15.Përqindja e kompresimit = 12 byte/32 bytes = 37.5%
Në një skedar të paketuar, bajt i prefiksit është bajt i parë në mënyrë që shpaketuesi të dijë se cili bajt është prefiksi.
b) Merrni një parashtesë të barabartë me "A", megjithëse në fakt paketuesi nuk do ta bëjë këtë, pasi nuk ka shumë karaktere në këtë sekuencë, kështu që arkivuesi do të marrë një karakter të papërdorur si parashtesë.
Sekuenca e paketuar:
"A", "C", "A", "B", 10, "A", "E", 10, "A", "A"Përqindja e kompresimit = 10 byte/22 bytes = 45,5%
2.Tani le të paketojmë të njëjtat linja sipas modifikimit 1 të metodës RLE me të njëjtat vlera të prefiksit për të analizuar efikasitetin.
"D", "D", "A" , 2 , "D", "B" , 7 ,
8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 3 bit"D", "A", 7, "D", "A" , 2
8 bit 8 bit 3 bit 8 bit 8 bit 3 bitPërqindja e kompresimit=84 bit/(22*8) bit = 32.8%
"A" , "C", "A", "B" , 7 , "A" , "E" , 7 , "A" , "A"
8 bit 8 bit 8 bit 8 bit 4 bit 8 bit 8 bit 3 bit 8 bit 8 bitPërqindja e kompresimit=70 bit/(22*8) bit = 39.8%
3. Tani le të kontrollojmë efektivitetin e modifikimit të fundit:
a) Sekuenca e paketuar:
"D", "D", "A" , 2 , "D", "B" , 7 , 0
8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 3 bit 8 bit"D", "A", 7, 5
8 bit 8 bit 3 bit 8 bitPërqindja e kompresimit = 81 bit/(32*8) bit = 31,6%
b) Sekuenca e paketuar:
"A" , "C", "A", "B" , 7 , 0 , "A" , "E"
8 bit 8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 8 bit7 , 0 , "A", "A"
3 bit 8 bit 8 bit 8 bitPërqindja e kompresimit = 86 bit/(22*8) bit = 48,9%
Këta shembuj tregojnë se në varësi të përmbajtjes së të dhënave të paketuara, njëri ose tjetri algoritëm është efektiv, kështu që për të zgjedhur se cili algoritëm është më efikas, duhet t'i testoni ato në lloje të ndryshme skedarësh.
(II). Opsioni i dytë për regjistrimin e informacionit të kontrollit për paketuesin është si vijon: nëse në tekst shfaqet një karakter i vetëm, atëherë një bit kontrolli i barabartë me një dhe vetë ky karakter shkruhen në skedarin dalës. Nëse ka një sekuencë bajtësh të përsëritur, për shembull "AAAAAA", atëherë informacioni i paketuar do të duket kështu: 0 (1 bit), bajt A (8 bit), numërim (3-8 bit);
Le të japim një shembull për qartësi. Për ta bërë këtë, merrni sekuenca nga shembujt e mëparshëm.
1) Numri i bajteve të përsëritura është i koduar në 8 bit.
a) 0 , "A" , 5 , 0 , "B" , 10 , 1 , "C" , 1 , "C" , 0 , "A" , 15
1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b. 1b. 8b. 1b. 8b. 8b.Përqindja e kompresimit = 71 bit/256 bit = 27,7%
b) 1 , "C" , 0 , "B" , 10 , 0 , "E" , 10 , 1 , "A"
1b. 8b. 1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b.Përqindja e kompresimit = 52 bit/176 bit = 29,5%
2) Tani le të marrim 3 bit për të koduar numrin e bajteve të përsëritura, në të cilat mund të kodohen vlerat nga 2 në 8 (0 - 6), nëse gjatësia e sekuencës përsëritëse është më e madhe, atëherë këta tre bit përmbajnë "111" (7 dhjetore), dhe gjatësia e vërtetë është në bajtin tjetër (gjatësia 9 deri në 264).
a) 0 , "A" , 3 , 0 , "B" , 7 , 1 , 0 , "C" , 0 , 0 , "A" , 7 , 6
1b. 8b. 3b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 1b. 8b. 3b. 8b.Përqindja e kompresimit = 64 bit/256 bit = 20.3%
b) 1 , "C" , 0 , "B" , 7 , 1 , 0 , "E" , 7 , 1 , 1, "A"
1b. 8b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 8b. 1b. 8b.Përqindja e kompresimit = 58 bit / 176 bit = 33%
Nëse sasia është e koduar në 4 bit (2..16), atëherë
1 , "C" , 0 , "B" , 8 , 0 , "E" , 8 , 1 , "A"
1b. 8b. 1b. 8b. 4b. 1b. 8b. 4b. 1b. 8b.Përqindja e kompresimit = 44 bit / 176 bit = 25%
Siç mund ta shihni nga shembujt, opsioni i dytë i paketimit është më efikas, pasi ngjesh sekuencat që fillojnë me dy karaktere, të cilat zakonisht janë shumica dërrmuese. Varianti i parë ka paketuar sekuenca duke filluar nga tre karaktere.
Klasifikimi bazë i algoritmeve të kompresimit të kthyeshëm
Ka shumë metoda të ndryshme praktike të kompresimit pa humbje, të cilat priren të kenë efikasitet të ndryshëm për lloje të ndryshme të dhënash dhe vëllime të ndryshme. Megjithatë, këto metoda bazohen në tre skema kryesore klasike të kompresimit:
Kodimi i serive të sekuencës (RLE);
Metodat statistikore të kompresimit;
Metodat e ngjeshjes fjalorore (heuristike).
Kompresimi sipas metodës së kodimit në seri: Algoritmi RLE
Qasja më e njohur e thjeshtë dhe algoritmi i kompresimit të kthyeshëm është Run Length Encoding (RLE). Thelbi i metodave të kësaj qasjeje është zëvendësimi i zinxhirëve ose serive të bajteve të përsëritura ose sekuencave të tyre me një bajt kodues dhe një numërues për numrin e përsëritjeve të tyre. Problemi me të gjitha metodat e ngjashme është të përcaktohet mënyra në të cilën algoritmi i dekompresimit mund të dallojë seritë e koduara nga sekuencat e tjera të bajtit të pakoduar në rrjedhën e bajtit që rezulton. Zgjidhja e problemit zakonisht arrihet duke vendosur etiketa në fillim të zinxhirëve të koduar. Shenja të tilla mund të jenë, për shembull, vlerat karakteristike të bitit në bajtin e parë të një ekzekutimi të koduar, vlerat e bajtit të parë të një ekzekutimi të koduar dhe të ngjashme. Këto metoda janë zakonisht mjaft efikase për kompresimin e bitmap. imazhe grafike(BMP, PCX, TIF, GIF), sepse këto të fundit përmbajnë mjaft seri të gjata të sekuencave të përsëritura të bajteve. Disavantazhi i metodës RLE është një raport mjaft i ulët i kompresimit ose kostoja e kodimit të skedarëve me një numër të vogël serish dhe, edhe më keq, me një numër të vogël bajtësh të përsëritur në seri.
Algoritmi RLE bazohet në idenë e identifikimit të sekuencave të përsëritura të të dhënave dhe zëvendësimit të tyre me një strukturë më të thjeshtë që specifikon kodin e të dhënave dhe faktorin e përsëritjes. Për shembull, le të jepet një sekuencë e tillë e të dhënave që i nënshtrohet kompresimit: 1 1 1 1 2 2 3 4 4 4 . Në algoritmin RLE, propozohet të zëvendësohet me strukturën e mëposhtme: 1 4 2 2 3 1 4 3 , ku numri i parë i çdo çifti numrash është kodi i të dhënave dhe i dyti është faktori i përsëritjes. Nëse 1 bajt ndahet për të ruajtur çdo element të dhënash të sekuencës hyrëse, atëherë e gjithë sekuenca do të zërë 10 bajt memorie, ndërsa sekuenca e daljes (versioni i kompresuar) do të zërë 8 bajtë memorie. Është e qartë se algoritmi RLE do të japë një efekt më të mirë kompresimi me një gjatësi më të madhe të sekuencës së përsëritur të të dhënave. Në rastin e shembullit të mësipërm, nëse sekuenca e hyrjes duket kështu: 1 1 1 1 1 1 3 4 4 4, atëherë raporti i kompresimit do të jetë 60%. Në këtë drejtim, efikasiteti më i madh i algoritmit RLE arrihet duke kompresuar të dhënat grafike (veçanërisht për imazhet me një ton).
Algoritme heuristike (fjalorike). compression (LZ, LZW) kërkoni për rreshta në skedar që përsëriten dhe ndërtoni një fjalor frazash që tashmë janë hasur. Në mënyrë tipike, algoritme të tilla kanë një numër parametrash specifikë (madhësia e tamponit, gjatësia maksimale e frazës, etj.), Zgjedhja e të cilave varet nga përvoja e autorit të veprës, dhe këto parametra zgjidhen në atë mënyrë që të arrihet raporti optimal koha e ekzekutimit të algoritmit, raporti i kompresimit dhe lista e skedarëve që kompresohen mirë.
Algoritme Statistikore(Huffman, Shannon-Fano, aritmetika) Algoritmet statistikore përdorin një model të dhënash statistikore dhe cilësia e kompresimit të informacionit varet drejtpërdrejt nga sa i mirë është ky model. Marrja parasysh e vetive statistikore të të dhënave në rastin më të thjeshtë nënkupton përdorimin e kodeve jo uniforme për kodim - karakteret që ndodhin shpesh kodohen në kode të shkurtra, dhe rrallë në ato të gjata. Kjo do të thotë, algoritme të tilla duhet të dinë probabilitetet e shfaqjes së karaktereve në imazh, të cilat mund të vlerësohen në rastin e thjeshtë nga frekuenca e shfaqjes së karaktereve në të dhënat hyrëse. Si rregull, këto probabilitete janë të panjohura. Qëllimi i kodimit është shndërrimi i rrymës hyrëse në një rrymë bit me gjatësi minimale, e cila arrihet duke reduktuar entropinë (kaotike) të rrjedhës hyrëse duke marrë parasysh frekuencat e simboleve.
Gjatësia e kodit që përfaqëson karakteret nga alfabeti i transmetimit duhet të jetë në përpjesëtim me sasinë e informacionit në rrjedhën hyrëse dhe gjatësia e karaktereve të transmetimit në bit nuk mund të jetë shumëfish i 8-ës apo edhe i ndryshueshëm. Nëse dihet shpërndarja e probabilitetit të frekuencave të shfaqjes së karaktereve nga alfabeti i rrymës hyrëse, atëherë është e mundur të ndërtohet një model kodimi optimal. Sidoqoftë, për shkak të ekzistencës së një numri të madh të formateve të ndryshme të skedarëve, detyra bëhet shumë më e ndërlikuar, sepse. shpërndarja e frekuencës së simbolit të të dhënave nuk dihet paraprakisht. Në këtë rast, përdoren dy qasje.
Së pari konsiston në shikimin e rrjedhës hyrëse dhe ndërtimin e një kodimi bazuar në statistikat e mbledhura (kjo kërkon dy kalime nëpër skedar - një për shikimin dhe mbledhjen informacion statistikor, e dyta - për kodim, e cila kufizon disi fushëveprimin e algoritmeve të tilla, sepse, kështu, mundësia e kodimit me një kalim "në fluturim", e përdorur në sistemet e telekomunikacionit, ku sasia e të dhënave ndonjëherë nuk dihet, dhe e tyre ritransmetimi ose analizimi mund të marrë një kohë të gjatë të paarsyeshme). Në një rast të tillë, skema e entropisë e kodimit të përdorur shkruhet në rrjedhën e daljes. Kjo teknikë njihet si kodimi statik i Huffman. Tabela e simboleve transferohet së bashku me skedarin e ngjeshur. Algoritme të tilla kompresojnë mjaft mirë shumicën e skedarëve, por transmetimin e nevojshëm shtesë të tabelës së frekuencës së simboleve, si dhe nevojën për dy kalime skedari burimor për mbledhjen dhe kompresimin e statistikave.
Metoda e dytë- metodë kodimi adaptive. Parimi i tij është të ndryshojë skemën e kodimit në varësi të natyrës së ndryshimeve në rrjedhën hyrëse. Adaptive - filloni të punoni me një tabelë fillestare fikse të frekuencave të karaktereve (zakonisht të gjitha karakteret janë të njëjta në fillim) dhe në procesin e punës kjo tabelë ndryshon në varësi të karaktereve që ndodhin në skedar. Përparësitë: algoritmi me një kalim, nuk ka nevojë të transferoni tabelën e frekuencës së simboleve, kompreson një klasë të gjerë skedarësh në mënyrë mjaft efikase. Kjo qasje ka një algoritëm me një kalim dhe nuk kërkon ruajtje të qartë të informacionit në lidhje me kodimin e përdorur. Kodimi adaptiv mund të japë një shkallë më të madhe kompresimi sesa kodimi statik, pasi ndryshimet në frekuencat e rrymës hyrëse merren parasysh më plotësisht. Kjo teknikë njihet si kodimi dinamik Huffman.
Me kete ne mendje algoritme statistikore mund të ndahet në tri klasa:
1. Jo-përshtatës - përdorni probabilitete simbolesh fikse, të paracaktuara. Tabela e probabilitetit të simboleve nuk transferohet me skedarin sepse dihet para kohe. Disavantazhi: zona e ngushtë e përdorimit për një tabelë të caktuar frekuencash, për të cilën arrihet një raport i pranueshëm i ngjeshjes.
2. Gjysmë-përshtatës - një tabelë e frekuencave të karaktereve ndërtohet për çdo skedar dhe skedari kompresohet në bazë të tij. Tabela e simboleve transferohet së bashku me skedarin e ngjeshur. Algoritme të tilla kompresojnë mjaft mirë shumicën e skedarëve, por është i nevojshëm transmetimi shtesë i tabelës së frekuencës së simboleve, si dhe nevoja për dy kalime të skedarit burimor për mbledhjen e statistikave dhe kompresimin.
3. Adaptive - filloni të punoni me një tabelë fillestare fikse të frekuencave të karaktereve (zakonisht të gjitha karakteret janë të njëjta në fillim) dhe në procesin e punës kjo tabelë ndryshon në varësi të karaktereve që ndodhin në skedar. Përparësitë: algoritmi me një kalim, nuk ka nevojë të transferoni tabelën e frekuencës së simboleve, kompreson një klasë të gjerë skedarësh në mënyrë mjaft efikase.
Algoritmi Huffman bazohet në idenë e kodimit sipas grupeve të biteve. Kryerja e parë analiza e frekuencës sekuenca e të dhënave hyrëse, d.m.th., vendoset frekuenca e shfaqjes së secilit karakter që ndodh në të. Pas kësaj, personazhet renditen sipas uljes së shpeshtësisë së shfaqjes.
Ideja bazë është që sa më i zakonshëm të jetë një karakter, aq më pak bite kodon. Rezultati i kodimit futet në fjalorin e kërkuar për dekodim. Konsideroni një shembull të thjeshtë që ilustron funksionimin e algoritmit Huffman.
Në kodimin statik të Huffman, karaktereve hyrëse (vargjeve të biteve me gjatësi të ndryshme) u caktohen vargje bit, gjithashtu me gjatësi të ndryshueshme - kodet e tyre. Gjatësia e kodit të çdo karakteri merret në përpjesëtim me logaritmin binar të frekuencës së tij, marrë me shenjën e kundërt. POR grup i përbashkët i të gjithë personazheve të ndryshëm që hasen përbën alfabetin e rrymës. Ky kodim është prefiks, gjë që e bën të lehtë dekodimin e tij në rrjedhën që rezulton, sepse, me kodimin e prefiksit, kodi i asnjë karakteri nuk është një parashtesë e kodit të ndonjë karakteri tjetër - alfabeti është unik.
Edhe 10-15 vjet më parë, arkivuesit përdoreshin kryesisht për të kursyer hapësirë hard disqet dhe në mënyrë që të vendosen të dhënat maksimale në floppy disk. Megjithatë, kohët kanë ndryshuar. Askush nuk ka përdorur disqe si një mjet për transferimin dhe ruajtjen e informacionit për një kohë të gjatë, dhe kostoja e disqeve është bërë aq e ulët sa askush nuk mendon as të kompresojë të dhënat për të kursyer hapësirë. Përveç kësaj, vëllimet e të dhënave janë bërë aq të mëdha saqë arkivimi dhe heqja e tyre për të kursyer hapësirë thjesht nuk është praktike, sepse kërkon shumë kohë. Epo, me të vërtetë, sot sasia e të dhënave në disqet e përdoruesve matet në terabajt. Tani imagjinoni se sa kohë do të duhej për të arkivuar një terabajt të dhënash. Kjo do të zgjasë jo një apo edhe dy orë, por të paktën 10-12 orë, domethënë kompjuteri do të duhet të lihet i ndezur gjithë natën.
Duket se arkivuesit sot duhet të humbasin gradualisht rëndësinë e tyre. Por asgjë e tillë nuk ndodh. Shumica dërrmuese e përdoruesve, midis programeve të tjera, kanë arkivues të instaluar ose përdorin një arkivues të integruar në sistemin operativ Windows (ne nuk i konsiderojmë sistemet e tjera operative në këtë botim).
Fakti është se emërimi i arkivorëve ka ndryshuar. Sot ato përdoren kryesisht për postimin e të dhënave në ueb. Shumica e drejtuesve në faqet e internetit të prodhuesve janë të vendosura në arkiva, dhe shumica e programeve në burime të ndryshme janë gjithashtu të arkivuara. Nga rruga, vetë përdoruesi, përpara se të ngarkojë ndonjë të dhënë në Rrjet (për shembull, në burimet e ndarjes së skedarëve), i paketon të dhënat në një arkiv.
në lidhje me tregu rus, atëherë kemi tre arkivuesit më të zakonshëm: WinRAR, WinZip dhe 7-Zip, të paraqitur në të dy versionet 32 dhe 64-bit. Janë ata që ne do t'i krahasojmë në këtë artikull. Megjithatë, së pari, le të hedhim një vështrim të shpejtë në disa aspektet teorike punë arkivimi.
Algoritmet e kompresimit të informacionit
Thelbi i çdo algoritmi të kompresimit të informacionit është të përftohet, me një transformim të caktuar të grupit fillestar të biteve të informacionit, në dalje një grup të caktuar. më të vogla. Për më tepër, të gjitha algoritmet e transformimit të të dhënave mund të ndahen me kusht në dy klasa: të kthyeshme dhe të pakthyeshme.
Një algoritëm i pakthyeshëm i kompresimit të informacionit nënkupton një transformim të tillë të sekuencës origjinale të biteve, në të cilën sekuenca dalëse e një madhësie më të vogël nuk lejon që sekuenca e hyrjes të rikthehet saktësisht. Përdoren algoritme të pakthyeshme të kompresimit, për shembull, në lidhje me të dhënat grafike, video dhe audio, dhe kjo çon gjithmonë në një humbje të cilësisë së tyre. Natyrisht, algoritmet për kompresimin e pakthyeshëm të të dhënave nuk përdoren në arkivues, dhe për këtë arsye ne nuk do t'i shqyrtojmë ato më tej.
Algoritmet e kthyeshme të kompresimit të të dhënave ju lejojnë të rivendosni saktësisht sekuencën origjinale të të dhënave nga sekuenca e ngjeshur. Janë këto algoritme që përdoren në arkivues. Karakteristikat e zakonshme të të gjitha algoritmeve të kompresimit janë raporti i kompresimit (raporti i vëllimeve të sekuencës së të dhënave origjinale dhe të ngjeshur), shkalla e ngjeshjes (koha e shpenzuar për arkivimin e një sasie të caktuar të dhënash) dhe cilësia e kompresimit (një vlerë që tregon sa fort sekuenca e të dhënave kompresohet duke aplikuar rikompresim në të sipas të njëjtit ose një algoritmi tjetër).
Teoria e kompresimit të informacionit, e njohur edhe si teoria e kodimit ekonomik të informacionit diskret, është një degë mjaft komplekse e shkencës matematikore. Sigurisht, prezantimi edhe i bazave të tij është shumë përtej qëllimit të këtij artikulli, dhe për këtë arsye ne do të shqyrtojmë vetëm sipërfaqësisht algoritme të ndryshme të kompresimit të informacionit pa hyrë në detaje. Përveç kësaj, shumë algoritme të kompresimit të të dhënave janë zhvilluar sot, dhe shqyrtimi i tyre është gjithashtu pjesë e detyrës sonë. Prandaj, ne do të përshkruajmë vetëm në mënyrë cilësore disa algoritme që na lejojnë të marrim ide e pergjithshme në lidhje me metodat e ngjeshjes së informacionit.
Algoritmi RLE
Një nga metodat më të vjetra dhe më të thjeshta të kompresimit të informacionit është algoritmi RLE (Run Length Encoding), pra algoritmi për kodimin e serive të sekuencave. Kjo metodë është shumë e thjeshtë për t'u zbatuar dhe është një nga algoritmet e arkivimit, dhe thelbi i saj është zëvendësimi i një serie (grupi) bajtësh të përsëritur me një bajt kodues dhe një numërues për numrin e përsëritjeve të tyre. Kjo do të thotë, një grup bajtësh identikë do të zëvendësohet nga një palë:<счетчик повторений, значение>, e cila redukton tepricën e të dhënave.
Në këtë algoritëm, shenja e numëruesit janë ato në dy bitet e sipërme të bajtit të lexuar. Për shembull, nëse dy bitët e parë janë 11, atëherë 6 bitët e mbetur ndahen në numërues, i cili mund të marrë vlera nga 1 në 64. Prandaj, një seri prej 64 bajtësh të përsëritur mund të përcaktohet me vetëm dy bajt, që është, i ngjeshur me 32 herë.
Ekziston një zbatim tjetër i këtij algoritmi, kur shenja e numëruesit është 1 në bajtin e parë të numëruesit. Në këtë rast, numëruesi mund të marrë vlera maksimale, e barabartë me 127 - dhe për këtë arsye raporti maksimal i kompresimit do të jetë i barabartë me 64.
Është e qartë se algoritmi RLE është efikas vetëm kur ka një numër të madh grupesh të gjata të bajteve identike. Nëse bajtët nuk përsëriten, atëherë përdorimi i metodës RLE çon në një rritje të madhësisë së skedarit.
Metoda RLE është përgjithësisht shumë efikase për kompresimin e grafikëve bitmap (BMP, PCX, TIF, GIF) sepse ato përmbajnë seri shumë të gjata të sekuencave të bajtit të përsëritur.
Kufizimi i alfabetit të informacionit
Një mënyrë tjetër mjaft e thjeshtë për të kompresuar informacionin mund të quhet kufizim alfabeti informativ. Vëmë re menjëherë se në praktikë një algoritëm i tillë nuk zbatohet, por prezantimi i kësaj metode do të ndihmojë për të kuptuar më mirë metodën e kodeve me gjatësi të ndryshueshme.
Në vijim, me alfabetin informativ do të nënkuptojmë grupin e simboleve të përdorura për të koduar sekuencën informative. Për shembull, supozoni se ka një mesazh me tekst. Çdo shkronjë e këtij mesazhi është e koduar duke përdorur një tabelë ASCII të përbërë nga 256 karaktere. Në këtë rast, saktësisht 8 bit (1 bajt) ndahen për kodimin e çdo karakteri. Në këtë rast, alfabeti i informacionit është të gjitha 256 karakteret e tabelës së kodimit ASCII.
Është e qartë se jo të gjitha 256 karakteret e tabelës ASCII mund të përdoren në mesazhin origjinal me tekst. Për shembull, nëse po flasim për një mesazh me tekst në rusisht, në të cilin nuk ka numra, atëherë mjaftojnë 64 karaktere (33 shkronja të vogla dhe 31 shkronja të mëdha). Nëse kësaj i shtojmë shenjat e pikësimit, paragrafin dhe shenjat e linjës së re, bëhet e qartë se numri i karaktereve nuk do të kalojë 100. Në këtë rast, mund të përdorni kodimin e karaktereve jo 8, por 7-bit, i cili ju lejon të merrni një tabelë me 128 karaktere. Kjo do të thotë, ne, si të thuash, kufizojmë alfabetin informativ, për shkak të të cilit mund të zvogëlojmë thellësinë e bitit të çdo karakteri të renditur. Mund të shkoni më tej - për të përcaktuar me saktësi numrin e karaktereve të përdorura në një mesazh me tekst. Nëse, për shembull, rezulton se në mesazh përdoren vetëm 30 karaktere (përfshirë karakteret e linjës së re), atëherë mund të përdoret një tabelë kodimi 5-bit që përmban 32 karaktere, dhe më pas raporti i kompresimit mesazh me tekst do të bëhet edhe më i madh. Në të vërtetë, nëse kodimi i karaktereve 8-bit përdoret në mesazhin origjinal, dhe kodimi i karaktereve 5-bit përdoret në mesazhin e ngjeshur, atëherë raporti i kompresimit do të jetë 8/5.
Megjithë thjeshtësinë e dukshme të metodës së kufizimit të alfabetit, në praktikë ajo nuk përdoret. Fakti është se metoda e përshkruar nuk lejon deshifrimin e saktë të mesazhit origjinal pa transferuar informacion shtesë. Në të vërtetë, pa ditur tabelat e kodimit të përdorura për të kompresuar informacionin, është e pamundur ta deshifrosh atë. Kjo do të thotë, së bashku me sekuencën e informacionit të koduar, është e nevojshme të transmetohen tabelat e kodimit. Është e qartë se në këtë rast fitimi nga përdorimi i një alfabeti të kufizuar reduktohet në zero.
Metoda e alfabetit të kufizuar ka edhe disavantazhe të tjera. Nëse mesazhi origjinal i informacionit përmban një numër të madh karakteresh të ndryshëm, atëherë nuk do të jetë e mundur të zvogëlohet thellësia e bitit të paraqitjes së karaktereve alfabetike dhe kjo metodë thjesht nuk do të funksionojë. Supozoni, për shembull, që mesazhi origjinal i informacionit përmban 129 karaktere nga një alfabet me 256 karaktere. Nuk do të jetë e mundur të përdoret kodimi i karaktereve 7-bit në këtë rast, pasi 7 bit do të kodojnë vetëm 128 karaktere. Prandaj, për 129 karaktere, do të duhet të përdorni të njëjtin kodim 8-bit si në alfabetin origjinal me 256 karaktere.
Kodet me gjatësi të ndryshueshme
Një nga disavantazhet kryesore të metodës hipotetike të kufizimit të alfabetit që kemi shqyrtuar është se ajo përdor një kod uniform kur të gjithë karakteret e alfabetit informues kanë të njëjtën gjatësi (8.7 bit ose më pak). Do të ishte më logjike të përdoret një sistem i tillë kodimi në të cilin gjatësia e kodit të karakterit varet nga frekuenca e shfaqjes së tij në mesazhin e informacionit. Kjo do të thotë, nëse në mesazhin informativ origjinal disa karaktere shfaqen më shpesh se të tjerët, atëherë është optimale të përdoren kode të shkurtra për ta, dhe ato më të gjata për ato të rralla.
Si shembull hipotetik, merrni parasysh mesazhin informues të mëposhtëm: "përplasje ajrore" , i cili përmban 14 karaktere. Supozoni se kemi një alfabet prej 14 karakteresh që na lejon të kodojmë këtë mesazh. Nëse përdoret një kod uniform, atëherë kërkohen 4 bit për çdo karakter të alfabetit (një gjatësi kodi prej 4 bitësh do të formojë 16 karaktere). Sidoqoftë, është e lehtë të shihet se në mesazhin tonë të informacionit simboli "a" shfaqet pesë herë, simboli "t" - dy herë, dhe pjesa tjetër e simboleve - një herë. Nëse për simbolin "a" përdorim një kod prej 2 bitësh, për simbolin "t" - 3 bit, dhe për pjesën tjetër të karaktereve - 4 bit, atëherë sigurisht që mund të kursejmë. Është e nevojshme vetëm të kuptohet se si të ndërtohen saktësisht kodet me gjatësi të ndryshueshme dhe se si saktësisht gjatësia e kodit duhet të varet nga frekuenca e simbolit në mesazhin informativ.
Nëse të gjithë personazhet janë përfshirë në mesazhin informues me të njëjtën frekuencë(equiprobable), atëherë me një alfabet informativ me N karaktere, çdo karakter do të duhet të kodohet saktësisht log 2 N pak. Në fakt, ky është një rast i kodit uniform.
Nëse simbolet kanë probabilitet të ndryshëm për t'u shfaqur në mesazhin informativ, atëherë, sipas teorisë së K. Shannon, simboli, probabiliteti i të cilit është i barabartë me p, është optimal dhe, ajo që është veçanërisht e rëndësishme, teorikisht është e mundur të shoqëroni një kod të gjatësisë -log 2 fq. Duke iu rikthyer shembullit tonë me mesazhin informativ "përplasje ajrore" dhe duke qenë se probabiliteti i shfaqjes së karakterit "a" (p(a)) është 5/14, probabiliteti i shfaqjes së karakterit "t" është 2. /14, dhe probabiliteti i shfaqjes së të gjithë karaktereve të tjera është 1/14, marrim se: për karakterin "a", gjatësia optimale e kodit është -log 2 (5/14) = 1,48 bit; për karakterin "t" - -log 2 (2/14) = 2.8 bit, dhe për të gjitha karakteret e tjera është -log 2 (1/14) = 3.8. Meqenëse në rastin tonë gjatësia e kodit mund të ketë vetëm një vlerë të plotë, atëherë, duke rrumbullakosur lart, marrim se për simbolin "a" është optimale të përdoret një kod me gjatësi 2 bit, për simbolin "t" - 3. bit të gjata, dhe për pjesën tjetër - 4 bit të gjata.
Le të llogarisim raportin e kompresimit kur përdorim këtë kodim. Nëse do të përdorej një kod uniform i bazuar në një alfabet me 14 karaktere, atëherë do të kërkoheshin 56 bit për të koduar fjalën "përplasje ajrore". Kur përdorni kode me gjatësi të ndryshueshme, do të kërkohen 5×2 bit + 2×3 bit + 7×4 bit = 44 bit, d.m.th. raporti i kompresimit do të jetë 1.27.
Tani merrni parasysh algoritmet për marrjen e kodeve me gjatësi të ndryshueshme.
kodimi i prefiksit
Shumica metodë e thjeshtë marrja e kodeve me gjatësi të ndryshueshme është i ashtuquajturi kodim prefiks, i cili ju lejon të merrni kode me gjatësi të plotë. tipar kryesor kodet e parashtesave qëndrojnë në faktin se brenda secilit prej sistemeve të tyre kodet më të shkurtra nuk përkojnë me fillimin (prefiksin) e kodeve më të gjata. Është kjo veti e kodeve të prefiksit që e bën shumë të lehtë dekodimin e informacionit.
Le të shpjegojmë këtë veti të kodeve të parashtesave nga shembull specifik. Le të ketë një sistem prej tre kodesh prefiks: (0, 10, 11). Siç mund ta shihni, kodi më i shkurtër 0 nuk përkon me fillimin e kodeve më të gjata 10 dhe 11. Lëreni kodin 0 të specifikojë karakterin "a", kodin 10 karakterin "m" dhe kodin 11 karakterin "p". Pastaj fjala "kornizë" është e koduar nga sekuenca 110100. Le të përpiqemi të deshifrojmë këtë sekuencë. Meqenëse biti i parë është 1, karakteri i parë mund të jetë vetëm "m" ose "p" dhe përcaktohet nga vlera e bitit të dytë. Meqenëse biti i dytë është 1, karakteri i parë është "p". Biti i tretë është 0 dhe përputhet në mënyrë unike me karakterin "a". Biti i katërt është 1, domethënë, duhet të shikoni vlerën e bitit tjetër, i cili është 0, atëherë karakteri i tretë është "m". Biti i fundit është 0, i cili përputhet në mënyrë unike me karakterin "a". Kështu, vetia e kodeve të parashtesave, e cila konsiston në faktin se kodet më të shkurtra nuk mund të përkojnë me fillimin e kodeve më të gjata, bën të mundur deshifrimin e qartë të një mesazhi informacioni të koduar me kode parashtesash me gjatësi të ndryshueshme.
Kodet e parashtesave zakonisht merren nga kodet e ndërtimit (për sistemin binar). Çdo nyje e brendshme e një peme të tillë binare ka dy skaje dalëse, dhe njëra skaj i korrespondon karakter binar"0" dhe tjetra - "1". Për saktësi, mund të pajtohemi që skajit të majtë duhet t'i caktohet simboli "0", dhe skajit të djathtë - simboli "1".
Meqenëse nuk mund të ketë cikle në një pemë, mund të ketë gjithmonë vetëm një rrugë nga nyja rrënjë në nyjen e gjetheve. Nëse skajet e pemës janë të numëruara, atëherë çdo rrugë e tillë korrespondon me një sekuencë binare unike. Sekuenca e të gjitha sekuencave të tilla do të formojë një sistem kodesh parashtesash.
Për shembullin e konsideruar të një sistemi me tre kode parashtesash: (0, 10, 11), të cilat përcaktojnë simbolet "a", "m" dhe "p", pema e kodit është paraqitur në Fig. një.
Oriz. 1. Pema e kodit për sistemin
prej tre kodeve prefiks: (0, 10, 11)
Komoditeti i përfaqësimit të pemës së kodeve të parashtesave qëndron në faktin se është struktura e pemës që bën të mundur formimin e kodeve me gjatësi të ndryshueshme që plotësojnë kushtin kryesor të kodeve të parashtesave, domethënë kushtin që kodet më të shkurtra të mos përkojnë me fillimi i kodeve më të gjata.
Deri më tani, ne kemi shqyrtuar vetëm idenë e kodeve të prefiksit me gjatësi të ndryshueshme. Sa i përket algoritmeve për marrjen e kodeve të prefiksit, ato mund të zhvillohen mjaft, por më të famshmet janë dy metoda: Shannon-Fano dhe Huffman.
Algoritmi Shannon-Fano
Ky algoritëm për marrjen e kodeve të prefiksit u propozua në mënyrë të pavarur nga R. Fano dhe K. Shannon, është si më poshtë. Në hapin e parë, të gjitha simbolet e sekuencës fillestare të informacionit renditen në probabilitete zbritëse ose në rritje të shfaqjes së tyre (frekuencat e shfaqjes së tyre), pas së cilës seria e renditur e simboleve në një vend ndahet në dy pjesë në mënyrë që në secilën prej tyre. shuma e frekuencave të simboleve është afërsisht e njëjtë. Si demonstrim, merrni parasysh fjalën tashmë të njohur "përplasje ajrore" .
Nëse personazhet që përbëjnë një fjalë të caktuar renditen në rend zbritës të shpeshtësisë së shfaqjes së tyre, atëherë marrim sekuencën e mëposhtme: (a(5), m(2), b(1), u(1), k( 1), c(1), p(1), o(1), f(1)) (në kllapa tregohet frekuenca e përsëritjes së një simboli në një fjalë). Më pas, ne duhet ta ndajmë këtë sekuencë në dy pjesë në mënyrë që në secilën prej tyre shuma e frekuencave të simboleve të jetë afërsisht e njëjtë (për aq sa është e mundur). Është e qartë se seksioni do të kalojë midis simboleve "t" dhe "c", si rezultat i të cilave formohen dy sekuenca: (a (5), t (2)) dhe (në (1), u (1 ), k (1), c(1), p(1), o(1), φ(1)). Për më tepër, shumat e frekuencave të përsëritjes së simboleve në sekuencën e parë dhe të dytë do të jenë të njëjta dhe të barabarta me 7.
Në hapin e parë të ndarjes së një sekuence karakteresh, marrim shifrën e parë të kodit të çdo karakteri. Rregulli këtu është i thjeshtë: për ato karaktere që janë në sekuencën në të majtë, kodi do të fillojë me "0", dhe për ata në të djathtë - me "1".
Në veçanti, sekuenca (a(5), m(2)) do të ndahet në dy karaktere të veçanta: a(5) dhe m(2) (nuk ka opsione të tjera ndarjeje). Atëherë shifra e dytë e kodit për simbolin "a" është "0", dhe për simbolin "t" - "1". Meqenëse, si rezultat i ndarjes së sekuencës, morëm elementë të veçantë, ato nuk ndahen më dhe për karakterin "a" marrim kodin 00, dhe për karakterin "t" - kodin 01.
Sekuenca (në(1), u(1), k(1), c(1), p(1), o(1), f(1)) mund të ndahet ose në sekuenca (në(1), u(1), k(1)) dhe (c(1), p(1), o(1), φ(1)), ose në (v(1), u(1), k(1) ), (c(1)) dhe (p(1), o(1), φ(1)).
Në rastin e parë, shuma e frekuencave të simboleve në sekuencën e parë dhe të dytë do të jetë përkatësisht 3 dhe 4, dhe në rastin e dytë, përkatësisht 4 dhe 3. Për saktësi, ne përdorim opsionin e parë.
Për karakteret e sekuencës së re që rezulton (v(1), u(1), k(1)) (kjo është sekuenca e majtë), dy shifrat e para të kodit do të jenë 10, dhe për sekuencën (c( 1), p(1), o(1), f(1)) - 11.
Në shembullin tonë (Fig. 2 dhe 3), është marrë sistemi i mëposhtëm i kodeve të parashtesave: "a" - 00, "t" - 01, "c" - 100, "i" - 1010, "k" - 1011, "s" - 1100, "p" - 1101, "o" - 1110, "f" - 1111. Siç mund ta shihni, kodet më të shkurtra nuk janë fillimi i kodeve më të gjata, domethënë plotësohet vetia kryesore e kodeve të parashtesave. .
Oriz. 2. Demonstrimi i algoritmit Shannon-Fano
Oriz. 3. Pema e kodit për fjalën "përplasje ajrore"
në algoritmin Shannon-Fano
Algoritmi Huffman
Algoritmi Huffman është një tjetër algoritëm për marrjen e kodeve të prefiksit me gjatësi të ndryshueshme. Ndryshe nga algoritmi Shannon-Fano, i cili parashikon ndërtimin pema e kodit nga lart poshtë, ky algoritëm nënkupton ndërtimin e një peme kodi në rend të kundërt, domethënë nga poshtë lart (nga nyjet e gjetheve në nyjen rrënjë).
Në fazën e parë, si në algoritmin Shannon-Fano, sekuenca fillestare e simboleve renditet në rend zbritës të shpeshtësisë së përsëritjes së simboleve (elementet e sekuencës). Për shembullin e diskutuar më parë me fjalën "përplasje ajrore" marrim sekuencën e mëposhtme të renditur të elementeve: (a(5), m(2), b(1), u(1), k(1), c(1), p(1), o(1), f(1)).
Më pas, dy elementët e fundit të sekuencës zëvendësohen me element i ri S1, të cilit i caktohet një përsëritshmëri e barabartë me shumën e përsëritshmërisë së elementeve origjinale. Pastaj kryhet një renditje e re e elementeve të sekuencës në përputhje me përsëritjen e tyre. Në rastin tonë, dy elementët e fundit o(1) dhe f(1) zëvendësohen nga elementi S1(2), dhe sekuenca e re e renditur do të marrë formën: (a(5), m(2), S1( 2), c(1), u(1), k(1), c(1), p(1)).
Vazhdimi i kësaj procedure të zëvendësimit të dy elementet e fundit sekuencë në një element të ri me përsëritshmëri totale dhe ri-renditje pasuese të sekuencës në përputhje me përsëritshmërinë e elementeve, do të vijmë në një situatë ku vetëm një element mbetet në sekuencë (Fig. 4).
Oriz. 4. Demonstrimi i algoritmit Huffman
në shembullin e fjalës "përplasje ajrore"
Njëkohësisht me zëvendësimin e elementeve dhe riorganizimin e sekuencës, ndërtohet një pemë binare e kodit. Algoritmi për ndërtimin e një peme është shumë i thjeshtë: operacioni i kombinimit (zëvendësimit) të dy elementeve të një sekuence gjeneron një element të ri nyje në pemën e kodit. Kjo do të thotë, nëse shikoni pemën nga poshtë lart, skajet e pemës koduese vijnë gjithmonë nga elementët e zëvendësuar dhe konvergojnë në një element të ri nyje që korrespondon me elementin e sekuencës së marrë nga zëvendësimi (Fig. 5). Në këtë rast, skajit të majtë të pemës së kodit mund t'i caktohet vlera "0", dhe skajit të djathtë - "1". Këto vlera më vonë do të shërbejnë si elementë të kodit të prefiksit.
Oriz. 5. Ndërtimi i një peme kodi
në algoritmin Huffman
(duke zëvendësuar elementet "o" dhe "f"
element i ri S1)
Pema e plotë e kodit Huffman për një fjalë "përplasje ajrore" treguar në fig. 6.
Oriz. 6. Pema e kodit të plotë për fjalën "përplasje ajrore",
ndërtuar sipas algoritmit Huffman
Duke ecur përgjatë skajeve të pemës së kodit nga lart poshtë, është e lehtë të merrni kodet e parashtesave për të gjithë personazhet e alfabetit tonë informues:
Tani nëse përpiqeni të shkruani një fjalë "përplasje ajrore" në kodimin Huffman, marrim një sekuencë 41-bitësh 0 1101 11000 0 11001 0 111 0 1010 111 1011 1000 1001 0. Është interesante të theksohet se kur përdorim Shannon-Fano, marrim gjithashtu një kod prefiks 1-bit. fjala “përplasje ajri”. Kjo do të thotë, në një shembull specifik, efikasiteti i kodimit të Huffman dhe Shannon-Fano është i njëjtë. Por nëse marrim parasysh se alfabeti i vërtetë i informacionit është 256 karaktere (dhe jo 14, si në shembullin tonë), dhe sekuencat reale të informacionit janë skedarë të çdo përmbajtje dhe gjatësi, atëherë lind pyetja për kodin optimal të prefiksit, d.m.th. , kodi që ju lejon të merrni gjatësinë minimale të sekuencës së daljes.
Mund të vërtetohet se sistemi i kodit i marrë duke përdorur algoritmin Huffman është më i miri ndër të gjithë sistemet e mundshme kodet e parashtesave në kuptimin që gjatësia e sekuencës së informacionit të koduar që rezulton është minimale. Kjo do të thotë, algoritmi Huffman është optimal.
Disavantazhi kryesor i algoritmit Huffman është kompleksiteti i procesit të ndërtimit të një sistemi kodesh. Sidoqoftë, është algoritmi optimal i Huffman-it ai që është algoritmi më i zakonshëm i gjenerimit të kodit me gjatësi të ndryshueshme dhe është i mishëruar në shumicën e shërbimeve për kompresimin dhe arkivimin e informacionit.
Kodimi aritmetik
Siç e kemi vërejtur tashmë, sipas kriterit Shannon, kodi optimal është ai në të cilin një kod me gjatësi –log 2 caktohet për çdo karakter. fq pak. Dhe nëse, për shembull, probabiliteti i një karakteri të caktuar është 0.2, atëherë gjatësia optimale e kodit të tij do të jetë -log 2 0.2 = 2.3 bit. Është e qartë se kodet e prefiksit nuk mund të ofrojnë një gjatësi të tillë kodi, dhe për këtë arsye nuk janë optimale. Në përgjithësi, gjatësia e kodit e përcaktuar nga kriteri Shannon është vetëm një kufi teorik. Pyetja e vetme është se cila metodë e kodimit ju lejon të afroheni sa më afër këtij kufiri teorik. Kodet e prefiksave me gjatësi të ndryshueshme janë efikase dhe mjaft të lehta për t'u zbatuar, por ka metoda më efikase të kodimit, në veçanti algoritmi i kodimit aritmetik.
Ideja e kodimit aritmetik është që në vend të kodimit të karaktereve individuale, kodi i caktohet njëkohësisht të gjithë sekuencës së informacionit. Në të njëjtën kohë, është e qartë se gjatësia e kodit për një karakter individual mund të mos jetë një numër i plotë. Kjo është arsyeja pse kjo metodë e kodimit është shumë më efikase se kodimi me prefiks dhe është më në përputhje me kriterin Shannon.
Ideja e algoritmit të kodimit aritmetik është si më poshtë. Si në të gjitha metodat e kodimit të konsideruara më parë, çdo simbol i sekuencës origjinale të informacionit karakterizohet nga probabiliteti i tij. Sekuencës origjinale të pakoduar i caktohet një gjysmë interval )
