Gennemgang af datakomprimeringsmetoder. Datakomprimering

"Datakomprimering"

Et karakteristisk træk ved de fleste datatyper er deres redundans. Graden af dataredundans afhænger af typen af data. For eksempel er graden af redundans for videodata flere gange større end for grafiske data, og graden af redundans af grafiske data er til gengæld større end redundansgraden af tekstdata. En anden faktor, der påvirker graden af redundans, er det anvendte kodesystem. Et eksempel på kodningssystemer ville være almindelige kommunikationssprog, som ikke er andet end systemer til kodning af begreber og ideer til at udtrykke tanker. Det er således fastslået, at indkodning af tekstdata ved brug af det russiske sprog i gennemsnit giver en redundans, der er 20-25 % større end indkodning af tilsvarende data ved brug af det engelske sprog.

For mennesker er dataredundans ofte forbundet med informationskvalitet, da redundans har en tendens til at forbedre forståeligheden og opfattelsen af information. Men når det kommer til lagring og transmission af information ved hjælp af computerteknologi, spiller redundans en negativ rolle, da det fører til en stigning i omkostningerne ved lagring og transmission af information. Dette problem bliver især relevant i tilfælde af behandling af enorme mængder af information med ubetydelige mængder lagringsmedier. I denne henseende opstår problemet med at reducere redundans eller datakomprimering konstant. Hvis datakomprimeringsmetoder anvendes på færdige filer, bruges ofte i stedet for udtrykket "datakomprimering" udtrykket "dataarkivering"; den komprimerede version af dataene kaldes arkiv, A software, som implementere komprimeringsmetoder kaldes arkivarer.

Afhængigt af objektet, hvori de data, der skal komprimeres, er placeret:

Komprimering (arkivering) af filer: bruges til at reducere størrelsen af filer, når de forberedes til transmission via kommunikationskanaler eller til transport på eksterne medier med lille kapacitet;

Mappekomprimering (arkivering): bruges som et middel til at reducere mængden af mapper før langtidslagring, f.eks. backup;

Diskkomprimering (komprimering): bruges til at øge effektiviteten ved at bruge diskplads ved at komprimere data, når du skriver dem til et lagermedie (normalt ved hjælp af operativsystemet).

Der er mange praktiske datakomprimeringsalgoritmer, men de er alle baseret på tre teoretiske måder at reducere dataredundans på. Den første måde er at ændre indholdet af dataene, den anden er at ændre strukturen af dataene, og den tredje er at ændre både strukturen og indholdet af dataene på samme tid.

Hvis datakomprimering ændrer indholdet, kaldes komprimeringsmetoden irreversible, det vil sige, at når der gendannes (arkiveres) data fra et arkiv, gendannes informationen ikke fuldstændigt. Sådanne metoder kaldes ofte tabskontrollerede kompressionsmetoder. Det er klart, at disse metoder kun kan anvendes til datatyper, hvor tab af en del af indholdet ikke fører til væsentlig forvrængning af information. Disse typer data omfatter video-, lyd- og grafikdata. Tabskontrollerede komprimeringsmetoder giver væsentligt højere komprimeringsrater, men kan ikke anvendes på tekstdata. Eksempler på tabsgivende komprimeringsformater omfatter:

JPEG - til grafiske data;

MPG - til videodata;

MP3 - til lyddata.

Hvis datakomprimering kun ændrer datastrukturen, kaldes komprimeringsmetoden reversibel. I dette tilfælde er det muligt at gendanne oplysningerne fuldstændigt fra arkivet. Reversible komprimeringsmetoder kan anvendes på enhver type data, men de giver mindre komprimering end irreversible komprimeringsmetoder. Eksempler på tabsfri komprimeringsformater:

GIF, TIFF - til grafiske data;

AVI - til videodata;

ZIP, ARJ, RAR, CAB, LH - til vilkårlige typer data.

Der er mange forskellige praktiske tabsfri kompressionsmetoder, som har en tendens til at have varierende effektivitet til forskellige typer data og forskellige mængder. Disse metoder er dog baseret på tre teoretiske algoritmer:

RLE (Run Length Encoding) algoritme;

algoritmer for KWE (KeyWord Encoding) gruppen;

Huffman algoritme.

RLE algoritme

RLE-algoritmen er baseret på ideen om at identificere gentagne datasekvenser og erstatte dem med en enklere struktur, der specificerer datakoden og gentagelsesfaktoren. Lad f.eks. følgende sekvens af data angives, der er genstand for komprimering:

1 1 1 1 2 2 3 4 4 4

RLE-algoritmen foreslår at erstatte den følgende struktur: 1 4 2 2 3 1 4 3, hvor det første tal i hvert par tal er datakoden, og det andet er gentagelsesfaktoren. Hvis 1 byte er allokeret til at lagre hvert dataelement i inputsekvensen, så vil hele sekvensen optage 10 bytes hukommelse, mens outputsekvensen (komprimeret version) vil optage 8 bytes hukommelse. Kompressionsforholdet, som karakteriserer kompressionsgraden, kan beregnes ved hjælp af formlen:

hvor Vx er mængden af hukommelse, der kræves til at lagre outputdatasekvensen (resulterende), Vn er inputdatasekvensen.

Jo lavere kompressionsforhold, jo mere effektiv er kompressionsmetoden. Det er klart, at RLE-algoritmen vil give en bedre komprimeringseffekt, når den gentagne datasekvens er længere. I tilfældet med eksemplet diskuteret ovenfor, hvis inputsekvensen ser sådan ud: 1 1 1 1 1 1 3 4 4 4, så vil kompressionsforholdet være 60%. I denne henseende opnås større effektivitet af RLE-algoritmen ved komprimering af grafiske data (især for monokromatiske billeder).

Algoritmer for KWE-gruppen

Nøgleordskomprimeringsalgoritmen er baseret på princippet om indkodning af leksikale enheder i grupper af bytes af en fast længde. Et eksempel på en leksikalsk genstand ville være et almindeligt ord. I praksis er gentagne sekvenser af symboler valgt til at spille rollen som leksikalske enheder og er kodet af en kæde af symboler (kode) af kortere længde. Kodningsresultatet placeres i en tabel, der danner en såkaldt ordbog.

Der er en del implementeringer af denne algoritme, blandt hvilke de mest almindelige er Lempel-Ziv-algoritmen (LZ-algoritmen) og dens modifikation, Lempel-Ziv-Welch-algoritmen (LZW-algoritmen). Ordbog i denne algoritme er en potentielt uendelig liste af sætninger. Algoritmen starter med en næsten tom ordbog, der kun indeholder én kodet streng, den såkaldte NULL-streng. Når det næste tegn i inputdatasekvensen læses, tilføjes det til den aktuelle linje. Processen fortsætter indtil nuværende linje matcher en sætning fra ordbogen. Men før eller siden holder den nuværende linje op med at svare til en eller anden ordbogssætning. På det punkt, hvor den aktuelle linje repræsenterer det sidste ordbogsmatch plus det beskedtegn, der lige er blevet læst, producerer koderen en kode, der består af matchens indeks og det næste tegn, der brød linjematchen. En ny sætning, bestående af matchindekset og det følgende tegn, føjes til ordbogen. Næste gang denne sætning optræder i en besked, kan den bruges til at konstruere en længere sætning, hvilket øger graden af komprimering af information.

