• Tutorial

Shumë kohë më parë, kur isha ende një nxënës naiv, papritmas u bëra tmerrësisht kurioz: si me magji zënë më pak hapësirë ​​të dhënat në arkiva? Pasi mbaja dial-up-in tim besnik, fillova të shfletoj në internet në kërkim të një përgjigjeje dhe gjeta shumë artikuj me një prezantim mjaft të detajuar të informacionit që më interesonte. Por asnjëri prej tyre atëherë nuk më dukej i lehtë për t'u kuptuar - listimet e kodeve dukej se ishin shkrim e këndim kinez dhe përpjekjet për të kuptuar terminologjinë e pazakontë dhe formula të ndryshme ishin të pasuksesshme.

Prandaj, qëllimi i këtij artikulli është të japë një ide të algoritmeve më të thjeshta të kompresimit për ata që, me njohuritë dhe përvojën e tyre, ende nuk i lejojnë ata të kuptojnë menjëherë më shumë literaturë profesionale, ose profili i të cilëve është larg temave të ngjashme. ato. Do t'ju tregoj me gishta për disa nga algoritmet më të thjeshta dhe do të jap shembuj të zbatimit të tyre pa listat e kodeve të kilometrave.

Unë do t'ju paralajmëroj menjëherë se nuk do të marr parasysh detajet e zbatimit të procesit të kodimit dhe nuanca të tilla si kërkimi efektiv i dukurive të një vargu. Artikulli do të prekë vetëm vetë algoritmet dhe metodat e paraqitjes së rezultatit të punës së tyre.

RLE - uniformitet kompakt

Algoritmi RLE është ndoshta më i thjeshtë nga të gjithë: thelbi i tij është të kodojë përsëritjet. Me fjalë të tjera, ne marrim sekuenca të elementeve identike dhe i "kolapsojmë" ato në çifte sasi/vlerë. Për shembull, një varg si "AAAAAAAABCCCC" mund të konvertohet në një varg si "8 × A, B, 4 × C". Kjo është, në përgjithësi, gjithçka që duhet të dini rreth algoritmit.

Shembull zbatimi

Supozoni se kemi një grup koeficientësh të plotë që mund të marrin vlera nga 0 në 255. Logjikisht, arritëm në përfundimin se është e arsyeshme ta ruajmë këtë grup si një grup bajtash:
të dhëna karakteresh të panënshkruara = (0, 0, 0, 0, 0, 0, 4, 2, 0, 4, 4, 4, 4, 4, 4, 4, 80, 80, 80, 80, 0, 2, 2 , 2, 2, 255, 255, 255, 255, 255, 0, 0);

Për shumë, do të jetë shumë më e njohur për të parë këto të dhëna në formën e një hale hex:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF FF 00 00

Pas disa mendimeve, vendosëm që do të ishte mirë të kompresonim disi grupe të tilla për të kursyer hapësirë. Për ta bërë këtë, ne i analizuam ato dhe identifikuam një model: shumë shpesh ka nënsekuenca që përbëhen nga të njëjtat elementë. Sigurisht, RLE është e dobishme për këtë!

Le të kodojmë të dhënat tona duke përdorur njohuritë e marra rishtazi: 6 × 0, 4, 2, 0, 7 × 4, 4 × 80, 0, 4 × 2, 5 × 255, 2 × 0.

Është koha që disi të paraqesim rezultatin tonë në një formë të kuptueshme nga kompjuteri. Për ta bërë këtë, në rrjedhën e të dhënave, ne duhet të ndajmë disi bajtet e vetme nga vargjet e koduara. Meqenëse i gjithë diapazoni i vlerave të bajtit përdoret nga të dhënat tona, nuk do të jetë e mundur që thjesht të ndajmë ndonjë varg vlerash për qëllimet tona.

Ekzistojnë të paktën dy mënyra për të dalë nga kjo situatë:

