Algoritmi kompresije: opis, osnovne tehnike, karakteristike

Kompresija je poseban slučaj kodiranja, čija je glavna karakteristika da je dobijeni kod manji od originalnog. Proces se zasniva na traženju ponavljanja u informativnim redovima, a zatim na čuvanju samo jednog pored broja ponavljanja. Tako, na primjer, ako se niz pojavi u datoteci kao" AAAAAA", koji zauzima 6 bajtova, bit će spremljen kao" 6A", koji zauzima samo 2 bajta, u algoritmu kompresije RLE.

Istorija procesa

Morzeova azbuka, izumljena 1838. godine, prvi je poznati slučaj kompresije podataka. Kasnije, kada su mainframe Računari počeli da dobijaju popularnost 1949. godine, Claude Shannon i Robert Fano izmislili su kodiranje, nazvano po autorima-Shannon-Fano. Ova enkripcija dodjeljuje kodove simbolima u nizu podataka prema teoriji vjerovatnoće.

Tek 1970-ih, sa pojavom interneta i online memorije, implementirani su punopravni algoritmi kompresije. Huffman kodovi su dinamički generisani na osnovu ulaznih informacija. Ključna razlika između Shannon-Fano kodiranja i Huffmanovog kodiranja je u tome što je u prvom, stablo vjerovatnoće izgrađeno odozdo prema gore, stvarajući suboptimalni rezultat, a u drugom odozgo prema dolje.

1977. godine Abraham Lempel i Jacob Ziv objavili su svoju inovativnu metodu LZ77, koristeći moderniziraniji rječnik. 1978. godine isti tim autora objavio je poboljšani algoritam kompresije LZ78. Koji koristi novi rečnik koji analizira ulazne podatke i generiše statički rečnik, a ne dinamički, kao u verziji 77.

Oblici izvršenja kompresije

Kompresiju vrši program koji koristi formulu ili algoritam koji određuje, kako smanjiti za smanjenje Veličina podataka. Na primjer, za predstavljanje niza bitova s manjim nizom 0 i 1, koristeći rječnik za transformacije ili formulu.

Kompresija može biti jednostavna. Takav, na primjer, kako izbrisati sve nepotrebni znakovi, umetnite jedan kod koji se ponavlja da odredite niz ponavljanja i zamijenite manji bitni niz. Algoritam kompresije datoteka može smanjiti tekstualni fajl do 50% ili znatno više.

Za prenos, proces se izvodi u bloku prenosa, uključujući podatke zaglavlja. Kada se informacije šalju ili primaju putem interneta, arhivirane pojedinačno ili zajedno sa drugim velikim fajlovima mogu se prenijeti u ZIP, GZIP ili drugom "smanjen" format.

Prednost algoritama kompresije:

1. Značajno smanjuje količinu memorije. Sa omjerom kompresije 2: 1, fajl Od 20 megabajta (MB) će zauzimati 10 MB prostora. Kao rezultat toga, mrežni administratori troše manje novca i vremena na čuvanje baze podataka.
2. Optimizira performanse sigurnosne kopije.
3. Važna metoda smanjenja podataka.
4. Gotovo svaki fajl se može komprimovati, ali je važno izabrati pravu tehnologiju za određeni tip datoteke. U suprotnom datoteke mogu biti "smanjen", ali ukupna veličina se neće promijeniti.

Koriste se dvije vrste metoda - algoritmi kompresije bez gubitaka i gubitaka. Prvi vam omogućava da vratite fajl u prvobitno stanje bez gubitka ni malo informacija kada je datoteka nekomprimovana. Drugi - jedan je tipičan , pristup izvršnim fajlovima, tekstu i tabelama, gde će gubitak reči ili brojeva dovesti do promene informacija.

Kompresija sa gubicima trajno uklanja dijelove podataka koji su suvišni, nevažni ili neupadljivi. Koristan je sa grafikom, audio, video i slikama, gde uklanjanje nekih bitova gotovo da nema primetan efekat na prezentaciju sadržaja.