LZW-algoritmen er bygget op omkring en sætningstabel (ordbog), der erstatter tegnstrengene i den komprimerede meddelelse til koder med fast længde. Tabellen har den såkaldte forhåndsegenskab, det vil sige, at for hver sætning i ordbogen, der består af en bestemt sætning w og symbolet K, indtastes sætningen w også i ordbogen. Hvis alle dele af ordbogen er fuldstændigt udfyldt, ophører kodningen med at være adaptiv (kodningen sker baseret på sætninger, der allerede findes i ordbogen).

Kompressionsalgoritmer fra denne gruppe er mest effektive til store tekstdata og er ineffektive for små filer (på grund af behovet for at gemme ordbogen).

Huffman algoritme

Huffman-algoritmen er baseret på ideen om bitgruppekodning. Først udføres en frekvensanalyse af inputdatasekvensen, det vil sige, at hyppigheden af forekomsten af hvert tegn, der findes i den, etableres. Herefter sorteres symbolerne efter faldende forekomstfrekvens.

Den grundlæggende idé er denne: Jo hyppigere et tegn forekommer, jo færre bits er det kodet. Kodningsresultatet indtastes i den ordbog, der kræves til afkodning. Lad os se på et simpelt eksempel, der illustrerer, hvordan Huffman-algoritmen fungerer.

Lad en tekst gives, hvor bogstavet "A" optræder 10 gange, bogstavet "B" - 8 gange, "C" - 6 gange, "D" - 5 gange, "E" og "F" - 4 gange hver . Derefter er en af de mulige kodningsmuligheder ved hjælp af Huffman-algoritmen vist i tabel 1.

Tabel 1.

	Forekomst frekvens	Bit kode

Som det fremgår af tabel 1, er størrelsen af inputteksten før komprimering 37 bytes, mens den efter komprimering er 93 bit, det vil sige cirka 12 bytes (eksklusive længden af ordbogen). Kompressionsforholdet er 32%. Huffman-algoritmen er universel; den kan bruges til at komprimere data af enhver type, men den er ineffektiv for små filer (på grund af behovet for at gemme en ordbog).

I praksis syntetiserer datakomprimeringssoftware disse tre "rene" algoritmer, da deres effektivitet afhænger af typen og mængden af data. Tabel 2 viser almindelige komprimeringsformater og de tilsvarende arkiveringsprogrammer, der anvendes i praksis.

Tabel 2.

Kompressionsformat	Operativsystem MS DOS		Windows operativsystem
Kompressionsformat	Arkiveringsprogram	Udpakningsprogram	Arkiveringsprogram	Udpakningsprogram

Derudover giver moderne arkivere brugeren et komplet udvalg af tjenester til at arbejde med arkiver, hvoraf de vigtigste er:

oprettelse af et nyt arkiv;

tilføje filer til et eksisterende arkiv;

udpakning af filer fra arkivet;

oprettelse af selvudtrækkende arkiver;

oprettelse af distribuerede arkiver af en fast størrelse til små lagringsmedier;

beskyttelse af arkiver med adgangskoder mod uautoriseret adgang;

se indholdet af filer i forskellige formater uden først at pakke ud;

søg efter filer og data inde i arkivet;

kontrol for virus i arkivet før udpakning;

valg og justering af kompressionsforholdet.

Kontrolspørgsmål

1. Hvilke faktorer påvirker graden af dataredundans? 2. Hvad er et arkiv? Hvilke softwareværktøjer kaldes arkivere? 3. Hvorfor kaldes komprimeringsmetoder, der ændrer dataindholdet, irreversible? 4. Giv eksempler på tabsgivende komprimeringsformater. 5. Hvad er fordelen ved reversible kompressionsmetoder frem for irreversible? Hvad med ulempen? 6. Hvad er forholdet mellem kompressionsforholdet og effektiviteten af kompressionsmetoden? 7. Hvad er hovedideen med RLE-algoritmen? 8. Hvad er hovedideen med KWE-gruppealgoritmerne? 9. Hvad er hovedideen med Huffman-algoritmen? 10. Hvilke softwarearkivere kender du? Beskriv dem kort.

Computer videnskab. Grundkursus. / Ed. S.V.Simonovich. - Skt. Petersborg, 2000

A.P. Miklyaev, IBM PC User's Handbook 3. udgave M.:, "Solon-R", 2000, 720 s.

Simonovich S.V., Evseev G.A., Murakhovsky V.I. Du har købt en computer: Den komplette begyndervejledning til spørgsmål og svar. - M.: AST-PRESS BOG; Inforcom-Press, 2001.- 544 s.: ill. (1000 tips).

Kovtanyuk Yu.S., Solovyan S.V. Selvbetjeningsvejledning til at arbejde på personlig computer- K.:Junior, 2001.- 560 s., ill.

Min vejleder og jeg er ved at udarbejde en lille monografi om billedbehandling. Jeg besluttede at præsentere for habra-samfundet et kapitel om billedkomprimeringsalgoritmer. Da det er svært at passe et helt kapitel ind i et indlæg, besluttede jeg at dele det op i tre indlæg:
1. Datakomprimeringsmetoder;
2. Tabsfri billedkomprimering;
3. Lossy billedkomprimering.
Herunder kan du læse det første indlæg i serien.

I øjeblikket er der et stort antal tabsfri komprimeringsalgoritmer, som kan opdeles i to store grupper:
1. Stream og ordbog algoritmer. Denne gruppe inkluderer algoritmer fra familierne RLE (run-length encoding), LZ* osv. Et træk ved alle algoritmer i denne gruppe er, at kodningen ikke bruger information om frekvensen af symboler i meddelelsen, men information om sekvenser, der stødes på. tidligere.
2. Algoritmer til statistisk (entropi) komprimering. Denne gruppe af algoritmer komprimerer information ved at udnytte de uregelmæssige frekvenser, med hvilke forskellige tegn forekommer i en besked. Algoritmer i denne gruppe inkluderer aritmetiske og præfikskodningsalgoritmer (ved hjælp af Shannon-Fanno, Huffman, sekanttræer).
Algoritmer til konvertering af information kan klassificeres i en separat gruppe. Algoritmer fra denne gruppe komprimerer ikke direkte information, men deres brug forenkler i høj grad yderligere komprimering ved hjælp af strøm-, ordbogs- og entropialgoritmer.

Stream og ordbog algoritmer

Kørselslængdekodning

Run-Length Encoding (RLE) er en af de enkleste og mest almindelige datakomprimeringsalgoritmer. I denne algoritme erstattes en sekvens af gentagne tegn med et tegn og det antal gange, det gentages.
For eksempel kan strengen "AAAAAA", som kræver, at 5 bytes lagres (forudsat at en byte er allokeret til at gemme et tegn), erstattes med "5A", bestående af to bytes. Det er klart, at denne algoritme er mere effektiv, jo længere rækken af gentagelser er.

Den største ulempe ved denne algoritme er dens ekstremt lave effektivitet på sekvenser af ikke-gentagende tegn. For eksempel, hvis vi betragter sekvensen "ABABAB" (6 bytes), vil den efter anvendelse af RLE-algoritmen blive til "1A1B1A1B1A1B" (12 bytes). For at løse problemet med ikke-gentagende tegn er der forskellige metoder.

