Materialet e propozuara formuan bazën e punës testuese për lëndën “Bazat matematikore të Informatikës” (nga A. Gein), të cilën e përfundova me sukses në vitin 2011 në universitetin në distancë “1 Shtatori”. Materialet janë përshtatur për një kurs të zgjeruar të shkencave kompjuterike në klasën e 11-të.

Shkarko:

Pamja paraprake:

Kompresimi i të dhënave Liceu nr.329

Andreeva O.A.

Plani i mësimit

Klasa 11

Tema e mësimit: Kompresimi i të dhënave.

Lloji i mësimit : studimi i materialit të ri edukativ me elemente të bisedës ballore.

Objektivat e mësimit : zgjerimi i kompetencave në krijimin e hapësirës suaj të informacionit.

Objektivat e mësimit:

kurrikula - shqyrto konceptin ngjeshja e të dhënave dhe njohuni me algoritmet për kompresimin e të dhënave të karaktereve;

njohës - prezantoj konceptintepricë e të dhënave;

arsimore - për të krijuar kushte për aktivitetin e vrullshëm të secilit student.

Software

ofrimi i mësimit:- prezantim me temën "Ngjeshja e të dhënave";

teknike

duke ofruar një mësim: - vendi i punës së një studenti me një PC PentiumIII;

1. dërrasë me majë të ndjerë;
2. projektor për demonstrim të prezantimit.

GJATË ORËSVE

Faza I : dalje në temën e mësimit dhe motivimi për të studiuar materialin;

Faza II : mesazhi i materialit mësimor;

Faza III : aktualizimi i njohurive të marra - përgjigjet e pyetjeve për konsolidim;

Faza IV : mesazhi i detyrave të shtëpisë; duke përmbledhur mësimin.

Përmbledhja e mësimit

Faza I:

Sasia e informacionit që i nevojitet një personi po rritet vazhdimisht. Aftësitë e ruajtjes dhe gjerësia e brezit po rriten gjithashtu. Megjithatë, sasia e informacionit po rritet më shpejt.
Ekzistojnë tre mënyra për të zgjidhur këtë problem:

së pari - kufizimi i sasisë së informacionit. Fatkeqësisht, nuk është gjithmonë e pranueshme. Për imazhet, për shembull, kjo do të thotë një rënie në rezolucionin, e cila do të çojë në humbjen e detajeve të imta dhe mund t'i bëjë imazhet përgjithësisht të padobishme (për shembull, për imazhet mjekësore ose hapësinore). Kjo rrugë nuk është e zbatueshme për programe dhe tekste.
e dyta - një rritje në vëllimin e transportuesve të informacionit dhe kapacitetin e kanaleve të komunikimit. Ky vendim shoqërohet me kosto materiale, dhe nganjëherë shumë domethënëse.
e treta - përdorimi i kompresimit të informacionit. Kjo zgjidhje ju lejon të zvogëloni disa herë kërkesat për vëllimin e pajisjeve të ruajtjes së të dhënave dhe gjerësinë e brezit të kanaleve të komunikimit pa kosto shtesë (me përjashtim të kostove të zbatimit të algoritmeve të kompresimit). Kushtet për zbatueshmërinë e tij janë teprica e informacionit dhe aftësia për të instaluar softuer ose pajisje speciale për të kryer këto procedura.

Një tipar karakteristik i shumicës së llojeve të të dhënave dixhitale është teprica e tyre. Sasia e tepricës së të dhënave varet nga lloji i të dhënave. Për shembull, për të dhënat video, shkalla e tepricës është disa herë më e madhe se e të dhënave grafike, dhe shkalla e tepricës së të dhënave grafike, nga ana tjetër, është më e madhe se shkalla e tepricës së të dhënave tekstuale. Një faktor tjetër që ndikon në shkallën e tepricës është sistemi i kodimit i miratuar. Efikasiteti i kodimit mund të rritet kur punoni me një grup specifik të dhënash.

Është vërtetuar teorikisht se teprica e tekstit letrar rus është 0.6. Me fjalë të tjera, kur transmetohet teksti përmes një kanali komunikimi, çdo gjashtë shkronja nga dhjetë të transmetuara nuk mbartin asnjë informacion dhe thjesht nuk mund të transmetohet pa asnjë humbje.

Burimet e tjera të informacionit kanë të njëjtën, në mos më të lartë (ρi = 0,9 ... 0,95) tepricë - të folurit, dhe veçanërisht muzika, imazhet televizive, etj.

Kompresimi i të dhënave përdoret në shumë sisteme informacioni. Sistemet moderne radio-teknike të transmetimit dhe komunikimit të informacionit thjesht nuk mund të funksiononin nëse nuk do të kryhej në to ky lloj kompresimi. Nuk do të kishte komunikim dixhital celular të standardeve GSM dhe CDMA. Sistemet televizive satelitore dixhitale nuk do të funksiononin, interneti do të ishte shumë i paefektshëm dhe nuk mund të bëhej fjalë për të parë një video ose për të dëgjuar muzikë të mirë nga një disk lazer. E gjithë kjo sigurohet nga kodimi efikas ose ekonomik i informacionit në këto sisteme.

Faza II:

Demonstrimi i prezantimit me ritmin e duhur me shpjegime të materialit në çdo sllajd.

Slide 5 (shpjegime shtesë):

Zgjedhja e një sistemi kompresimi jo shkatërrues (pa humbje) ose shkatërrues (me humbje) varet nga lloji i të dhënave që do të kompresohen. Kur kompresohen të dhënat e tekstit, programet kompjuterike, dokumentet, vizatimet, etj. është mjaft e qartë se është e nevojshme të përdoren metoda jo shkatërruese, pasi është e nevojshme të rivendosni absolutisht me saktësi informacionin origjinal pas ngjeshjes së tij. Gjatë kompresimit të të folurit, të dhënave muzikore dhe imazheve, përkundrazi, kompresimi shkatërrues përdoret më shpesh, pasi me shtrembërime pothuajse të padukshme siguron një renditje të madhësisë, dhe nganjëherë dy herë më të ulët R ... Në rastin e përgjithshëm, kompresimi shkatërrues siguron, si rregull, raporte kompresimi dukshëm më të larta sesa jo-shkatërruese.

Slide 18 (shpjegime shtesë):

Le të shohim parimin e kompresimit të bazuar në fjalor. LZ është një teknikë e kompresimit të të dhënave që përfiton nga zinxhirët e përsëritur të të dhënave. Fjalori burimor për kompresim përmban një fjalor të simboleve të përdorura. Më pas, vargjet e karaktereve që ndryshojnë nga një karakter do të shtohen në fjalor. Zinxhirët do të zgjaten dhe gjithnjë e më shpesh do të ketë zinxhirë fjalësh në tekst, të cilët do të zëvendësohen nga lidhjet e fjalorit. Fjalët, frazat, rreshtat e tekstit do të shtohen në fjalor. Efekti i kompresimit arrihet duke koduar vargjet e karaktereve të përsëritura.

Le ta imagjinojmë këtë proces duke përdorur shembullin e ngjeshjes së frazës. Fjalori është ndërtuar tashmë, dhe vargjet me interes për ne janë shtuar në fjalor (ato do të përsëriten në frazë). Ata kanë lidhje dixhitale. Kur rifutni frazën, ato zëvendësohen me lidhje. Natyrisht, të dhënat janë duke u ngjeshur.

Ekziston një familje e tërë algoritmesh LZ që janë efikase për lloje të ndryshme të dhënash.

Përfundimi i fazës II:

Kështu, e ardhmja i përket algoritmeve të reja me kërkesa të larta për burime dhe raporte kompresimi gjithnjë e më të larta.