1. Zgjidhni një vlerë bajt si tregues të zinxhirit të ngjeshur dhe në rast përplasjeje me të dhënat reale, t'i shpëtoni. Për shembull, nëse përdorim vlerën 255 për qëllime "shërbimi", atëherë kur ta takojmë këtë vlerë në të dhënat hyrëse, do të duhet të shkruajmë "255, 255" dhe pas treguesit të përdorim një maksimum prej 254.
2. Për të strukturuar të dhënat e koduara, duke specifikuar numrin jo vetëm për elementët e vetëm të përsëritur, por edhe të mëtejshëm të mëtejshëm. Atëherë do të dimë paraprakisht se ku janë të dhënat.

Metoda e parë në rastin tonë nuk duket të jetë efektive, kështu që, ndoshta, do t'i drejtohemi të dytës.

Pra, tani kemi dy lloje sekuencash: vargjet e elementeve të vetme (si "4, 2, 0") dhe vargjet e elementeve identike (si "0, 0, 0, 0, 0, 0"). Le të ndajmë një bit në bajtet e "shërbimit" për llojin e sekuencës: 0 - elemente të vetme, 1 - identike. Le të marrim për këtë, të themi, pjesën më të rëndësishme të një bajt.

Në 7 bitet e mbetura, do të ruajmë gjatësitë e sekuencave, d.m.th. gjatësia maksimale e sekuencës së koduar është 127 bajt. Ne mund të ndajmë për nevojat e shërbimit, të themi, dy bajt, por në rastin tonë sekuenca të tilla të gjata janë jashtëzakonisht të rralla, kështu që është më e lehtë dhe më ekonomike t'i ndajmë ato thjesht në ato më të shkurtra.

Rezulton se në rrjedhën e daljes do të shkruajmë së pari gjatësinë e sekuencës, dhe më pas ose një vlerë të përsëritur, ose një zinxhir elementësh që nuk përsëriten me gjatësinë e specifikuar.

Gjëja e parë që duhet t'ju bie në sy është se në këtë situatë kemi disa vlera të papërdorura. Nuk mund të ketë sekuenca me gjatësi zero, kështu që mund të rrisim gjatësinë maksimale në 128 bajt duke zbritur një nga gjatësia kur kodojmë dhe duke shtuar një kur deshifrojmë. Kështu, ne mund të kodojmë gjatësitë nga 1 në 128 në vend të gjatësive nga 0 në 127.

Gjëja e dytë që mund të vërehet është se nuk ka sekuenca të elementeve identike me gjatësi njësi. Prandaj, ne do të zbresim një më shumë nga vlera e gjatësisë së sekuencave të tilla gjatë kodimit, duke rritur kështu gjatësinë e tyre maksimale në 129 (gjatësia maksimale e një zinxhiri elementësh të vetëm është ende e barabartë me 128). ato. Zinxhirët e elementëve identikë mund të kenë një gjatësi nga 2 në 129.

Le të kodojmë përsëri të dhënat tona, por tani në një formë të kuptueshme nga kompjuteri. Ne do t'i shkruajmë bajtet e sipërme si, ku T është lloji i sekuencës dhe L është gjatësia. Menjëherë do të marrim parasysh që gjatësitë i shkruajmë në një formë të modifikuar: në T = 0 zbresim një nga L, dhe në T = 1 - dy.

0, , 4, 2, 0, , 4, , 80, , 0, , 2, , 255, , 0

Le të përpiqemi të deshifrojmë rezultatin tonë:

• ... T = 1, që do të thotë se bajt-i tjetër do të përsëritet L + 2 (4 + 2) herë: 0, 0, 0, 0, 0, 0.
• ... T = 0, kështu që ne thjesht lexojmë L + 1 (2 + 1) bajt: 4, 2, 0.
• ... T = 1, ne përsërisim bajtin tjetër 5 + 2 herë: 4, 4, 4, 4, 4, 4, 4.
• ... T = 1, ne përsërisim bajtin tjetër 2 + 2 herë: 80, 80, 80, 80.
• ... T = 0, lexo 0 + 1 bajt: 0.
• ... T = 1, përsëritni bajtin 2 + 2 herë: 2, 2, 2, 2.
• ... T = 1, ne përsërisim bajt 3 + 2 herë: 255, 255, 255, 255, 255.
• ... T = 1, ne përsërisim bajt 0 + 2 herë: 0, 0.

Dhe tani hapi i fundit: ruajeni rezultatin si një grup bajt. Për shembull, një çift i paketuar në bajt do të duket kështu:

