Gjennomgang av datakomprimeringsmetoder. Datakomprimering

"Datakomprimering"

Et karakteristisk trekk ved de fleste datatyper er deres redundans. Graden av dataredundans avhenger av typen data. For videodata er for eksempel redundansgraden flere ganger større enn for grafiske data, og redundansgraden for grafiske data er på sin side større enn redundansgraden for tekstdata. En annen faktor som påvirker graden av redundans er kodesystemet som er tatt i bruk. Et eksempel på kodesystemer vil være vanlige kommunikasjonsspråk, som ikke er annet enn systemer for koding av konsepter og ideer for å uttrykke tanker. Dermed er det fastslått at koding av tekstdata ved bruk av russisk språk gir i gjennomsnitt en redundans som er 20-25 % større enn koding av tilsvarende data ved bruk av engelsk.

For mennesker er dataredundans ofte forbundet med informasjonskvalitet, siden redundans har en tendens til å forbedre forståeligheten og oppfatningen av informasjon. Men når det gjelder lagring og overføring av informasjon ved hjelp av datateknologi, spiller redundans en negativ rolle, siden det fører til en økning i kostnadene ved lagring og overføring av informasjon. Dette problemet blir spesielt relevant ved behandling av store mengder informasjon med ubetydelige mengder lagringsmedier. I denne forbindelse oppstår problemet med å redusere redundans eller datakomprimering konstant. Hvis datakomprimeringsmetoder brukes på ferdige filer, brukes ofte i stedet for begrepet "datakomprimering" begrepet "dataarkivering"; den komprimerte versjonen av dataene kalles arkiv, A programvare, som implementere komprimeringsmetoder kalles arkivarer.

Avhengig av objektet som dataene som skal komprimeres er plassert i:

Komprimering (arkivering) av filer: brukes til å redusere størrelsen på filer når de klargjøres for overføring via kommunikasjonskanaler eller for transport på eksterne medier med liten kapasitet;

Mappekomprimering (arkivering): brukes som et middel for å redusere volumet av mapper før langtidslagring, f.eks. backup;

Diskkomprimering (komprimering): brukes til å øke effektiviteten ved å bruke diskplass ved å komprimere data når du skriver dem til et lagringsmedium (vanligvis ved bruk av operativsystemet).

Det finnes mange praktiske datakomprimeringsalgoritmer, men de er alle basert på tre teoretiske måter å redusere dataredundans på. Den første måten er å endre innholdet i dataene, den andre er å endre strukturen til dataene, og den tredje er å endre både strukturen og innholdet i dataene samtidig.

Hvis datakomprimering endrer innholdet, kalles komprimeringsmetoden irreversible, det vil si at når man gjenoppretter (arkiverer) data fra et arkiv, blir ikke informasjonen fullstendig gjenopprettet. Slike metoder kalles ofte tapskontrollerte kompresjonsmetoder. Det er klart at disse metodene kun kan brukes for datatyper der tap av deler av innholdet ikke fører til vesentlig forvrengning av informasjon. Disse typer data inkluderer video-, lyd- og grafikkdata. Tapskontrollerte komprimeringsmetoder gir betydelig høyere komprimeringshastigheter, men kan ikke brukes på tekstdata. Eksempler på tapsgivende komprimeringsformater inkluderer:

JPEG - for grafiske data;

MPG - for videodata;

MP3 - for lyddata.

Hvis datakomprimering bare endrer datastrukturen, kalles komprimeringsmetoden reversible. I dette tilfellet er det mulig å gjenopprette informasjonen fullstendig fra arkivet. Reversible komprimeringsmetoder kan brukes på alle typer data, men de gir mindre komprimering enn irreversible komprimeringsmetoder. Eksempler på tapsfrie komprimeringsformater:

GIF, TIFF - for grafiske data;

AVI - for videodata;

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

Det finnes mange forskjellige praktiske tapsfrie kompresjonsmetoder, som har en tendens til å ha varierende effektivitet for forskjellige typer data og forskjellige volumer. Imidlertid er disse metodene basert på tre teoretiske algoritmer:

RLE (Run Length Encoding) algoritme;

algoritmer for KWE (KeyWord Encoding)-gruppen;

Huffman algoritme.

RLE-algoritme

RLE-algoritmen er basert på ideen om å identifisere gjentatte datasekvenser og erstatte dem med en enklere struktur som spesifiserer datakoden og repetisjonsfaktoren. La for eksempel følgende sekvens av data gis som er gjenstand for komprimering:

1 1 1 1 2 2 3 4 4 4

RLE-algoritmen foreslår å erstatte den følgende struktur: 1 4 2 2 3 1 4 3, der det første tallet i hvert tallpar er datakoden, og det andre er repetisjonsfaktoren. Hvis 1 byte er tildelt for å lagre hvert dataelement i inngangssekvensen, vil hele sekvensen oppta 10 byte minne, mens utgangssekvensen (komprimert versjon) vil oppta 8 byte minne. Kompresjonsforholdet, som kjennetegner graden av kompresjon, kan beregnes ved hjelp av formelen:

der Vx er mengden minne som kreves for å lagre utdatasekvensen (resulterende), Vn er inngangsdatasekvensen.

Jo lavere kompresjonsforhold, desto mer effektiv er kompresjonsmetoden. Det er klart at RLE-algoritmen vil gi en bedre komprimeringseffekt når den repeterende datasekvensen er lengre. I tilfellet med eksemplet diskutert ovenfor, hvis inngangssekvensen ser slik ut: 1 1 1 1 1 1 3 4 4 4, vil kompresjonsforholdet være 60 %. I denne forbindelse oppnås større effektivitet av RLE-algoritmen ved komprimering av grafiske data (spesielt for monokromatiske bilder).

Algoritmer til KWE-gruppen

Nøkkelordkomprimeringsalgoritmen er basert på prinsippet om å kode leksikale enheter i grupper av byte med fast lengde. Et eksempel på et leksikalsk element vil være et vanlig ord. I praksis blir repeterende sekvenser av symboler valgt for å spille rollen som leksikale enheter og kodes av en kjede av symboler (kode) med kortere lengde. Kodingsresultatet plasseres i en tabell, og danner en såkalt ordbok.

Det er ganske mange implementeringer av denne algoritmen, blant dem de vanligste er Lempel-Ziv-algoritmen (LZ-algoritmen) og dens modifikasjon, Lempel-Ziv-Welch-algoritmen (LZW-algoritmen). Ordbok i denne algoritmen er en potensielt uendelig liste med setninger. Algoritmen starter med en nesten tom ordbok som kun inneholder én kodet streng, den såkalte NULL-strengen. Når du leser neste tegn i inndatasekvensen, legges det til den gjeldende linjen. Prosessen fortsetter til gjeldende linje samsvarer med en setning fra ordboken. Men før eller siden slutter den nåværende linjen å tilsvare en eller annen ordbokfrase. På punktet der den gjeldende linjen representerer det siste ordboktreffet pluss meldingstegnet som nettopp ble lest, produserer koderen en kode som består av indeksen for treffet og det neste tegnet som brøt linjetreffet. En ny frase, bestående av samsvarsindeksen og følgende tegn, legges til i ordboken. Neste gang denne setningen vises i en melding, kan den brukes til å konstruere en lengre setning, noe som øker graden av komprimering av informasjon.

