Kompresimi i të dhënave(kompresimi i të dhënave) teknikë zvogëlimi i vëllimit (madhësive) të regjistrimit të të dhënave në median e tyre (disk i fortë magnetik, disketë, shirit magnetik); Zbatohet me metoda të ndryshme, kryesisht duke përdorur kodim (të fjalëve, frazave, simboleve të përsëritura). Mund të dallohen dy grupe të mënyrave të kompresimit të të dhënave: statike dhe dinamike; të bëjë dallimin midis ngjeshjes fizike dhe logjike; kompresim simetrik dhe asimetrik; kodim adaptiv, gjysmë-përshtatës dhe jo-përshtatës; ngjeshje pa humbje, pa humbje dhe pa humbje. Metodat (llojet) e kompresimit të të dhënave:

Kompresimi statik i të dhënave - përdoret për ruajtje dhe arkivim afatgjatë; kryhet duke përdorur programe speciale të shërbimeve arkivuese, si ARJ, PKZIP/PKUNZIP. Pas rikuperimit (dekompresimit), regjistrimi origjinal rikthehet.
Kompresim dinamik (kompresim në kohë reale; kompresim dinamik, kompresim në kohë reale) - i projektuar për të reduktuar hapësirën e zënë në disk nga të dhënat që kërkojnë qasje në internet dhe dalje në pajisje të jashtme kompjuter (përfshirë në ekranin e monitorit). Kompresimi dhe rikuperimi dinamik i të dhënave kryhet nga softuer special automatikisht dhe "menjëherë".
Kompresimi fizik është një metodologji kompresimi në të cilën të dhënat rindërtohen në një formë më kompakte "formalisht", domethënë, pa marrë parasysh natyrën e informacionit që përmbahet në të.
Kompresimi logjik është një metodologji në të cilën një grup karakteresh alfabetike, numerike ose binare zëvendësohet nga një tjetër. Në të njëjtën kohë, kuptimi semantik i të dhënave origjinale ruhet. Një shembull është zëvendësimi i një fraze me shkurtesën e saj. Kompresimi Boolean bëhet në një karakter ose më shumë nivel të lartë dhe bazohet vetëm në përmbajtjen e të dhënave origjinale. Kompresimi Boolean nuk zbatohet për imazhet.
Kompresimi simetrik është një metodologji kompresimi, sipas së cilës parimet e ndërtimit të algoritmeve për paketimin dhe zbërthimin e të dhënave janë të lidhura ngushtë ose ngushtë. Kur përdorni kompresimin simetrik, koha e shpenzuar për kompresimin dhe dekompresimin e të dhënave është proporcionale. Programet e komunikimit zakonisht përdorin kompresim simetrik.
Kompresimi asimetrik është një metodologji sipas së cilës harxhohet më shumë kohë gjatë kryerjes së punës "në një drejtim" sesa gjatë kryerjes së punës në një drejtim tjetër. Kompresimi i imazheve zakonisht kërkon shumë më tepër kohë dhe burime të sistemit sesa dekompresimi i tyre. Efektiviteti i kësaj qasjeje përcaktohet nga fakti se imazhet mund të kompresohen vetëm një herë, dhe të dekompresohen për t'i shfaqur ato shumë herë. Algoritmet asimetrike "në drejtim të kundërt" (duhet më pak kohë për të kompresuar të dhënat sesa për të dekompresuar) përdoren gjatë kryerjes Rezervo kopje të dhëna.
Kodimi adaptiv është një metodologji kodimi për kompresimin e të dhënave që nuk është i para-konfiguruar për një lloj specifik të dhënash. Programet që përdorin kodim adaptiv përshtaten me çdo lloj të dhënash të ngjeshur, duke arritur reduktimin maksimal të volumit të tyre.
Kodimi jo-përshtatës - Metodologjia e kodimit e orientuar drejt kompresimit lloj i caktuar ose llojet e të dhënave. Koduesit e ndërtuar mbi këtë parim kanë fjalorë statikë të "nënvargjeve të paracaktuara" që dihet se shfaqen shpesh në të dhënat e koduara. Një shembull është metoda e kompresimit Huffman.
Kodimi gjysmë-përshtatës është një metodologji e kodimit të kompresimit të të dhënave që përdor elemente të kodimit adaptiv dhe jo-përshtatës. Parimi i funksionimit të kodimit gjysmë-përshtatës është që koduesi kryen dy grupe operacionesh: së pari, shikimin e grupit të të dhënave të koduara dhe ndërtimin e një fjalori për to, dhe më pas kodimin e vetvetes.
Kompresimi pa humbje është një metodologji kompresimi në të cilën një pjesë e koduar më parë e të dhënave rikthehet plotësisht pas dekompresimit pa asnjë ndryshim.
Kompresimi me humbje është një metodologji në të cilën, për të siguruar shkallën maksimale të ngjeshjes grup origjinal një pjesë e të dhënave që përmban hidhet poshtë. Për të dhënat tekstuale, numerike dhe tabelare, përdorimi i programeve që zbatojnë metoda të ngjashme kompresimi është i papranueshëm. Megjithatë, për programet që punojnë me grafikë, kjo është shpesh e dobishme. Cilësia e imazhit të restauruar varet nga natyra e materialit grafik dhe korrektësia e algoritmit të kompresimit të zbatuar në program. Ekzistojnë një sërë algoritmesh kompresimi që marrin parasysh nivelet e pranueshme të humbjes së imazhit grafik origjinal në raste specifike të përdorimit të imazhit të tij të rivendosur, për shembull, duke e parë atë në një ekran monitori, duke e printuar me printer, në poligrafi. Këto teknika së bashku referohen si kompresim i minimizuar me humbje.
Kompresimi i imazhit (ngjeshja e imazhit) është një teknikë ose metodë e zvogëlimit të vëllimit (madhësive) të regjistrimit të imazheve grafike (vizatime, vizatime, diagrame) në median e tyre (për shembull, në një disk magnetik, shirit magnetik). Në thelb, "ngjeshja e imazhit" është një lloj kompresimi dinamik. Për zbatimin e tij përdoren metoda të ndryshme të kodimit të të dhënave, të cilat fokusohen në elementët grafikë që përbëjnë imazhin, duke përfshirë objektet në lëvizje. Përdoret gjithashtu gjatë transmetimit të informacionit faksimile përmes kanaleve të komunikimit, në sistemet multimediale, videofonat.
Kompresimi i diskut është një teknikë e bazuar në kompresimin dinamik në procesin e shkrimit në disk dhe gjatë leximit të tyre. rikuperim automatik në formën origjinale. Kompresimi i diskut përdoret për të rritur kapacitetin e diskut. Në varësi të natyrës së regjistrimeve, kapaciteti i diskut mund të rritet me rreth 1,5 deri në 5 herë. Kompresimi i diskut kryhet nga speciale programet e aplikimit, të tilla si DoubleSpace, Stacker, SuperStor.

Metodat dhe mjetet e kompresimit të të dhënave:
Metoda e kompresimit Huffman (kodimi CCITT) u zhvillua në vitin 1952 nga David Huffman. Komiteti Konsultativ Ndërkombëtar për Telefoninë dhe Telegrafinë (CCITT) ka zhvilluar mbi bazën e tij një numër protokollesh komunikimi për transmetimin me faks. imazhe bardh e zi mbi kanalet telefonike dhe rrjetet e të dhënave (Standard T.4 CCIT dhe T.6 CCITT, ato janë gjithashtu kompresimi i grupit CCITT 3 dhe kompresimi i grupit CCITT 4).
Kompresimi fraktal - metoda e ngjeshjes bitmap duke i shndërruar në të ashtuquajturat fraktale. Ruajtja e imazheve si fraktale kërkon katër herë më pak hapësirë ​​në disk sesa në piksel.
ART është një metodë për kompresimin e tekstit, grafikës, audios dhe videos. Parimi i funksionimit të algoritmit të kompresimit bazohet në analizën e imazhit dhe identifikimin e veçorive kryesore të tij (ngjyra, zhurma, skajet, veçoritë e përsëritura).
AC3 Dolby është një metodë dhe format kompresimi që ju lejon të kompresoni, ruani dhe transmetoni deri në 6 kanale të të dhënave audio në një skedar të vetëm me një shpejtësi prej 32 deri në 640 kbps.
DJVU (DjVu, djvu, deja vu) është një teknologji dhe format për ngjeshjen dinamike të faqeve të skanuara të botimeve që përmbajnë tekst dhe materiale ilustruese.
DVI (Digital Video Interactive) është një sistem për kompresimin dinamik dhe restaurimin e regjistrimeve audio dhe video në formë dixhitale. Përdorimi i tij ju lejon të shkruani një film video me gjatësi të plotë së bashku me zërin në një CD-ROM.
EAD (Encoded Archival Description) është një standard kodimi i zhvilluar nga Zyra e Zhvillimit të Rrjetit dhe e Standardeve MARC të Bibliotekës së Kongresit në bashkëpunim me Shoqërinë e Arkivistëve Amerikanë në 1998 (përditësuar 2002). Standardi përcakton parimet për krijimin, zhvillimin dhe mirëmbajtjen e skemave të kodimit për mjetet ndihmëse të kërkimit arkivor dhe bibliotekar (ndihmesa për gjetjen).
Menaxheri i kompresimit të imazhit është një menaxher dinamik i ngjeshjes së imazhit që ofron mundësinë e përdorimit metoda të ndryshme Kompresimi/rikuperimi i imazhit (MPEG, JPEG).
JBIG (Joint Bi-level Image Experts Group) është një metodë kompresimi pa humbje për imazhet me dy nivele (me dy ngjyra), e krijuar nga Grupi i Përbashkët i Ekspertëve të Imazhit në Dy nivele të ISO dhe CCIT në 1988. Metoda JBIG u miratua në 1993 si një standard i kodimit të të dhënave me dy nivele në vend të algoritmeve më pak efikase të kompresimit MR (Modified READ) dhe MMR (Modified Modified READ).
LZW (Lempel-Ziv-Welch) është një metodë dinamike kompresimi e bazuar në kërkimin e të gjithë skedarit dhe ruajtjen e sekuencave identike të të dhënave (ato quhen fraza) në fjalor. Secilës sekuencë unike të të dhënave i caktohen shenja (çelësat) më të shkurtër.
MP3 (Moving Pictures Experts Group, Layer 3) është një metodë dinamike e kompresimit (algoritëm) dhe një format i veçantë për regjistrimin e skedarëve të të dhënave audio. MP3 siguron një shkallë të lartë të kompresimit të regjistrimeve audio dhe përdoret në aplikacionet multimediale, veçanërisht në luajtësit dixhital (lojtarët) dhe internetin.
RLE (Run Length Encoding) është një metodë e kompresimit dinamik të të dhënave grafike, kryesisht imazheve, bazuar në reduktimin madhësia fizike duke përsëritur vargjet e karaktereve.