Huffman Algoritam Kompresije

Ovo je proces koji se može koristiti za "smanji" ili šifrirajte.

Zasniva se na dodjeli kodova različitih dužina bita svakom ponavljajućem znaku, što je više takvih ponavljanja, to je veći omjer kompresije. Da biste vratili originalni fajl, morate znati dodijeljeni kod i njegovu dužinu u bitovima. Slično tome, upotrijebite program za šifriranje datoteka.

Redoslijed kreiranja algoritama kompresije podataka:

1. Izračunajte koliko se puta svaki znak ponavlja u datoteci do "smanji".
2. Kreirajte povezanu listu sa informacijama o simbolima i frekvencijama.
3. Sortirajte listu od najmanje do najveće, ovisno o učestalosti.
4. Pretvorite svaku stavku na listi u drvo.
5. Kombinirajte drveće u jedno, dok prva dva čine novo.
6. Dodajte frekvencije svake grane u novi element stabla.
7. Umetnite novu na pravo mjesto na listi, prema zbiru primljenih frekvencija.
8. Dodijelite novi binarni kod za svaki znak. Ako se uzme nulta grana, kodu se dodaje nula, a ako se uzme prva grana, dodaje se jedna.
9. Datoteka se prekodira prema novim kodovima.
10. Na primjer, karakteristike algoritama kompresije za kratki tekst:"ata la jaca a la estaca"
11. Izbrojite koliko se puta svaki znak pojavi i napravite povezanu listu:" (5), a(9), c(2), e(1), j(1), l(2), s(1), t(2)
12. Poredano po frekvenciji od najniže do najviše: e(1), j (1), s(1), c (2), l (2), t(2), "(5), a (9)

Kao što vidite, korijenski čvor stabla je kreiran, a zatim se dodjeljuju kodovi.

I ostaje samo spakovati bitove u grupe od osam, odnosno u bajtove:

01110010	11010101	11111011	00010010	11010101	11110111	10111001	10000000
0x72	0xd5	0xFB	0x12	0xd5	0xF7	0xB9	0x80

Samo osam bajtova, a originalni tekst 23.

Demonstracija biblioteke LZ77

Razmotrite LZ77 algoritam na primjer teksta"howtogeek". Ako se ponovi tri puta, promijenit će se na sljedeći način.

Zatim, kada želi da pročita tekst nazad, zameniće svaku instancu (h) sa "howtogeek", vraćajući se na originalnu frazu. Ovo pokazuje algoritam kompresije podataka bez gubitaka, budući da se uneseni podaci podudaraju sa primljenim podacima.

Ovo je savršen primjer kada je većina teksta komprimirana s nekoliko znakova. Na primjer, riječ" ovo " će biti komprimirana, čak i ako se pojavljuje u riječima kao što su "ovo"," njihovo "i"ovo". Sa ponovljenim riječima možete dobiti ogromne omjere kompresije. Na primjer, tekst s riječju" howtogeek " ponovljenom 100 puta ima veličinu od tri kilobajta, pri komprimiranju će biti potrebno samo 158 bajtova, odnosno sa 95% "smanjenje".

Ovo je, naravno, prilično ekstreman primjer, ali jasno pokazuje svojstva algoritama kompresije. U opštoj praksi, to je 30-40% sa zip formatom teksta. LZ77 algoritam se odnosi na sve binarne podatke, a ne samo na tekst, iako je potonje lakše komprimirati zbog ponovljenih riječi.

Diskretna kosinusna transformacija slika

Video i audio kompresije funkcioniše sasvim drugačije. Za razliku od teksta, gdje se izvode algoritmi kompresije bez gubitaka, a podaci se neće izgubiti, sa slikama ", vrši se smanjenje gubitaka" , i što je veći %, to je veći gubitak. To dovodi do onih JPEG datoteka užasnog izgleda koje su ljudi nekoliko puta učitavali, razmjenjivali i snimali snimke ekrana.