LZW-algoritmen er bygget rundt en frasetabell (ordbok) som erstatter tegnstrengene til den komprimerte meldingen til koder med fast lengde. Tabellen har den såkalte forhåndsegenskapen, det vil si at for hver frase i ordboken, bestående av en bestemt frase w og symbolet K, legges også frasen w inn i ordboken. Hvis alle deler av ordboken er fullstendig fylt ut, slutter kodingen å være adaptiv (koding skjer basert på fraser som allerede finnes i ordboken).

Komprimeringsalgoritmer for denne gruppen er mest effektive for store tekstdata og er ineffektive for små filer (på grunn av behovet for å lagre ordboken).

Huffman algoritme

Huffman-algoritmen er basert på ideen om bitgruppekoding. Først utføres en frekvensanalyse av inngangsdatasekvensen, det vil si at frekvensen av forekomsten av hvert tegn som finnes i den, blir etablert. Etter dette blir symbolene sortert etter avtagende frekvens.

Den grunnleggende ideen er denne: jo oftere et tegn forekommer, jo færre biter er det kodet. Kodingsresultatet legges inn i ordboken som kreves for dekoding. La oss se på et enkelt eksempel som illustrerer hvordan Huffman-algoritmen fungerer.

La det gis en tekst der bokstaven "A" vises 10 ganger, bokstaven "B" - 8 ganger, "C" - 6 ganger, "D" - 5 ganger, "E" og "F" - 4 ganger hver . Deretter vises et av de mulige kodealternativene ved å bruke Huffman-algoritmen i tabell 1.

Tabell 1.

	Forekomstfrekvens	Bitkode

Som det fremgår av tabell 1 er størrelsen på inndatateksten før komprimering 37 byte, mens den etter komprimering er 93 biter, det vil si ca. 12 byte (ekskludert lengden på ordboken). Kompresjonsforholdet er 32 %. Huffman-algoritmen er universell; den kan brukes til å komprimere data av enhver type, men den er ineffektiv for små filer (på grunn av behovet for å lagre en ordbok).

I praksis syntetiserer datakomprimeringsprogramvare disse tre "rene" algoritmene, siden deres effektivitet avhenger av typen og volumet av data. Tabell 2 viser vanlige komprimeringsformater og de tilsvarende arkiveringsprogrammene som brukes i praksis.

Tabell 2.

Komprimeringsformat	Operativsystem MS DOS		Windows operativsystem
Komprimeringsformat	Arkiveringsprogram	Utpakke program	Arkiveringsprogram	Utpakke program

I tillegg gir moderne arkivere brukeren et komplett spekter av tjenester for arbeid med arkiver, hvorav de viktigste er:

opprette et nytt arkiv;

legge til filer til et eksisterende arkiv;

pakke ut filer fra arkivet;

opprette selvutstrakt arkiver;

opprettelse av distribuerte arkiver av en fast størrelse for små lagringsmedier;

beskytte arkiver med passord mot uautorisert tilgang;

se innholdet i filer i forskjellige formater uten først å pakke ut;

søk etter filer og data inne i arkivet;

se etter virus i arkivet før utpakking;

valg og justering av kompresjonsforholdet.

Kontrollspørsmål

1. Hvilke faktorer påvirker graden av dataredundans? 2. Hva er et arkiv? Hvilke programvareverktøy kalles arkivere? 3. Hvorfor kalles komprimeringsmetoder som endrer datainnholdet irreversible? 4. Gi eksempler på tapsgivende komprimeringsformater. 5. Hva er fordelen med reversible kompresjonsmetoder fremfor irreversible? Hva med ulempen? 6. Hva er forholdet mellom kompresjonsforholdet og effektiviteten til kompresjonsmetoden? 7. Hva er hovedideen til RLE-algoritmen? 8. Hva er hovedideen til KWE-gruppealgoritmene? 9. Hva er hovedideen til Huffman-algoritmen? 10. Hvilke programvarearkivere kjenner du til? Beskriv dem kort.

Datavitenskap. Grunnkurs. / Red. S.V.Simonovich. - St. Petersburg, 2000

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

Simonovich S.V., Evseev G.A., Murakhovsky V.I. Du kjøpte en datamaskin: Den komplette nybegynnerveiledningen til spørsmål og svar. - M.: AST-PRESS BOK; Inforcom-Press, 2001.- 544 s.: ill. (1000 tips).

Kovtanyuk Yu.S., Solovyan S.V. Egen bruksanvisning for arbeid med personlig datamaskin- K.:Junior, 2001.- 560 s., ill.

Jeg og veilederen min holder på å utarbeide en liten monografi om bildebehandling. Jeg bestemte meg for å presentere for habra-fellesskapet et kapittel dedikert til bildekomprimeringsalgoritmer. Siden det er vanskelig å få plass til et helt kapittel i ett innlegg, bestemte jeg meg for å dele det inn i tre innlegg:
1. Datakomprimeringsmetoder;
2. Tapsfri bildekomprimering;
3. Tapsbildekomprimering.
Nedenfor kan du lese det første innlegget i serien.

For tiden er det et stort antall tapsfrie komprimeringsalgoritmer, som kan deles inn i to store grupper:
1. Strøm- og ordbokalgoritmer. Denne gruppen inkluderer algoritmer av RLE (run-length encoding), LZ*, etc. familiene. Et trekk ved alle algoritmer i denne gruppen er at ved koding er det ikke informasjon om frekvensene til symbolene i meldingen som brukes, men informasjon om sekvenser som er påtruffet tidligere.
2. Algoritmer for statistisk (entropi) komprimering. Denne gruppen av algoritmer komprimerer informasjon ved å dra nytte av de uregelmessige frekvensene som forskjellige tegn forekommer med i en melding. Algoritmer i denne gruppen inkluderer aritmetiske og prefikskodingsalgoritmer (ved bruk av Shannon-Fanno, Huffman, sekanttrær).
Algoritmer for å konvertere informasjon kan klassifiseres i en egen gruppe. Algoritmer fra denne gruppen komprimerer ikke direkte informasjon, men bruken av dem forenkler ytterligere komprimering ved bruk av strøm-, ordbok- og entropialgoritmer.

Strøm- og ordbokalgoritmer

Kjørelengdekoding

Run-Length Encoding (RLE) er en av de enkleste og vanligste datakomprimeringsalgoritmene. I denne algoritmen erstattes en sekvens av gjentatte tegn med et tegn og antall ganger den gjentas.
For eksempel kan strengen "AAAAAA", som krever at 5 byte lagres (forutsatt at en byte er allokert til å lagre ett tegn), erstattes med "5A", bestående av to byte. Selvfølgelig er denne algoritmen mer effektiv jo lengre repetisjonsrekke er.