Si rezultat, marrim sa vijon:
0000: 84 00 02 04 02 00 85 04 82 80 00 00 82 02 83 FF
0010: 80 00

Në një mënyrë kaq të thjeshtë, për këtë shembull të të dhënave hyrëse, morëm 18 nga 32 bajt. Jo një rezultat i keq, veçanërisht duke pasur parasysh që në zinxhirë më të gjatë mund të rezultojë shumë më i mirë.

Përmirësime të mundshme

Efikasiteti i një algoritmi varet jo vetëm nga vetë algoritmi, por edhe nga mënyra se si zbatohet. Prandaj, për të dhëna të ndryshme, mund të zhvilloni variacione të ndryshme të kodimit dhe paraqitjes së të dhënave të koduara. Për shembull, kur kodoni imazhe, mund të krijoni zinxhirë me gjatësi të ndryshueshme: ndani një bit për treguesin e një zinxhiri të gjatë dhe nëse është vendosur në një, atëherë ruani gjatësinë edhe në bajtin tjetër. Pra, ne sakrifikojmë gjatësinë e zinxhirëve të shkurtër (65 elementë në vend të 129), por nga ana tjetër, japim mundësinë për të koduar zinxhirë deri në 16385 elementë të gjatë (2 14 + 2) me vetëm tre bajt!

Efikasitet shtesë mund të arrihet përmes përdorimit të teknikave të kodimit heuristik. Për shembull, le të kodojmë vargun e mëposhtëm në mënyrën tonë: "ABBA". Marrim ", A,, B,, A" - d.m.th. Kemi kthyer 4 bajt në 6, kemi fryrë të dhënat origjinale sa një herë e gjysmë! Dhe sa më shumë sekuenca të tilla të shkurtra alternative të llojeve të ndryshme, aq më shumë të dhëna të tepërta. Nëse e marrim këtë parasysh, atëherë do të ishte e mundur të kodojmë rezultatin si ", A, B, B, A" - do të kishim shpenzuar vetëm një bajt shtesë.

LZ77 - Shkurtësi në përsëritje

LZ77 është një nga algoritmet më të thjeshtë dhe më të njohur në familjen LZ. I quajtur sipas krijuesve të tij: Abraham Lempel (Abraham L empel) dhe Jacob Ziva (Jacob Z iv). Numrat 77 në titull nënkuptojnë vitin 1977, në të cilin u botua një artikull që përshkruan këtë algoritëm.

Ideja bazë është që të kodohen të njëjtat sekuenca elementesh. Kjo do të thotë, nëse një zinxhir elementësh ndodh më shumë se një herë në të dhënat hyrëse, atëherë të gjitha shfaqjet e mëvonshme të tij mund të zëvendësohen me "lidhje" në instancën e tij të parë.

Ashtu si pjesa tjetër e algoritmeve në këtë familje të familjes, LZ77 përdor një fjalor që ruan sekuencat e hasura më parë. Për këtë, ai zbaton parimin e të ashtuquajturit. "Dritarja rrëshqitëse": zona, gjithmonë përpara pozicionit aktual të kodimit, brenda së cilës mund të adresojmë lidhjet. Kjo dritare është një fjalor dinamik për këtë algoritëm - çdo element në të korrespondon me dy atribute: pozicioni në dritare dhe gjatësia. Edhe pse në një kuptim fizik, është vetëm një pjesë e kujtesës që ne e kemi koduar tashmë.

Shembull zbatimi

Le të përpiqemi të kodojmë diçka tani. Le të krijojmë një linjë të përshtatshme për këtë (kërkoj falje paraprakisht për absurditetin e saj):

“Ngjeshja dhe dekompresimi lënë një përshtypje. Hahahahaha!"

Kështu do të duket në memorie (enkodimi ANSI):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 Kompresimi
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 dhe dekompresoni
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 ssion lë një i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 shtypje. Hahah
0040: 61 68 61 68 61 21 ahaha!