Dërgoni punën tuaj të mirë në bazën e njohurive është e thjeshtë. Përdorni formularin e mëposhtëm

Punë e mirë në sajtin">

Studentët, studentët e diplomuar, shkencëtarët e rinj që përdorin bazën e njohurive në studimet dhe punën e tyre do t'ju jenë shumë mirënjohës.

Priti në http://www.allbest.ru/

Kompresimi i të dhënave

1. Informacion. Llojet dhe vetitë e tij

Në literaturë, mund të gjeni mjaft përkufizime të termit "informacion", duke pasqyruar qasje të ndryshme për interpretimin e këtij koncepti. Fjalori shpjegues i gjuhës ruse Ozhegov jep 2 përkufizime të fjalës "informacion":

Informacion rreth botës përreth dhe proceseve që ndodhin në të, të perceptuara nga një person ose një pajisje e veçantë.

Mesazhe që informojnë për gjendjen e punëve, për gjendjen e diçkaje. (Informacione shkencore-teknike dhe gazetore, masmedia - shtyp, radio, televizion, kinema).

Informacioni dhe vetitë e tij janë objekt studimi i një sërë disiplinash shkencore, si teoria e informacionit (teoria matematikore e sistemeve të transmetimit të informacionit), kibernetika (shkenca e komunikimit dhe kontrollit në makina dhe kafshë, si dhe në shoqëri dhe në njerëz. qeniet), semiotika (shkenca e shenjave dhe sistemeve të shenjave), teoria e komunikimit masiv (studimi i mediave dhe ndikimi i tyre në shoqëri), informatika (studimi i proceseve të grumbullimit, transformimit, ruajtjes, mbrojtjes, kërkimit dhe transmetimin e të gjitha llojeve të informacionit dhe mjeteve të tyre përpunimi i automatizuar), fizikë dhe matematikë.

Informacioni ka karakter të dyfishtë: material - mund të transmetohet, ruhet etj.; dhe i paprekshëm - sipas squfurit të transmetimit, ai mund të rimbushet. Informacioni nuk mund të ekzistojë pa bartësin e tij material, një mjet për ta transferuar atë në hapësirë ​​dhe kohë. Vetë objekti fizik ose ekuivalenti i tij i energjisë mund të veprojë si bartës si sinjale të zërit, dritës, elektrike dhe të tjera.

Për ta bërë këtë, aktualisht, janë shpikur shumë metoda për ruajtjen e informacionit në media të jashtme (në lidhje me trurin e njeriut) dhe transmetimin e tij në distanca të mëdha.

Llojet kryesore të informacionit në formën e tij të paraqitjes, metodat e kodimit dhe ruajtjes së tij, që ka vlera më e lartë për shkenca kompjuterike, kjo është:

· grafike ose pikturale - lloji i parë për të cilin u zbatua një metodë e ruajtjes së informacionit për botën përreth në formën e pikturave shkëmbore, dhe më vonë në formën e pikturave, fotografive, diagrameve, vizatimeve në letër, kanavacë, mermer dhe materiale të tjera që përshkruajnë fotografi. të botës reale;

· tingull- bota rreth nesh është plot me tinguj dhe problemi i ruajtjes dhe përsëritjes së tyre u zgjidh me shpikjen e pajisjeve të regjistrimit të zërit në 1877; shumëllojshmëria e tij është informacion muzikor - për këtë lloj, u shpik një metodë e kodimit duke përdorur karaktere speciale, gjë që bën të mundur ruajtjen e tij në një mënyrë të ngjashme informacion grafik;

· tekstuale- një mënyrë për të koduar fjalimin njerëzor me karaktere të veçanta - shkronja, dhe popuj të ndryshëm kanë gjuhë të ndryshme dhe përdorin grupe të ndryshme shkronjash për të shfaqur fjalimin; kjo metodë u bë veçanërisht e rëndësishme pas shpikjes së letrës dhe printimit;

· numerike- masa sasiore e objekteve dhe vetive të tyre në botën përreth; mori rëndësi të veçantë me zhvillimin e tregtisë, ekonomisë dhe këmbimit të parave; po ashtu informacion teksti për ta shfaqur atë, përdoret metoda e kodimit me karaktere të veçanta - numra, dhe sistemet e kodimit (numrat) mund të jenë të ndryshëm;

· informacion video- një mënyrë për të ruajtur fotot "live" të botës përreth nesh, të cilat u shfaqën me shpikjen e kinemasë.

Për të transmetuar informacion në distanca të gjata, fillimisht u përdorën sinjale të koduara të dritës, me shpikjen e energjisë elektrike - transmetimi i një sinjali të koduar në një mënyrë të caktuar mbi tela, më vonë - duke përdorur valë radio.

Me ardhjen e kompjuterëve (ose, siç quheshin fillimisht në vendin tonë, kompjuterët - elektronikë makinat informatike) fillimisht u shfaq një mjet për përpunim informacion numerik. Megjithatë, në të ardhmen, veçanërisht pas përdorimit të gjerë të kompjuterëve personalë (PC), kompjuterët filluan të përdoren për ruajtjen, përpunimin, transmetimin dhe kërkimin e informacionit tekstual, numerik, vizual, audio dhe video. Që nga ardhja e kompjuterëve të parë personalë - PC (vitet 80 të shekullit të 20-të) - deri në 80% të kohës së tyre të punës i kushtohet punës me informacion tekstual.

Ruajtja e informacionit gjatë përdorimit të kompjuterëve kryhet në disqe magnetike ose fjongo, disqe lazer(CD dhe DVD), pajisje speciale të memories jo të paqëndrueshme (memorie flash, etj.). Këto metoda janë duke u përmirësuar vazhdimisht, pajisje të reja dhe transportues informacioni janë duke u shpikur. Përpunimi i informacionit (riprodhimi, konvertimi, transferimi, regjistrimi në media të jashtme) kryhet nga procesori kompjuterik. Duke përdorur një kompjuter, është e mundur të krijohet dhe ruhet informacione të rejaçdo lloj për të cilin shërbejnë programe të veçanta përdoret në kompjuterë dhe pajisje hyrëse.

Aktualisht, informacioni i paraqitur në internetin global mund të konsiderohet një lloj i veçantë informacioni. Ai përdor teknika të veçanta për ruajtjen, përpunimin, kërkimin dhe transmetimin e informacionit të shpërndarë në vëllime të mëdha dhe mënyra të veçanta të punës me lloje të ndryshme informacion. Përmirësuar vazhdimisht software, e cila ofron punë kolektive me informacione të të gjitha llojeve.

Karakteristikat e informacionit

Mund të citohen shumë veti të ndryshme të informacionit. Çdo disiplinë shkencore merr në konsideratë ato që janë më të rëndësishme për të. Nga pikëpamja e shkencës kompjuterike, vetitë e mëposhtme janë më të rëndësishmet:

1. Objektiviteti dhe subjektiviteti i informacionit. Informacion më objektiv konsiderohet të jetë informacioni në të cilin metodat paraqesin një element subjektiv më të vogël. Gjatë procesit të informacionit, shkalla e objektivitetit të informacionit gjithmonë zvogëlohet.

2. Plotësia e informacionit. Plotësia e informacionit karakterizon kryesisht cilësinë e informacionit dhe përcakton mjaftueshmërinë e të dhënave për vendimmarrje ose për krijimin e të dhënave të reja bazuar në ato ekzistuese.

3. Besueshmëria e informacionit. Të dhënat ndodhin në momentin e regjistrimit të sinjaleve, por jo të gjitha sinjalet janë "të dobishme" - ekziston gjithmonë një nivel sinjalesh të jashtme.

5. Disponueshmëria e informacionit.

6. Rëndësia.

2. Kompresimi i të dhënave

Rregulli i njohur në bota kompjuterike atë kapacitet hard disk nuk ndodh shumë. Në të vërtetë, është e vështirë të mos pajtohesh me të: pa marrë parasysh sa i madh mund të duket hard disku gjatë blerjes, ai bllokohet shpejt me ndonjë informacione të panevojshme. Meqenëse është për të ardhur keq të fshish gjithçka, ia vlen kohë pas kohe për të "ruajtur" të gjitha këto gjëra në një lloj ruajtjeje, arkivimi.

NGAngjeshja e të dhënave- procedurën e rikodimit të të dhënave, e kryer me qëllim zvogëlimin e volumit të tyre. Përdoret për përdorim më racional të pajisjeve të ruajtjes dhe transmetimit të të dhënave. Nëse metodat e kompresimit të informacionit aplikohen në dokumentet e përfunduara, atëherë termi "kompresim i të dhënave" shpesh zëvendësohet me termin "arkivim të të dhënave".

Kompresimi bazohet në eliminimin e tepricës së informacionit që përmban të dhënat origjinale. Një shembull i tepricës është përsëritja e fragmenteve në tekst (për shembull, fjalë të natyrshme ose gjuha e makinerisë). Një tepricë e tillë zakonisht eliminohet duke zëvendësuar sekuencën përsëritëse me një vlerë (kod) më të shkurtër. Një lloj tjetër i tepricës është për faktin se disa vlera në të dhënat e kompresuara ndodhin më shpesh se të tjerat, ndërkohë që është e mundur të zëvendësohen të dhënat që ndodhin shpesh me më shumë. kode të shkurtra, ndërsa të rrallat janë më të gjata (ngjeshja probabilistike). Kompresimi i të dhënave që nuk kanë vetinë e tepricës (për shembull, sinjal i rastësishëm ose zhurmë) është e pamundur pa humbje. Gjithashtu, zakonisht nuk është e mundur të kompresohen informacionet e koduara.