Den største ulempen med denne algoritmen er dens ekstremt lave effektivitet på sekvenser av ikke-repeterende tegn. For eksempel, hvis vi vurderer sekvensen "ABABAB" (6 byte), vil den etter bruk av RLE-algoritmen bli til "1A1B1A1B1A1B" (12 byte). For å løse problemet med ikke-repeterende tegn, er det ulike metoder.

Det meste enkel metode er følgende modifikasjon: byten som koder for antall repetisjoner må lagre informasjon ikke bare om antall repetisjoner, men også om deres tilstedeværelse. Hvis den første biten er 1, indikerer de neste 7 bitene antall repetisjoner av det tilsvarende tegnet, og hvis den første biten er 0, indikerer de neste 7 bitene antall tegn som må tas uten repetisjon. Hvis vi koder "ABABAB" ved å bruke denne modifikasjonen, vil vi få "-6ABABAB" (7 byte). Det er åpenbart at den foreslåtte teknikken betydelig kan øke effektiviteten til RLE-algoritmen på ikke-repeterende tegnsekvenser. Implementeringen av den foreslåtte tilnærmingen er vist i liste 1:

type

funksjon RLEEncode(InMsg: ShortString) : TRLEEncodedString;

MatchFl: boolsk;

MatchCount: shortint ;

EncodedString: TRLEEncodedString;

N, i: byte;

begynne

N:=0;

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

mens lengde(InMsg) >= 1 do

begynne

MatchFl : = (lengde(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

begynne

N:=N+2;

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

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

ellers

begynne

hvis MatchCount<>lengde(InMsg) da

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] ) ;

slutt ;

delete(InMsg, 1, MatchCount) ;

slutt ;

SetLength(EncodedString, N) ;

RLEEncode := EncodedString;

slutt ;

Dekoding av en komprimert melding er veldig enkel og koker ned til en enkelt passering gjennom den komprimerte meldingen, se liste 2:

type

TRLEEncodedString = array av byte;

funksjon RLEDecode(InMsg: TRLEEncodedString) : ShortString;

RepeatCount: shortint ;

i, j: ord;

OutMsg: ShortString;

begynne

OutMsg : = "" ;

i := 0 ;

mens jeg< length(InMsg) do

begynne

RepeatCount : = InMsg[ i] - 128 ;

i: = i + 1;

hvis RepeatCount< 0 then

begynne

RepeatCount := abs (RepeatCount) ;

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

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

i : = i + RepeatCount;

ellers

begynne

for j : = 1 til RepeatCount do

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

i: = i + 1;

slutt ;

slutt ;

RLEDecode := OutMsg;

slutt ;

Den andre metoden for å øke effektiviteten til RLE-algoritmen er å bruke inforsom ikke direkte komprimerer dataene, men bringer dem til en form som er mer praktisk for komprimering. Som et eksempel på en slik algoritme vil vi vurdere BWT-permutasjonen, oppkalt etter oppfinnerne av Burrows-Wheeler-transformasjonen. Denne permutasjonen endrer ikke selve tegnene, men endrer bare rekkefølgen deres i strengen, mens gjentatte understrenger etter bruk av permutasjonen samles inn i tette grupper, som er mye bedre komprimert ved hjelp av RLE-algoritmen. Direkte BWT-konvertering kommer ned til følgende trinn:
1. Legge til den originale strengen et spesielt linjeslutttegn som ikke forekommer andre steder;
2. Innhenting av alle sykliske permutasjoner av den opprinnelige strengen;
3. Sortere de mottatte strengene i leksikografisk rekkefølge;
4. Returnerer den siste kolonnen i den resulterende matrisen.
En implementering av denne algoritmen er vist i oppføring 3.

konst

EOMsg = "|" ;

function BWTEncode(InMsg: ShortString) : ShortString;

OutMsg: ShortString;

LastChar:ANSIChar;

N, i: ord ;

begynne

InMsg : = InMsg + EOMsg;

N : = lengde(InMsg) ;

ShiftTable[ 1 ] : = InMsg;

for i : = 2 til N do

begynne

LastChar : = InMsg[ N];

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

ShiftTable[ i] : = InMsg;

slutt ;

Sort(ShiftTable) ;

OutMsg : = "" ;

for i : = 1 til N do

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

BWTEncode := OutMsg;

slutt ;

Den enkleste måten å forklare denne transformasjonen på er med et spesifikt eksempel. La oss ta strengen "ANANAS" og bli enige om at slutten av strengtegnet vil være tegnet "|". Alle sykliske permutasjoner av denne strengen og resultatet av deres leksikografiske sortering er gitt i tabell. 1.

De. Resultatet av en direkte konvertering er strengen "|NNAAAC". Det er lett å se at denne strengen er komprimert mye bedre enn den originale av RLE-algoritmen, fordi den inneholder lange etterfølger av gjentatte bokstaver.
En lignende effekt kan oppnås ved bruk av andre transformasjoner, men fordelen med BWT-transformasjonen er at den er reversibel, selv om den omvendte transformasjonen er mer komplisert enn den direkte. For å gjenopprette den opprinnelige strengen, må du utføre følgende trinn:
Lag en tom matrise av størrelse n*n, der n er antall tegn i den kodede meldingen;
Fyll den tomme kolonnen lengst til høyre med den kodede meldingen;
Sorter tabellrader i leksikografisk rekkefølge;
Gjenta trinn 2-3 så lenge det er tomme kolonner;
Returner strengen som slutter med linjeslutt-tegnet.

Implementering av omvendt konvertering er ikke vanskelig ved første øyekast, og et av implementeringsalternativene er vist i oppføring 4.

konst

EOMsg = "|" ;

funksjon BWTDecode(InMsg: ShortString) : ShortString;

OutMsg: ShortString;

ShiftTable: array av ShortString;

N, i, j: ord;

begynne

OutMsg : = "" ;

N : = lengde(InMsg) ;

SetLength(ShiftTable, N + 1 ) ;

for i : = 0 til N do

ShiftTable[ i] : = "" ;

for i : = 1 til N do

begynne

for j := 1 til N do

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

Sort(ShiftTable) ;

slutt ;

for i : = 1 til N do

hvis ShiftTable[ i] [ N] = EOMsg da

OutMsg : = ShiftTable[ i] ;

delete(OutMsg, N, 1 );

BWTDecode := OutMsg;

slutt ;

Men i praksis avhenger effektiviteten av den valgte sorteringsalgoritmen. Trivielle algoritmer med kvadratisk kompleksitet vil åpenbart ha en svært negativ innvirkning på ytelsen, så det anbefales å bruke effektive algoritmer.

Etter å ha sortert tabellen oppnådd i det syvende trinnet, må du velge en rad fra tabellen som slutter med tegnet "|". Det er lett å se at dette er den eneste linjen. At. Vi så på BWT-transformasjonen ved å bruke et spesifikt eksempel.

For å oppsummere kan vi si at hovedfordelen med RLE-gruppen av algoritmer er enkelheten og operasjonshastigheten (inkludert dekodingshastighet), og den største ulempen er ineffektivitet på ikke-repeterende tegnsett. Bruken av spesielle permutasjoner øker effektiviteten til algoritmen, men øker også kjøretiden (spesielt dekoding).

Ordbokkomprimering (LZ-algoritmer)