Jo vetëm që algoritmet po vjetërohen, por edhe llojet e informacionit ku ata janë të orientuar. Kështu, grafika me një numër të vogël ngjyrash dhe tekst të paformatuar u zëvendësuan nga imazhe dhe dokumente elektronike me cilësi të lartë në formate të ndryshme. Algoritmet e njohura nuk janë gjithmonë efikase për llojet e reja të të dhënave. Kjo e bën problemin e sintetizimit të algoritmeve të reja jashtëzakonisht urgjente.

Pamja paraprake:

Për të përdorur pamjen paraprake të prezantimeve, krijoni vetes një llogari (llogari) Google dhe hyni në të: https://accounts.google.com

Titrat e rrëshqitjes:

Kompresimi i të dhënave

Qëllimi i kompresimit të të dhënave është të kursejë burime gjatë ruajtjes ose transferimit të të dhënave Kompresimi i të dhënave është procesi i reduktimit të sasisë së të dhënave. Metodat e kompresimit Modifikimi i përmbajtjes së të dhënave (zvogëlimi i tepricës së të dhënave) Modifikimi i strukturës së të dhënave (kodimi efikas) Modifikimi i përmbajtjes dhe strukturës së të dhënave Të dhënat origjinale Të dhënat e rikuperuara Formati i ri Formati origjinal i të dhënave të kompresuara Arkivimi i të dhënave - rikuperimi i plotë i të dhënave

Raporti i kompresimit është një vlerë për efikasitetin e metodës së kompresimit, e barabartë me raportin e sasisë së informacionit para dhe pas ngjeshjes.Të dhënat origjinale Të dhënat e kompresuara Madhësia e skedarit 2MB Madhësia e skedarit 512 KB K i ngjeshur = 2 MB / 0,5 MB = 4

Kompresimi i të dhënave mund të ndodhë me humbje dhe pa humbje Kompresimi pa humbje (plotësisht i kthyeshëm) është një metodë e ngjeshjes së të dhënave në të cilën të dhënat restaurohen pasi t'i shpaketohen plotësisht pa bërë asnjë ndryshim (përdoret për tekste, programe) Kszh deri në 50% Kompresimi pa humbje është kompresim i të dhënave metodat në të cilat një pjesë e të dhënave hidhet dhe nuk mund të rikuperohet (përdoret për video, zë, imazhe) Kszh deri në 99%

Kompresim me humbje Lloji i skedarit pas kompresimit Raporti i ngjeshjes Grafika.JPG deri në 99% Video.MPG Audio.MP3 Lloji i të dhënave Lloji i skedarit pas ngjeshjes Raporti i ngjeshjes Graphics.GIF .TIF .PCX Deri në 50% Video.AVI Çdo lloj.ZIP . ARJ .RAR .LZH Ngjeshje pa humbje

Algoritmet e kompresimit të të dhënave të karaktereve Metodat statistikore janë metoda të kompresimit të bazuara në përpunimin statistikor të tekstit. Kompresimi i fjalorit është një teknikë kompresimi e bazuar në ndërtimin e një fjalori të brendshëm.

Paketimi i të dhënave homogjene 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 _ 1010 + 1011 - 1108 me gjatësi 510100, 1010 + 1011 - 1100, 1010, 1010, 1000, 1000. mesazhi është 16 bajt. Tabela e kodit të ri për paketim: Kodi i mesazhit pas paketimit është 8 bajt: 000011010 01010101 00011000 0100011 110101011 01100011 00011010 00000001 K comp = 2

Raporti i kompresimit rritet me madhësinë e mesazhit të karakterit; është e nevojshme të specifikoni një tabelë të re kodi për shpaketim; efektive vetëm për mesazhe homogjene duke përdorur një grup të kufizuar karakteresh në alfabetin origjinal; + - - Përparësitë dhe disavantazhet e metodës

Metoda statistikore e kompresimit Algoritmi Huffman Karaktere të ndryshme gjenden në një mesazh me frekuenca të ndryshme, për shembull, për alfabetin rus, mesatarisht për 1000 karaktere: përsëritjet e karaktereve të hapësirës: sa më shpesh të ndodhë një karakter, aq më i shkurtër është kodi i tij (kodimi i pabarabartë)

Kodimi Huffman (ngjeshja) është një teknikë kompresimi që cakton kode me gjatësi të ndryshueshme për karakteret në alfabet bazuar në shpeshtësinë e shfaqjes së atyre karaktereve në mesazh. Hapësira e kodit të karaktereve 00 o 01 p 101 deri në 110 s 0110 f 1001

Problemi i dekodimit Shembull: Lërini kodet e karaktereve a -10, b -101, c -1010 të dekodojnë mesazhin 10101011010 10 101 1010 10 10 101 10 10 1010 101 1010 kodin e fjalës.

Një kod prefiks është një kod në të cilin asnjë fjalë e koduar nuk është e prefiksuar me ndonjë fjalë kodi tjetër. Shembull i një kodi prefiks: 00 10 010 110 0110 0111 1110 1111 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 Kodi i parashtesës jepet nga një digraf me gjethe të shënuara

Shembull: ndërtoni kodin Huffman për frazën FROM_HOOSE_HOOPS_DUST_PO_FIELD_LETTER Përcaktoni frekuencën e shfaqjes së karaktereve në frazën: Ndërtoni një digraf Huffman: -simboli specifikon kulmin -fleta e digrafit; -pesha e kulmit është e barabartë me shpeshtësinë e shfaqjes së simbolit; - lidhen çiftet e kulmeve me peshën më të vogël: - degët e majta shënohen me 0; - degët e djathta shënohen me 1; -përcaktoni kodin e karakterit nga rrënja në fletë; simboli A E I K L O P T S Y _ frekuenca 1 1 1 1 3 6 5 6 2 1 1 6

RRËNJA E PEMËS T- O- S- _ P- L- Y- L- E- K- I- A- 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 00011 00010 11000 11001 11011 11010 001 010 011 111 10 0000 Çdo kulm tregohet me një shigjetë

Kodet e ndërtuara të prefiksit të karaktereve: Mesazhi në kodet e reja përmban 110 bit, në kodimin ASCII - 34 * 8 = 272 bit pastaj K sr = 272/110 = 2, 47 Simboli A E I K L O P T Y L Y _ Kodi 11011 1101 1101 1101 1101 0000 00011 00010 111 Gjatësia e kodit 5 5 5 5 3 2 3 3 4 5 5 3

Algoritmi i Huffman është universal, ai mund të përdoret për të kompresuar të dhënat e çdo lloji; Algoritmi klasik Huffman kërkon ruajtjen e një peme koduese, e cila rrit madhësinë e skedarit. + - Përparësitë dhe disavantazhet e metodës

Metoda e fjalorit Algoritmi i ngjeshjes LZ Ky algoritëm u përshkrua për herë të parë nga A. Lempel dhe J. Ziv (Abraham Lempel, Jacob Ziv) në 1977-78, prandaj kjo metodë shpesh quhet Lempel-Ziv, ose shkurt LZ. Ai bazohet në idenë e zëvendësimit të vargjeve të karaktereve (strings) që hasen më shpesh në një skedar me lidhje me vargjet "mostra" të ruajtura në një tabelë të krijuar posaçërisht (fjalor).

Algoritmi u zhvillua nga matematikanët kangjella Jaco Ziv dhe Abrakhum Lempel. Fjalori përmban, ndër shumë të tjera, zinxhirët e mëposhtëm: 1-pa 2-ab 3-at 4-mate 5-mi_ 6-am 7-bo 8-th_ 9-bom 10-th 11-lem Algoritmi u zhvillua nga matematikanët izraelitë 5Yako7 Ziv821x68 L10ne11 Sa më i gjatë të jetë zinxhiri i zëvendësuar nga një lidhje fjalori, aq më i madh është efekti i kompresimit.

E aplikueshme për çdo të dhënë; - shpejtësi shumë e lartë e kompresimit; - raport i lartë i kompresimit; + - Përparësitë dhe disavantazhet e metodës - fjalori është konfiguruar për llojin e tekstit; - fjalori mund të jetë shumë i madh;