For det meste enkel metode er følgende modifikation: byten, der koder for antallet af gentagelser, skal gemme information ikke kun om antallet af gentagelser, men også om deres tilstedeværelse. Hvis den første bit er 1, så angiver de næste 7 bit antallet af gentagelser af det tilsvarende tegn, og hvis den første bit er 0, så angiver de næste 7 bit antallet af tegn, der skal tages uden gentagelse. Hvis vi koder "ABABAB" ved hjælp af denne modifikation, får vi "-6ABABAB" (7 bytes). Det er indlysende, at den foreslåede teknik betydeligt kan øge effektiviteten af RLE-algoritmen på ikke-gentagende tegnsekvenser. Implementeringen af den foreslåede tilgang er vist i liste 1:

type

funktion RLEEncode(InMsg: ShortString): TRLEEncodedString;

MatchFl: boolesk;

MatchCount: shortint ;

EncodedString: TRLEEncodedString;

N, i: byte;

begynde

N:=0;

SetLength(EncodedString, 2 * length(InMsg) );

mens længde(InMsg) >= 1 do

begynde

MatchFl : = (længde(InMsg) > 1 ) og (InMsg[ 1 ] = InMsg[ 2 ] );

MatchCount: = 1;

mens (MatchCount<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do

MatchCount: = MatchCount + 1;

hvis MatchFl da

begynde

N:=N+2;

EncodedString[ N - 2 ] : = MatchCount + 128 ;

EncodedString[ N - 1 ] : = ord (InMsg[ 1 ] );

andet

begynde

hvis MatchCount<>længde(InMsg) derefter

MatchCount : = MatchCount - 1 ;

N: = N + 1 + MatchCount;

EncodedString[ N - 1 - MatchCount] : = - MatchCount + 128 ;

for i : = 1 til MatchCount do

EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] );

ende ;

delete(InMsg, 1, MatchCount);

ende ;

SetLength(EncodedString, N) ;

RLEEncode := EncodedString;

ende ;

Afkodning af en komprimeret besked er meget enkel og koges ned til en enkelt passage gennem den komprimerede besked, se liste 2:

type

TRLEEncodedString = array af byte;

funktion RLEDecode(InMsg: TRLEEncodedString): ShortString;

RepeatCount: shortint ;

i, j: ord;

OutMsg: ShortString;

begynde

OutMsg : = "" ;

i := 0;

mens jeg< length(InMsg) do

begynde

RepeatCount : = InMsg[ i] - 128 ;

i: = i + 1;

hvis RepeatCount< 0 then

begynde

RepeatCount := abs (RepeatCount) ;

for j : = i til i + RepeatCount - 1 do

OutMsg : = OutMsg + chr (InMsg[ j] );

i : = i + GentagTæl;

andet

begynde

for j : = 1 til RepeatCount do

OutMsg : = OutMsg + chr (InMsg[ i] );

i: = i + 1;

ende ;

ende ;

RLEDecode := OutMsg;

ende ;

Den anden metode til at øge effektiviteten af RLE-algoritmen er at brugeitmer, der ikke direkte komprimerer dataene, men bringer dem i en form, der er mere bekvem til komprimering. Som et eksempel på en sådan algoritme vil vi overveje BWT-permutationen, opkaldt efter opfinderne af Burrows-Wheeler-transformationen. Denne permutation ændrer ikke selve tegnene, men ændrer kun deres rækkefølge i strengen, mens gentagne understrenge efter anvendelse af permutationen samles i tætte grupper, som er meget bedre komprimeret ved hjælp af RLE-algoritmen. Direkte BWT-konvertering kommer ned til følgende trin:
1. Tilføjelse til den originale streng af et særligt ende-på-linje-tegn, der ikke forekommer andre steder;
2. Opnåelse af alle cykliske permutationer af den oprindelige streng;
3. Sortering af de modtagne strenge i leksikografisk rækkefølge;
4. Returnerer den sidste kolonne i den resulterende matrix.
En implementering af denne algoritme er vist i liste 3.

konst

EOMsg = "|" ;

function BWTEncode(InMsg: ShortString) : ShortString;

OutMsg: ShortString;

LastChar:ANSIChar;

N, i: ord ;

begynde

InMsg: = InMsg + EOMsg;

N : = længde(InMsg);

ShiftTable[ 1 ] : = InMsg;

for i : = 2 til N do

begynde

LastChar : = InMsg[ N];

InMsg : = LastChar + copy(InMsg, 1 , N - 1 );

ShiftTable[ i] : = InMsg;

ende ;

Sort(ShiftTable) ;

OutMsg : = "" ;

for i : = 1 til N do

OutMsg : = OutMsg + ShiftTable[ i] [N] ;

BWTEncode := OutMsg;

ende ;

Den nemmeste måde at forklare denne transformation på er med et specifikt eksempel. Lad os tage strengen "ANANAS" og blive enige om, at slutningen af strengtegnet vil være tegnet "|". Alle cykliske permutationer af denne streng og resultatet af deres leksikografiske sortering er angivet i tabel. 1.

De der. Resultatet af en direkte konvertering er strengen "|NNAAAC". Det er let at se, at denne streng er komprimeret meget bedre end den originale af RLE-algoritmen, fordi den indeholder lange efterfølger af gentagne bogstaver.
En lignende effekt kan opnås ved brug af andre transformationer, men fordelen ved BWT-transformationen er, at den er reversibel, selvom den omvendte transformation er mere kompliceret end den direkte. For at gendanne den originale streng skal du udføre følgende trin:
Opret en tom matrix af størrelse n*n, hvor n er antallet af tegn i den kodede meddelelse;
Udfyld den tomme kolonne længst til højre med den kodede meddelelse;
Sorter tabelrækker i leksikografisk rækkefølge;
Gentag trin 2-3, så længe der er tomme kolonner;
Returner den streng, der slutter med linjens endetegn.

Implementering af den omvendte konvertering er ikke svært ved første øjekast, og en af implementeringsmulighederne er vist i liste 4.

konst

EOMsg = "|" ;

funktion BWTDecode(InMsg: ShortString) : ShortString;

OutMsg: ShortString;

ShiftTable: array af ShortString;

N, i, j: ord;

begynde

OutMsg : = "" ;

N : = længde(InMsg);

SetLength(ShiftTable, N + 1 );

for i : = 0 til N do

ShiftTable[ i] : = "" ;

for i : = 1 til N do

begynde

for j := 1 til N do

ShiftTable[ j] : = InMsg[ j] + ShiftTable[ j] ;

Sort(ShiftTable) ;

ende ;

for i : = 1 til N do

hvis ShiftTable[ i] [ N] = EOMsg så

OutMsg : = ShiftTable[ i] ;

delete(OutMsg, N, 1 );

BWTDecode := OutMsg;

ende ;

Men i praksis afhænger effektiviteten af den valgte sorteringsalgoritme. Trivielle algoritmer med kvadratisk kompleksitet vil naturligvis have en meget negativ indflydelse på ydeevnen, så det anbefales at bruge effektive algoritmer.

Efter at have sorteret tabellen opnået i det syvende trin, skal du vælge en række fra tabellen, der slutter med tegnet "|". Det er let at se, at dette er den eneste linje. At. Vi så på BWT-transformationen ved hjælp af et specifikt eksempel.

For at opsummere kan vi sige, at den største fordel ved RLE-gruppen af algoritmer er enkelheden og hastigheden af operationen (inklusive afkodningshastighed), og den største ulempe er ineffektivitet på ikke-gentagende tegnsæt. Brugen af specielle permutationer øger effektiviteten af algoritmen, men øger også køretiden (især afkodning) betydeligt.