Algoritme për kompresimin e teksteve / skedarëve të një formati të panjohur

Ekzistojnë 2 mënyra kryesore për të kompresuar skedarët me format të panjohur.

Në çdo hap të algoritmit të kompresimit, ose karakteri tjetër vendoset siç është (me një flamur të veçantë që tregon se nuk është i ngjeshur), ose kufijtë e fjalëve specifikohen nga pjesa e mëparshme, e cila përputhet me karakteret vijuese në skedar. Zbërthimi i skedarëve të ngjeshur në këtë mënyrë është shumë i shpejtë, kështu që këto algoritme përdoren për të krijuar programe vetë-ekstraktuese.

Për çdo sekuencë, statistikat e paraqitjes së saj në skedar mblidhen në çdo moment të kohës. Bazuar në këto statistika, llogaritet probabiliteti i vlerave për simbolin e ardhshëm. Pas kësaj, ju mund të përdorni një ose një lloj tjetër kodimi i entropisë, për shembull, kodimi aritmetik ose kodimi Huffman për të zëvendësuar sekuencat që ndodhin shpesh me ato më të shkurtra dhe ato që ndodhin rrallë me ato më të gjata.

Kompresimi mund të jetë pa humbje (kur është e mundur të rivendosni të dhënat origjinale pa shtrembërim) ose me humbje (rikuperimi është i mundur me shtrembërime që janë të parëndësishme nga pikëpamja e përdorimit të mëtejshëm të të dhënave të rikuperuara). Kompresimi pa humbje përdoret zakonisht në përpunim programet kompjuterike dhe të dhënat, më rrallë - për të zvogëluar volumin e informacionit të zërit, fotografisë dhe videove. Kompresimi me humbje përdoret për të zvogëluar sasinë e informacionit audio, foto dhe video, është dukshëm më efikas se kompresimi asnjë humbje.

3. Softuer për kompresimin e të dhënave

Nëse metodat e ngjeshjes së informacionit aplikohen në dokumentet e përfunduara. Shpesh termi "kompresim i të dhënave" zëvendësohet me termin "arkivim i të dhënave" dhe softueri që kryen këto operacione quhet arkivues.

Arkivuesit janë krijuar për të kompresuar skedarët, dmth. për të reduktuar hapësirën e tyre në disk. Ato lejojnë përdorimin e metodave speciale të paketimit të informacionit për të kompresuar informacionin në disqe, duke krijuar kopje të skedarëve në një skedar arkivi. Pavarësisht se sasia e memories së kompjuterit po rritet vazhdimisht, nevoja për arkivim nuk po zvogëlohet.

Pra, arkivimi mund të jetë i dobishëm:

1) Kur ruani kopje të skedarëve dhe disketave, sepse disketa është e kufizuar në madhësi;

2) Për të liruar hapësirën në hard disk;

3) Kur transmetoni informacion në rrjet.

Arkivimi i informacionit është një transformim i tillë i informacionit në të cilin vëllimi i tij nuk zvogëlohet, por sasia e informacionit mbetet e njëjtë.

Skedari i ngjeshur quhet arkiv. Skedari i arkivit është në një mënyrë të veçantë skedar i organizuar, që përmban një ose më shumë skedarë në formë të ngjeshur dhe të pakompresuar, dhe informacion shërbimi për emrat e tyre.

Shkalla e ngjeshjes së informacionit varet nga lloji skedari burimor, programin e përdorur dhe metodën e paketimit të zgjedhur. Skedarët më të mirë për të kompresuar objekte grafike, skedarët e tekstit dhe skedarët e të dhënave, për të cilët raporti i kompresimit mund të arrijë 5-40%, skedarët kompresohen më pak programe të ekzekutueshme dhe modulet e nisjes -60-90%.

Zhvillues të ndryshëm kanë krijuar shumë programe arkivimi. Midis tyre, më të zakonshmet për Windows janë WINRAR, WINZIP.

Nga popullariteti i saj Arkivi WinRAR, pa dyshim, është në vendin e parë në Rusi, dhe një nga të parët - në të gjithë botën. Arkivi u zhvillua nga Evgeny Roshal në 2003. Programi ofron kontroll të plotë dosjet në arkiva, rikuperimi i arkivave të dëmtuara, enkriptimi, krijimi i arkivave vetënxjerrëse dhe shumëvëllimore.

WinZip është një nga programet më të njohura në internet, pasi ka marrë një numër të konsiderueshëm çmimesh nga botime të ndryshme kompjuterike në të gjithë botën.

Vetë Zip - algoritmi përdoret lirshëm në dhjetëra programe, megjithatë, për shumë përdorues të Windows, WinZip është PIKËRISHT. program standard për të punuar me arkivat. Mjetet e integruara të përpunimit të arkivit WinZIP ju lejojnë të paketoni, shikoni dhe ekstraktoni skedarë nga formatet e arkivit të përdorur gjerësisht si ZIP, CAB, Microsoft Compress, GZIP, TAR, etj. WinZip është shumë i thjeshtë dhe i lehtë për t'u përdorur.

Megjithatë, nuk është gjithmonë e justifikuar të përdoren arkivues të veçantë me mjediset e tyre grafike. Predha më e përshtatshme për arkivuesit është një menaxher i rregullt i skedarëve, për shembull, Komandanti i Windows, i cili ka aftësinë për të parë dhe shpaketuar skedarët e arkivit ZTP, ARJ, RAR, TAR, GZ, CAB, ACE. Megjithatë, shumica e operacioneve me skedarë, duke përfshirë arkivat, kryhen në menaxherë të tillë.

4. Kompresimi i të dhënave me humbje

Kompresimi i të dhënave me humbjeështë një metodë e kompresimit të të dhënave ku skedari i dekompresuar ndryshon nga origjinali, por është "afër sa duhet" për të qenë i dobishëm në një farë mënyre. Ky lloj kompresimi përdoret shpesh në internet, veçanërisht në transmetim dhe telefoni. Këto metoda shpesh quhen kodekë në këtë kontekst. Alternativa është kompresimi pa humbje.

Llojet e kompresimit me humbje

Ekzistojnë dy skema kryesore të kompresimit me humbje:

Në kodekët e transformimit, kornizat e imazheve ose zërit merren, priten në segmente të vogla, shndërrohen në një hapësirë ​​të re bazë dhe kryhet kuantizimi. Rezultati më pas kompresohet me anë të metodave të entropisë.

Në kodekët parashikues, të dhënat e mëparshme dhe/ose të ardhshme përdoren për të parashikuar kornizën aktuale të një imazhi ose tingulli. Gabimi midis të dhënave të parashikuara dhe të dhënave reale, së bashku me informacionin shtesë të nevojshëm për të prodhuar parashikimin, më pas kuantizohet dhe kodohet.

Disa sisteme kombinojnë këto dy teknika duke përdorur kodekët e transformimit për të kompresuar sinjalet e gabuara të krijuara gjatë fazës së parashikimit.

Kompresim me humbje vs pa humbje

Avantazhi i metodave të kompresimit me humbje mbi metodat e kompresimit pa humbje është se të parat e tejkalojnë ndjeshëm raportin e kompresimit, ndërkohë që plotësojnë kërkesat.

Teknikat e kompresimit me humbje shpesh përdoren për të kompresuar audion ose imazhet.

Në raste të tilla, skedari i dekompresuar mund të jetë shumë i ndryshëm nga origjinali në një nivel bit-për-bit, por praktikisht i padallueshëm për veshin ose syrin e njeriut në shumicën e aplikacioneve praktike.

Shumë metoda fokusohen në veçoritë strukturore të organeve shqisore të njeriut. Modeli psikoakustik përcakton se sa zë mund të kompresohet pa degraduar cilësinë e perceptuar të zërit. Papërsosmëritë e shkaktuara nga ngjeshja me humbje që është e dukshme për veshin ose syrin e njeriut njihen si artefakte kompresimi.

Të dhënat audio të kompresuara me humbje nuk pranohen nga gjykatat si provë materiale (dhe as nuk merren parasysh) për faktin se informacioni i ngjeshur fiton artefakte kompresimi dhe humb zhurmën natyrale të mjedisit nga i cili është bërë regjistrimi. Në lidhje me këtë, është e pamundur të përcaktohet nëse regjistrimi është i vërtetë apo i sintetizuar. Kjo është arsyeja pse rekorde të rëndësishme rekomandohet të prodhohet në format PCM (PCM) ose të përdoret një magnetofon.

Fotot e regjistruara në Formati JPEG, mund të pranohet nga gjykata (pavarësisht se të dhënat kanë pësuar komprimim me humbje). Por në të njëjtën kohë, duhet të sigurohet kamera me të cilën janë bërë, ose tabela përkatëse e interpretimit të ngjyrave.

Metodat e kompresimit të të dhënave me humbje

v Kompresimi i imazhit:

Ulje e thellësisë së ngjyrës

· Metoda e komponentit kryesor;

· Kompresim fraktal;

v Kompresimi i videos:

· Flash (gjithashtu mbështet imazhet lëvizëse JPEG);

MPEG-1 Pjesa 2;

· MPEG-2 Pjesa 2;

· MPEG-4 Pjesa 2;

v Kompresimi i audios:

· MP3 - Përcaktuar nga specifikimi MPEG-1;

Ogg Vorbis (i dukshëm për mungesën e kufizimeve të patentave dhe më shumë cilesi e larte);

· AAC, AAC+ - ekziston në disa versione të përcaktuara nga specifikimet MPEG-2 dhe MPEG-4, të përdorura, për shembull, në kompjuterin Apple;

eAAC+ është një format i ofruar nga Sony si një alternativë ndaj AAC dhe AAC+;

· WMA - pronë e Microsoft;