Leksioni numër 4. Kompresimi i informacionit

Parimet e kompresimit të informacionit

Qëllimi i kompresimit të të dhënave është të sigurojë një paraqitje kompakte të të dhënave të gjeneruara nga burimi për ruajtjen dhe transmetimin më ekonomik përmes kanaleve të komunikimit.

Supozoni se kemi një skedar me madhësi 1 (një) megabajt. Ne duhet të marrim një skedar më të vogël prej tij. Asgjë e komplikuar - ne ekzekutojmë një arkivues, për shembull, WinZip, dhe marrim, të themi, një skedar me madhësi 600 kilobajt. Ku shkuan 424 kilobajt e mbetur?

Kompresimi i informacionit është një nga mënyrat për ta koduar atë. Në përgjithësi, kodet ndahen në tre grupe të mëdha - kodet e kompresimit (kodet efektive), kodet e korrigjimit të gabimeve dhe kodet kriptografike. Kodet e krijuara për të kompresuar informacionin ndahen, nga ana tjetër, në kode pa humbje dhe kode me humbje. Kodimi pa humbje nënkupton rikuperimin absolutisht të saktë të të dhënave pas dekodimit dhe mund të përdoret për të kompresuar çdo informacion. Kodimi me humbje zakonisht ka një raport kompresimi shumë më të lartë se kodimi pa humbje, por lejon disa devijime të të dhënave të dekoduara nga origjinali.

Llojet e kompresimit

Të gjitha metodat e ngjeshjes së informacionit mund të ndahen me kusht në dy klasa të mëdha jo të mbivendosura: ngjeshja me humbje informacionit dhe kompresimit asnjë humbje informacion.

Kompresim pa humbje informacioni.

Ne jemi të interesuar kryesisht për këto metoda kompresimi, pasi ato përdoren kur transferoni dokumente teksti dhe programe, kur lëshoni një punë të përfunduar tek një klient, ose kur krijoni kopje rezervë të informacionit të ruajtur në një kompjuter.

Metodat e kompresimit të kësaj klase nuk mund të lejojnë humbjen e informacionit, prandaj ato bazohen vetëm në eliminimin e tepricës së tij, dhe informacioni ka tepricë pothuajse gjithmonë (megjithëse, nëse dikush nuk e ka ngjeshur më parë). Nëse nuk do të kishte tepricë, nuk do të kishte asgjë për të ngjeshur.

Ja një shembull i thjeshtë. Në rusisht ka 33 shkronja, dhjetë numra dhe rreth një duzinë shenja pikësimi dhe karaktere të tjera të veçanta. Për tekstin që është shkruar vetëm me shkronja të mëdha ruse(si në telegrame dhe radiograme) do të mjaftonin gjashtëdhjetë vlera të ndryshme. Sidoqoftë, çdo karakter zakonisht kodohet nga një bajt që përmban 8 bit dhe mund të shprehë 256 kode të ndryshme. Kjo është arsyeja e parë e tepricës. Për tekstin tonë "telegrafik", do të mjaftonin gjashtë bit për karakter.

Ja një shembull tjetër. Kodimi ndërkombëtar i karaktereve ASCII për të koduar çdo karakter, ndahen i njëjti numër bitesh (8), ndërkohë që të gjithë e dinë prej kohësh mirë se ka kuptim që karakteret më të zakonshme të kodohen me më pak karaktere. Kështu, për shembull, në "kodin Morse" shkronjat "E" dhe "T", të cilat gjenden shpesh, janë të koduara nga një karakter (përkatësisht, një pikë dhe një vizë). Dhe shkronja të tilla të rralla si "U" (- -) dhe "C" (- -) janë të koduara me katër karaktere. Kodimi joefikas është arsyeja e dytë e tepricës. Programet që kryejnë kompresimin e informacionit mund të fusin kodimin e tyre (të ndryshëm për skedarë të ndryshëm) dhe t'i caktojnë një tabelë (fjalor) skedarit të ngjeshur, nga i cili programi i shpaketimit zbulon se si janë koduar disa karaktere ose grupe të tyre në këtë skedar. Algoritmet e bazuara në transkodimin e informacionit quhen Algoritmet Huffman.

Prania e fragmenteve të përsëritura është arsyeja e tretë e tepricës. Kjo është e rrallë në tekste, por në tabela dhe grafika, përsëritja e kodeve është e zakonshme. Kështu, për shembull, nëse numri 0 përsëritet njëzet herë me radhë, atëherë nuk ka kuptim të vendosni njëzet zero bajt. Në vend të kësaj, ata vendosin një zero dhe një koeficient 20. Algoritme të tilla të bazuara në zbulimin e përsëritjeve quhen metodatRLE (Vraponi Gjatësia Kodimi).

Ilustrimet grafike dallohen veçanërisht nga sekuenca të mëdha përsëritëse të të njëjtave bajt, por jo fotografike (ka shumë zhurmë dhe pikat fqinje ndryshojnë ndjeshëm në parametra), por ato që artistët pikturojnë me një ngjyrë "të lëmuar", si në filmat e animuar. .

Kompresim me humbje.

Kompresimi me humbje do të thotë që pas shpaketimit të arkivit të ngjeshur, marrim një dokument që është paksa i ndryshëm nga ai që ishte në fillim. Kuptohet që sa më i madh të jetë raporti i ngjeshjes, aq më i madh është humbja dhe anasjelltas.

Natyrisht, algoritme të tilla nuk janë të zbatueshme për dokumentet tekstuale, tabelat e bazës së të dhënave dhe veçanërisht për programet. Shtrembërimet e vogla në një tekst të thjeshtë të paformatuar ende mund të mbijetojnë disi, por shtrembërimi i të paktën një biti në program do ta bëjë atë absolutisht jofunksional.

Në të njëjtën kohë, ka materiale në të cilat ia vlen të sakrifikoni disa për qind të informacionit për të marrë dhjetëfishin e kompresimit. Këto përfshijnë ilustrime fotografike, video dhe kompozime muzikore. Humbja e informacionit gjatë ngjeshjes dhe zbërthimi i mëvonshëm në materiale të tilla perceptohet si shfaqja e një "zhurme" shtesë. Por meqenëse një "zhurmë" është ende e pranishme gjatë krijimit të këtyre materialeve, rritja e saj e vogël nuk duket gjithmonë kritike, dhe fitimi në madhësinë e skedarëve është i madh (10-15 herë për muzikën, 20-30 herë për materialet fotografike dhe video).

Algoritmet e kompresimit me humbje përfshijnë algoritme të tilla të njohura si JPEG dhe MPEG. Algoritmi JPEG përdoret për të kompresuar imazhet fotografike. Skedarët grafikë të ngjeshur duke përdorur këtë metodë kanë shtesën JPG. Algoritmet MPEG përdoren për të kompresuar videon dhe muzikën. Këta skedarë mund të kenë shtesa të ndryshme, në varësi të programit specifik, por më të njohurit janë .MPG për video dhe MP3 për muzikë.

Algoritmet e kompresimit me humbje përdoren vetëm për aplikacionet e konsumatorit. Kjo do të thotë, për shembull, që nëse një fotografi dërgohet për shikim dhe muzika për riprodhim, atëherë mund të përdoren algoritme të ngjashme. Nëse ato transferohen për përpunim të mëtejshëm, për shembull, për redaktim, atëherë asnjë humbje e informacionit në materialin origjinal nuk është e pranueshme.

Shuma e humbjes së lejueshme të kompresimit zakonisht mund të kontrollohet. Kjo ju lejon të eksperimentoni dhe të arrini raportin optimal të madhësisë / cilësisë. Në ilustrimet fotografike të destinuara për shfaqje në ekran, humbja e 5% e informacionit zakonisht nuk është kritike, dhe në disa raste, 20-25% mund të tolerohet.

Algoritmet e kompresimit pa humbje

Kodi Shannon-Fano