Nuk kemi vendosur ende për madhësinë e dritares, por do të biem dakord që ajo të jetë më e madhe se madhësia e vargut të koduar. Le të përpiqemi të gjejmë të gjitha vargjet e karaktereve të përsëritura. Ne do ta konsiderojmë një zinxhir si një sekuencë simbolesh me një gjatësi prej më shumë se një. Nëse zinxhiri është pjesë e një zinxhiri më të gjatë të përsëritur, ne do ta injorojmë atë.

“Ngjeshja dhe largimi [an] i. Hah!"

Për qartësi më të madhe, le të shohim diagramin ku korrespondenca e sekuencave të përsëritura dhe shfaqjet e tyre të para janë të dukshme:

Ndoshta e vetmja pikë e paqartë këtu do të jetë sekuenca "Hahahahaha!" Por nuk ka asgjë të pazakontë këtu, ne përdorëm një mashtrim që lejon algoritmin ndonjëherë të sillet si RLE e përshkruar më parë.

Fakti është se kur shpaketojmë, do të lexojmë numrin e specifikuar të karaktereve nga fjalori. Dhe meqenëse e gjithë sekuenca është periodike, d.m.th. Meqenëse të dhënat në të përsëriten me një periudhë të caktuar, dhe simbolet e periudhës së parë do të vendosen pikërisht përballë pozicionit të shpaketimit, atëherë ne mund të rikrijojmë të gjithë zinxhirin prej tyre duke kopjuar thjesht simbolet e periudhës së mëparshme në tjetër.

Me këtë të rregulluar. Tani le të zëvendësojmë dublikatat e gjetura me lidhje në fjalor. Lidhjen do ta shkruajmë në format, ku P është pozicioni i shfaqjes së parë të zinxhirit në varg, L është gjatësia e tij.

“Ngjeshja dhe t de largimi i. Hah!"

Por mos harroni se kemi të bëjmë me një dritare rrëshqitëse. Për të kuptuar më mirë, në mënyrë që lidhjet të mos varen nga madhësia e dritares, ne do të zëvendësojmë pozicionet absolute me diferencën midis tyre dhe pozicionit aktual të kodimit.

“Ngjeshja dhe t de largimi i. Hah!"

Tani na duhet vetëm të zbresim P nga pozicioni aktual i kodimit për të marrë pozicionin absolut në varg.

Është koha për të vendosur për madhësinë e dritares dhe gjatësinë maksimale të frazës së koduar. Meqenëse kemi të bëjmë me tekst, rrallë do të ketë sekuenca veçanërisht të gjata të përsëritura në të. Pra, le të ndajmë për gjatësinë e tyre, të themi, 4 bit - një kufi prej 15 karaktere në një kohë është i mjaftueshëm për ne.

Por madhësia e dritares tashmë varet nga sa thellë do të kërkojmë për zinxhirë identikë. Meqenëse kemi të bëjmë me tekste të vogla, do të ishte e drejtë të plotësojmë numrin e biteve që përdorim në dy bajt: do të adresojmë lidhje në intervalin 4096 bajt, duke përdorur 12 bit për këtë.

Ne e dimë nga përvoja me RLE se jo të gjitha vlerat mund të përdoren. Natyrisht, një lidhje mund të ketë një vlerë minimale prej 1, prandaj, për të adresuar përsëri në intervalin 1..4096, duhet të zbresim një nga lidhja gjatë kodimit dhe ta shtojmë përsëri kur deshifrojmë. E njëjta gjë është edhe me gjatësitë e sekuencave: në vend të 0..15 do të përdorim diapazonin 2..17, pasi nuk punojmë me gjatësi zero dhe karakteret individuale nuk janë sekuenca.

Pra, le të paraqesim tekstin tonë të koduar me këto ndryshime:

“Ngjeshja dhe t de largimi i. Hah!"

Tani, përsëri, ne duhet të ndajmë disi zinxhirët e ngjeshur nga pjesa tjetër e të dhënave. Mënyra më e zakonshme është të ripërdorni strukturën dhe të specifikoni drejtpërdrejt se ku janë të dhënat e kompresuara dhe ku jo. Për ta bërë këtë, ne do t'i ndajmë të dhënat e koduara në grupe me tetë elementë (simbole ose lidhje), dhe para secilit prej këtyre grupeve do të fusim një bajt, ku secili bit korrespondon me llojin e elementit: 0 për një simbol dhe 1. për një lidhje.