Gruppen av ordbokalgoritmer, i motsetning til algoritmene til RLE-gruppen, koder ikke antall repetisjoner av tegn, men tidligere påtruffet sekvenser av tegn. Mens algoritmene som vurderes kjører, opprettes en tabell dynamisk med en liste over allerede påtruffet sekvenser og deres tilsvarende koder. Denne tabellen kalles ofte en ordbok, og den tilsvarende gruppen av algoritmer kalles ordbok.

Den enkleste versjonen av ordbokalgoritmen er beskrevet nedenfor:
Initialiser ordboken med alle tegn som vises i inndatastrengen;
Finn i ordboken den lengste sekvensen (S) som samsvarer med begynnelsen av den kodede meldingen;
Skriv ut koden til den funnet sekvensen og fjern den fra begynnelsen av den kodede meldingen;
Hvis slutten av meldingen ikke nås, les neste tegn og legg til Sc i ordboken, gå til trinn 2. Ellers avslutt.

For eksempel er den nylig initialiserte ordboken for uttrykket "CUCKOOKOOKUSHONKOKUPILAKAHOOD" vist i tabellen. 3:

Under komprimeringsprosessen vil ordboken bli supplert med sekvenser som finnes i meldingen. Prosessen med å oppdatere ordboken er gitt i tabell. 4.

Ved beskrivelse av algoritmen ble en beskrivelse av situasjonen når ordboken er fullstendig fylt bevisst utelatt. Avhengig av varianten av algoritmen, er forskjellig oppførsel mulig: fullstendig eller delvis tømming av ordboken, slutte å fylle ordboken, eller utvide ordboken med en tilsvarende økning i kodekapasiteten. Hver av disse tilnærmingene har visse ulemper. For eksempel kan stopp av etterfylling av ordboken føre til en situasjon der ordboken lagrer sekvenser som oppstår i begynnelsen av strengen som komprimeres, men som ikke oppstår senere. Samtidig kan rengjøring av ordboken føre til fjerning av hyppige sekvenser. De fleste av implementeringene som brukes, når du fyller ordboken, begynner å overvåke komprimeringsnivået, og når det synker under et visst nivå, blir ordboken gjenoppbygd. Deretter vil vi vurdere den enkleste implementeringen som slutter å oppdatere ordboken når den er full.

Først, la oss definere en ordbok som en post som lagrer ikke bare understrengene som påtreffes, men også antallet understrenger som er lagret i ordboken:

Tidligere påtruffede undersekvenser lagres i Words-matrisen, og koden deres er undersekvensnumrene i denne matrisen.
Vi vil også definere funksjonene for å søke i ordboken og legge til i ordboken:

konst

MAX_DICT_LENGTH = 256 ;

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

r:heltall;

i:heltall ;

fl:boolean ;

begynne

r: = -1;

hvis D. WordCount > 0 da

begynne

i := D. WordCount ;

fl := usant ;

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

begynne

i: = i-1;

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

slutt ;

slutt ;

hvis fl da

r:= i;

FindInDict: = r;

slutt ;

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

begynne

hvis D. WordCount< MAX_DICT_LENGTH then

begynne

D. WordCount : = D. WordCount + 1 ;

SetLength(D. Words, D. WordCount) ;

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

slutt ;

slutt ;

Ved å bruke disse funksjonene kan kodingsprosessen i henhold til den beskrevne algoritmen implementeres som følger:

funksjon LZWEncode(InMsg: ShortString) : TEncodedString;

OutMsg: TEncodedString;

tmpstr: Kortstreng;

D: TDictionary;

i, N: byte;

begynne

SetLength(OutMsg, length(InMsg) );

N:=0;

InitDict(D) ;

mens lengde(InMsg) > 0 gjør

begynne

tmpstr : = InMsg[ 1 ] ;

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

tmpstr : = tmpstr + InMsg[ lengde(tmpstr) + 1 ] ;

if FindInDict(D, tmpstr)< 0 then

delete(tmpstr, lengde(tmpstr) , 1 );

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

N:=N+1;

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

hvis lengde(InMsg) > 0 da

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

slutt ;

SetLength(OutMsg, N) ;

LZWEncode := OutMsg;

slutt ;

Resultatet av kodingen vil være antall ord i ordboken.
Dekodingsprosessen reduseres til direkte dekoding av koder, og det er ikke nødvendig å overføre den opprettede ordboken; det er nok at ordboken initialiseres under dekoding på samme måte som under koding. Deretter vil ordboken bli fullstendig gjenopprettet direkte under dekodingsprosessen ved å sammenkoble forrige undersekvens og gjeldende symbol.

Det eneste problemet er mulig i følgende situasjon: når det er nødvendig å dekode en undersekvens som ennå ikke er i ordboken. Det er lett å se at dette kun er mulig når det er nødvendig å trekke ut en delstreng som skal legges til på det aktuelle trinnet. Dette betyr at delstrengen tilfredsstiller cSc-mønsteret, dvs. begynner og slutter med samme karakter. I dette tilfellet er cS delstrengen som ble lagt til i forrige trinn. Den vurderte situasjonen er den eneste når det er nødvendig å dekode en linje som ennå ikke er lagt til. Med tanke på det ovennevnte, kan vi foreslå følgende alternativ for å dekode en komprimert streng:

funksjon LZWDecode(InMsg: TEncodedString) : ShortString;

D: TDictionary;

OutMsg, tmpstr: ShortString;

i: byte ;

begynne

OutMsg : = "" ;

tmpstr : = "" ;

InitDict(D) ;

for i : = 0 til lengde(InMsg) - 1 do

begynne

hvis InMsg[ i] >= D. WordCount da

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

ellers

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

OutMsg : = OutMsg + tmpstr;

hvis jeg > 0 da

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

slutt ;

LZWDecode := OutMsg;

slutt ;

Fordelene med ordbokalgoritmer inkluderer deres større komprimeringseffektivitet sammenlignet med RLE. Det må imidlertid forstås at den faktiske bruken av disse algoritmene innebærer noen implementeringsvansker.

Entropi koding

Koding ved hjelp av Shannon-Fano-trær

Shannon-Fano-algoritmen er en av de første kompresjonsalgoritmene som ble utviklet. Algoritmen er basert på ideen om å representere hyppigere tegn ved å bruke kortere koder. Dessuten har koder oppnådd ved bruk av Shannon-Fano-algoritmen egenskapen prefiks: dvs. ingen kode er begynnelsen på noen annen kode. Prefiksegenskapen sikrer at kodingen er én-til-én. Algoritmen for å konstruere Shannon-Fano-koder er presentert nedenfor:
1. Del alfabetet i to deler, hvor de totale sannsynlighetene for symbolene er så nær hverandre som mulig.
2. Legg til 0 til prefikskoden til den første delen av tegnene, legg til 1 til prefikskoden til den andre delen av tegnene.
3. Utfør trinn 1-3 rekursivt for hver del (som inneholder minst to tegn).
Til tross for sin komparative enkelhet, er Shannon-Fano-algoritmen ikke uten ulemper, den viktigste av disse er ikke-optimal koding. Selv om partisjonen ved hvert trinn er optimal, garanterer ikke algoritmen et optimalt resultat som helhet. Tenk for eksempel neste linje: "AAAABVGDEZH". Det tilsvarende Shannon-Fano-treet og kodene oppnådd på grunnlag av det er presentert i fig. 1:

Uten bruk av koding vil meldingen oppta 40 biter (forutsatt at hvert tegn er kodet med 4 biter), og ved bruk av Shannon-Fano-algoritmen 4*2+2+4+4+3+3+3=27 biter. Meldingsvolumet gikk ned med 32,5 %, men nedenfor vil vi vise at dette resultatet kan forbedres betydelig.

Koding med Huffman Trees

Huffman-kodealgoritmen, utviklet flere år etter Shannon-Fano-algoritmen, har også egenskapen prefiksitet, og i tillegg bevist minimal redundans, som er det som bestemmer den ekstremt brede distribusjonen. For å få Huffman-koder, bruk følgende algoritme:
1. Alle tegn i alfabetet er representert som frie noder, og vekten av noden er proporsjonal med frekvensen til tegnet i meldingen;
2. Fra settet med frie noder velges to noder med minimal vekt og en ny (overordnet) node opprettes med en vekt lik summen av vektene til de valgte nodene;
3. De valgte nodene fjernes fra den frie listen, og den overordnede noden som er opprettet på grunnlag av dem, legges til denne listen;
4. Trinn 2-3 gjentas til det er mer enn én node i den ledige listen;
5. Basert på det konstruerte treet, blir hvert tegn i alfabetet tildelt en prefikskode;
6. Meldingen er kodet med de mottatte kodene.

La oss vurdere det samme eksempelet som i tilfellet med Shannon-Fano-algoritmen. Huffman-treet og kodene oppnådd for meldingen "AAAABVGDEJ" er presentert i fig. 2:

Det er lett å beregne at volumet til den kodede meldingen vil være 26 biter, som er mindre enn i Shannon-Fano-algoritmen. Separat er det verdt å merke seg at på grunn av populariteten til Huffman-algoritmen, er det for tiden mange alternativer for Huffman-koding, inkludert adaptiv koding, som ikke krever overføring av symbolfrekvenser.
Blant ulempene med Huffman-algoritmen er en betydelig del problemer knyttet til kompleksiteten i implementeringen. Å bruke symboler for reelle variabler for å lagre frekvenser er assosiert med tap av presisjon, så i praksis brukes ofte heltallsvariabler, men siden Vekten til overordnede noder vokser stadig, før eller siden oppstår et overløp. Til tross for enkelheten til algoritmen, kan dens korrekte implementering fortsatt forårsake noen vanskeligheter, spesielt for store alfabeter.

Koding med sekantfunksjonstrær

Koding ved hjelp av sekantfunksjoner er en algoritme utviklet av forfatterne som lar deg få prefikskoder. Algoritmen er basert på ideen om å konstruere et tre, hvor hver node inneholder en sekantfunksjon. For å beskrive algoritmen mer detaljert, er det nødvendig å introdusere flere definisjoner.
Et ord er en ordnet sekvens av m biter (tallet m kalles ordkapasiteten).
En sekantliteral er et par av formen siffer-sifferverdi. For eksempel betyr bokstaven (4,1) at bit 4 i ordet må være 1. Hvis betingelsen for bokstaven er oppfylt, anses bokstaven som sann, ellers er den usann.
En k-bit sekant er et sett med k literaler. Hvis alle bokstaver er sanne, er selve sekantfunksjonen sann, ellers er den usann.

Treet er konstruert slik at hver node deler alfabetet i så nære deler som mulig. I fig. Figur 3 viser et eksempel på et sekanttre:

Treet av sekantfunksjoner i det generelle tilfellet garanterer ikke optimal koding, men det gir ekstremt høy hastighet arbeid på grunn av enkelheten i driften i nodene.

Aritmetisk koding

Aritmetisk koding er en av de mest effektive måter informasjonskomprimering. I motsetning til Huffman-algoritmen, lar aritmetisk koding meldinger kodes med entropi mindre enn 1 bit per tegn. Fordi De fleste aritmetiske kodealgoritmer er beskyttet av patenter; bare de grunnleggende ideene vil bli beskrevet nedenfor.
La oss anta at alfabetet som er i bruk inneholder N symboler a_1,...,a_N, med henholdsvis frekvensene p_1,...,p_N. Da vil den aritmetiske kodingsalgoritmen se slik ut:
Ta som et arbeidshalvt intervall

Komprimering av tomme områder

Å komprimere mellomrom kan beskrives mer generelt som "fjerne det som ikke interesserer oss." Selv om denne metoden er teknisk poeng Selv om syn er en tapskompresjonsteknikk, er den fortsatt nyttig for mange typer datarepresentasjoner som vi møter i den virkelige verden. For eksempel, selv om HTML er mye lettere å lese i et tekstredigeringsprogram når du legger til innrykk og linjeavstand, har ikke noe av dette "hvitrommet" noen effekt på gjengivelsen av HTML-dokumentet i en nettleser. Hvis du vet med sikkerhet at et bestemt HTML-dokument er beregnet utelukkende for nettleseren (eller en slags robot/søkeagent), kan det være lurt å fjerne alt mellomrom slik at dokumentet overføres raskere og tar opp mindre lagringsplass. Alt vi fjerner når vi komprimerer tomme områder, bærer faktisk ingen funksjonell belastning.

Når det gjelder eksemplet som presenteres, kan bare en liten del av informasjonen fjernes fra den beskrevne rapporten. Linjen med "="-symboler langs den øverste kanten av rapporten har ikke noe funksjonelt innhold; det samme gjelder for "-"-tegn i tall og mellomrom mellom tall. Alt dette er nyttig for den som leser den originale rapporten, men har ingen betydning hvis vi anser disse tegnene som "data". Det vi fjerner er ikke akkurat "tomt rom" i tradisjonell forstand, men det er det egentlig.

Komprimering av tomme områder er ekstremt "billig" fra et implementeringssynspunkt. Det er bare et spørsmål om å lese datastrømmen og ekskludere noen få spesifikke verdier fra utdatastrømmen. I mange tilfeller er "utpakking"-trinnet ikke gitt i det hele tatt. Men selv om vi ønsket å gjenskape noe nær den opprinnelige datastrømmen, ville det bare kreve en liten mengde CPU eller minneressurser. De gjenopprettede dataene vil ikke nødvendigvis være de samme som de opprinnelige dataene; det avhenger av hvilke regler og restriksjoner som var inneholdt i originalen. HTML-side, skrevet av en person i en tekstbehandler, vil sannsynligvis inneholde mellomrom ordnet i henhold til visse regler. Det samme gjelder automatiserte verktøy som ofte lager «rimelig» innrykk og mellomrom i HTML-kode. Når det gjelder det stive rapportformatet som presenteres i vårt eksempel, er det ingen grunn til at den opprinnelige representasjonen ikke kunne gjenskapes av en slags "formateringsutpakker".

Gruppekoding