Humbja e arkivit të kompresimit të informacionit

5. Kompresimi i të dhënave pa humbje

Kompresim pa humbje(eng. Kompresimi i të dhënave pa humbje) - një metodë e ngjeshjes së informacionit, duke përdorur të cilën informacioni i koduar mund të rikthehet brenda një biti. Në këtë rast, të dhënat origjinale rikthehen plotësisht nga gjendja e ngjeshur. Ky lloj kompresimi është thelbësisht i ndryshëm nga kompresimi i të dhënave me humbje. Për çdo lloj informacioni dixhital, si rregull, ekzistojnë algoritme optimale të kompresimit pa humbje.

Kompresimi i të dhënave pa humbje përdoret në shumë aplikacione. Për shembull, përdoret në skedarin popullor format ZIP dhe programi i Unix Gzip. Përdoret gjithashtu si një komponent në kompresimin me humbje.

Kompresimi pa humbje përdoret kur identiteti i të dhënave të kompresuara me origjinalin është i rëndësishëm. Një shembull i zakonshëm janë skedarët e ekzekutueshëm dhe kodi burimor. Disa grafik formatet e skedarëve, të tilla si PNG ose GIF, përdorni vetëm kompresim pa humbje; ndërsa të tjerët (TIFF, MNG) mund të përdorin kompresim me humbje dhe pa humbje.

Teknika e kompresimit pa humbje

Nga kombinatorika rezulton se nuk ka asnjë algoritëm kompresimi pa humbje që mund të zvogëlojë çdo skedar me të paktën një bajt. Megjithatë, kjo nuk është një shenjë e cilësisë së një algoritmi kompresimi - algoritmi duhet të funksionojë në mënyrë efektive në të dhënat për të cilat është krijuar.

Algoritmet e kompresimit me shumë qëllime ndryshojnë në atë që janë në gjendje të zvogëlojnë gamë të gjerë të dhëna - skedarë të ekzekutueshëm, skedarë të dhënash, tekste, grafikë etj., dhe përdoren në arkivues. Algoritmet e specializuara janë krijuar për një lloj të caktuar skedarësh (tekst, grafikë, zë, etj.), por ato i kompresojnë skedarë të tillë shumë më fort. Për shembull: arkivuesit e kompresojnë tingullin me rreth një të tretën (1,5 herë), ndërsa FLAC e ngjesh atë me 2,5 herë. Shumica e algoritmeve të specializuara kanë pak përdorim për llojet e skedarëve "të huaj": për shembull, të dhënat audio kompresohen dobët nga një algoritëm i krijuar për tekste.

Shumica e algoritmeve të kompresimit pa humbje funksionojnë në dy faza: i pari gjeneron një model statistikor për të dhënat hyrëse, i dyti krijon bitmap të dhënat hyrëse, duke përdorur modelin për të prodhuar të dhëna "probabiliste" (d.m.th., që ndodhin shpesh) që përdoren më shpesh sesa ". të dhëna të pamundura..

Modelet statistikore të algoritmeve për tekstin (ose të dhënat binare të bazuara në tekst, siç janë ato të ekzekutueshme) përfshijnë:

Transformimi Burrows-Wheeler (parapërpunimi i renditjes së bllokut që e bën kompresimin më efikas)

LZ77 dhe LZ78 (duke përdorur DEFLATE)

Algoritmet e kodimit përmes gjenerimit të sekuencave të biteve:

Algoritmi Huffman (i përdorur gjithashtu nga DEFLATE)

kodimi aritmetik

Metodat e kompresimit pa humbje

· Me shumë qëllime

· Kodimi i gjatësisë së vrapimit - qark i thjeshtë, duke dhënë kompresim i mirë të dhëna që përmbajnë shumë vlera të dyfishta

· LZW - përdoret në gif dhe shumë të tjera.

· Deflate - përdoret në gzip, një version i avancuar i zip, dhe si pjesë e procesit të kompresimit PNG.

· LZMA - përdoret në 7-zip.

v Kompresimi i audios:

· Apple Lossless - ALAC (Apple Lossless Audio Codec);

· Kodimi pa humbje audio - i njohur gjithashtu si MPEG-4 ALS;

· Transferimi i drejtpërdrejtë i rrjedhës - DST;

· Kodiku i audios pa humbje - FLAC;

v Kompresimi i grafikës

ABO - Optimizimi Binar Adaptive;

· GIF - (pa humbje vetëm për imazhet që përmbajnë më pak se 256 ngjyra);

· JBIG2 - (me ose pa imazhe B/W me humbje);

· JPEG-LS - (standardi i kompresimit pa humbje / pothuajse pa humbje);

· JPEG 2000 - (përfshin kompresimin pa humbje; testuar gjithashtu nga Sunil Kumar, profesor i Universitetit Shtetëror të San Diegos);

· PGF - Skedari Grafik Progresiv (ngjeshje me/pa humbje);

PNG - Portable Network Graphics;

· WMPhoto - (përfshirë metodën e kompresimit pa humbje);

v Kompresimi i videos

Kodeku i animacionit;

· CamStudio Video Codec;

6. Ruajtja e informacionit (teksti, grafiku, zëri)

Informacioni ruhet duke përdorur media të caktuara ruajtjeje. Një person ruan njohuritë e tij ose në kujtesën e tij ose në disa media e jashtme.

Në fillim, një person përdori kujtesën e tij për të ruajtur dhe grumbulluar informacion - ai thjesht mësoi përmendësh informacionin e marrë dhe e mbajti atë për ca kohë. Gradualisht, njerëzit arritën në përfundimin se kjo metodë e ruajtjes së informacionit ka një sërë disavantazhesh. Duke kuptuar mosbesueshmërinë e një metode të tillë të ruajtjes dhe grumbullimit të informacionit, një person filloi të regjistrojë informacione në formën e vizatimeve, me shpikjen e shkrimit - në papirus, dhe më vonë në libra. Më pas si elementë u shfaqën pllaka fotografike dhe pajisjet e regjistrimit të zërit memorie të jashtme informacione video dhe audio, fletore, libra referimi, enciklopedi etj., që ne i quajmë ruajtje e jashtme të dhëna. Nga mesi i shekullit të 20-të, kompjuteri ishte shpikur. Menjëherë lindi pyetja se si do ta ruante informacionin.

Bartësi i informacionit mund të jetë i një natyre të ndryshme: letra. Mekanike, magnetike, elektrike. Informacioni i regjistruar në media mund të jetë në formën e një simboli të lexueshëm nga njeriu ose në një formë të koduar. Informacion për një regjistrues kasetë, regjistrues video, kamerë filmi - tingull të ruajtura në pajisje speciale: kaseta audio, videokaseta, filma. Përdorimi i mikrofonit dhe pajisjeve të tjera informacione të shëndosha të regjistruara në shirit magnetik.

Në kompjuterë, si pajisje për të shkruar, filloi të përdoret leximi i informacionit: lexues letrash me grushta; disqe magnetike, disqe (disk drive) dhe hard (hard drive) disqe magnetike; disqet kompakte (CD-ROM) dhe pajisje të tjera më moderne për grumbullimin dhe ruajtjen e informacionit.

Lista bibliografike

1. Ligji federal Federata Ruse“Për Informacionin, Informatizimin dhe Mbrojtjen e Informacionit” datë 27 korrik 2006 Nr. 149-FZ.

2. Levin A.Sh. Tutorial kompjuterik. - Shën Petersburg: Peter, 2006. - 655 f.

3. Romanova N.I. Bazat e informatikës. - Shën Petersburg: Politeknik, 2004. -224 f.

4. Simonovich S.V. Informatikë. Kursi bazë. - Shën Petersburg: Peter, 2008 - 640 f.

Pritet në Allbest.ru

Dokumente të ngjashme

Llojet e kompresimit të të dhënave: me humbje (me humbje) dhe pa humbje (pa humbje). Kompresim me tepricë minimale. Kodimi Shannon-Fano. Kontrollimi i programit për kompresimin e skedarëve bmp dhe xls. Zbatimi në Algoritmi Delphi Ngjeshjet e Shannon dhe Huffman.

punim afatshkurtër, shtuar 26.01.2011


Klasifikimi dhe karakteristikat kryesore të metodës së kompresimit të të dhënave. Llogaritja e raporteve të ngjeshjes dhe vlerësimi i efikasitetit të tyre. Algoritmet për metodat e kompresimit polinom, ekstrapolimi dhe interpolimi dhe krahasimi i tyre. Parashikimi linear optimal.

punim afatshkurtër, shtuar 17.03.2011


Arkivimi dhe kompresimi si metoda të ngjeshjes së imazhit. Algoritmet e kompresimit të të dhënave. Ndihmës, të cilat përdoren për të reduktuar madhësinë e skedarëve: ndryshim model ngjyrash imazhe, ndryshimi i rezolucionit të një skedari bitmap, rimostrim.

prezantim, shtuar 01/06/2014


Studimi i llojeve kryesore të programeve të arkivimit. Kompresimi i skedarëve gjatë arkivimit. Shkalla e kompresimit të skedarit. Vlerësimi i funksionalitetit të paketuesve më të njohur. Karakteristikat teknike të proceseve të kompresimit. Metodat e arkivimit pa humbje.

abstrakt, shtuar 12/05/2013


Zbulimi i qëllimit të kompresimit të skedarëve dhe përshkrimi i qëllimit të arkivuesve si programe që paketojnë dhe shpaketojnë skedarët në një arkiv për lehtësinë e transferimit dhe ruajtjes. Llojet kryesore të arkivuesve: skedari, programi, disku. Metoda e kompresimit pa humbje.

prezantim, shtuar 04/05/2011


Konceptet dhe metodat bazë të ngjeshjes së të dhënave. Konvertimi i informacionit të ruajtur në një skedar në një formë që redukton tepricën në paraqitjen e tij. Metodat e ngjeshjes statistikore dhe të fjalorit. Programet e arkivimit, tiparet kryesore të WinRAR.

punë kontrolli, shtuar 03/12/2011