Për arsye të mëtejshme, do të jetë e përshtatshme të imagjinojmë skedarin tonë burimor me tekst si një burim karakteresh që shfaqen një nga një në daljen e tij. Nuk e dimë paraprakisht se cili personazh do të jetë më pas, por e dimë se shkronja "a" do të shfaqet me probabilitet p1, shkronja "b" do të shfaqet me probabilitet p2, e kështu me radhë.

Në rastin më të thjeshtë, të gjithë personazhet e tekstit do t'i konsiderojmë të pavarur nga njëri-tjetri, d.m.th. probabiliteti i shfaqjes së simbolit të ardhshëm nuk varet nga vlera e simbolit të mëparshëm. Natyrisht, ky nuk është rasti për një tekst kuptimplotë, por tani po shqyrtojmë një situatë shumë të thjeshtuar. Në këtë rast, shprehja "simboli mbart sa më shumë informacion, aq më pak probabiliteti i shfaqjes së tij".

Le të imagjinojmë një tekst, alfabeti i të cilit përbëhet nga vetëm 16 shkronja: A, B, C, D, D, E, F, Z, I, K, L, M, N, O, P, R. Secila nga këto Shenjat mund të kodohen me vetëm 4 bit: nga 0000 në 1111. Tani imagjinoni që probabilitetet që këto karaktere të ndodhin shpërndahen si më poshtë:

Shuma e këtyre probabiliteteve është, natyrisht, një. Le t'i ndajmë këto simbole në dy grupe në mënyrë që probabiliteti i përgjithshëm i simboleve të secilit grup të jetë ~ 0,5 (Fig). Në shembullin tonë, këto do të jenë grupe karakteresh A-B dhe G-R. Rrathët në figurë, që tregojnë grupe simbolesh, quhen nyje ose nyje, dhe vetë ndërtimi i këtyre nyjeve quhet pemë binare (B-pema). Le t'i caktojmë çdo nyje kodin e vet, duke treguar njërën nyje me numrin 0 dhe tjetrën me numrin 1.

Le ta ndajmë sërish grupin e parë (AB) në dy nëngrupe në mënyrë që probabilitetet totale të tyre të jenë sa më afër njëra-tjetrës. Le të shtojmë numrin 0 në kodin e nëngrupit të parë, dhe numrin 1 në kodin e të dytit.

Ne do ta përsërisim këtë veprim derisa të mbetet një simbol në çdo kulm të "pemës" tonë. Pema e plotë për alfabetin tonë do të ketë 31 nyje.

Kodet e karaktereve (nyjet më të djathta të pemës) kanë kode me gjatësi të pabarabartë. Pra, shkronja A, e cila ka një probabilitet prej p = 0,2 për tekstin tonë imagjinar, është e koduar vetëm me dy bit, dhe shkronja P (nuk tregohet në figurë), e cila ka një probabilitet prej p = 0,013, është e koduar me një kombinim me gjashtë bit.

Pra, parimi është i qartë - karakteret që shfaqen shpesh kodohen me më pak bit, ato të rralla - me më shumë. Si rezultat, numri mesatar i biteve për karakter do të jetë

ku ni është numri i biteve që kodojnë simbolin i-të, pi është probabiliteti i simbolit të i-të.

Kodi Huffman.

Algoritmi i Huffman-it zbaton me hijeshi idenë e përgjithshme të kodimit të entropisë duke përdorur grupe parashtesash dhe funksionon si më poshtë:

1. Shkruani me radhë të gjitha simbolet e alfabetit në rend rritës ose zbritës sipas mundësisë së paraqitjes së tyre në tekst.

2. Kombinoni në mënyrë të njëpasnjëshme dy simbole me probabilitetin më të ulët të paraqitjes në një simbol të ri të përbërë, probabiliteti i të cilit supozohet të jetë i barabartë me shumën e probabiliteteve të simboleve përbërëse të tij. Së fundi, ne do të ndërtojmë një pemë, secila nyje e së cilës ka probabilitetin total të të gjitha nyjeve poshtë saj.

3. Gjurmoni shtegun për çdo gjethe të pemës, duke shënuar drejtimin në secilën nyje (për shembull, në të djathtë - 1, në të majtë - 0). Sekuenca që rezulton jep një fjalë kodi që korrespondon me çdo karakter (Fig.).

Le të ndërtojmë një pemë kodi për një mesazh me alfabetin e mëposhtëm:

Disavantazhet e metodave

Vështirësia më e madhe me kodet, siç sugjeron diskutimi i mëparshëm, është nevoja për të pasur tabela të probabiliteteve për çdo lloj të dhënash që kompresohen. Ky nuk është problem nëse dihet se teksti në anglisht ose rusisht është i ngjeshur; ne thjesht i sigurojmë koduesit dhe dekoderit një pemë kodi të përshtatshme për tekstin anglisht ose rusisht. Në rastin e përgjithshëm, kur probabiliteti i simboleve për të dhënat hyrëse është i panjohur, kodet statike Huffman funksionojnë në mënyrë joefektive.

Zgjidhja e këtij problemi është analiza statistikore e të dhënave të koduara, e kryer gjatë kalimit të parë mbi të dhënat, dhe hartimi i një peme kodi bazuar në të. Në këtë rast, kodimi aktual kryhet në kalimin e dytë.

Një tjetër pengesë e kodeve është se gjatësia minimale e fjalës së kodit për to nuk mund të jetë më e vogël se një, ndërsa entropia e një mesazhi mund të jetë 0,1 dhe 0,01 bit / shkronjë. Në këtë rast, kodi bëhet dukshëm i tepërt. Problemi zgjidhet duke aplikuar algoritmin në blloqe simbolesh, por më pas procedura e kodimit / dekodimit bëhet më e ndërlikuar dhe pema e kodit zgjerohet ndjeshëm, e cila në fund të fundit duhet të ruhet së bashku me kodin.

Këto kode nuk marrin parasysh marrëdhëniet midis karaktereve, të cilat janë të pranishme pothuajse në çdo tekst. Për shembull, nëse në tekstin në anglisht hasim shkronjën q, atëherë mund të themi me siguri se shkronja u do të vijë pas saj.

Run Length Encoding (RLE) është një nga algoritmet më të vjetër dhe më të thjeshtë të arkivimit. Kompresimi në RLE ndodh duke zëvendësuar vargjet e bajteve identike me çifte kundërvlerash. ("E kuqe, e kuqe, ..., e kuqe" shkruhet si "N e kuqe").

Një nga zbatimet e algoritmit është si më poshtë: ata kërkojnë për bajtin më pak të shpeshtë, e quajnë atë një parashtesë dhe zëvendësojnë vargjet e karaktereve identike me treshe "prefiks, numërues, vlerë". Nëse ky bajt shfaqet në skedarin burimor një ose dy herë radhazi, atëherë ai zëvendësohet me një palë "prefiks, 1" ose "prefiks, 2". Ekziston një çift i papërdorur "prefiks, 0" që mund të përdoret si shenjë e përfundimit të të dhënave të paketuara.

Kur kodoni skedarët exe, mund të kërkoni dhe paketoni sekuenca të formës AxAyAzAwAt ..., të cilat shpesh gjenden në burime (vargjet e koduara në Unicode)

Aspektet pozitive të algoritmit përfshijnë faktin se ai nuk kërkon memorie shtesë gjatë funksionimit dhe ekzekutohet shpejt. Algoritmi përdoret në formatet PCX, TIFF, BMP. Një tipar interesant i kodimit grupor në PCX ë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.

Kodi LZW (Lempel-Ziv & Welch) është një nga kodet më të zakonshme të kompresimit pa humbje. Është me ndihmën e kodit LZW që kryhet kompresimi në formate të tilla grafike si TIFF dhe GIF, me ndihmën e modifikimeve LZW, shumë arkivues universalë kryejnë funksionet e tyre. Funksionimi i algoritmit bazohet në kërkimin e skedarit hyrës për sekuenca të përsëritura të karaktereve, të cilat janë të koduara me kombinime prej 8 deri në 12 bit në gjatësi. Kështu, ky algoritëm është më efektiv në skedarët e tekstit dhe skedarët grafikë, të cilët kanë zona të mëdha njëngjyrëshe ose sekuenca të përsëritura pikselësh.