Većina slika, fotografija i drugih stvari čuva listu brojeva, od kojih svaki predstavlja jedan piksel. JPEG ih sprema koristeći algoritam kompresije slike koji se zove diskretna kosinusna transformacija. To je skup sinusoidnih talasa koji se zbrajaju različitog intenziteta.

Ova metoda koristi 64 različite jednačine, a zatim Huffman kodiranje za dodatno smanjenje veličine datoteke. Takav algoritam kompresije slike daje suludo visok omjer kompresije i smanjuje ga sa nekoliko megabajta na nekoliko kilobajta, ovisno o potrebnoj kvaliteti. Većina fotografija je komprimirana kako bi se uštedjelo vrijeme učitavanja, posebno za mobilne korisnike sa lošim prijenosom podataka.

Video zapisi funkcionišu malo drugačije od slika. Tipično, algoritme za kompresiju grafičkih informacija koristi ono što se naziva "kompresija među kadrovima", koja izračunava promjene između svakog kadra i pohranjuje ih. Tako, na primer, , ako postoji relativno još uvek snimljen koji traje nekoliko sekundi u videu, hoće "biti smanjen" po jedan. Inter-frame kompresije pruža digitalni TV i web video. Bez toga, video bi težio stotinama gigabajta, što je više od prosječne veličine čvrstog diska 2005. godine.

Audio kompresija funkcioniše veoma slično kompresiji teksta i slike. Ako JPEG ukloni detalje sa slike koji nisu vidljivi ljudskom oku, audio kompresija čini isto za zvukove. MP3 koristi brzinu prijenosa u rasponu od nižeg nivoa od 48 i 96 kbit/s (donja granica) do 128 i 240 kbit/s (prilično dobro) do 320 kbit / s (zvuk visokog kvaliteta), A razliku možete čuti samo sa izuzetno dobrim slušalicama. Postoje kompresijski kodeci bez gubitaka za zvuk, od kojih je glavni FLAC i koristi LZ77 kodiranje za prijenos zvuka bez gubitaka.

"" Formati Za Smanjenje Teksta

Raspon biblioteka za tekst uglavnom se sastoji od algoritma kompresije podataka bez gubitaka, osim u ekstremnim slučajevima za podatke s pomičnim zarezom. Većina kompresorskih kodeka uključuje "smanjenje" LZ77, Huffman i aritmetičko kodiranje. Primjenjuju se nakon drugih alata za istiskivanje još nekoliko postotnih tačaka kompresije.

Niz vrijednosti su kodirani kao znak praćen dužinom pokretanja. Can originalni stream biti ispravno obnovljena. Ako je dužina serije<= 2 znaka, ima smisla ostaviti ih nepromijenjene, na primjer, kao na kraju streama sa "bb".

U nekim rijetkim slučajevima, dodatna ušteda se postiže primjenom transformacije sa algoritmima kompresije sa gubicima na dijelove sadržaja prije primjene metode bez gubitaka. Pošto se fajlovi u ovim konverzijama ne mogu vratiti u prvobitno stanje, ovi "moji procesi" rezervisani su za tekstualne dokumente. Koji neće patiti od gubitka informacija, na primjer, skraćivanje cifara s pomičnim zarezom na samo dvije značajne decimale.

Danas većina sistema za kompresiju teksta radi kombinovanjem različitih transformacija podataka kako bi se postigli maksimalni rezultati. Poanta svake faze sistema je izvesti transformaciju na takav način da sljedeća faza može nastaviti efikasnu kompresiju. Sumiranje ovih koraka daje mali fajl koji se može vratiti bez gubitka. Postoje doslovno stotine formata i kompresijskih sistema, od kojih svaki ima svoje prednosti i nedostatke u odnosu na različite vrste podataka.

HTTP šeme: ispuhati i GZIP

Danas se na Internetu koriste dva široko korištena http algoritma za kompresiju teksta: DEFLATE i GZIP.