Shqyrtim i shkurtër teoritë kryesore të kompresimit. Konceptet e ideve dhe zbatimi i tyre. Kompresimi i të dhënave duke përdorur transformimin Burrows-Wheeler. Algoritmi statik i Huffman. Algoritmi i kompresimit adaptiv lokal. Algoritmi Ziv-Lempel (Welch) dhe metoda Shannon-Fano.

punë praktike, shtuar 24.04.2014


Entropia dhe sasia e informacionit. Vlerësimi kombinator, probabilist dhe algoritmik i sasisë së informacionit. Modelimi dhe kodimi. Disa algoritme të kompresimit të të dhënave. Algoritmi kodimi aritmetik. Dërgimi dhe marrja në rritje.

punim afatshkurtër, shtuar 28.07.2009


Përdorimi i algoritmeve që ofrojnë një shkallë të lartë kompresimi për të rritur shpejtësinë e transmetimit të të dhënave përmes kanaleve të komunikimit. Veçoritë dhe metodat për gjetjen e zbërthimit të vlerave njëjës. Zhvillimi i një programi që zbaton kompresimin e imazhit duke përdorur kompresimin SVD.

tezë, shtuar 13.10.2015


Programe për krijimin e arkivave. Efikasiteti i kompresimit të të dhënave si karakteristika më e rëndësishme arkivues. Metodat themelore të ngjeshjes së të dhënave. Karakteristikat e programit për paketimin e teksteve dhe Programet WinRar. Shpaketimi i skedarëve, paketimi i skedarëve dhe dosjeve në një arkiv të përbashkët.

"Kompresimi i të dhënave"

Një tipar karakteristik i shumicës së llojeve të të dhënave është teprica e tyre. Shkalla 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 për të dhënat 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. Një shembull i sistemeve të kodimit mund të jenë gjuhët e zakonshme të komunikimit, të cilat nuk janë gjë tjetër veçse sisteme kodimi për konceptet dhe idetë për të shprehur mendimet. Kështu, është zbuluar se kodimi i të dhënave tekstuale duke përdorur gjuhën ruse jep një tepricë mesatare prej 20-25% më të madhe se kodimi i të dhënave të ngjashme duke përdorur gjuhën angleze.

Për njerëzit, teprica e të dhënave shpesh shoqërohet me cilësinë e informacionit, pasi teprica tenton të përmirësojë kuptueshmërinë dhe perceptimin e informacionit. Megjithatë, kur bëhet fjalë për ruajtjen dhe transmetimin e informacionit me anë të teknologjisë kompjuterike, teprica luan një rol negativ, pasi çon në një rritje të kostos së ruajtjes dhe transmetimit të informacionit. Ky problem bëhet veçanërisht urgjent në rastin e përpunimit të sasive të mëdha të informacionit me sasi të vogla të bartësve të të dhënave. Në këtë drejtim, problemi i reduktimit të tepricës ose ngjeshjes së të dhënave lind vazhdimisht. Nëse metodat e kompresimit të të dhënave aplikohen në skedarët e përfunduar, atëherë shpesh termi "arkivim i të dhënave" përdoret në vend të termit "kompresim i të dhënave", versioni i ngjeshur i të dhënave quhet Arkivi, dhe quhen mjetet softuerike që zbatojnë metodat e kompresimit arkivues.

Në varësi të objektit në të cilin ndodhen të dhënat që do të kompresohen, ekzistojnë:

Kompresimi (arkivimi) i skedarëve: përdoret për të zvogëluar madhësinë e skedarëve në përgatitje për transmetim nga kanalet e komunikimit ose për transport në media të jashtme me kapacitet të vogël;

Kompresimi i dosjeve (arkivimi): përdoret si një mjet për të reduktuar volumin e dosjeve përpara ruajtjes afatgjatë, për shembull, kur bëni kopje rezervë;

Kompresimi (ngjeshja) e disqeve: përdoret për të përmirësuar efikasitetin e përdorimit të hapësirës në disk duke kompresuar të dhënat gjatë shkrimit të tyre në një medium ruajtjeje (zakonisht me anë të një sistemi operativ).

Ka shumë algoritme praktike për kompresimin e të dhënave, por të gjithë bazohen në tre mënyra teorike për të reduktuar tepricën e të dhënave. Mënyra e parë është ndryshimi i përmbajtjes së të dhënave, e dyta është ndryshimi i strukturës së të dhënave dhe e treta është ndryshimi i strukturës dhe përmbajtjes së të dhënave në të njëjtën kohë.

Nëse përmbajtja e të dhënave ndryshon gjatë kompresimit të të dhënave, atëherë thirret metoda e kompresimit të pakthyeshme, d.m.th., kur rikthen (zhbllokon) të dhënat nga një arkiv, informacioni nuk restaurohet plotësisht. Metoda të tilla shpesh quhen metoda të kompresimit me humbje. Është e qartë se këto metoda mund të përdoren vetëm për llojet e të dhënave për të cilat humbja e një pjese të përmbajtjes nuk çon në një shtrembërim të konsiderueshëm të informacionit. Këto lloj të dhënash përfshijnë të dhëna video dhe audio, si dhe të dhëna grafike. Metodat e kompresimit të kontrolluara me humbje sigurojnë një raport shumë më të lartë kompresimi, por ato nuk mund të aplikohen në të dhënat e tekstit. Shembuj të formateve të kompresimit me humbje janë:

JPEG - për të dhëna grafike;

MPG - për të dhëna video;

MP3 - për të dhënat audio.

Nëse kompresimi i të dhënave ndryshon vetëm strukturën e të dhënave, atëherë thirret metoda e kompresimit e kthyeshme. Në këtë rast, ju mund të rivendosni plotësisht informacionin nga arkivi. Metodat e kompresimit të kthyeshëm mund të aplikohen për çdo lloj të dhënash, por ato ofrojnë një raport më të ulët të kompresimit sesa metodat e kompresimit jo të kthyeshëm. Shembuj të formateve të kompresimit pa humbje:

GIF, TIFF - për të dhëna grafike;

AVI - për të dhënat video;

ZIP, ARJ, RAR, CAB, LH - për lloje arbitrare të të dhënave.

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 algoritme teorike:

Algoritmi RLE (Run Length Encoding);

algoritmet e grupit KWE (KeyWord Encoding);

Algoritmi Huffman.

Algoritmi RLE

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 zëvendësimi i tij 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. Raporti i kompresimit, i cili karakterizon shkallën e ngjeshjes, mund të llogaritet me formulën:

ku Vx është sasia e memories së nevojshme për të ruajtur sekuencën e të dhënave dalëse (rezultuese), Vn është sekuenca e të dhënave hyrëse.

Sa më e vogël të jetë vlera e raportit të ngjeshjes, aq metodë më efikase ngjeshja. Ë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).

Algoritmet e grupit KWE

Algoritmi i ngjeshjes së fjalëve kyçe bazohet në parimin e kodimit të njësive leksikore sipas grupeve të bajteve me gjatësi fikse. Një shembull i një njësie leksikore do të ishte një fjalë e zakonshme. Në praktikë, për rolin e njësive leksikore zgjidhen sekuenca të përsëritura karakteresh, të cilat kodohen nga një zinxhir karakteresh (kodi) me gjatësi më të vogël. Rezultati i kodimit vendoset në një tabelë, duke formuar një të ashtuquajtur fjalor.

Ka mjaft implementime të këtij algoritmi, ndër të cilët më të zakonshmet janë algoritmi Lempel-Ziva (algoritmi LZ) dhe modifikimi i tij, algoritmi Lempel-Ziva-Welch (algoritmi LZW). Fjalor në këtë algoritëmështë një listë potencialisht e pafund frazash. Algoritmi fillon me një fjalor pothuajse bosh që përmban vetëm një varg të koduar, të ashtuquajturin varg NULL. Kur lexoni karakterin tjetër të sekuencës së të dhënave hyrëse, ai shtohet në rreshtin aktual. Procesi vazhdon derisa rreshti aktual të përputhet me disa fraza nga fjalori. Por herët a vonë rreshti aktual pushon së korresponduari me çdo frazë fjalori. Në pikën ku rreshti aktual është përputhja e fundit e fjalorit plus karakteri i mesazhit të sapo lexuar, koduesi nxjerr një kod që përbëhet nga indeksi i përputhjes, i ndjekur nga karakteri që ka thyer përputhjen e vargut. Një frazë e re, e përbërë nga indeksi i përputhjes i ndjekur nga një karakter, shtohet në fjalor. Herën tjetër që kjo frazë shfaqet në një mesazh, mund të përdoret për të ndërtuar një frazë më të gjatë, e cila rrit sasinë e ngjeshjes së informacionit.

Algoritmi LZW është ndërtuar rreth një tabele frazash (fjalori) që zëvendëson vargjet e karaktereve të mesazhit të ngjeshur në kode me gjatësi fikse. Tabela ka të ashtuquajturën veti të shikimit përpara, domethënë, për secilën frazë në fjalor, e përbërë nga disa fraza w dhe simboli K, fraza w futet gjithashtu në fjalor. Nëse të gjitha pjesët e fjalorit janë mbushur plotësisht, kodimi pushon së qeni përshtatës (kodimi ndodh bazuar në frazat që ekzistojnë tashmë në fjalor).

Algoritmet e kompresimit të këtij grupi janë më efikase për të dhëna të mëdha teksti dhe joefektive për skedarë të vegjël (për shkak të nevojës për të ruajtur fjalorin).

Algoritmi Huffman

Algoritmi Huffman bazohet në idenë e kodimit sipas grupeve të biteve. Së pari, kryhet një analizë e frekuencës së sekuencës së të dhënave hyrëse, domethënë përcaktohet 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.

Le të jepet teksti, në të cilin "A" burva hyn 10 herë, shkronja "B" - 8 herë, "C" - 6 herë, "D" - 5 herë, "E" dhe "F" - 4 herë. secili. Pastaj një nga opsionet e mundshme të kodimit për algoritmin Huffman është dhënë në Tabelën 1.

Tabela 1.

	Frekuenca e shfaqjes	kod bit