Mungesa e humbjes së informacionit gjatë kodimit LZW çoi në përdorimin e gjerë të formatit TIFF të bazuar në të. Ky format nuk vendos asnjë kufizim në madhësinë dhe thellësinë e ngjyrës së imazhit dhe përdoret gjerësisht, për shembull, në industrinë e printimit. Një format tjetër i bazuar në LZW - GIF - është më primitiv - ju lejon të ruani imazhe me një thellësi ngjyrash jo më shumë se 8 bit / pixel. Në fillim të skedarit GIF ekziston një paletë - një tabelë që vendos një korrespondencë midis një indeksi ngjyrash - një numër në rangun nga 0 në 255 dhe një vlerë të vërtetë ngjyrash 24-bit.

Algoritmet e kompresimit me humbje

Algoritmi JPEG u zhvillua nga një grup firmash të quajtur Joint Photographic Experts Group. Qëllimi i projektit ishte krijimi i një standardi kompresimi shumë efikas për imazhet bardh e zi dhe me ngjyra, dhe ky qëllim u arrit nga zhvilluesit. Aktualisht, JPEG përdoret gjerësisht aty ku kërkohet një raport i lartë kompresimi - për shembull, në internet.

Ndryshe nga LZW, kodimi JPEG është me humbje. Vetë algoritmi i kodimit bazohet në matematikë shumë komplekse, por në terma të përgjithshëm mund të përshkruhet si më poshtë: imazhi ndahet në katrorë 8 * 8 pikselë, dhe më pas çdo katror shndërrohet në një zinxhir vijues prej 64 pikselësh. Më tej, çdo zinxhir i tillë i nënshtrohet të ashtuquajturit transformim DCT, i cili është një nga varietetet e transformimit diskrete të Furierit. Ai konsiston në faktin se sekuenca e hyrjes së pikselëve mund të përfaqësohet si një shumë e përbërësve sinusoidalë dhe kosinusikë me frekuenca të shumta (të ashtuquajturat harmonikë). Në këtë rast, ne vetëm duhet të dimë amplitudat e këtyre komponentëve në mënyrë që të rindërtojmë sekuencën hyrëse me një shkallë të mjaftueshme saktësie. Sa më shumë komponentë harmonikë të dimë, aq më pak do të jetë mospërputhja midis imazhit origjinal dhe atij të ngjeshur. Shumica e koduesve JPEG ju lejojnë të rregulloni shkallën e kompresimit. Kjo arrihet në një mënyrë shumë të thjeshtë: sa më i lartë të vendoset raporti i kompresimit, aq më pak harmonikë do të përfaqësojë çdo bllok 64 pikselësh.

Sigurisht, pika e fortë e këtij lloji të kodimit është raporti i lartë i kompresimit duke ruajtur thellësinë origjinale të ngjyrës. Është kjo veti që ka përcaktuar përdorimin e saj të gjerë në internet, ku zvogëlimi i madhësisë së skedarëve është i një rëndësie të madhe, në enciklopeditë multimediale, ku kërkohet të ruhet sasia më e madhe e mundshme e grafikëve në një sasi të kufizuar.

Një veti negative e këtij formati është se ai degradon cilësinë e figurës, e cila nuk mund të hiqet në asnjë mënyrë. Është ky fakt i trishtë që nuk e lejon përdorimin e tij në industrinë e printimit, ku cilësia është në krye.

Megjithatë, formati JPEG nuk është kufiri i përsosmërisë në përpjekjen për të zvogëluar madhësinë e skedarit përfundimtar. Kohët e fundit janë kryer kërkime intensive në fushën e të ashtuquajturit transformim valëzues (ose transformim i shpërthimit). Bazuar në parimet më komplekse matematikore, koduesit e valëve ju lejojnë të merrni më shumë kompresim se JPEG, me më pak humbje informacioni. Pavarësisht kompleksitetit të transformimit të valëzimit matematikor, në zbatimin e softuerit është më i thjeshtë se JPEG. Megjithëse algoritmet e kompresimit të valëve janë ende në fazat e hershme të zhvillimit, ata kanë një të ardhme të shkëlqyer.

Kompresimi fraktal

Kompresimi i imazhit fraktal është një algoritëm i kompresimit të imazhit me humbje i bazuar në aplikimin e sistemeve të funksioneve të përsëritura (IFS, zakonisht transformime afinale) në imazhe. Ky algoritëm është i njohur për faktin se në disa raste lejon marrjen e raporteve shumë të larta të kompresimit (shembuj më të mirë janë deri në 1000 herë me cilësi të pranueshme vizuale) për fotografi reale të objekteve natyrore, gjë që nuk është e disponueshme për algoritme të tjera të ngjeshjes së imazhit në parim. Për shkak të situatës së vështirë me patentim, algoritmi nuk u përdor gjerësisht.

Arkivimi fraktal bazohet në faktin se duke përdorur koeficientët e sistemit të funksioneve të përsëritura, imazhi paraqitet në një formë më kompakte. Përpara se të shikojmë procesin e arkivimit, le të hedhim një vështrim se si IFS ndërton një imazh.

Në mënyrë të rreptë, IFS është një grup transformimesh afine tre-dimensionale që transformojnë një imazh në një tjetër. Pikat në hapësirën tredimensionale (koordinata x, koordinata y, shkëlqimi) transformohen.

Baza e metodës së kodimit fraktal është zbulimi i zonave të ngjashme në imazh. Mundësia e aplikimit të teorisë së sistemeve të funksioneve të përsëritura (IFS) në problemin e kompresimit të imazhit u eksplorua për herë të parë nga Michael Barnsley dhe Alan Sloan. Ata e patentuan idenë e tyre në 1990 dhe 1991. Jacquin prezantoi një metodë kodimi fraktal që përdor një sistem të blloqeve të nënimazheve të domenit dhe diapazonit, blloqe me formë katrore që mbulojnë të gjithë imazhin. Kjo qasje u bë baza për shumicën e metodave të kodimit fraktal që përdoren sot. Ai u rafinua nga Yuval Fisher dhe një numër studiuesish të tjerë.

Kjo metodë e ndan imazhin në një grup nënimazhesh të diapazonit që nuk mbivendosen dhe përcakton një grup nënimazhesh domenesh të mbivendosura. Për çdo bllok të renditjes, algoritmi i kodimit gjen bllokun më të përshtatshëm të domenit dhe një transformim afin që e përkthen këtë bllok domeni në një bllok të caktuar të renditjes. Struktura e imazhit është hartuar në një sistem blloqesh të renditjes, blloqeve të domenit dhe transformimeve.

Ideja është si më poshtë: supozoni se imazhi origjinal është pika fikse e një harte tkurrjeje. Më pas, në vend të vetë imazhit, mund ta mbani mend disi këtë hartë, dhe për ta rikthyer atë, mjafton të aplikoni në mënyrë të përsëritur këtë hartë në çdo imazh fillestar.

Sipas teoremës së Banach, përsëritje të tilla çojnë gjithmonë në një pikë fikse, domethënë në imazhin origjinal. Në praktikë, e gjithë vështirësia qëndron në gjetjen e hartës më të përshtatshme të kompresimit nga imazhi dhe në ruajtjen e tij kompakte. Në mënyrë tipike, algoritmet e kërkimit të ekranit (d.m.th., algoritmet e kompresimit) janë kryesisht shteruese dhe intensive llogaritëse. Në të njëjtën kohë, algoritmet e rikuperimit janë mjaft efikase dhe të shpejta.