Ordbogskomprimering (LZ-algoritmer)

Gruppen af ordbogsalgoritmer koder i modsætning til RLE-gruppens algoritmer ikke antallet af gentagelser af tegn, men tidligere stødte på sekvenser af tegn. Mens de overvejede algoritmer kører, oprettes en tabel dynamisk med en liste over allerede stødte sekvenser og deres tilsvarende koder. Denne tabel kaldes ofte en ordbog, og den tilsvarende gruppe af algoritmer kaldes ordbog.

Den enkleste version af ordbogsalgoritmen er beskrevet nedenfor:
Initialiser ordbogen med alle tegn, der vises i inputstrengen;
Find i ordbogen den længste sekvens (S), der matcher begyndelsen af den kodede meddelelse;
Udskriv koden for den fundne sekvens og fjern den fra begyndelsen af den kodede meddelelse;
Hvis slutningen af beskeden ikke nås, skal du læse det næste tegn og tilføje Sc til ordbogen, gå til trin 2. Ellers skal du afslutte.

For eksempel er den nyligt initialiserede ordbog for sætningen "CUCKOOKOOKUSHONKOOKUPILAKAHOOD" vist i tabel. 3:

Under komprimeringsprocessen vil ordbogen blive suppleret med sekvenser fundet i beskeden. Processen med at opdatere ordbogen er angivet i tabel. 4.

Ved beskrivelse af algoritmen blev en beskrivelse af situationen, når ordbogen er helt udfyldt, bevidst udeladt. Afhængigt af varianten af algoritmen er forskellig adfærd mulig: fuldstændig eller delvis rydning af ordbogen, stop med at udfylde ordbogen eller udvidelse af ordbogen med en tilsvarende forøgelse af kodekapaciteten. Hver af disse tilgange har visse ulemper. For eksempel kan standsning af genopfyldning af ordbogen føre til en situation, hvor ordbogen gemmer sekvenser, der opstår i begyndelsen af strengen, der komprimeres, men som ikke opstår efterfølgende. Samtidig kan rengøring af ordbogen føre til fjernelse af hyppige sekvenser. De fleste af de anvendte implementeringer, når ordbogen fyldes, begynder at overvåge komprimeringsniveauet, og når det falder til under et vist niveau, genopbygges ordbogen. Dernæst vil vi overveje den enkleste implementering, der stopper med at opdatere ordbogen, når den er fuld.

Lad os først definere en ordbog som en post, der lagrer ikke kun de understrenge, der stødes på, men også antallet af understrenge, der er gemt i ordbogen:

Tidligere stødte undersekvenser gemmes i Words-arrayet, og deres kode er undersekvensnumrene i dette array.
Vi vil også definere funktionerne til at søge i ordbogen og tilføje til ordbogen:

konst

MAX_DICT_LENGTH = 256 ;

function FindInDict(D: TDictionary; str: ShortString): heltal ;

r:heltal;

i:heltal ;

fl:boolean ;

begynde

r: = -1;

hvis D. WordCount > 0 så

begynde

i := D. WordCount ;

fl := falsk;

mens (ikke fl) og (i >= 0 ) gør

begynde

i: = i-1;

fl : = D. Ord [ i] = str;

ende ;

ende ;

hvis fl da

r:= i;

FindInDict: = r;

ende ;

procedure AddToDict(var D: TDictionary; str: ShortString) ;

begynde

hvis D. WordCount< MAX_DICT_LENGTH then

begynde

D. WordCount : = D. WordCount + 1 ;

SetLength(D. Words, D. WordCount) ;

D. Ord [ D. WordCount - 1 ] : = str;

ende ;

ende ;

Ved at bruge disse funktioner kan kodningsprocessen i henhold til den beskrevne algoritme implementeres som følger:

funktion LZWEncode(InMsg: ShortString): TEncodedString;

OutMsg: TEncodedString;

tmpstr: Kortstreng;

D: TOrdbog;

i, N: byte;

begynde

SetLength(OutMsg, length(InMsg) );

N:=0;

InitDict(D) ;

mens længde(InMsg) > 0 gør

begynde

tmpstr : = InMsg[ 1 ] ;