Siç shihet nga tabela 1, madhësia e tekstit hyrës para ngjeshjes është 37 bit, ndërsa pas ngjeshjes është 93 bit, pra rreth 12 bajt (duke përjashtuar gjatësinë e fjalorit). Raporti i kompresimit është 32%. Algoritmi Huffman është universal, mund të përdoret për të kompresuar të dhënat e çdo lloji, por është i paefektshëm për skedarë të vegjël (për shkak të nevojës për të ruajtur fjalorin).

Në praktikë, softueri i kompresimit të të dhënave sintetizon këto tre algoritme "të pastra", pasi efektiviteti i tyre varet nga lloji dhe sasia e të dhënave. Tabela 2 liston formatet e zakonshme të kompresimit dhe programet e tyre përkatëse të arkivimit të përdorura në praktikë.

Tabela 2.

Formati i kompresimit	Sistemi operativ MS DOS		Sistemi operativ Windows
	Programi i arkivimit	Zhzip programin	Programi i arkivimit	Zhzip programin

Për më tepër, arkivuesit modernë i ofrojnë përdoruesit një gamë të plotë shërbimesh për të punuar me arkivat, kryesore prej të cilave janë:

krijimi i një arkivi të ri;

shtimi i skedarëve në një arkiv ekzistues;

zbërthimi i skedarëve nga arkivi;

krijimi i arkivave vetënxjerrëse (arkivë vetënxjerrëse);

krijimi i arkivave të shpërndara me madhësi fikse për mediat me kapacitet të vogël;

mbrojtja e arkivave me fjalëkalime nga aksesi i paautorizuar;

shikimi i përmbajtjes së skedarëve të formateve të ndryshme pa e shpaketuar më parë;

kërkoni për skedarë dhe të dhëna brenda arkivit;

kontrollimi i viruseve në arkiv për shpaketim;

përzgjedhja dhe rregullimi i raportit të ngjeshjes.

pyetjet e testit

1. Cilët faktorë ndikojnë në shkallën e tepricës së të dhënave? 2. Çfarë është një arkiv? Cilat mjete softuerike quhen arkivues? 3. Pse metodat e kompresimit që ndryshojnë përmbajtjen e të dhënave quhen të pakthyeshme? 4. Jepni shembuj të formateve të kompresimit me humbje. 5. Cili është avantazhi i metodave të kompresimit të kthyeshëm ndaj atyre të pakthyeshme? Po në lidhje me disavantazhin? 6. Cila është marrëdhënia ndërmjet raportit të ngjeshjes dhe efikasitetit të metodës së ngjeshjes? 7. Cila është ideja kryesore e algoritmit RLE? 8. Cila është ideja kryesore e algoritmeve të grupit KWE? 9. Cila është ideja kryesore e algoritmit Huffman? 10. Çfarë programesh arkivimi dini? Përshkruani ato shkurtimisht.

Informatikë. Kursi bazë. / Ed. S.V.Simonovich. - Shën Petersburg, 2000

A.P. Miklyaev, Manual për përdoruesit e IBM PC, botimi i 3-të M.:, "Solon-R", 2000, 720 f.

Simonovich S.V., Evseev G.A., Murakhovsky V.I. Keni blerë një kompjuter: Udhëzuesi i plotë për fillestarët për pyetje dhe përgjigje. - M.: LIBRI AST-PRESS; Inforkom-Press, 2001. - 544 f.: ill. (1000 këshilla).

Kovtanyuk Yu.S., Solovyan S.V. Tutorial për punën në Kompjuter personal- K.: Junior, 2001.- 560., ill.

Unë dhe mbikëqyrësi im po përgatisim një monografi të shkurtër mbi përpunimin e imazhit. Vendosa të paraqes në gjykatën e komunitetit habra një kapitull mbi algoritmet e kompresimit të imazhit. Meqenëse është e vështirë të vendosësh një kapitull të tërë brenda një postimi, vendosa ta ndaj në tre postime:
1. Metodat e kompresimit të të dhënave;
2. Kompresim i imazhit pa humbje;
3. Kompresimi i imazhit me humbje.
Më poshtë mund të lexoni postimin e parë të serisë.

Për momentin, ekziston një numër i madh i algoritmeve të kompresimit pa humbje, të cilat mund të ndahen me kusht në dy grupe të mëdha:
1. Algoritmet e transmetimit dhe fjalorit. Ky grup përfshin algoritme të familjeve RLE (kodimi me gjatësi të plotë), LZ*, etj. Një tipar i të gjitha algoritmeve të këtij grupi është se kodimi nuk përdor informacion për frekuencën e simboleve në mesazh, por informacion për sekuencat. hasur më herët.
2. Algoritmet për ngjeshjen statistikore (entropike). Ky grup algoritmesh ngjesh informacionin duke përdorur frekuencat e pabarabarta me të cilat shfaqen karaktere të ndryshme në një mesazh. Algoritmet e këtij grupi përfshijnë algoritme aritmetike dhe të kodimit të parashtesave (duke përdorur Shannon-Fanno, Huffman, pemë sekante).
NË grup i veçantë mund të dallohen algoritmet e transformimit të informacionit. Algoritmet e këtij grupi nuk e kompresojnë drejtpërdrejt informacionin, por aplikimi i tyre thjeshton shumë kompresimin e mëtejshëm duke përdorur algoritmet e transmetimit, fjalorit dhe entropisë.

Algoritmet e rrjedhës dhe fjalorit

Kodimi i gjatësisë së ekzekutimit

Run-Length Encoding (RLE) është një nga algoritmet më të thjeshtë dhe më të zakonshëm të kompresimit të të dhënave. Në këtë algoritëm, një sekuencë karakteresh të përsëritura zëvendësohet nga një karakter dhe nga numri i herëve që përsëritet.
Për shembull, vargu "AAAAA", i cili kërkon 5 bajt për të ruajtur (duke supozuar se një bajt është ndarë për ruajtjen e një karakteri), mund të zëvendësohet me "5A", i përbërë nga dy bajtë. Natyrisht, ky algoritëm është më efikas, sa më e gjatë të jetë seria e përsëritjeve.

Disavantazhi kryesor i këtij algoritmi është efikasiteti i tij jashtëzakonisht i ulët në sekuencat e karaktereve që nuk përsëriten. Për shembull, nëse marrim parasysh sekuencën "ABABAB" (6 bytes), atëherë pas aplikimit të algoritmit RLE, ai do të kthehet në "1A1B1A1B1A1B" (12 bytes). Ka metoda të ndryshme për të zgjidhur problemin e karaktereve që nuk përsëriten.

nga më së shumti metodë e thjeshtëështë modifikimi i mëposhtëm: bajt që kodon numrin e përsëritjeve duhet të ruajë informacion jo vetëm për numrin e përsëritjeve, por edhe për praninë e tyre. Nëse biti i parë është 1, atëherë 7 bitët e ardhshëm tregojnë numrin e përsëritjeve të karakterit përkatës, dhe nëse biti i parë është 0, atëherë 7 bitët e ardhshëm tregojnë numrin e karaktereve që duhen marrë pa përsëritje. Nëse kodojmë "ABABAB" duke përdorur këtë modifikim, marrim "-6ABABAB" (7 bytes). Natyrisht, teknika e propozuar mund të përmirësojë ndjeshëm efikasitetin e algoritmit RLE në sekuencat e karaktereve që nuk përsëriten. Zbatimi i qasjes së propozuar tregohet në Listën 1:

1. lloji
2. funksioni RLEEncode(InMsg: ShortString) : TRLEEncodedString;
3. MatchFl: boolean ;
4. MatchCount: shortint ;
5. EncodedString: TRLEEncodedString;
6. N, i: bytes;
7. fillojnë
8. N:=0;
9. SetLength(String i koduar, 2 * gjatësi (InMsg) );
10. ndërsa gjatësia(InMsg) >= 1 do
11. fillojnë
12. MatchFl : = (gjatësia(InMsg) > 1 ) dhe (InMsg[ 1 ] = InMsg[ 2 ] ) ;
13. Numri i ndeshjeve:= 1;
14. ndërsa (MatchCount<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. MatchCount: = MatchCount + 1;
16. nëse MatchFl atëherë
17. fillojnë
18. N: = N + 2;
19. EncodedString[ N - 2 ] : = MatchCount + 128 ;
20. EncodedString[ N - 1 ] : = ord (InMsg[ 1 ] ) ;
21. tjetër
22. fillojnë
23. nëse MatchCount<>gjatësia (InMsg) atëherë
24. MatchCount: = MatchCount - 1;
25. N := N + 1 + Numri i ndeshjeve;
26. EncodedString[ N - 1 - MatchCount] : = - MatchCount + 128 ;
27. për i := 1 për të bërë MatchCount
28. EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] ) ;
29. fundi ;
30. fshij(InMsg, 1, MatchCount) ;
31. fundi ;
32. SetLength(EncodedString, N);
33. RLEcode := EncodedString;
34. fundi ;

Dekodimi i një mesazhi të ngjeshur është shumë i thjeshtë dhe zbret në një kalim të vetëm përmes mesazhit të ngjeshur, shihni Listën 2:

1. lloji
2. TRLEEncodedString = grup bajtash;
3. funksioni RLEDecode(InMsg: TRLEEncodedString) : ShortString;
4. RepeatCount: shortint ;
5. i, j: fjalë;
6. OutMsg: ShortString;
7. fillojnë
8. OutMsg := "" ;
9. i:=0;
10. nderkohe une< length(InMsg) do
11. fillojnë
12. Numri i Përsëritjes: = InMsg[i] - 128;
13. i: = i + 1;
14. nëse RepeatCount< 0 then
15. fillojnë
16. RepeatCount := abs(RepeatCount) ;
17. për j : = i në i + RepeatCount - 1 do
18. OutMsg := OutMsg + chr (InMsg[ j] ) ;
19. i := i + Numri i Përsëritjes;
20. tjetër
21. fillojnë
22. për j := 1 në RepeatCount bëni
23. OutMsg := OutMsg + chr (InMsg[ i] ) ;
24. i: = i + 1;
25. fundi ;
26. fundi ;
27. RLDecode := OutMsg;
28. fundi ;