Shkurtimisht, metoda e propozuar nga Barnsley mund të përshkruhet si më poshtë. Imazhi është i koduar me disa transformime të thjeshta (në rastin tonë, ato afine), domethënë përcaktohet nga koeficientët e këtyre transformimeve (në rastin tonë, A, B, C, D, E, F).

Për shembull, imazhi i kurbës Koch mund të kodohet me katër transformime afine, ne do ta përcaktojmë në mënyrë unike duke përdorur vetëm 24 koeficientë.

Si rezultat, pika domosdoshmërisht do të shkojë diku brenda zonës së zezë në imazhin origjinal. Duke e kryer këtë operacion shumë herë, ne do të mbushim të gjithë hapësirën e zezë, duke rikthyer kështu figurën.

Më të njohurat janë dy imazhe IFS: Trekëndëshi i Sierpinskit dhe Fern Barnsley. E para jepet nga tre, dhe e dyta, nga pesë transformime afine (ose, në terminologjinë tonë, lente). Çdo transformim vendoset fjalë për fjalë nga bajtët e lexuar, ndërsa imazhi i ndërtuar me ndihmën e tyre mund të marrë disa megabajt.

Bëhet e qartë se si funksionon arkivi dhe pse kërkon kaq shumë kohë. Në fakt, kompresimi fraktal është një kërkim për rajone të ngjashme në një imazh dhe përcaktimin e parametrave të transformimeve afinike për to.

Në rastin më të keq, nëse nuk zbatohet algoritmi optimizues, do të kërkohet një numërim dhe krahasim i të gjitha fragmenteve të mundshme të imazhit të madhësive të ndryshme. Edhe për imazhe të vogla, duke marrë parasysh diskretitetin, marrim një numër astronomik opsionesh për t'u kërkuar. Edhe një ngushtim i mprehtë i klasave të transformimit, për shembull, duke shkallëzuar vetëm një numër të caktuar herë, nuk do të na lejojë të arrijmë një kohë të pranueshme. Përveç kësaj, cilësia e imazhit humbet. Shumica dërrmuese e kërkimeve në fushën e kompresimit fraktal tani synojnë zvogëlimin e kohës së arkivimit të kërkuar për të marrë një imazh me cilësi të lartë.

Për algoritmin e ngjeshjes fraktal, si dhe për algoritmet e tjera të kompresimit me humbje, mekanizmat me anë të të cilëve do të mundësohet rregullimi i raportit të ngjeshjes dhe raportit të humbjeve janë shumë të rëndësishëm. Deri më sot, është zhvilluar një grup mjaft i madh i metodave të tilla. Së pari, ju mund të kufizoni numrin e konvertimeve, duke siguruar me vetëdije se raporti i kompresimit nuk është më i ulët se një vlerë fikse. Së dyti, mund të kërkohet që në një situatë kur ndryshimi midis fragmentit të përpunuar dhe përafrimit më të mirë të tij është mbi një vlerë të caktuar pragu, ky fragment duhet të shtypet (për të, duhet të instalohen disa lente). Së treti, mund të ndaloni ndarjen e fragmenteve më të vogla se, të themi, katër pika. Duke ndryshuar vlerat e pragut dhe përparësinë e këtyre kushteve, ju mund të kontrolloni në mënyrë shumë fleksibël raportin e ngjeshjes së imazhit: nga përputhja bit-në-bit në çdo raport kompresimi.

Krahasimi me JPEG

Sot, algoritmi më i zakonshëm i arkivimit të grafikës është JPEG. Le ta krahasojmë me kompresimin fraktal.

Së pari, vini re se të dy algoritmet funksionojnë në imazhe me ngjyra 8-bit (shkallë gri) dhe 24-bit. Të dy janë algoritme kompresimi me humbje dhe ofrojnë raporte të ngjashme arkivimi. Si algoritmi fractal ashtu edhe JPEG kanë aftësinë për të rritur raportin e kompresimit duke rritur humbjen. Për më tepër, të dy algoritmet paralelizohen shumë mirë.

Dallimet fillojnë kur marrim parasysh kohën që duhet që algoritmet të zip / unzip. Kështu, algoritmi fraktal ngjesh qindra dhe madje mijëra herë më gjatë se JPEG. Nga ana tjetër, shpaketimi i imazhit do të jetë 5-10 herë më i shpejtë. Prandaj, nëse imazhi do të kompresohet vetëm një herë, por do të transmetohet përmes rrjetit dhe do të shpaketohet shumë herë, atëherë është më fitimprurëse të përdoret algoritmi fraktal.

JPEG përdor zbërthimin e imazhit në funksione kosinus, kështu që humbja në të (madje edhe me një humbje minimale të caktuar) shfaqet në valë dhe halo në kufirin e tranzicionit të mprehtë të ngjyrave. Është për këtë efekt që nuk u pëlqen ta përdorin atë kur kompresojnë imazhe që janë përgatitur për printim me cilësi të lartë: atje ky efekt mund të bëhet shumë i dukshëm.

Algoritmi fraktal e eliminon këtë disavantazh. Për më tepër, kur printoni një imazh, çdo herë duhet të kryeni një operacion shkallëzimi, pasi rasteri (ose rregulli) i pajisjes së printimit nuk përputhet me rasterin e figurës. Gjatë konvertimit, mund të ndodhin edhe disa efekte të pakëndshme, të cilat mund të trajtohen ose duke shkallëzuar imazhin në mënyrë programore (për pajisje të lira printimi si printerët konvencionalë lazer dhe me bojë), ose duke pajisur pajisjen e printimit me procesorin e vet, hard diskun dhe një grup programesh për përpunimin e imazhit (për makinat e shtrenjta për vendosjen e fotografive). Siç mund ta merrni me mend, kur përdorni algoritmin fraktal, praktikisht nuk ka probleme të tilla.

Zhvendosja e JPEG nga algoritmi fraktal në përdorim të gjerë nuk do të ndodhë së shpejti (të paktën për shkak të shpejtësisë së ulët të arkivimit të këtij të fundit), megjithatë, në fushën e aplikacioneve multimediale, në lojërat kompjuterike, përdorimi i tij është mjaft i justifikuar.

Përmbledhje e mësimit në informatikë dhe TIK

Lloji i : Mësimi për të mësuar materiale të reja

Tema : Arkivuesit. Metodat e kompresimit të informacionit.

Golat :

Eksploroni teknikat e kompresimit të informacionit (paketimi dhe Huffman)

Zhvilloni të menduarit algoritmik

Nxitja e një qëndrimi të përgjegjshëm ndaj përfundimit të detyrës.

Metoda: Shpjeguese dhe ilustruese

Gjatë orëve të mësimit:

Momenti organizativ (2 min)

Përditësimi i njohurive. (5 minuta)

Shpjegimi i materialit dhe shkrimi në fletore. (25 minuta)

Konsolidimi fillestar i materialit (10 min)

Duke përmbledhur. (3 min)

Pyetje për përditësimin e njohurive:

Si e kuptoni konceptin e "kompresimit të informacionit"?

Si kompresohet informacioni dixhital?

Çfarë programesh njihni arkivues?

Informacioni në çfarë forme kërkon kompresim të detyrueshëm?

Materiali teorik:

Në jetën e çdo përdoruesi të kompjuterit, situatat lindin rregullisht kur, për shembull, duhet të transferoni një ose disa skedarë në një kompjuter tjetër duke përdorur një media të lëvizshme të kufizuar në madhësi, të dërgoni një skedar të madh me e-mail, etj. Si rregull, ekziston problemi i ndarjes së një skedari të madh në disa skedarë të vegjël me mundësinë e rindërtimit të mëtejshëm të tij, grupimin e një numri të madh skedarësh të vegjël në më të mëdhenj, kompresimin e skedarëve për të zvogëluar madhësinë e tyre, etj. Për të zgjidhur probleme të tilla, përdoren arkivues.