Gruppekoding (RLE) er den enkleste av de mest brukte tapsfrie komprimeringsmetodene. Som å krympe tomme områder, krever det ikke spesielle kostnader, spesielt for dekoding. Tanken bak denne metoden er at mange datarepresentasjoner hovedsakelig består av strenger med repeterende byte. Eksempelrapporten vår er en slik datavisning. Den starter med en streng med gjentatte "="-tegn og har linjer med kun mellomrom spredt over hele rapporten. I stedet for å representere hvert tegn med sin egen byte, innebærer RLE-metoden (noen ganger eller alltid) å spesifisere antall repetisjoner, etterfulgt av tegnet som skal spilles det antallet ganger.

Hvis dataformatet som behandles domineres av gjentatte byte, kan det være hensiktsmessig og effektivt å bruke en algoritme der én eller flere byte indikerer antall repetisjoner, etterfulgt av tegnet som gjentas. Men hvis du har tegnstrenger med enhetslengde, vil det ta to (eller flere) byte å kode dem. Med andre ord kan ett ASCII-tegn "X" i inngangsstrømmen kreve en utdatabitstrøm på 00000001 01011000. På den annen side vil koding av hundre påfølgende "X"-tegn bruke samme antall biter: 01100100 01011000 , noe som er ganske effektivt.

Ulike varianter av RLE bruker ofte selektivt byte for å indikere antall repetisjoner, mens de gjenværende bytene ganske enkelt representerer seg selv. For dette formålet må minst én enkeltbyte-verdi reserveres, som om nødvendig kan fjernes fra utgangen. For eksempel, i vår eksempeltelefonnummerrapport, vet vi at all informasjonen i inndatastrømmen består av enkle ASCII-tegn. Spesielt har alle slike tegn den første biten av ASCII-verdien lik 0. Vi kan bruke denne første ASCII-biten til å indikere at byten angir antall repetisjoner i stedet for et vanlig tegn. De neste syv bitene av iteratorbyten kan brukes til å indikere antall repetisjoner, og neste byte kan inneholde tegnet som gjentas. Så, for eksempel, kan vi representere strengen "YXXXXXXXX" som følger:

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

Dette eksemplet forklarer ikke hvordan man forkaster iteratorbyteverdier, og gir heller ikke mulighet for å bruke mer enn 127 repetisjoner av et enkelt tegn. Imidlertid løser ulike varianter av RLE, om nødvendig, disse problemene.

Huffman-koding

Huffman-koding behandler symboltabellen som et helt sett med data. Komprimering oppnås ved å finne "vektene" til hvert tegn i datasettet. Noen tegn brukes oftere enn andre, så Huffman-koding antar at hyppige tegn skal kodes i færre biter enn mindre vanlige tegn. Eksistere ulike alternativer Huffman-koding, men den originale (og mest brukte) versjonen innebærer å finne det vanligste tegnet og kode det med en enkelt bit, for eksempel 1. Og hvis en 0 forekommer i den kodede sekvensen, betyr dette at det på dette stedet er et annet tegn kodet med et stort antall biter.

La oss forestille oss at vi brukte Huffman-koding for å kode eksemplet vårt (forutsatt at vi allerede hadde utsatt rapporten for komprimering av mellomrom). Vi kan få følgende resultat:

Tabell 2. Huffman-kodingsresultater

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

Det originale tegnsettet (bestående av tall) kan enkelt kodes (uten komprimering) som 4-bits sekvenser (nibbles). Følgende Huffman-koding vil bruke opptil 5 bits for tegn i verste fall, noe som åpenbart er verre enn nibble-koding. Men i beste fall er alt som kreves 1 bit; det er kjent at det er det beste tilfellet som vil bli brukt oftest (siden dette er symbolet som dukker opp oftest i dataene). Så vi kan kode et spesifikt telefonnummer som dette:

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

Hvis det er kodet med nibbles, vil representasjonen av telefonnummeret ta 28 biter, men i vårt tilfelle tar kodingen 19 biter. Mellomrom er lagt til i eksemplet bare for bedre forståelse; deres tilstedeværelse i de kodede symbolene er ikke nødvendig, siden det alltid er mulig å bestemme fra kodetabellen om slutten av det kodede symbolet er nådd eller ikke (det er imidlertid fortsatt nødvendig å holde styr på gjeldende posisjon i dataene ).

Huffman-koding er fortsatt veldig "billig" å dekode når det gjelder CPU-tid. Det krever imidlertid et kodebokoppslag, så det er kanskje ikke så "billig" som RLE. Huffman-koding er ganske dyrt, siden det krever en full skanning av dataene og konstruksjon av en tabell med symbolfrekvenser. I noen tilfeller, når du bruker Huffman-koding, er en "snarvei" passende. Standard Huffman-koding brukes på det spesifikke datasettet som kodes, med utdata først etterfulgt av en symboltabell. Men hvis ikke et enkelt sett med data overføres, men et helt format med de samme mønstrene for forekomst av tegn, kan den globale Huffman-tabellen brukes. Gitt en slik tabell kan vi hardkode søk i våre kjørbare filer, noe som vil gjøre komprimering og dekompresjon mye "billigere" (minus den innledende globale samplingen og hardkodingen). For eksempel, hvis vi vet at datasettet vårt vil være prosa i engelske språk, da er frekvensene for forekomst av bokstaver velkjente og konstante for forskjellige datasett.

Komprimering ved hjelp av Lempel-Ziv-algoritmen

Sannsynligvis den viktigste tapsfrie komprimeringsmetoden er Lempel-Ziv-algoritmen. I denne artikkelen vi vil snakke om LZ78-varianten, men LZ77 og andre varianter fungerer på lignende måte. Ideen bak LZ78-algoritmen er å kode en strømsekvens av byte ved å bruke en dynamisk tabell. Ved starten av bitstrømkomprimering er LZ-tabellen fylt med det faktiske tegnsettet, sammen med noen få tomme spor. Algoritmen bruker tabeller forskjellige størrelser, men i dette eksemplet med telefonnumre (med tomromskomprimering) brukes en tabell med 32 elementer (nok for dette eksemplet, men er kanskje ikke nok for andre datatyper). Først fyller vi de ti første sporene med tegnene i alfabetet som brukes (tall). Når nye byte ankommer, hentes først tabellverdien som tilsvarer den lengste matchende sekvensen, og deretter skrives sekvensen med lengde N+1 til neste tilgjengelige spor. I verste fall bruker vi 5 bits i stedet for 4 for et enkelt tegn, men i de fleste tilfeller klarer vi oss med 5 bits for flere tegn. La oss se på et eksempel på hvordan denne algoritmen fungerer (bordsporet er indikert i firkantede parenteser):

7 --> Søk: 7 funnet --> ingenting å legge til --> fortsett søket 7 --> Søk: 77 ikke funnet --> legg til "77" til --> display =00111 2 --> Søk: 72 ikke funnet --> legg til "72" til --> display =00111 7 --> Søk: 27 ikke funnet --> legg til "27" til --> display =00010 6 --> Søk: 76 ikke funnet --> legg til "76" til --> display =00111 2 --> Søk: 62 ikke funnet --> legg til "62" til --> display =00110 8 --> Søk: 28 ikke funnet --> legg til "28" til --> utgang =00010