Metoda e dytë për të rritur efikasitetin e algoritmit RLE është përdorimi i algoritmeve të transformimit të informacionit që nuk i kompresojnë drejtpërdrejt të dhënat, por i konvertojnë ato në një formë që është më e përshtatshme për komprimim. Si shembull i një algoritmi të tillë, ne do të shqyrtojmë një ndërrim BWT të emërtuar sipas shpikësve të transformimit Burrows-Wheeler. Ky permutacion nuk i ndryshon vetë karakteret, por ndryshon vetëm rendin e tyre në varg, ndërsa nënvargjet e përsëritura, pas aplikimit të permutacionit, mblidhen në grupe të dendura që kompresohen shumë më mirë duke përdorur algoritmin RLE. Transformimi i drejtpërdrejtë BWT zbret në një sekuencë të hapave të mëposhtëm:
1. Shtimi në vargun burimor të një karakteri të veçantë fundor që nuk shfaqet askund tjetër;
2. Marrja e të gjitha permutacioneve ciklike të vargut origjinal;
3. Renditja e vargjeve të marra sipas rendit leksikografik;
4. Kthimi i kolonës së fundit të matricës që rezulton.
Zbatimi i këtij algoritmi tregohet në Listën 3.

1. konst
2. EOMsg="|" ;
3. funksioni BWTEcode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. LastChar: ANSIChar;
6. N, i: fjalë;
7. fillojnë
8. InMsg := InMsg + EOMsg;
9. N := gjatësia(InMsg) ;
10. ShiftTable[ 1 ] := InMsg;
11. për i := 2 deri në N bëj
12. fillojnë
13. LastChar := InMsg[N] ;
14. InMsg: = LastChar + kopje(InMsg, 1, N - 1);
15. ShiftTable[i] := InMsg;
16. fundi ;
17. Rendit (ShiftTable) ;
18. OutMsg := "" ;
19. për i := 1 deri në N bëj
20. OutMsg : = OutMsg + ShiftTable[ i] [N] ;
21. BWTEcode := OutMsg;
22. fundi ;

Mënyra më e lehtë për të shpjeguar këtë transformim është me një shembull konkret. Le të marrim vargun "pineapple" dhe të biem dakord që simboli "|" të jetë fundi i vargut. Të gjitha permutacionet ciklike të këtij vargu dhe rezultati i renditjes leksikografike të tyre janë dhënë në tabelë. një.

ato. rezultati i konvertimit të drejtpërdrejtë do të jetë vargu "|NNAAAC". Është e lehtë të shihet se ky varg është shumë më i mirë se ai origjinal, ai është i ngjeshur nga algoritmi RLE, sepse ai përmban vargje të gjata të shkronjave të përsëritura.
Një efekt i ngjashëm mund të arrihet me transformime të tjera, por avantazhi i transformimit BWT është se ai është i kthyeshëm, megjithatë, transformimi i kundërt është më i ndërlikuar se ai i drejtpërdrejtë. Për të rivendosur vargun origjinal, duhet të kryeni hapat e mëposhtëm:
Krijo një matricë boshe me madhësi n*n, ku n është numri i karaktereve në mesazhin e koduar;
Plotësoni kolonën bosh djathtas me mesazhin e koduar;
Rendit rreshtat e tabelave sipas rendit leksikografik;
Përsëritni hapat 2-3 për sa kohë që ka kolona boshe;
Ktheni vargun që përfundon me një karakter fundor.

Zbatimi i transformimit të anasjelltë nuk është i vështirë në shikim të parë, dhe një nga zbatimet tregohet në Listën 4.

1. konst
2. EOMsg="|" ;
3. funksioni BWTDecode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. ShiftTable: grup i ShortString;
6. N, i, j: fjalë;
7. fillojnë
8. OutMsg := "" ;
9. N := gjatësia(InMsg) ;
10. SetLength (ShiftTable, N + 1);
11. për i := 0 deri në N bëj
12. ShiftTable[i] := "" ;
13. për i := 1 deri në N bëj
14. fillojnë
15. për j := 1 deri në N bëj
16. ShiftTable[ j] : = InMsg[ j] + ShiftTable[ j] ;
17. Rendit (ShiftTable) ;
18. fundi ;
19. për i := 1 deri në N bëj
20. nëse ShiftTable[ i] [N] = EOMsg atëherë
21. OutMsg := ShiftTable[i] ;
22. fshij(OutMsg, N, 1);
23. BWTDecode := OutMsg;
24. fundi ;

Por në praktikë, efikasiteti varet nga algoritmi i përzgjedhur i renditjes. Algoritmet e parëndësishme me kompleksitet kuadratik padyshim do të kenë një ndikim jashtëzakonisht negativ në performancën, prandaj rekomandohet përdorimi i algoritmeve efikase.

Pas renditjes së tabelës së marrë në hapin e shtatë, është e nevojshme të zgjidhni një rresht nga tabela që përfundon me simbolin "|". Është e lehtë të shihet se kjo është e vetmja linjë. Se. ne kemi shqyrtuar transformimin BWT në një shembull specifik.

Duke përmbledhur, mund të themi se avantazhi kryesor i grupit të algoritmit RLE është thjeshtësia dhe shpejtësia e funksionimit (përfshirë shpejtësinë e dekodimit), dhe disavantazhi kryesor është joefikasiteti në grupet e karaktereve që nuk përsëriten. Përdorimi i permutacioneve speciale rrit efikasitetin e algoritmit, por gjithashtu rrit shumë kohën e funksionimit (veçanërisht dekodimin).

Kompresimi i fjalorit (algoritmet LZ)

Grupi i algoritmeve të fjalorit, ndryshe nga algoritmet e grupit RLE, kodon jo numrin e përsëritjeve të karaktereve, por sekuencat e karaktereve të hasura më herët. Gjatë funksionimit të algoritmeve në shqyrtim, në mënyrë dinamike krijohet një tabelë me një listë të sekuencave të hasura tashmë dhe kodet e tyre përkatëse. Kjo tabelë shpesh quhet fjalor, dhe grupi përkatës i algoritmeve quhet fjalor.

Versioni më i thjeshtë i algoritmit të fjalorit përshkruhet më poshtë:
Inicializoni fjalorin me të gjitha karakteret që gjenden në vargun e hyrjes;
Gjeni në fjalor sekuencën më të gjatë (S) që përputhet me fillimin e mesazhit të koduar;
Lëshoni kodin e sekuencës së gjetur dhe hiqni atë nga fillimi i mesazhit të koduar;
Nëse fundi i mesazhit nuk arrihet, lexoni karakterin tjetër dhe shtoni Sc në fjalor, shkoni në hapin 2. Përndryshe, dilni.

Për shembull, një fjalor i sapo inicializuar për frazën "CUCKOOCOOKOOHOOD" është paraqitur në tabelë. 3:

Gjatë procesit të kompresimit, fjalori do të plotësohet nga sekuencat e hasura në mesazh. Procesi i përditësimit të fjalorit është dhënë në tabelë. 4.

Gjatë përshkrimit të algoritmit, përshkrimi i situatës kur fjalori është plotësuar plotësisht u hoq qëllimisht. Në varësi të variantit të algoritmit, është e mundur një sjellje e ndryshme: pastrimi i plotë ose i pjesshëm i fjalorit, përfundimi i plotësimit të fjalorit ose zgjerimi i fjalorit me një rritje përkatëse të kapacitetit të kodit. Secila prej këtyre qasjeve ka disavantazhe të caktuara. Për shembull, ndalimi i rimbushjes së fjalorit mund të çojë në një situatë ku fjalori ruan sekuencat që ndodhin në fillim të vargut të ngjeshur, por që nuk ndodhin më vonë. Në të njëjtën kohë, pastrimi i fjalorit mund të rezultojë në heqjen e sekuencave të shpeshta. Shumica e zbatimeve të përdorura, kur plotësojnë fjalorin, fillojnë të gjurmojnë shkallën e ngjeshjes dhe kur ajo ulet nën një nivel të caktuar, fjalori rindërtohet. Më pas, ne do të shqyrtojmë zbatimin më të thjeshtë që ndalon rimbushjen e fjalorit kur ai të jetë i plotë.

Së pari, le të përcaktojmë një fjalor si një rekord që ruan jo vetëm nënvargjet e hasura, por edhe numrin e nënvargjeve të ruajtura në fjalor:

Nënsekuencat e hasura më parë ruhen në vargun Words, dhe kodi i tyre është numrat e nënsekuencave në këtë grup.
Ne gjithashtu përcaktojmë kërkimin e fjalorit dhe shtojmë në funksionet e fjalorit:

1. konst
2. MAX_DICT_LENGTH = 256 ;
3. funksioni FindInDict(D: TDictionary; str: ShortString) : integer ;
4. r: numër i plotë
5. i: numër i plotë;
6. fl: boolean;
7. fillojnë
8. r := - 1;
9. nëse D. WordCount > 0 atëherë
10. fillojnë
11. i := D.Numri i fjalëve;
12. fl := false ;
13. ndërsa (jo fl) dhe (i >= 0 ) bëjnë
14. fillojnë
15. i := i - 1 ;
16. fl:=D.Fjalë[i]=str;
17. fundi ;
18. fundi ;
19. nëse fl atëherë
20. r :=i;
21. FindInDict := r;
22. fundi ;
23. procedura AddToDict(var D: TDictionary; str: ShortString) ;
24. fillojnë
25. nëse D.WordCount< MAX_DICT_LENGTH then
26. fillojnë
27. D.WordCount := D.WordCount + 1 ;
28. SetLength(D. Words, D. WordCount);
29. D. Fjalët [ D. Numri i fjalëve - 1 ] : = str;
30. fundi ;
31. fundi ;

Duke përdorur këto funksione, procesi i kodimit sipas algoritmit të përshkruar mund të zbatohet si më poshtë:

1. funksioni LZWEncode(InMsg: ShortString) : TEncodedString;
2. OutMsg: TEncodedString;
3. tmpstr: ShortString;
4. D: TFjalori;
5. i, N: bytes;
6. fillojnë
7. SetLength(OutMsg, gjatësia(InMsg) );
8. N:=0;
9. InitDict(D) ;
10. ndërsa gjatësia(InMsg) > 0 do
11. fillojnë
12. tmpstr := InMsg[ 1 ] ;
13. ndërsa (FindInDict(D, tmpstr) >= 0 ) dhe (gjatësia(InMsg) > gjatësia(tmpstr) ) bëjnë
14. tmpstr : = tmpstr + InMsg[ gjatësia(tmpstr) + 1 ] ;
15. nëse FindInDict(D, tmpstr)< 0 then
16. fshij(tmpstr, gjatësi(tmpstr) , 1 );
17. OutMsg[N] := FindInDict(D, tmpstr) ;
18. N: = N + 1;
19. delete(InMsg, 1, gjatësia(tmpstr) );
20. nëse gjatësia(InMsg) > 0 atëherë
21. AddToDict(D, tmpstr + InMsg[ 1 ] );
22. fundi ;
23. SetLength(OutMsg, N);
24. LZWEkodi := OutMsg;
25. fundi ;

Rezultati i kodimit do të jetë numri i fjalëve në fjalor.
Procesi i dekodimit reduktohet në deshifrimin e drejtpërdrejtë të kodeve, dhe nuk ka nevojë të transferohet fjalori i krijuar, mjafton që fjalori të inicializohet gjatë dekodimit në të njëjtën mënyrë si gjatë kodimit. Më pas fjalori do të rikthehet plotësisht drejtpërdrejt në procesin e dekodimit duke bashkuar nërenditjen e mëparshme dhe karakterin aktual.

Problemi i vetëm është i mundur në situatën e mëposhtme: kur është e nevojshme të deshifroni një nënsekuencë që nuk është ende në fjalor. Është e lehtë të shihet se kjo është e mundur vetëm në rastin kur është e nevojshme të nxirret një nënvarg që duhet shtuar në hapin aktual. Dhe kjo do të thotë që nënvargu plotëson modelin cSc, d.m.th. fillon dhe mbaron me të njëjtin karakter. Në këtë rast, cS është nënvargu i shtuar në hapin e mëparshëm. Situata e konsideruar është e vetmja kur është e nevojshme të deshifrohet një varg që nuk është shtuar ende. Duke pasur parasysh sa më sipër, ne mund të ofrojmë opsionin e mëposhtëm për dekodimin e një vargu të ngjeshur:

1. funksioni LZWDecode(InMsg: TEncodedString) : ShortString;
2. D: TFjalori;
3. OutMsg, tmpstr: ShortString;
4. i: bajt;
5. fillojnë
6. OutMsg := "" ;
7. tmpstr := "" ;
8. InitDict(D) ;
9. për i := 0 në gjatësi(InMsg) - 1 do
10. fillojnë
11. if InMsg[i] >= D.WordCount atëherë
12. tmpstr : = D. Fjalët [ InMsg[ i - 1 ] ] + D. Fjalët [ InMsg[ i - 1 ] ] [ 1 ]
13. tjetër
14. tmpstr := D. Fjalët [ InMsg[ i] ] ;
15. OutMsg := OutMsg + tmpstr;
16. nëse i > 0 atëherë
17. AddToDict(D, D. Fjalët [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] );
18. fundi ;
19. LZWDecode := OutMsg;
20. fundi ;

Përparësitë e algoritmeve të fjalorit përfshijnë efikasitetin më të madh të kompresimit në krahasim me RLE. Megjithatë, duhet kuptuar se përdorim real këto algoritme shoqërohen me disa vështirësi në zbatim.

Kodimi i entropisë

Kodimi me Shannon-Fano Trees

Algoritmi Shannon-Fano është një nga algoritmet e para të zhvilluara të kompresimit. Algoritmi bazohet në idenë e përfaqësimit të karaktereve më të shpeshta me kode më të shkurtra. Në këtë rast, kodet e marra duke përdorur algoritmin Shannon-Fano kanë vetinë e prefiksit: d.m.th. asnjë kod nuk është fillimi i ndonjë kodi tjetër. Vetia e prefiksit siguron që kodimi të jetë një-për-një. Algoritmi për ndërtimin e kodeve Shannon-Fano është paraqitur më poshtë:
1. Ndani alfabetin në dy pjesë, probabilitetet totale të simboleve në të cilat janë sa më afër njëra-tjetrës.
2. Shtoni 0 në kodin prefiks të pjesës së parë të simboleve, shtoni 1 në kodin e parashtesës së pjesës së dytë të simboleve.
3. Për secilën pjesë (që ka të paktën dy karaktere), kryeni në mënyrë rekursive hapat 1-3.
Megjithë thjeshtësinë e tij relative, algoritmi Shannon-Fano nuk është pa të meta, më i rëndësishmi prej të cilave është kodimi jo optimal. Megjithëse ndarja në çdo hap është optimale, algoritmi nuk garanton rezultatin optimal në tërësi. Konsideroni, për shembull, rreshti tjetër: "AAAABVGDEZH". Pema përkatëse Shannon-Fano dhe kodet që rrjedhin prej saj janë paraqitur në Fig. një:

Pa kodim, mesazhi do të marrë 40 bit (me kusht që çdo karakter të jetë i koduar me 4 bit), dhe duke përdorur algoritmin Shannon-Fano 4*2+2+4+4+3+3+3=27 bit. Vëllimi i mesazhit u ul me 32.5%, por më poshtë do të tregohet se ky rezultat mund të përmirësohet ndjeshëm.

Kodimi me Pemët Huffman

Algoritmi i kodimit Huffman, i zhvilluar disa vite pas algoritmit Shannon-Fano, ka gjithashtu vetinë e prefiksit dhe, përveç kësaj, tepricën minimale të provuar, kjo është arsyeja e shpërndarjes jashtëzakonisht të gjerë të tij. Për të marrë kodet Huffman, përdoret algoritmi i mëposhtëm:
1. Të gjithë karakteret e alfabetit paraqiten si nyje të lira, ndërsa pesha e nyjës është proporcionale me frekuencën e karakterit në mesazh;
2. Nga grupi i nyjeve të lira zgjidhen dy nyje me peshë minimale dhe krijohet një nyje e re (mëmë) me peshë të barabartë me shumën e peshave të nyjeve të zgjedhura;
3. Nyjet e përzgjedhura hiqen nga lista e lirë dhe nyja mëmë e krijuar në bazë të tyre shtohet në këtë listë;
4. Hapat 2-3 përsëriten derisa të ketë më shumë se një nyje në listën e lirë;
5. Në bazë të pemës së ndërtuar, çdo karakteri të alfabetit i caktohet një kod prefiks;
6. Mesazhi është i koduar me kodet e marra.

Konsideroni të njëjtin shembull si në rastin e algoritmit Shannon-Fano. Pema Huffman dhe kodet e marra për mesazhin "AAAABVGDEZH" janë paraqitur në Fig. 2:

Është e lehtë të llogaritet se madhësia e mesazhit të koduar do të jetë 26 bit, që është më pak se në algoritmin Shannon-Fano. Më vete, duhet të theksohet se për shkak të popullaritetit të algoritmit Huffman, për momentin ka shumë opsione për kodimin Huffman, përfshirë kodimin adaptiv, i cili nuk kërkon transmetimin e frekuencave të simboleve.
Ndër të metat e algoritmit Huffman, një pjesë e rëndësishme janë problemet që lidhen me kompleksitetin e zbatimit. Përdorimi i ndryshoreve reale për të ruajtur frekuencat e simboleve shoqërohet me një humbje të saktësisë, prandaj, në praktikë, shpesh përdoren variabla me numër të plotë, por, meqë pesha e nyjeve mëmë po rritet vazhdimisht, herët a vonë ndodh një tejmbushje. Kështu, megjithë thjeshtësinë e algoritmit, zbatimi i saktë i tij mund të shkaktojë ende disa vështirësi, veçanërisht për alfabetet e mëdha.

Kodimi me pemë sekante

Kodimi duke përdorur funksione sekante është një algoritëm i zhvilluar nga autorët që lejon marrjen e kodeve të prefiksit. Algoritmi bazohet në idenë e ndërtimit të një peme, secila nyje e së cilës përmban një funksion sekant. Për të përshkruar më në detaje algoritmin, është e nevojshme të prezantohen disa përkufizime.
Një fjalë është një sekuencë e renditur prej m bit (numri m quhet gjatësia e fjalës).
Literali sekant është një çift me vlerë bit. Për shembull, literali (4,1) do të thotë se 4 bit të fjalës duhet të jenë të barabarta me 1. Nëse kushti i fjalëpërfjalës është i vërtetë, atëherë literali konsiderohet i vërtetë, përndryshe është i gabuar.
Një sekant k-bitësh është një grup k literalësh. Nëse të gjitha fjalët e drejta janë të vërteta, atëherë vetë funksioni sekant është i vërtetë, përndryshe është i rremë.

Pema është ndërtuar në mënyrë që çdo nyje e ndan alfabetin në pjesët më të afërta të mundshme. Në Fig. 3 tregon një shembull të një peme sekante:

Pema e sekantit funksionon në rast i përgjithshëm nuk garanton kodim optimal, por ofron jashtëzakonisht shpejtësi e lartë puna për shkak të thjeshtësisë së funksionimit në nyje.

Kodimi aritmetik

Kodimi aritmetik është një nga më mënyra efektive ngjeshja e informacionit. Ndryshe nga algoritmi Huffman, kodimi aritmetik lejon që mesazhet të kodohen me një entropi më të vogël se 1 bit për simbol. Sepse shumica e algoritmeve të kodimit aritmetik mbrohen nga patenta, vetëm idetë kryesore do të përshkruhen më poshtë.
Le të supozojmë se në alfabetin e përdorur ka N karaktere a_1,…,a_N, me frekuenca p_1,…,p_N, përkatësisht. Atëherë algoritmi i kodimit aritmetik do të duket kështu:
Si një gjysmë interval pune, merrni )