Arkivuesit janë programe që ju lejojnë të krijoni, duke përdorur metoda të veçanta kompresimi, kopje të skedarëve me madhësi më të vogël dhe të kombinoni kopje të disa skedarëve në një skedar arkiv, si dhe të shpaketoni arkivat (ekstraktoni skedarët nga një arkiv).

Ekzistojnë algoritme të ndryshme për arkivimin e të dhënave pa humbur informacion, d.m.th. kur shpaketohen, të dhënat do të rikthehen në formën e tyre origjinale. Për Windows, arkivuesit më të njohur janë WinRAR, WinZIP, WinACE.

Kompresimi i informacionit është procesi i konvertimit të informacionit të ruajtur në një skedar, si rezultat i të cilit reduktohet teprica e tij, dhe në përputhje me rrethanat, kërkohet më pak memorie për ruajtje.

Kompresimi i informacionit në skedarë kryhet duke eliminuar tepricën në mënyra të ndryshme, për shembull, duke thjeshtuar kodet, duke eliminuar bitet konstante prej tyre, ose duke përfaqësuar simbole të përsëritura ose një sekuencë të përsëritur simbolesh në formën e një faktori përsëritjeje dhe simboleve përkatëse. Përdoren algoritme të ndryshme për një kompresim të tillë informacioni.

Metoda e paketimit

Teksti i hyrjes "BELL_BALL_BALL" përmban gjithsej 5 karaktere të ndryshme (K, O, L, A, _). Prandaj, çdo simbol mund të kodohet me tre bit. Ka gjithsej 18 karaktere në testin origjinal, kështu që kërkohen 18X3 = 54 bit. Raporti i kompresimit është 144/54 = 2.7

Metoda Huffman.

Pika e dobët e metodës së paketimit është se simbolet janë të koduara në sekuenca bit me të njëjtën gjatësi. Për shembull, çdo tekst që përmban vetëm shkronjat "A" dhe "B" kompresohet me metodën e paketimit tetë herë. Sidoqoftë, nëse shtoni vetëm një shkronjë në një tekst të tillë, për shembull "C", atëherë raporti i kompresimit do të përgjysmohet menjëherë, dhe pavarësisht nga gjatësia e tekstit dhe numri i karaktereve të shtuara "C"

Përmirësimet në raportin e kompresimit mund të arrihen duke koduar simbolet e zakonshme në kode të shkurtra dhe ato të rralla në ato më të gjata. Kjo është pikërisht ideja pas metodës së publikuar nga D. Huffman në 1952.

Algoritmi Huffman

Karakteret në alfabetin e hyrjes formojnë një listë të nyjeve të lira. Çdo nyje ka një peshë të barabartë me numrin e shfaqjeve të një karakteri në mesazhin origjinal.

Dy nyje të lira me peshën më të vogël zgjidhen nga lista.

Nyja e tyre "prind" krijohet me një peshë të barabartë me shumën e peshave të tyre; ajo lidhet me "fëmijët" me harqe.

Njëri hark që largohet nga "prindi" i caktohet biti 1, tjetrit - biti 0.

Prindi i shtohet listës falas dhe dy nga fëmijët e tij hiqen nga kjo listë.

Hapat që fillojnë nga e dyta përsëriten derisa të mbetet vetëm një nyje e lirë në listën e lirë. Ai do të konsiderohet rrënja e pemës.

Detyrat e detyrave

Paketoni mesazhin me 2 mënyra: Arkhip_osip._Osip_ocryp.

Pyetje për përmbledhjen e mësimit:

Çfarë është kompresimi i informacionit?

Qëllimi kryesor i programeve të arkivimit.

Çfarë metodash kompresimi kemi mësuar sot?

Cila është metoda më efikase e kompresimit dhe pse?

Plani:

Prezantimi

• 1 Parimet e kompresimit të të dhënave
• 2 Karakteristikat e algoritmeve të kompresimit dhe zbatueshmëria e tyre
  • 2.1 Raporti i kompresimit
  • 2.2 Toleranca ndaj humbjes
  • 2.3 Kërkesat e sistemit të algoritmit
• 3 Algoritmet e kompresimit të të dhënave të formatit të panjohur
Letërsia

Prezantimi

Kompresimi i të dhënave(eng. ngjeshja e të dhënave) - transformimi algoritmik i të dhënave i kryer për të zvogëluar volumin e tyre. Përdoret për përdorim më racional të pajisjeve të ruajtjes dhe transmetimit të të dhënave. Sinonimet - paketimi i të dhënave, kompresimi, kodimi i kompresimit, kodimi i burimit. Procedura e kundërt quhet rikuperimi i të dhënave (zhpaketimi, dekompresimi).

Kompresimi bazohet në eliminimin e tepricës në të dhënat origjinale. Shembulli më i thjeshtë i tepricës është përsëritja e fragmenteve në tekst (për shembull, fjalë të gjuhës natyrore ose makine). Kjo tepricë zakonisht eliminohet duke zëvendësuar sekuencën e përsëritur me një referencë në një fragment tashmë të koduar me një tregues të gjatësisë së tij. Një lloj tjetër i tepricës lidhet me faktin se disa vlera në të dhënat që kompresohen ndodhin më shpesh se të tjerat. Zvogëlimi i sasisë së të dhënave arrihet duke zëvendësuar të dhënat e hasura shpesh me fjalë kodike të shkurtra, dhe të dhënat e rralla me ato të gjata (kodimi i entropisë). Kompresimi i të dhënave që nuk kanë vetinë e tepricës (për shembull, një sinjal i rastësishëm ose zhurmë, mesazhe të koduara) është thelbësisht i pamundur pa humbje.

1. Parimet e ngjeshjes së të dhënave

Çdo metodë kompresimi bazohet në modelin e burimit të të dhënave, ose më saktë, në modelin e tepricës. Me fjalë të tjera, kompresimi i të dhënave përdor disa informacione a priori se çfarë lloj të dhënash po kompresohen. Pa një njohuri të tillë të burimit, është e pamundur të bëhet ndonjë supozim për transformimin që do të zvogëlonte madhësinë e mesazhit. Modeli i tepricës mund të jetë statik, i pandryshuar për të gjithë mesazhin që kompresohet, ose mund të ndërtohet ose parametrizohet gjatë fazës së kompresimit (dhe rikuperimit). Metodat që lejojnë ndryshimin e modelit të tepricës së informacionit bazuar në të dhënat hyrëse quhen adaptive. Jo-adaptive janë zakonisht algoritme shumë të specializuara që përdoren për të punuar me të dhëna me karakteristika të mirëpërcaktuara dhe të pandryshueshme. Shumica dërrmuese e algoritmeve mjaft universale janë përshtatëse në një shkallë ose në një tjetër.

Të gjitha metodat e kompresimit të të dhënave ndahen në dy klasa kryesore:

• Kompresim pa humbje
• Kompresim me humbje

Kur përdorni kompresim pa humbje, është i mundur rikuperimi i plotë i të dhënave origjinale; kompresimi me humbje ju lejon të rikuperoni të dhëna me shtrembërime, të cilat zakonisht janë të parëndësishme nga pikëpamja e përdorimit të mëtejshëm të të dhënave të rikuperuara. Kompresimi pa humbje zakonisht përdoret për të transferuar dhe ruajtur të dhënat e tekstit, programet kompjuterike, më rrallë - për të zvogëluar volumin e të dhënave audio dhe video, fotografitë dixhitale, etj., Në rastet kur shtrembërimi është i papranueshëm ose i padëshirueshëm. Kompresimi me humbje, i cili është dukshëm më efikas se kompresimi pa humbje, zakonisht përdoret për të zvogëluar volumin e të dhënave audio dhe video dhe fotografive dixhitale në rastet kur një reduktim i tillë është prioritet dhe nuk kërkohet pajtueshmëria e plotë e të dhënave origjinale dhe të rikuperuara.

2. Karakteristikat e algoritmeve të kompresimit dhe zbatueshmëria e tyre

2.1. Raporti i kompresimit