Ndahemi në grupe:

• "Kompjuteri"
• "Reagimi"
• "Dhe t de"
• "Largohu"
• “Unë. hah"

Përbërja e grupeve:

"(0.0.0.0.0.0.0.0) Rezsioni i komp (0.0.0.0.0.0.0.0) (0.0.0.0.0.1 , 0,0) dhe t de (1,0,0,0,0,0,1 ,0) largohem (0,1,0,0,0,0,0,1) i. Hah (0)!"

Kështu, nëse gjatë zbërthimit hasim bitin 0, atëherë thjesht lexojmë karakterin në rrjedhën e daljes, nëse biti 1, lexojmë lidhjen dhe me referencë lexojmë sekuencën nga fjalori.

Tani gjithçka që duhet të bëjmë është të grupojmë rezultatin në një grup bajt. Le të biem dakord që ne përdorim bit dhe bajt në rendin më domethënës. Le të shohim se si lidhjet paketohen në bajt duke përdorur një shembull:

Si rezultat, rrjedha jonë e ngjeshur do të duket kështu:

0000: 00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f # Kompjuteri # ressio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #dhe t ## de ### l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 eave ## # i ##. Hah
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 ###!

Përmirësime të mundshme

Në parim, gjithçka që u përshkrua për RLE do të jetë e vërtetë këtu. Në veçanti, për të demonstruar përfitimet e kodimit heuristik, merrni parasysh shembullin e mëposhtëm:

“E gjatë goooooong. Lidhur më shumë."

Le të gjejmë sekuenca vetëm për fjalën "looooooower":

“E gjatë goooooong. Ishin të lidhur."

Për të koduar një rezultat të tillë, na duhen katër bajt për lidhje. Sidoqoftë, do të ishte më ekonomike ta bëni këtë:

“E gjatë goooooong. Unë isha i lidhur."

Atëherë do të shpenzonim një bajt më pak.

Në vend të një përfundimi

Megjithë thjeshtësinë e tyre dhe efikasitetin në dukje jo shumë të madh, këto algoritme ende përdoren gjerësisht në fusha të ndryshme të sferës së IT.

Plus i tyre është thjeshtësia dhe shpejtësia, dhe algoritme më komplekse dhe efikase mund të bazohen në parimet dhe kombinimet e tyre.

Shpresoj që thelbi i këtyre algoritmeve të paraqitura në këtë mënyrë do të ndihmojë dikë të kuptojë bazat dhe të fillojë të shikojë drejt gjërave më serioze.

Kodimi me gjatësi ekzekutimi (RLE) ose kodimi i përsëritur është një algoritëm i thjeshtë i kompresimit të të dhënave që funksionon me seri të dhënash, domethënë sekuenca në të cilat i njëjti karakter shfaqet disa herë me radhë. Gjatë kodimit, një varg karakteresh identike që përbëjnë një seri zëvendësohet me një varg që përmban vetë karakterin e përsëritur dhe numrin e përsëritjeve të tij.

Karakteristikat e algoritmit RLE:

Raportet e kompresimit: Opsioni i parë: 32, 2, 0.5. Opsioni i dytë: 64, 3, 128/129. (Shanset më të mira, mesatare, më të këqija). Klasa e imazhit: Algoritmi është i fokusuar në imazhe me një numër të vogël ngjyrash: grafika biznesi dhe shkencore. Simetria: Përafërsisht një.

Karakteristikat: Aspektet pozitive të algoritmit, ndoshta, mund t'i atribuohen vetëm faktit se ai nuk kërkon memorie shtesë gjatë arkivimit dhe heqjes së arkivimit, dhe gjithashtu funksionon shpejt. Një tipar interesant i kodimit në grup është se shkalla e arkivimit për disa imazhe mund të rritet ndjeshëm thjesht duke ndryshuar rendin e ngjyrave në paletën e imazheve.

Versioni i parë i algoritmit