DEFLATE - obično kombinuje podatke, koristeći LZ77, Huffman kodiranje. Gzip datoteka koristi ispuhivanje interno, zajedno sa nekim zanimljivim bravama, filtriranjem heuristike, zaglavlja i kontrolne sume. Općenito, dodatno zaključavanje i heuristika pomoću GZIP-a daju bolje omjere kompresije od samo jednog ISPUHIVANJA.

Protokoli podataka sljedeće generacije - SPDY i HTTP2.0, podržava kompresiju zaglavlja koristeći GZIP, tako da će ga većina web steka koristiti u budućnosti.

Većina programera jednostavno učitava nekomprimovani sadržaj i oslanja se na web server na "smanji" podaci o letu. Ovo daje odlične rezultate i algoritam jednostavan za korištenje za komprimiranje grafičkih slika. Podrazumevano, mnogi serveri imaju instaliran GZIP sa nivoom 6, od kojih je najviši nivo 9. Ovo se radi namjerno, što omogućava serverima da brže komprimiraju podatke zbog veće izlazne datoteke.

Bzip2 i LZMA formati koji stvaraju kompaktnije forme od GZIP-a, koji se istovremeno brže dekomprimiraju.

LZMA se može smatrati dalekim srodnikom GZIP-a. Obojica počinju sa Popular dictionary LZ slijedi statistički sistem kodiranja. Međutim, poboljšana LZMA sposobnost komprimiranja malih datoteka leži u njenim " naprednim LZ mapiranjem i algoritmima prozora.

Predobrada dokumenta

Za visokokvalitetnu kompresiju vrši se dvostepeni proces:

• faza minimizacije;
• faza bez gubitaka.

Minifikacija smanjuje veličinu podataka tako da se mogu koristiti bez obrade, brišući mnogo nepotrebnih stvari u datoteci bez sintaktičke promjene. Dakle, sigurno je ukloniti većinu razmaka iz Jscript-a, smanjujući veličinu bez promjene sintakse. Minifikacija se vrši tokom procesa izgradnje. Bilo kao ručni korak ili kao deo automatizovanog lanca izgradnje.

Postoji mnogo programa koji izvode osnovne algoritme kompresije, među njima:

1. Winzip je format za pohranu bez gubitaka koji se široko koristi za dokumente, slike ili aplikacije. Ovo je prilično jednostavan program koji komprimira svaku od datoteka pojedinačno, što vam omogućava da svaku vratite bez potrebe za čitanjem ostalih. Time se povećava produktivnost procesa.
2. 7zip je besplatan menadžer za veoma moćan i najjednostavniji algoritam kompresije informacija. Zahvaljujući formatu datoteke 7z, koji poboljšava ZIP standard za 50%. Podržava druge najčešći formati kao što su RAR, ZIP, CAB, GZIP i ARJ, tako da ne stvara probleme za upotrebu sa bilo kojom komprimovanom datotekom i integriše se sa kontekstnim menijem u Windows-u.
3. GZIP je jedan od najpoznatijih kompresora dizajniranih za Linux. S obzirom na uspjeh na ovoj platformi, izmijenjena je za Windows. Jedna od glavnih prednosti gzip-a je ta što koristi algoritam DEFLATE (kombinacija LZ77 i Huffman kodiranja).
4. WinRAR-kompresorski program i multifunkcionalni dekompresor podataka. Neophodan je alat za uštedu prostora na disku i vrijeme prijenosa prilikom slanja i primanja datoteka putem interneta ili prilikom sigurnosne kopije. Koristi se za komprimiranje svih vrsta dokumenata ili programa tako da zauzimaju manje prostora na disku i mogu se brže sačuvati ili prenijeti putem mreže. Ovo je prvi kompresor koji implementira 64-bitno upravljanje datotekama, što vam omogućava da obrađujete samo velike količine ograničene od strane operativnog sistema.

CSS Minifiers

Postoji mnogo CSS minifikatora. Neke od dostupnih opcija uključuju:

• online CSS Minifier;
• freeformatter.com / css-minifier;
• cleanss.com / css-minify;
• cnvyr.io;
• minifier.org;
• CSS-minifier.com.

Glavna razlika između ovih alata ovisi o tome koliko su duboki njihovi procesi minifikacije. Dakle, pojednostavljena optimizacija filtrira tekst za uklanjanje nepotrebnih razmaka i nizova. Napredna optimizacija uključuje zamjenu "AntiqueWhite" sa "#FAEBD7", budući da je heksadecimalni oblik u datoteci kraći i prisiljava upotrebu nižeg gzip-registarskog znaka.

Agresivnije CSS metode štede prostor, ali mogu krše zahtjeve CSS. Dakle, većina njih nema mogućnost automatiziranja, a programeri biraju između veličine ili stepena rizika.

U stvari, postoji novi trend kreiranja drugih verzija sa CSS jezika kako bi se efikasnije pomoglo autoru koda kao dodatna prednost, omogućavajući kompajleru da proizvede manji CSS kod.

Prednosti i nedostaci kompresije

Glavne prednosti kompresije su smanjenje hardvera za skladištenje podataka, vremena prenosa podataka i propusnog opsega komunikacije.

Takav fajl zahtijeva manje memorije, a korištenje metode dovodi do nižih troškova za disk ili SSD pogone. Potrebno je manje vremena za prijenos pri maloj propusnosti mreže.

Glavni nedostatak kompresije je utjecaj na performanse kao rezultat korištenja CPU-a i memorijskih resursa za proces i naknadnu dekompresiju.

Mnogi proizvođači su razvili sisteme kako bi pokušali da minimiziraju uticaj računarstva koje zahteva velike resurse povezane sa kompresijom. Ako se izvrši prije nego što se podaci zapišu na disk, sistem može istovariti proces za spremanje sistemskih resursa. Na primjer, IBM koristi zasebnu karticu za hardversko ubrzanje za obradu kompresije u nekim sistemima za skladištenje preduzeća.

Ako se podaci komprimiraju nakon što se zapišu na disk ili nakon obrade, izvršavaju se u pozadini kako bi se smanjio uticaj na performanse mašine. Iako kompresija nakon obrade smanjuje vrijeme odziva za svaki ulaz i izlaz (I/o), Ona i dalje troši memoriju i CPU cikluse i utiče na broj operacija koje sistem za skladištenje obrađuje. Pored toga, pošto se podaci inicijalno moraju zapisati na disk ili fleš diskove u nekomprimovanom obliku, fizička štednja memorije nije tako velika kao kod izgrađenih "- u smanjenju".

Budućnost nikada nije sigurna, ali na osnovu trenutnih trendova moguće je napraviti neka predviđanja o tome šta bi se moglo dogoditi s tehnologijom kompresije podataka. , algoritmi za miješanje konteksta kao što su PAQ i njegove varijante počeli su da dobijaju popularnost i imaju tendenciju da dostignu najviše koeficijente "". Iako su obično spori.

Sa eksponencijalnim povećanjem brzine hardvera prema Mooreovom zakonu, procesi miješanja konteksta će vjerovatno procvjetati. Budući da troškove brzine savlada brza oprema zbog visokog omjera kompresije. Algoritam koji je PAQ nastojao da poboljšaju zove se "Predviđanje parcijalne podudaranje staze". Ili PPM.

Konačno, algoritam lanca Lempel-Ziv-Markov (LZMA) dosledno pokazuje odličan kompromis između brzine i visokog stepena kompresije i verovatno će stvoriti više novih varijanti u budućnosti. On će biti u vodstvu, jer je već usvojen u mnogim konkurentskim formatima kompresije, na primjer, u programu 7-Zip.

Drugi potencijalni razvoj je upotreba kompresije za nabrajanje podloge (CSE), koja je obećavajuća tehnologija i još uvijek nema mnogo implementacija softvera.