Vi har ikke fått noe utbytte av dette så langt, men la oss gå videre til neste telefonnummer:

7 --> Søk: 87 ikke funnet --> legg til "87 til --> display =00100 7 --> Søk: 77 funnet --> ingenting å legge til --> fortsett søket 2 --> Søk: 772 ikke funnet - -> legg til "772" til --> output =01011 8 --> Søk: 28 funnet --> ingenting å legge til --> fortsett søket 6 --> Søk: 286 ikke funnet --> legg til "286" til -- > utgang =10000 ....

Ovennevnte operasjoner bør være tilstrekkelige til å demonstrere funksjonen til modellen. Selv om ingen merkbar komprimering ennå er oppnådd, kan det allerede sees at vi har gjenbrukt sporene 11 og 16, som koder for to symboler hver med ett utgangssymbol. I tillegg har vi allerede samlet en ekstremt nyttig sekvens av byte 772 i spor 18, som deretter vil vises gjentatte ganger i strømmen.

LZ78-algoritmen fyller én symboltabell med (antagelig) nyttige oppføringer, skriver deretter tabellen, sletter den og starter en ny. I en slik situasjon er det kanskje ikke tilstrekkelig med en tabell på 32 tegn, siden den vil bli tømt før vi gjentatte ganger kan bruke sekvenser som 772 og lignende. Men ved hjelp av en liten tabell er det lettere å illustrere algoritmens virkemåte.

I typiske datasett oppnår varianter av Lempel-Ziv-metoden betydelig mer høye odds kompresjon enn Huffman- og RLE-metoder. På den annen side bruker varianter av Lempel-Ziv-metoden betydelige ressurser på iterasjoner, og tabellene deres kan ta opp mye minneplass. Mest eksisterende verktøy og komprimeringsbiblioteker bruker en kombinasjon av Lempel-Ziv- og Huffman-metodene.

Riktig problemstilling

Ved å velge riktig algoritme kan du oppnå betydelige gevinster selv sammenlignet med mer optimaliserte, men upassende metoder. Lignende riktig valg datapresentasjon er ofte viktigere enn valg komprimeringsmetoder (som alltid er en slags påfølgende optimalisering av de nødvendige funksjonene). Det enkle eksempeldatasettet i denne artikkelen gir en utmerket illustrasjon av en situasjon der det å tenke nytt om et problem er en bedre løsning enn å bruke noen av de gitte kompresjonsmetodene.

Det er nødvendig å ta en ny titt på problemet som dataene utgjør. Siden dette ikke er et generelt datasett og det er klare forutsetninger for det, kan problemstillingen omformuleres. Det er kjent at det er maksimalt 30 000 telefonnumre (fra 7720000 til 7749999), hvorav noen er aktive og noen ikke. Vi står ikke overfor oppgaven med å vise en fullstendig representasjon av alle aktive tall. Vi trenger bare å indikere å bruke en boolsk verdi, aktiv dette nummeret eller ikke. Når vi tenker på problemet på denne måten, kan vi ganske enkelt allokere 30 000 biter i minne og lagring og bruke hver bit til å indikere aktiviteten (ja eller nei) til det tilsvarende telefonnummeret. Rekkefølgen på bitene i punktgrafikken kan tilsvare telefonnumre, sortert i stigende rekkefølge (laveste til høyeste).

En slik bitmapbasert løsning er ideell fra alle synsvinkler. Det krever nøyaktig 3750 byte for å representere datasettet; forskjellige komprimeringsmetoder vil bruke varierende volum avhengig av antall telefonnumre i settet og effektiviteten til komprimeringen. Men hvis 10 000 av de 30 000 mulige telefonnumrene er aktive, og selv om du effektiv metode komprimering krever flere byte per telefonnummer, så vinner bitmapet definitivt. Når det gjelder CPU-krav, er ikke bare bitmap overlegen noen av komprimeringsmetodene som er diskutert, men det er også bedre enn normal metode representasjon av telefonnumre som strenger (uten komprimering). Å krysse punktgrafikken og øke gjeldende telefonnummerteller kan gjøres effektivt selv i den innebygde hurtigbufferen til moderne prosessorer.

Fra dette enkelt eksempel Du kan forstå at ikke alle problemer har en så ideell løsning som den som er diskutert ovenfor. Mange problemer krever betydelige mengder minne, båndbredde, lagring og CPU-ressurser; og i de fleste slike tilfeller kan kompresjonsteknikker lindre eller redusere disse kravene. Men det viktigere er at før du bruker komprimeringsteknikker, bør du dobbeltsjekke at du har valgt riktig konsept for å representere dataene dine.

Dedikert til minnet om Claude Shannon.

For mennesker er dataredundans ofte forbundet med informasjonskvalitet, siden redundans har en tendens til å forbedre forståeligheten og oppfatningen av informasjon. Men når det gjelder lagring og overføring av informasjon ved hjelp av datateknologi, spiller redundans en negativ rolle, siden det fører til en økning i kostnadene ved lagring og overføring av informasjon. Dette problemet blir spesielt relevant ved behandling av store mengder informasjon med ubetydelige mengder lagringsmedier. I denne forbindelse oppstår problemet med å redusere redundans eller datakomprimering konstant. Hvis datakomprimeringsmetoder brukes på ferdige filer, brukes ofte i stedet for begrepet "datakomprimering" begrepet "dataarkivering"; den komprimerte versjonen av dataene kalles arkiv, og programvare som implementerer komprimeringsmetoder kalles arkivarer.

Avhengig av objektet som dataene som skal komprimeres er plassert i:

1. Komprimering (arkivering) av filer: brukes til å redusere størrelsen på filer når de klargjøres for overføring via kommunikasjonskanaler eller for transport på eksterne medier med liten kapasitet;

2. Komprimering (arkivering) av mapper: brukes som et middel for å redusere volumet av mapper før langtidslagring, for eksempel under sikkerhetskopiering;

3. Komprimering (komprimering) av disker: brukes til å øke effektiviteten ved å bruke diskplass ved å komprimere data når du skriver det til et lagringsmedium (vanligvis ved bruk av operativsystemet).

· JPEG - for grafiske data;

· MPG - for videodata;

· MP3 - for lyddata.

· GIF, TIFF - for grafiske data;

· AVI - for videodata;

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

Tabell 2 viser vanlige komprimeringsformater og de tilsvarende arkiveringsprogrammene som brukes i praksis.

Moderne arkivarer

Spesialprogrammer

Forelesning 6

Arkivere er programmer for å lage arkiver. Arkiver er designet for å lagre data i en praktisk, kompakt form. Dataene er vanligvis filer og mapper. Som regel utsettes data først for komprimering eller pakking. Derfor er nesten hver arkiver også et datakomprimeringsprogram. På den annen side kan ethvert datakomprimeringsprogram betraktes som en arkiver. Kompresjonseffektivitet er den viktigste egenskapen arkivere. Størrelsen avhenger av det opprettet arkiver. Jo mindre arkivet er, jo mindre plass kreves det for å lagre det. Overføring krever mindre overføringskanalbåndbredde eller tar kortere tid. Fordelene med arkiver er åpenbare, med tanke på at dataene er redusert i størrelse med 2 ganger og 5 ganger.