Ky algoritëm është jashtëzakonisht i thjeshtë për t'u zbatuar. Kodimi në grup - nga kodimi i gjatësisë angleze të ekzekutimit (RLE) - një nga algoritmet më të vjetër dhe më të thjeshtë për arkivimin e grafikëve. Imazhi në të (si në disa algoritme të përshkruara më poshtë) tërhiqet në një varg bajtësh përgjatë vijave raster. Vetë kompresimi në RLE ndodh për shkak të faktit se në imazhin origjinal ka vargje me të njëjtat bajt. Zëvendësimi i tyre me çifte<numërues i përsëritjes, vlerë> redukton tepricën e të dhënave.

Algoritmi është krijuar për grafika biznesi - imazhe me zona të mëdha të ngjyrave të përsëritura. Nuk është e pazakontë që një skedar të rritet më i madh për këtë algoritëm të thjeshtë. Mund të merret lehtësisht duke aplikuar kodimin e grupeve në fotografitë me ngjyra të përpunuara. Për të zmadhuar një imazh dy herë, ai duhet të aplikohet në një imazh në të cilin vlerat e të gjithë pikselëve janë më të mëdha se 11000000 binar dhe nuk përsëriten në çifte me radhë.

Varianti i dytë i algoritmit

Varianti i dytë i këtij algoritmi ka një raport maksimal të arkivimit dhe më pak rrit madhësinë e skedarit origjinal.

29. Algoritmi i kompresimit lzw

Algoritmi mori emrin e tij nga shkronjat e para të emrave të zhvilluesve të tij - Lempel, Ziv dhe Welch.

Algoritmi LZW bazohet në idenë e zgjerimit të alfabetit, i cili lejon përdorimin e karaktereve shtesë për të përfaqësuar vargjet e karaktereve të zakonshme. Duke përdorur, për shembull, në vend të kodeve 8-bit ASCII 9-bit, ju merrni 256 karaktere shtesë. Funksionimi i kompresorit reduktohet në ndërtimin e një tabele të përbërë nga linja dhe kodet e tyre përkatëse. Algoritmi i kompresimit zbret në sa vijon: programi lexon karakterin tjetër dhe e shton atë në rresht. Nëse rreshti është tashmë në tabelë, leximi vazhdon, nëse jo, rreshti i dhënë i shtohet tabelës së rreshtave. Sa më shumë rreshta dublikatë të ketë, aq më shumë të dhënat do të kompresohen. Duke iu rikthyer shembullit telefonik, mund të themi, duke përdorur një analogji shumë të thjeshtuar, se duke ngjeshur rekordin 233 34 44 duke përdorur metodën LZW, do të arrijmë në prezantimin e linjave të reja - 333 dhe 444, dhe duke i shprehur ato me karaktere shtesë. , do të jemi në gjendje të zvogëlojmë gjatësinë e rekordit.

Karakteristikat e algoritmit LZW:Raportet e kompresimit: Përafërsisht 1000, 4, 5/7 (Shanset më të mira, mesatare, më të këqija). Kompresimi prej 1000 herë arrihet vetëm në imazhe me një ngjyrë në shumëfisha prej rreth 7 MB. Klasa e imazhit: Fokusohet në LZW për imazhet e krijuara nga kompjuteri 8-bit. Kompresat për shkak të të njëjtave nënzinxhirë në rrjedhë. Simetria: Gati simetrike, duke supozuar zbatimin optimal të kërkimit për një rresht në një tabelë.

Karakteristikat: Situata kur algoritmi e zmadhon imazhin është jashtëzakonisht e rrallë. LZW është universal - janë variantet e tij që përdoren në arkivuesit e zakonshëm.

Procesi i kompresimit duket mjaft i thjeshtë. Ne lexojmë në mënyrë sekuenciale karakteret e rrjedhës hyrëse dhe kontrollojmë nëse ka një rresht të tillë në tabelën e rreshtave që kemi krijuar. Nëse ka një rresht, atëherë lexojmë karakterin tjetër, dhe nëse nuk ka rresht, atëherë futim kodin për rreshtin e gjetur të mëparshëm në rrjedhë, futim rreshtin në tabelë dhe fillojmë përsëri kërkimin.

E veçanta e LZW është se për dekompresim nuk është e nevojshme të ruhet tabela e vargjeve në një skedar për dekompresim. Algoritmi është i strukturuar në atë mënyrë që ne jemi në gjendje të rindërtojmë tabelën e vargjeve duke përdorur vetëm një rrjedhë kodesh.