Raporti i kompresimit është karakteristika kryesore e një algoritmi kompresimi. Përkufizohet si raporti i vëllimit të të dhënave origjinale të pakompresuara me vëllimin e të dhënave të kompresuara, domethënë:

ku k- raporti i kompresimit, S o është sasia e të dhënave fillestare, dhe S c - vëllimi i ngjeshur. Kështu, sa më i lartë të jetë raporti i kompresimit, aq më efikas është algoritmi. Duhet të theksohet:

• nëse k= 1, atëherë algoritmi nuk ngjesh, domethënë mesazhi i daljes është i barabartë në vëllim me atë hyrës;
• nëse k < 1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

Situata me k < 1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n biti është saktësisht 2 n, numri i mesazheve të ndryshme me gjatësi më të vogël ose të barabartë me n(nëse ka të paktën një mesazh me gjatësi më të shkurtër) do të jetë më pak se 2 n... Kjo do të thotë se është e pamundur të përputhen pa mëdyshje të gjitha mesazhet origjinale me një të ngjeshur: ose disa nga mesazhet origjinale nuk do të kenë një paraqitje të ngjeshur, ose disa mesazhe origjinale do të korrespondojnë me të njëjtin e ngjeshur, që do të thotë se ato nuk mund të dallohen.

Raporti i kompresimit mund të jetë ose konstant (disa algoritme për kompresimin e zërit, imazheve, etj., për shembull, A-law, μ-law, ADPCM, kodimi i blloqeve të cunguara), ose i ndryshueshëm. Në rastin e dytë, mund të përcaktohet ose për çdo mesazh specifik, ose të vlerësohet sipas disa kritereve:

• mesatare (zakonisht mbi disa grupe të dhënash testuese);
• maksimumi (rasti i kompresimit më të mirë);
• minimale (ngjeshja në rastin më të keq);

ose çfarëdo. Raporti i kompresimit me humbje në këtë rast varet shumë nga gabimi i lejueshëm i kompresimit ose cilësisë, i cili zakonisht vepron si parametër i algoritmit. Në përgjithësi, vetëm teknikat e kompresimit të të dhënave me humbje mund të ofrojnë një raport konstant kompresimi.

2.2. Toleranca ndaj humbjes

Kriteri kryesor për dallimin midis algoritmeve të kompresimit është prania ose mungesa e humbjeve të përshkruara më sipër. Në përgjithësi, algoritmet e kompresimit pa humbje janë universale në kuptimin që përdorimi i tyre është sigurisht i mundur për çdo lloj të dhënash, ndërsa mundësia e përdorimit të kompresimit me humbje duhet të justifikohet. Për disa lloje të dhënash, shtrembërimet në përgjithësi nuk janë të pranueshme. Midis tyre

• të dhëna simbolike, një ndryshim në të cilin në mënyrë të pashmangshme çon në një ndryshim në semantikën e tyre: programet dhe kodet e tyre burimore, grupet binare, etj.;
• të dhëna jetike, ndryshimet në të cilat mund të çojnë në gabime kritike: për shembull, të marra nga pajisjet matëse mjekësore ose pajisjet e kontrollit të avionëve, anijes kozmike, etj.;
• Të dhënat e ndërmjetme i nënshtrohen vazhdimisht kompresimit dhe restaurimit gjatë përpunimit shumëfazor të të dhënave grafike, audio dhe video.

2.3. Kërkesat e sistemit të algoritmit

Algoritme të ndryshme mund të kërkojnë një sasi të ndryshme të burimeve të sistemit kompjuterik në të cilat ato janë implementuar:

• memorie me akses të rastësishëm (për të dhëna të ndërmjetme);
• memorie e përhershme (për kodin e programit dhe konstantet);
• koha e procesorit.

Në përgjithësi, këto kërkesa varen nga kompleksiteti dhe "inteligjenca" e algoritmit. Tendenca e përgjithshme është si më poshtë: sa më efikas dhe i gjithanshëm të jetë një algoritëm, aq më të mëdha janë kërkesat për burimet llogaritëse që ai vendos. Megjithatë, në raste specifike, algoritmet e thjeshta dhe kompakte mund të performojnë po aq mirë sa ato komplekse dhe universale. Kërkesat e sistemit përcaktojnë cilësitë e tyre të konsumatorit: sa më pak kërkues të jetë algoritmi, aq më i thjeshtë, dhe për rrjedhojë, sistemi kompakt, i besueshëm dhe i lirë mund të zbatohet.

Meqenëse algoritmet e kompresimit dhe rikuperimit funksionojnë së bashku, raporti i kërkesave të sistemit ndaj tyre ka rëndësi. Shpesh është e mundur duke komplikuar një algoritëm për të thjeshtuar shumë një tjetër. Kështu, tre opsione janë të mundshme:

Algoritmi i kompresimit kërkon më shumë burime llogaritëse sesa algoritmi i rikuperimit. Kjo është marrëdhënia më e zakonshme, tipike për rastet kur të dhënat e kompresuara një herë do të përdoren shumë herë. Shembujt përfshijnë luajtës dixhital audio dhe video. Algoritmet e kompresimit dhe rikuperimit kërkojnë burime llogaritëse afërsisht të barabarta. Opsioni më i pranueshëm për linjat e komunikimit, kur kompresimi dhe restaurimi ndodh një herë në dy skaje (për shembull, në telefoninë dixhitale). Algoritmi i kompresimit është dukshëm më pak i kërkuar se algoritmi i rikuperimit. Kjo situatë është tipike për rastet kur procedura e kompresimit zbatohet nga një pajisje e thjeshtë, shpesh e lëvizshme, për të cilën sasia e burimeve të disponueshme është shumë kritike, për shembull, një anije kozmike ose një rrjet i madh sensorësh të shpërndarë. Mund të jenë gjithashtu të dhëna që duhen zbërthyer në një përqindje shumë të vogël të rasteve, për shembull, një regjistrim me kamera vëzhgimi me video.

3. Algoritme për kompresimin e të dhënave të formatit të panjohur

Ekzistojnë dy qasje kryesore për kompresimin e të dhënave të formatit të panjohur.

• Në çdo hap të algoritmit të kompresimit, karakteri tjetër i ngjeshur ose vendoset në buferin e daljes së koduesit kompresues ashtu siç është (me një flamur të veçantë që tregon se nuk është ngjeshur), ose një grup me disa karaktere të ngjeshur zëvendësohet me një lidhje me një grup karakteresh tashmë të koduar që përputhen me të. Për shkak se rikuperimi i të dhënave të kompresuara në këtë mënyrë është shumë i shpejtë, kjo qasje përdoret shpesh për të krijuar programe vetë-ekstraktuese.
• Për çdo sekuencë karakteresh që kompresohen, statistikat e paraqitjes së tij në të dhënat e koduara mblidhen një herë ose në çdo moment të kohës. Bazuar në këtë statistikë, llogaritet probabiliteti i vlerës së karakterit të koduar të ardhshëm (ose sekuencës së karaktereve). Pas kësaj, zbatohet një ose një lloj tjetër kodimi i entropisë, për shembull, kodimi aritmetik ose kodimi Huffman, për të përfaqësuar sekuenca të shpeshta në fjalë të kodit të shkurtër, dhe ato që gjenden rrallë me ato më të gjata.

Letërsia

• D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin. Metodat e kompresimit të të dhënave. Pajisja e arkivave, kompresimi i imazheve dhe videove. - Dialogu-MEPhI, 2002 .-- P. 384 .-- ISBN 5-86404-170-X 3000 kopje
• D. Salomon. Kompresimi i të dhënave, imazheve dhe zërit. - M .: Technosphere, 2004 .-- S. 368 .-- ISBN 5-94836-027-X 3000 kopje

Rrëshqitja 2

• Për ruajtjen afatgjatë të të dhënave në media të ndryshme ruajtjeje
• Për transmetimin e të dhënave nëpërmjet kanaleve të komunikimit