Datakomprimering brukes veldig mye. Du kan si nesten overalt. For eksempel, PDF-dokumenter, som regel inneholder komprimert informasjon. Ganske mange kjørbare EXE-filer komprimert med spesialpakkere. Alle typer multimediefiler (GIF, JPG, MP3, MPG) er en slags arkiver.

Den største ulempen med arkiver er manglende evne til direkte adgang til dataene. De må først hentes ut av arkivet eller pakkes ut. Utpakkingsoperasjonen krever imidlertid noe, i likhet med emballasje systemressurser. Dette er ikke en øyeblikkelig operasjon. Derfor brukes arkiver hovedsakelig med relativt lite brukte data. For eksempel for å lagre sikkerhetskopier eller installasjonsfiler.

Det er mange arkivere der ute for tiden. De varierer i utbredelse og effektivitet. Noen interessante arkivere er ikke kjent for et bredt spekter av potensielle brukere. Av spesiell interesse er evaluering og sammenligning av komprimeringseffektiviteten til populære arkivere.

Et stort antall forskjellige metoder, deres modifikasjoner og undertyper for datakomprimering er utviklet. Moderne arkivere har en tendens til å bruke flere metoder samtidig. Vi kan trekke frem noen grunnleggende.

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

En veldig enkel metode. En sekvensiell serie med identiske dataelementer erstattes av to tegn: elementet og antall ganger det forekommer. Mye brukt som tilleggs- og mellommetode. Som en uavhengig metode brukes den for eksempel i grafisk format BMP.

Ordbokmetode (LZ - forkortelse for Lempel Ziv - navn på forfattere)

Den vanligste metoden. Det brukes en ordbok som består av sekvenser av data eller ord. Under komprimering erstattes disse ordene med kodene deres fra ordboken. I den vanligste implementeringen er selve ordboken original blokk data.

Hovedparameteren til ordbokmetoden er størrelsen på ordboken. Jo større ordforråd, jo større effektivitet. For heterogene data er det imidlertid overdrevet stor størrelse kan være skadelig, siden hvis datatypen endres brått, vil ordboken bli fylt med irrelevante ord. For at denne komprimeringsmetoden skal fungere effektivt, kreves det ekstra minne. Omtrent en størrelsesorden større enn nødvendig for de originale ordbokdataene. En betydelig fordel med ordbokmetoden er den enkle og raske utpakkingsprosedyren. Ingen ekstra minne er nødvendig. Denne funksjonen er spesielt viktig hvis rask tilgang til data er nødvendig.

Entropimetode (Huffman - Huffman-koding, aritmetisk koding - aritmetisk koding)

I denne metoden blir dataelementer som forekommer oftere kodet med en kortere kode under komprimering, og mindre vanlige dataelementer kodes med en lengre kode. På grunn av det faktum at det er betydelig flere korte koder, Generell størrelse blir mindre enn originalen.

Mye brukt som en tilleggsmetode. Som en uavhengig metode brukes den for eksempel i JPG-grafikkformatet.

Kontekstmodelleringsmetode (CM - forkortelse for kontekstmodellering - kontekstmodellering)

I denne metoden bygges en modell av kildedataene. Når det neste dataelementet komprimeres, produserer denne modellen sin prediksjon eller sannsynlighet. I henhold til denne sannsynligheten er dataelementet kodet ved hjelp av entropimetoden. Hvordan mer presist modellen vil matche de originale dataene, jo mer nøyaktig vil det produsere spådommer, og jo kortere vil dataelementene bli kodet.

Å bygge en effektiv modell krever mye minne. Ved utpakking må du bygge nøyaktig samme modell. Derfor er hastigheten og volumkravene tilfeldig tilgang minne for pakking og utpakking er nesten det samme. For øyeblikket lar kontekstmodelleringsmetoder oss oppnå beste grad kompresjon, men har ekstremt lav hastighet.

PPM (PPM – Prediction by Partial Matching)

Dette er en spesiell undertype av kontekstmodellering. Forutsigelsen er laget basert på et visst beløp tidligere dataelementer. Hovedparameteren er rekkefølgen til modellen, som setter dette antallet elementer. Jo høyere modellrekkefølge, jo høyere komprimeringsforhold, men mer RAM kreves for å lagre modelldata. Hvis det ikke er nok RAM, viser en slik modell med en stor ordre dårlige resultater. PPM-metoden er spesielt effektiv for å komprimere tekstdata.

Fortransformasjoner eller filtrering

Disse metodene brukes ikke til komprimering, men for å presentere informasjon i en form som er praktisk for videre komprimering. For eksempel er ukomprimerte multimediedata preget av jevne endringer signalnivå. Derfor brukes en deltatransformasjon for dem, når en relativ verdi tas i stedet for en absolutt verdi. Det er filtre for tekst, kjørbare filer, databaser og andre.

Blokksorteringsmetode (BWT - forkortelse for Burrows Wheeler Transform - ved navn på forfatterne)

Dette er en spesiell type eller gruppe transformasjoner basert på sortering. Nesten alle data kan bli utsatt for denne transformasjonen. Sortering skjer over blokker, så dataene deles først inn i deler. Hovedparameteren er størrelsen på blokken som sorteres. For å pakke ut data må du gjøre nesten de samme trinnene som når du pakker. Derfor er hastigheten og RAM-kravene nesten de samme. Arkivere som bruker denne metoden, viser vanligvis høy hastighet og komprimeringsforhold for tekstdata.

Kontinuerlige blokker eller kontinuerlig modus (solid modus - kontinuerlig modus)

I mange komprimeringsmetoder er den første delen av dataene eller filen dårlig kodet. For eksempel, i ordbokmetoden er ordboken tom. I kontekstmodelleringsmetoden bygges ikke en modell. Når antallet filer er stort og størrelsen er liten, blir det totale komprimeringsforholdet betydelig redusert på grunn av disse innledende delene. For å forhindre at dette skjer når du bytter til neste fil, informasjon innhentet basert på tidligere filer. En lignende effekt kan oppnås enkel presentasjon kildefiler som én kontinuerlig fil.

Denne metoden brukes i mange arkivere og har betydelig ulempe. For å pakke ut en vilkårlig fil, må du også pakke ut filene som er i begynnelsen av arkivet. Dette er nødvendig for å riktig fylle ut ordboken eller bygge en modell. Det er også et mellomalternativ når det brukes kontinuerlige blokker med fast størrelse. Kompresjonstap er minimale, men for å pakke ut en fil som er på slutten stort arkiv, bare én sammenhengende blokk må pakkes ut, ikke hele arkivet.

Segmentering

I alle komprimeringsmetoder, når du endrer datatypen, er selve overgangen kodet svært dårlig. Ordboken blir irrelevant, modellen er konfigurert for andre data. I disse tilfellene brukes segmentering. Dette er en foreløpig oppdeling i homogene deler. Disse delene kodes så individuelt eller i grupper.