Një imazh tipik i marrë me një aparat fotografik dixhital ka një rezolucion prej rreth 3000x2000, d.m.th. rreth 6 megapikselë; ngjyra është zakonisht 24 bit për pixel. Kështu, vëllimi i të dhënave fillestare është rreth 17 megabajt. Për pajisjet profesionale të futjes së imazhit, madhësia e rasterit që rezulton mund të jetë dukshëm më e madhe, dhe thellësia e ngjyrës - deri në 48 bit për piksel ("Grafika e rasterit të harduerit modern"). Prandaj, madhësia e një imazhi mund të jetë më shumë se 200 megabajt. Prandaj, algoritmet ngjeshja imazhe, ose, me fjalë të tjera, algoritme që zvogëlojnë sasinë e të dhënave që përfaqësojnë një imazh.

Ekzistojnë dy klasa kryesore të algoritmeve:

1. A quhet algoritëm kompresim pa humbje(Anglisht kompresim pa humbje), nëse ekziston një algoritëm A -1 (i anasjelltë me A) i tillë që për çdo imazh I A (I) = I 1 dhe A -1 (I 1) = I. Imazhi I është specifikuar si një grup vlerash atributesh pixel; Pas aplikimit të Algoritmit A në I, marrim grupin e të dhënave I 1. Kompresimi pa humbje përdoret në formate të tilla grafike si GIF, PCX, PNG, TGA, TIFF 1 Në përgjithësi, ky format mbështet gjithashtu kompresimin me humbje., shumë formate të pronarit nga prodhuesit e kamerave dixhitale, etj.);
2. A quhet algoritëm kompresim me humbje(anglisht compression me humbje), nëse nuk siguron aftësinë për të rivendosur saktë imazhin origjinal. Një algoritëm që është çiftuar me A, i cili siguron një rikuperim të përafërt, do të shënohet si A *: për një imazh IA (I) = I 1, A * (I 1) = I 2 dhe imazhi i rindërtuar që rezulton I 2 jo domosdoshmërisht përkojnë saktësisht me I. Çifti A, A * zgjidhet në mënyrë që të sigurojë raporte të larta kompresimi dhe megjithatë të ruajë cilësinë vizuale, d.m.th. të arrijë një ndryshim minimal në perceptim midis I dhe I 2. Kompresimi me humbje përdoret në formatet e mëposhtme të imazhit: JPEG, JPEG2000, etj.

Ky leksion fokusohet në kompresimin pa humbje, i cili kërkohet në rastet kur informacioni është marrë me kosto të lartë (për shembull, imazhe mjekësore ose imazhe satelitore), ose në raste të tjera kur edhe shtrembërimi më i vogël është i padëshirueshëm.

13.2. Mosekzistenca e një algoritmi të përsosur

Siç u përmend tashmë në paragrafin e mëparshëm, imazhi I konsiderohet si një grup (sekuencë) vlerash të atributeve piksel. Më tej në këtë leksion, të gjitha algoritmet dhe deklaratat i referohen si imazheve ashtu edhe sekuencave arbitrare, elementët e të cilave mund të marrin një numër të kufizuar vlerash.

Deklarata 13.2.1... Nuk ka asnjë algoritëm për kompresimin pa humbje të çdo grupi të dhënash.

Ka 2 N sekuenca të madhësisë N bit (ne do të konsiderojmë një bit si mbartësin minimal të informacionit). Le të jetë një algoritëm A i tillë që, ku | I | - vëllimi i të dhënave (gjatësia e sekuencës). Le të M = max M k, pastaj M< N . Существует 2 1 + 2 2 + ... + 2 M последовательностей длины, меньшей или равной M . Но 2 1 +2 2 + ... + 2 M = 2 M + 1 -2< 2 N ... Kontradikta.

Nga deklarata rezulton se ka kuptim të zhvillohen algoritme që do të kompresonin në mënyrë efikase një klasë të caktuar imazhesh; në të njëjtën kohë, për këto algoritme do të ketë gjithmonë imazhe për të cilat ato nuk do të ofrojnë komprimim.