mens (FindInDict(D, tmpstr) >= 0 ) og (length(InMsg) > length(tmpstr) gør

tmpstr : = tmpstr + InMsg[ længde(tmpstr) + 1 ] ;

if FindInDict(D, tmpstr)< 0 then

delete(tmpstr, length(tmpstr), 1 );

OutMsg[ N] : = FindInDict(D, tmpstr) ;

N:=N+1;

delete(InMsg, 1 , length(tmpstr) );

hvis længde(InMsg) > 0 så

AddToDict(D, tmpstr + InMsg[ 1 ] );

ende ;

SetLength(OutMsg, N) ;

LZWEncode := OutMsg;

ende ;

Resultatet af kodningen vil være antallet af ord i ordbogen.
Afkodningsprocessen reduceres til direkte afkodning af koder, og der er ingen grund til at overføre den oprettede ordbog; det er nok, at ordbogen under afkodning initialiseres på samme måde som under indkodning. Så vil ordbogen blive fuldstændig gendannet direkte under afkodningsprocessen ved at sammenkæde den foregående undersekvens og det aktuelle symbol.

Det eneste problem er muligt i følgende situation: når det er nødvendigt at afkode en undersekvens, der endnu ikke er i ordbogen. Det er let at se, at dette kun er muligt, når det er nødvendigt at udtrække en understreng, der skal tilføjes på det aktuelle trin. Det betyder, at understrengen opfylder cSc-mønsteret, dvs. begynder og slutter med samme karakter. I dette tilfælde er cS den understreng, der blev tilføjet i det foregående trin. Den betragtede situation er den eneste, når det er nødvendigt at afkode en linje, der endnu ikke er tilføjet. I betragtning af ovenstående kan vi foreslå følgende mulighed for afkodning af en komprimeret streng:

funktion LZWDecode(InMsg: TEncodedString) : ShortString;

D: TOrdbog;

OutMsg, tmpstr: ShortString;

i: byte ;

begynde

OutMsg : = "" ;

tmpstr : = "" ;

InitDict(D) ;

for i : = 0 til længde(InMsg) - 1 do

begynde

hvis InMsg[ i] >= D. WordCount så

tmpstr : = D. Ord [ InMsg[ i - 1 ] ] + D. Words [ InMsg[ i - 1 ] ] [ 1 ]

andet

tmpstr : = D. Ord [ InMsg[ i] ] ;

OutMsg : = OutMsg + tmpstr;

hvis jeg > 0 så

AddToDict(D, D. Words [InMsg[ i - 1 ] ] + tmpstr[ 1 ] );

ende ;

LZWDecode := OutMsg;

ende ;

Fordelene ved ordbogsalgoritmer inkluderer deres større kompressionseffektivitet sammenlignet med RLE. Det skal dog forstås, at den faktiske brug af disse algoritmer involverer nogle implementeringsproblemer.

Entropi kodning

Kodning ved hjælp af Shannon-Fano træer

Shannon-Fano-algoritmen er en af de første kompressionsalgoritmer, der er udviklet. Algoritmen er baseret på ideen om at repræsentere hyppigere tegn ved hjælp af kortere koder. Desuden har koder opnået ved hjælp af Shannon-Fano-algoritmen præfiksegenskaben: dvs. ingen kode er begyndelsen på nogen anden kode. Præfiksegenskaben sikrer, at kodningen er en-til-en. Algoritmen til at konstruere Shannon-Fano-koder er præsenteret nedenfor:
1. Opdel alfabetet i to dele, hvor de samlede sandsynligheder for symbolerne er så tæt som muligt på hinanden.
2. Tilføj 0 til præfikskoden for den første del af tegnene, tilføj 1 til præfikskoden for den anden del af tegnene.
3. Udfør trin 1-3 rekursivt for hver del (som indeholder mindst to tegn).
På trods af dens komparative enkelhed er Shannon-Fano-algoritmen ikke uden sine ulemper, hvoraf den vigtigste er ikke-optimal kodning. Selvom partitionen ved hvert trin er optimal, garanterer algoritmen ikke et optimalt resultat som helhed. Overvej f.eks. næste linje: "AAAABVGDEZH". Det tilsvarende Shannon-Fano-træ og de opnåede koder på dets basis er vist i fig. 1:

Uden brug af kodning vil beskeden optage 40 bit (forudsat at hvert tegn er kodet med 4 bit), og ved brug af Shannon-Fano-algoritmen 4*2+2+4+4+3+3+3=27 bit. Beskedvolumen faldt med 32,5 %, men nedenfor vil vi vise, at dette resultat kan forbedres markant.

Kodning med Huffman Trees

Huffman-kodningsalgoritmen, udviklet flere år efter Shannon-Fano-algoritmen, har også egenskaben præfiks og derudover bevist minimal redundans, hvilket er det, der bestemmer dens ekstremt brede distribution. For at få Huffman-koder skal du bruge følgende algoritme:
1. Alle tegn i alfabetet er repræsenteret som frie noder, og nodens vægt er proportional med frekvensen af tegnet i beskeden;
2. Fra sættet af frie knudepunkter udvælges to knudepunkter med minimal vægt, og en ny (forælder) knude oprettes med en vægt svarende til summen af vægtene af de valgte knudepunkter;
3. De valgte noder fjernes fra den frie liste, og den overordnede node, der er oprettet på basis af dem, føjes til denne liste;
4. Trin 2-3 gentages, indtil der er mere end én knude på den frie liste;
5. Baseret på det konstruerede træ tildeles hvert tegn i alfabetet en præfikskode;
6. Beskeden er kodet med de modtagne koder.

Lad os betragte det samme eksempel som i tilfældet med Shannon-Fano-algoritmen. Huffman-træet og koder opnået for meddelelsen "AAAABVGDEJ" er vist i fig. 2:

Det er let at beregne, at volumen af den kodede meddelelse vil være 26 bit, hvilket er mindre end i Shannon-Fano-algoritmen. Separat er det værd at bemærke, at på grund af populariteten af Huffman-algoritmen, er der i øjeblikket mange muligheder for Huffman-kodning, herunder adaptiv kodning, som ikke kræver transmission af symbolfrekvenser.
Blandt ulemperne ved Huffman-algoritmen er en væsentlig del problemer forbundet med implementeringens kompleksitet. Brug af symboler for reelle variable til at gemme frekvenser er forbundet med et tab af præcision, så i praksis bruges heltalsvariable ofte, men da Vægten af forældreknuder vokser konstant, før eller siden opstår der et overløb. På trods af algoritmens enkelhed kan dens korrekte implementering stadig forårsage nogle vanskeligheder, især for store alfabeter.

Kodning med sekantfunktionstræer

Kodning ved hjælp af sekantfunktioner er en algoritme udviklet af forfatterne, der giver dig mulighed for at få præfikskoder. Algoritmen er baseret på ideen om at konstruere et træ, hvor hver knude indeholder en sekantfunktion. For at beskrive algoritmen mere detaljeret er det nødvendigt at introducere flere definitioner.
Et ord er en ordnet sekvens af m bit (tallet m kaldes ordet kapacitet).
En sekantliteral er et par af formen ciffer-cifret værdi. For eksempel betyder det bogstavelige (4,1), at bit 4 i ordet skal være 1. Hvis betingelsen for det bogstavelige er opfyldt, anses det bogstavelige for sandt, ellers er det falsk.
En k-bit sekant er et sæt af k literaler. Hvis alle bogstaver er sande, så er selve sekantfunktionen sand, ellers er den falsk.

Træet er konstrueret således, at hver node deler alfabetet i så tætte dele som muligt. I fig. Figur 3 viser et eksempel på et sekanttræ:

Træet af sekantfunktioner garanterer i det generelle tilfælde ikke optimal kodning, men det giver ekstremt høj hastighed arbejde på grund af enkelheden i driften i noderne.

Aritmetisk kodning

Aritmetisk kodning er en af de mest effektive måder informationskomprimering. I modsætning til Huffman-algoritmen tillader aritmetisk kodning, at meddelelser kodes med entropi mindre end 1 bit pr. tegn. Fordi De fleste aritmetiske kodningsalgoritmer er beskyttet af patenter; kun de grundlæggende ideer vil blive beskrevet nedenfor.
Lad os antage, at alfabetet i brug indeholder N symboler a_1,...,a_N, med henholdsvis frekvenserne p_1,...,p_N. Så vil den aritmetiske kodningsalgoritme se sådan ud:
Tag som et arbejdshalvt interval

Komprimering af tomme rum

At komprimere hvidt mellemrum kan beskrives mere generelt som "fjerne det, der ikke interesserer os." Selvom denne metode er teknisk punkt Selvom syn er en tabsgivende kompressionsteknik, er den stadig nyttig til mange typer datarepræsentationer, som vi støder på i den virkelige verden. For eksempel selvom HTML er meget nemmere at læse i en teksteditor, når du tilføjer indrykning og linjeafstand, intet af dette "hvide rum" har nogen effekt på gengivelsen af HTML-dokumentet i en webbrowser. Hvis du med sikkerhed ved, at et bestemt HTML-dokument udelukkende er beregnet til webbrowseren (eller en form for robot/søgeagent), så kan det være en god idé at fjerne alt det hvide mellemrum, så dokumentet overføres hurtigere og fylder mindre lagerplads. Alt det, vi fjerner, når vi komprimerer tomme pladser, bærer faktisk ikke nogen funktionel belastning.

I tilfælde af det præsenterede eksempel kan kun en lille del af informationen fjernes fra den beskrevne rapport. Linjen med "="-symboler langs den øverste kant af rapporten har ikke noget funktionelt indhold; det samme gælder for "-" tegn i tal og mellemrum mellem tal. Alt dette er nyttigt for den person, der læser den originale rapport, men har ingen betydning, hvis vi betragter disse tegn som "data". Det, vi fjerner, er ikke ligefrem "tomt rum" i traditionel forstand, men det er det i bund og grund.

Komprimering af tomme rum er ekstremt "billigt" set ud fra et implementeringssynspunkt. Det er bare et spørgsmål om at læse datastrømmen og udelukke nogle få specifikke værdier fra outputstrømmen. I mange tilfælde er "udpakningstrinnet" slet ikke tilvejebragt. Men selvom vi ønskede at genskabe noget tæt på den originale datastrøm, ville det kun kræve en lille mængde CPU eller hukommelsesressourcer. De gendannede data vil ikke nødvendigvis være de samme som de originale data; det afhænger af, hvilke regler og begrænsninger der var indeholdt i originalen. HTML-side, skrevet af en person i et tekstbehandlingsprogram, vil sandsynligvis indeholde mellemrum arrangeret efter visse regler. Det samme gælder for automatiserede værktøjer, der ofte skaber "rimelig" indrykning og mellemrum i HTML-kode. I tilfælde af det stive rapportformat, der præsenteres i vores eksempel, er der ingen grund til, at den originale repræsentation ikke kunne genskabes af en form for "formateringsudpakker".

Gruppekodning

Gruppekodning (RLE) er den enkleste af de almindeligt anvendte tabsfri komprimeringsmetoder. Ligesom at krympe tomme rum, det kræver ikke særlige omkostninger, især til afkodning. Ideen bag denne metode er, at mange datarepræsentationer for det meste består af strenge af gentagne bytes. Vores eksempelrapport er en sådan datavisning. Den starter med en streng af gentagne "="-tegn og har linjer med kun mellemrum spredt ud over rapporten. I stedet for at repræsentere hvert tegn med sin egen byte, involverer RLE-metoden (nogle gange eller altid) at specificere antallet af gentagelser, efterfulgt af det tegn, der skal spilles det antal gange.

Hvis dataformatet, der behandles, er domineret af gentagne bytes, så kan det være passende og effektivt at bruge en algoritme, hvor en eller flere bytes angiver antallet af gentagelser, efterfulgt af tegnet, der gentages. Men hvis du har tegnstrenge af enhedslængde, vil det tage to (eller flere) bytes at kode dem. Med andre ord kan ét ASCII-tegn "X" af inputstrømmen kræve en output bitstream på 00000001 01011000. På den anden side ville indkodning af hundrede på hinanden følgende "X"-tegn bruge det samme antal bit: 01100100 01011000 , hvilket er ret effektivt.

Forskellige varianter af RLE bruger ofte selektivt bytes til at angive antallet af gentagelser, mens de resterende bytes blot repræsenterer sig selv. Til dette formål skal der reserveres mindst én enkeltbyte-værdi, som om nødvendigt kan fjernes fra udgangen. For eksempel ved vi i vores eksempeltelefonnummerrapport, at alle oplysningerne i inputstrømmen består af simple ASCII-tegn. Især har alle sådanne tegn den første bit af ASCII-værdien lig med 0. Vi kunne bruge denne første ASCII-bit til at angive, at byten angiver antallet af gentagelser i stedet for et almindeligt tegn. De næste syv bits af iteratorbyten kunne bruges til at angive antallet af gentagelser, og den næste byte kunne indeholde det tegn, der gentages. Så for eksempel kunne vi repræsentere strengen "YXXXXXXXX" som følger:

"Y" Iter(8) "X" 01001111 10001000 01011000

Dette eksempel forklarer ikke, hvordan man kasserer iterator-byteværdier, og det giver heller ikke mulighed for at bruge mere end 127 gentagelser af et enkelt tegn. Forskellige variationer af RLE løser dog om nødvendigt disse problemer.

Huffman kodning

Huffman-kodning behandler symboltabellen som et helt sæt af data. Kompression opnås ved at finde "vægtene" af hvert tegn i datasættet. Nogle tegn bruges oftere end andre, så Huffman-kodning antager, at hyppige tegn skal kodes i færre bits end mindre almindelige tegn. Eksisterer forskellige muligheder Huffman-kodning, men den originale (og mest brugte) version går ud på at finde det mest almindelige tegn og indkode det med en enkelt bit, for eksempel 1. Og hvis der forekommer et 0 i den kodede sekvens, betyder det, at der på dette sted er et andet tegn kodet med et stort antal bits.

Lad os forestille os, at vi brugte Huffman-kodning til at kode vores eksempel (forudsat at vi allerede havde udsat rapporten for komprimering af hvidt mellemrum). Vi kunne få følgende resultat:

Tabel 2. Huffman-kodningsresultater

Kodningssymbol 1 7 010 2 011 3 00000 4 00001 5 00010 6 00011 8 00100 9 00101 0 00111 1

Det originale tegnsæt (bestående af tal) kan nemt kodes (uden komprimering) som 4-bit sekvenser (nibbles). Følgende Huffman-kodning vil i værste fald bruge op til 5 bit til tegn, hvilket naturligvis er værre end nibble-kodning. Men i det bedste tilfælde er alt, hvad der kræves 1 bit; det er kendt, at det er den bedste sag, der vil blive brugt oftest (da dette er det symbol, der optræder oftest i dataene). Så vi kunne kode et specifikt telefonnummer som dette:

772 7628 --> 1 1 010 1 00010 010 00011

Hvis det kodes ved hjælp af nibbles, vil repræsentationen af telefonnummeret tage 28 bit, men i vores tilfælde tager kodningen 19 bit. Mellemrum tilføjes kun i eksemplet for bedre forståelse; deres tilstedeværelse i de kodede symboler er ikke påkrævet, da det altid er muligt ud fra kodetabellen at bestemme, om slutningen af det kodede symbol er nået eller ej (det er dog stadig nødvendigt at holde styr på den aktuelle position i dataene ).

Huffman-kodning er stadig meget "billig" at afkode med hensyn til CPU-tid. Det kræver dog et kodebogsopslag, så det er måske ikke så "billigt" som RLE. Huffman-kodning er ret dyr, da det kræver en fuld scanning af data og konstruktion af en tabel med symbolfrekvenser. I nogle tilfælde, når du bruger Huffman-kodning, er en "genvej" passende. Standard Huffman-kodning anvendes på det specifikke datasæt, der kodes, med output først efterfulgt af en symboltabel. Men hvis ikke et enkelt sæt data transmitteres, men et helt format med de samme mønstre for forekomst af tegn, så kan den globale Huffman-tabel bruges. Givet en sådan tabel kan vi hardkode søgninger i vores eksekverbare filer, hvilket vil gøre komprimering og dekompression meget "billigere" (minus den indledende globale sampling og hårdkodning). For eksempel, hvis vi ved, at vores datasæt vil være prosa i engelsk sprog, så er frekvenserne for forekomst af bogstaver velkendte og konstante for forskellige datasæt.

Komprimering ved hjælp af Lempel-Ziv-algoritmen

Sandsynligvis den mest betydningsfulde tabsfri komprimeringsmetode er Lempel-Ziv-algoritmen. I denne artikel vi taler om LZ78-varianten, men LZ77 og andre varianter fungerer på lignende måde. Ideen bag LZ78-algoritmen er at kode en strømsekvens af bytes ved hjælp af en dynamisk tabel. Ved starten af bitstream-komprimering er LZ-tabellen fyldt med det faktiske tegnsæt sammen med et par tomme pladser. Algoritmen bruger tabeller forskellige størrelser, men i dette eksempel med telefonnumre (med tomrumskomprimering) bruges en tabel med 32 elementer (nok til dette eksempel, men er muligvis ikke nok til andre datatyper). Først udfylder vi de første ti pladser med tegnene i det anvendte alfabet (tal). Efterhånden som nye bytes ankommer, hentes først tabelværdien svarende til den længste matchende sekvens, og derefter skrives sekvensen med længden N+1 til den næste ledige slot. I værste fald bruger vi 5 bits i stedet for 4 for et enkelt tegn, men i de fleste tilfælde kan vi klare os med 5 bits for flere tegn. Lad os se på et eksempel på, hvordan denne algoritme fungerer (bordpladsen er angivet i firkantede parenteser):

7 --> Søg: 7 fundet --> intet at tilføje --> fortsæt søgning 7 --> Søgning: 77 ikke fundet --> tilføj "77" til --> display =00111 2 --> Søg: 72 ikke fundet --> tilføj "72" til --> display =00111 7 --> Søgning: 27 ikke fundet --> tilføj "27" til --> display =00010 6 --> Søgning: 76 ikke fundet --> tilføj "76" til --> display =00111 2 --> Søgning: 62 ikke fundet --> tilføj "62" til --> display =00110 8 --> Søgning: 28 ikke fundet --> tilføj "28" til --> output =00010

Vi har ikke fået nogen fordel ud af dette indtil videre, men lad os gå videre til næste telefonnummer:

7 --> Søgning: 87 ikke fundet --> tilføj "87 til --> display =00100 7 --> Søgning: 77 fundet --> intet at tilføje --> fortsæt søgning 2 --> Søgning: 772 ikke fundet - -> tilføj "772" til --> output =01011 8 --> Søgning: 28 fundet --> intet at tilføje --> fortsæt søgning 6 --> Søgning: 286 ikke fundet --> tilføj "286" til -- > output =10000 ....

Ovenstående operationer bør være tilstrækkelige til at demonstrere modellens funktion. Selvom der endnu ikke er opnået nogen mærkbar komprimering, kan det allerede ses, at vi har genbrugt slots 11 og 16, der koder to symboler med hver et outputsymbol. Derudover har vi allerede akkumuleret en yderst nyttig sekvens af bytes 772 i slot 18, som efterfølgende vil dukke op gentagne gange i strømmen.

LZ78-algoritmen udfylder en symboltabel med (formodentlig) nyttige poster, skriver derefter den tabel, rydder den og starter en ny. I en sådan situation er en tabel på 32 tegn muligvis ikke tilstrækkelig, da den vil blive ryddet, før vi gentagne gange kan bruge sekvenser som 772 og lignende. Men ved hjælp af en lille tabel er det lettere at illustrere algoritmens funktion.

I typiske datasæt opnår varianter af Lempel-Ziv-metoden væsentligt mere høje odds kompression end Huffman og RLE metoder. På den anden side bruger varianter af Lempel-Ziv-metoden betydelige ressourcer på iterationer, og deres tabeller kan optage meget hukommelsesplads. De fleste eksisterende værktøjer og komprimeringsbiblioteker bruger en kombination af Lempel-Ziv og Huffman metoderne.

Korrekt problemformulering

Ved at vælge den rigtige algoritme kan du opnå betydelige gevinster selv sammenlignet med mere optimerede, men uhensigtsmæssige metoder. Lignende rigtige valg datapræsentation er ofte vigtigere end valg komprimeringsmetoder (som altid er en form for efterfølgende optimering af de nødvendige funktioner). Det enkle eksempeldatasæt i denne artikel giver en glimrende illustration af en situation, hvor genovervejelse af et problem er en bedre løsning end at bruge nogen af de givne kompressionsmetoder.

Det er nødvendigt at tage et nyt kig på problemet, som dataene udgør. Da dette ikke er et generelt datasæt, og der er klare forudsætninger for det, kan problemstillingen omformuleres. Det er kendt, at der maksimalt er 30.000 telefonnumre (fra 7720000 til 7749999), hvoraf nogle er aktive og nogle ikke. Vi står ikke over for opgaven med at vise en komplet repræsentation af alle aktive numre. Vi skal bare indikere at bruge en boolesk værdi, aktiv dette nummer eller ikke. Når vi tænker på problemet på denne måde, kan vi simpelthen allokere 30.000 bits i hukommelse og lager og bruge hver bit til at angive aktiviteten (ja eller nej) for det tilsvarende telefonnummer. Rækkefølgen af bits i bitmap kan svare til telefonnumre, sorteret i stigende rækkefølge (laveste til højeste).

Sådan en bitmap-baseret løsning er ideel fra alle synspunkter. Det kræver præcis 3750 bytes at repræsentere datasættet; forskellige komprimeringsmetoder vil bruge varierende lydstyrke afhængigt af antallet af telefonnumre i sættet og effektiviteten af komprimeringen. Men hvis 10.000 af de 30.000 mulige telefonnumre er aktive, og selvom du effektiv metode komprimering kræver flere bytes pr. telefonnummer, så vinder bitmappet helt sikkert. Med hensyn til CPU-krav er bitmap ikke kun bedre end nogen af de diskuterede komprimeringsmetoder, men det er også bedre end normal metode repræsentation af telefonnumre som strenge (uden komprimering). Gennemgang af bitmap og forøgelse af den aktuelle telefonnummertæller kan gøres effektivt selv i den indbyggede cache i moderne processorer.

Fra dette simpelt eksempel Du kan forstå, at ikke alle problemer har en så ideel løsning som den, der er diskuteret ovenfor. Mange problemer kræver betydelige mængder hukommelse, båndbredde, lager og CPU-ressourcer; og i de fleste sådanne tilfælde kan kompressionsteknikker afhjælpe eller reducere disse krav. Men den vigtigere takeaway er, at før du bruger komprimeringsteknikker, bør du dobbelttjekke, at du har valgt det rigtige koncept til at repræsentere dine data.

Dedikeret til minde om Claude Shannon.

For mennesker er dataredundans ofte forbundet med informationskvalitet, da redundans har en tendens til at forbedre forståeligheden og opfattelsen af information. Men når det kommer til lagring og transmission af information ved hjælp af computerteknologi, spiller redundans en negativ rolle, da det fører til en stigning i omkostningerne ved lagring og transmission af information. Dette problem bliver især relevant i tilfælde af behandling af enorme mængder af information med ubetydelige mængder lagringsmedier. I denne henseende opstår problemet med at reducere redundans eller datakomprimering konstant. Hvis datakomprimeringsmetoder anvendes på færdige filer, bruges ofte i stedet for udtrykket "datakomprimering" udtrykket "dataarkivering"; den komprimerede version af dataene kaldes arkiv, og software, der implementerer komprimeringsmetoder, kaldes arkivarer.

Afhængigt af objektet, hvori de data, der skal komprimeres, er placeret:

1. Komprimering (arkivering) af filer: bruges til at reducere størrelsen af filer, når de forberedes til transmission via kommunikationskanaler eller til transport på eksterne medier med lille kapacitet;

2. Komprimering (arkivering) af mapper: bruges som et middel til at reducere mængden af mapper før langtidslagring, for eksempel under backup;

3. Komprimering (komprimering) af diske: bruges til at øge effektiviteten af at bruge diskplads ved at komprimere data, når de skrives til et lagermedie (normalt ved hjælp af operativsystemet).

· JPEG - til grafiske data;

· MPG - til videodata;

· MP3 - til lyddata.

· GIF, TIFF - til grafiske data;

· AVI - til videodata;

· ZIP, ARJ, RAR, CAB, LH - for vilkårlige datatyper.

Tabel 2 viser almindelige komprimeringsformater og de tilsvarende arkiveringsprogrammer, der anvendes i praksis.

Moderne arkivarer

Særlige programmer

Foredrag 6

Arkivere er programmer til oprettelse af arkiver. Arkiver er designet til at gemme data i en praktisk, kompakt form. Dataene er normalt filer og mapper. Som regel udsættes data først for kompression eller emballering. Derfor er næsten enhver arkiver også et datakomprimeringsprogram. På den anden side kan ethvert datakomprimeringsprogram betragtes som et arkiver. Kompressionseffektiviteten er den vigtigste egenskab arkivere. Størrelsen afhænger af det oprettede arkiver. Jo mindre arkivet er, jo mindre plads kræves der for at opbevare det. Transmission kræver mindre transmissionskanalbåndbredde eller tager mindre tid. Fordelene ved arkiver er indlysende, i betragtning af at dataene er reduceret i størrelse med 2 gange og 5 gange.

Datakomprimering bruges meget bredt. Man kan sige næsten overalt. For eksempel, PDF-dokumenter indeholder som regel komprimeret information. En hel del eksekverbare EXE filer komprimeret med specielle pakkere. Alle slags multimediefiler (GIF, JPG, MP3, MPG) er en slags arkiver.

Den største ulempe ved arkiver er manglende evne direkte adgang til dataene. De skal først trækkes ud af arkivet eller pakkes ud. Udpakningen kræver dog, ligesom emballering, noget systemressourcer. Dette er ikke en øjeblikkelig operation. Derfor bruges arkiver hovedsageligt med relativt sjældent anvendte data. For eksempel til at gemme sikkerhedskopier eller installationsfiler.

Der er mange arkivere derude i øjeblikket. De varierer i udbredelse og effektivitet. Nogle interessante arkivere er ikke kendt af en bred vifte af potentielle brugere. Af særlig interesse er evalueringen og sammenligningen af komprimeringseffektiviteten af populære arkivere.

En lang række forskellige metoder, deres modifikationer og undertyper til datakomprimering er blevet udviklet. Moderne arkivere har en tendens til at bruge flere metoder samtidigt. Vi kan fremhæve nogle grundlæggende.

Run-length-kodning (RLE - forkortelse for run-length-kodning)

En meget simpel metode. En sekventiel serie af identiske dataelementer erstattes af to tegn: elementet og antallet af gange, det forekommer. Meget brugt som ekstra og mellemmetode. Som selvstændig metode bruges den f.eks grafisk format BMP.

Ordbogsmetode (LZ - forkortelse for Lempel Ziv - navne på forfattere)

Den mest almindelige metode. Der bruges en ordbog bestående af sekvenser af data eller ord. Under komprimering erstattes disse ord med deres koder fra ordbogen. I den mest almindelige implementering er ordbogen selv original blok data.

Hovedparameteren for ordbogsmetoden er ordbogens størrelse. Jo større ordforråd, jo større effektivitet. Men for heterogene data er det for stort stor størrelse kan være skadeligt, da hvis datatypen ændres brat, vil ordbogen blive fyldt med irrelevante ord. For at denne komprimeringsmetode skal fungere effektivt, kræves der yderligere hukommelse. Cirka en størrelsesorden større end nødvendigt for de originale ordbogsdata. En væsentlig fordel ved ordbogsmetoden er den enkle og hurtige udpakningsprocedure. Der kræves ingen yderligere hukommelse. Denne funktion er især vigtig, hvis hurtig adgang til data er påkrævet.

Entropimetode (Huffman - Huffman-kodning, aritmetisk kodning - aritmetisk kodning)

I denne metode bliver dataelementer, der forekommer hyppigere, kodet med en kortere kode under komprimering, og mindre almindelige dataelementer kodes med en længere kode. På grund af det faktum, at der er væsentligt flere korte koder, samlet størrelse viser sig mindre end originalen.

Udbredt som en ekstra metode. Som en selvstændig metode bruges den f.eks. i JPG-grafikformatet.

Kontekstmodelleringsmetode (CM - forkortelse for kontekstmodellering - kontekstmodellering)

I denne metode bygges en model af kildedataene. Når det næste dataelement komprimeres, producerer denne model sin forudsigelse eller sandsynlighed. Ifølge denne sandsynlighed er dataelementet kodet ved hjælp af entropimetoden. Hvordan mere præcist modellen vil matche de originale data, jo mere præcist vil det producere forudsigelser, og jo kortere vil dataelementerne blive kodet.

At bygge en effektiv model kræver meget hukommelse. Ved udpakning skal du bygge nøjagtig den samme model. Derfor er kravene til hastighed og volumen Random Access Memory for pakning og udpakning er næsten det samme. I øjeblikket giver kontekstmodelleringsmetoder os mulighed for at opnå bedste grad kompression, men har en ekstrem lav hastighed.

PPM (PPM - Forudsigelse ved delvis matching)

Dette er en speciel undertype af kontekstmodellering. Forudsigelsen er lavet ud fra et vist beløb tidligere dataelementer. Hovedparameteren er rækkefølgen af modellen, som sætter dette antal elementer. Jo højere modelrækkefølgen er, desto højere er kompressionsforholdet, men der kræves mere RAM for at gemme modeldataene. Hvis der ikke er nok RAM, viser en sådan model med en stor ordre dårlige resultater. PPM-metoden er især effektiv til at komprimere tekstdata.

Fortransformationer eller filtrering

Disse metoder bruges ikke til komprimering, men til at præsentere information i en form, der er praktisk til yderligere komprimering. For eksempel er ukomprimerede multimediedata karakteriseret ved jævne ændringer signalniveau. Derfor bruges en deltatransformation til dem, når der tages en relativ værdi i stedet for en absolut værdi. Der er filtre til tekst, eksekverbare filer, databaser og andre.

Bloksorteringsmetode (BWT - forkortelse for Burrows Wheeler Transform - ved forfatternes navn)

Dette er en speciel type eller gruppe af transformationer baseret på sortering. Næsten alle data kan blive udsat for denne transformation. Sortering sker over blokke, så dataene først opdeles i dele. Hovedparameteren er størrelsen på den blok, der sorteres. For at pakke data ud skal du udføre næsten de samme trin, som når du pakker. Derfor er hastigheden og RAM-kravene næsten de samme. Arkivere, der bruger denne metode, viser normalt høj hastighed og komprimeringsforhold for tekstdata.

Kontinuerlige blokke eller kontinuerlig tilstand (fast tilstand - kontinuerlig tilstand)

I mange komprimeringsmetoder er den indledende del af dataene eller filen dårligt kodet. For eksempel i ordbogsmetoden er ordbogen tom. I kontekstmodelleringsmetoden bygges der ikke en model. Når antallet af filer er stort, og deres størrelse er lille, forringes det samlede komprimeringsforhold betydeligt på grund af disse indledende sektioner. For at forhindre, at dette sker, når du skifter til næste fil, indhentet information baseret på tidligere filer. En lignende effekt kan opnås enkel præsentation kildefiler som én kontinuerlig fil.

Denne metode bruges i mange arkivere og har væsentlig ulempe. For at pakke en vilkårlig fil ud, skal du også pakke de filer ud, der er i begyndelsen af arkivet. Dette er nødvendigt for at udfylde ordbogen korrekt eller bygge en model. Der er også en mellemmulighed, når der anvendes kontinuerlige blokke af en fast størrelse. Kompressionstab er minimale, men for at udtrække en fil, der er i slutningen stort arkiv, skal kun én sammenhængende blok pakkes ud, ikke hele arkivet.

Segmentering

Ved alle komprimeringsmetoder er selve overgangen kodet meget dårligt ved ændring af datatype. Ordbogen bliver irrelevant, modellen er konfigureret til andre data. I disse tilfælde anvendes segmentering. Dette er en foreløbig opdeling i homogene dele. Disse dele kodes derefter individuelt eller i grupper.