13.3. Algoritmet e kodimit të gjatësisë së përsëritjes (RLE).

Ky lloj algoritmesh (algoritmet e kodimit të gjatësisë së përsëritjes 2 Një emër tjetër shpesh gjendet në literaturë - kodimi në grup.(RLE 3 anglisht Kodimi i gjatësisë së ekzekutimit)) bazohet në parimin më të thjeshtë: ne do të zëvendësojmë grupet përsëritëse të elementeve të sekuencës origjinale me një çift (sasi, element) ose vetëm me sasi.

RLE - niveli i bitit

Ne do t'i konsiderojmë të dhënat origjinale në nivelin e një sekuence bitash; për shembull, duke përfaqësuar një imazh bardh e zi. Zakonisht ka disa 0 ose 1 në një rresht, dhe ju mund të mbani mend vetëm numrin e shifrave të njëpasnjëshme identike. ato. sekuenca 0000 11111 000 11111111111 korrespondon me një grup numrash të numrave të përsëritjeve 4 5 3 11. Shfaqet nuanca e mëposhtme: numrat që tregojnë numrin e përsëritjeve duhet gjithashtu të kodohen në bit. Mund të supozojmë se çdo numër përsëritjesh varion nga 0 në 7 (d.m.th., mund të kodohet saktësisht me tre bit), atëherë sekuenca 11111111111 mund të krahasohet me numrat 7 0 4, d.m.th. 7 njëshe, 0 zero, 4 njëshe. Për shembull, një sekuencë prej 21 njësh, 21 zero, 3 njësh dhe 7 zero është e koduar si kjo: 111 000 111 000 111 111 000 111 000 111 011 111 , d.m.th. nga sekuenca origjinale, e cila ka një gjatësi prej 51 bitësh, është marrë një sekuencë me gjatësi 36 bit.

Ideja pas kësaj metode përdoret kur dërgoni fakse.

RLE - Niveli i Bajtit

Supozoni se hyrja është një imazh në shkallë gri, ku 1 bajt i ndahet vlerës së intensitetit të pikselit. Është e qartë se, në krahasim me një raster bardh e zi, pritshmëria për një varg të gjatë bitash identike është reduktuar ndjeshëm.

Ne do ta ndajmë rrjedhën hyrëse në bajt (shkronja) dhe do të kodojmë shkronjat përsëritëse në çifte (numër, shkronja).

ato. Kodi AABBBCDAA (2A) (3B) (1C) (1D) (2A). Megjithatë, mund të ketë segmente të gjata të dhënash ku asgjë nuk përsëritet, dhe ne kodojmë secilën shkronjë në një çift (numër, shkronjë).

Supozoni se kemi një numër fiks (gërmë) M (nga 0 në 255). Atëherë një shkronjë e vetme mund të kodohet në vetvete, - prodhimi = S, dhe nëse ka disa shkronja ose, atëherë dalja = CS, ku C> M, dhe C - M është numri i shkronjave të njëpasnjëshme S. Për shembull, do të japim vetëm algoritmin e dekodimit.

// M - kufiri fiks // lexoni karakteret në mënyrë sekuenciale nga rrjedha hyrëse // në - hyrje - sekuencë e ngjeshur // jashtë - dalje - sekuencë e pakompresuar ndërsa (in. Lexo (c)) (nëse (c> M) (// numëruesi i rastit n = c - M; in.Lexo (c); për (i = 0; i< n; i++) out.Write(c); } else // случай просто символа out.Write(c); } Listimi 13.1. Algoritmi i dekodimit RLE - Shtresa e Bajtit

Numri M është zakonisht 127. Më shpesh, përdoret një modifikim i këtij algoritmi, ku shenja e numëruesit është prania e atyre në 2 pjesët më domethënëse të karakterit që lexohet. 6 bitet e mbetura janë vlera e kundërt.

Ky modifikim i këtij algoritmi përdoret në formatin PCX. Sidoqoftë, modifikimet e këtij algoritmi rrallë përdoren më vete, pasi nënklasa e sekuencave në të cilat ky algoritëm është efektiv është relativisht i ngushtë. Modifikimet e algoritmit përdoren si një nga fazat e tubacionit të kompresimit (për shembull, në formatin JPEG,