Bezeztrátová komprese

Bezeztrátová komprese dat je třída algoritmů  komprese dat (video, audio, grafika, dokumenty prezentované v digitální podobě, programy v programovacích jazycích a strojových kódech a mnoho dalších typů dat), při jejichž použití lze zakódovaná data jednoznačně rekonstruovat. na nejbližší bit , pixel , voxel atd. V tomto případě jsou původní data zcela obnovena z komprimovaného stavu. Tento typ komprese se zásadně liší od ztrátové komprese dat . Pro každý typ digitální informace zpravidla existují optimální bezeztrátové kompresní algoritmy.

Bezztrátová komprese dat se používá v mnoha aplikacích. Používá se například ve všech archivátorech souborů . Používá se také jako komponent ve ztrátové kompresi.

Bezeztrátová komprese se používá, když je důležitá identita komprimovaných dat s originálem. Běžným příkladem jsou spustitelné soubory a zdrojový kód. Některé formáty grafických souborů (jako PNG ) používají pouze bezeztrátovou kompresi, zatímco jiné ( TIFF , FLIF nebo GIF ) mohou používat ztrátovou i bezeztrátovou kompresi.

Komprese a kombinatorika

Větu lze snadno dokázat.

Důkaz. Bez ztráty obecnosti můžeme předpokládat, že soubor A o délce přesně N se zmenšil . Označme abecedu jako . Podívejme se na sadu . V této sadě zdrojových souborů není více než . Proto je dekompresní funkce nejednoznačná , což je v rozporu. Věta byla prokázána.

Tato věta však ani v nejmenším nevrhá stín na bezeztrátovou kompresi. Faktem je, že jakýkoli kompresní algoritmus lze upravit tak, aby zvětšil velikost nejvýše o 1 bit: pokud algoritmus zmenšil soubor, zapíšeme „1“, pak komprimovanou sekvenci, pokud se zvětší, zapíšeme „ 0“, pak původní.

Takže nestlačitelné fragmenty nepovedou k nekontrolovanému "nafouknutí" archivu. „Skutečné“ soubory délky N jsou mnohem menší než (říkají, že data mají nízkou informační entropii ) – například je nepravděpodobné, že by se ve smysluplném textu objevila kombinace písmen „stydlivý“ a v digitalizovaném zvuku úroveň nemůže skok z 0 na 100 %. Navíc díky specializaci algoritmů na určitý typ dat (text, grafika, zvuk atd.) je možné dosáhnout vysokého stupně komprese: např. univerzální algoritmy používané v archivátorech komprimují zvuk o cca. třetí (1,5krát), zatímco FLAC  je 2,5krát. Většina specializovaných algoritmů je málo použitelná pro "cizí" typy souborů: například zvuková data jsou špatně komprimována algoritmem určeným pro texty.

Metoda bezztrátové komprese

Obecně lze říci, že význam bezeztrátové komprese je následující: v původních datech se najde nějaký vzor a po zohlednění tohoto vzoru se vygeneruje druhá sekvence, která úplně popisuje původní. Například pro kódování binárních sekvencí s mnoha 0 a několika jedničkami můžeme použít následující substituci:

V tomto případě šestnáct bitů

budou převedeny na třináct bitů

Taková substituce je prefix code , to znamená, že má následující vlastnost: pokud napíšeme komprimovaný řetězec bez mezer, stále do něj můžeme vkládat mezery - a tedy obnovit původní sekvenci. Nejznámější předponový kód je Huffmanův kód .

Většina bezeztrátových kompresních algoritmů pracuje ve dvou fázích: první generuje statistický model pro příchozí data, druhý bitmapuje příchozí data, přičemž pomocí modelu vytváří „pravděpodobnostní“ (tj. často se vyskytující) data, která se používají častěji než "nepravděpodobné" údaje.

Modely statistických algoritmů pro text (nebo textová binární data, jako jsou spustitelné soubory) zahrnují:

• Burrows-Wheelerova transformace (předzpracování blokového třídění, které zefektivňuje kompresi)
• LZ77 a LZ78 (používá DEFLATE )
• LZW

Algoritmy kódování prostřednictvím generování bitových sekvencí:

• Huffmanův algoritmus (také používá DEFLATE )
• Aritmetické kódování

Bezeztrátové kompresní metody

Podívejte se na úplný seznam v kategorii: Komprese dat

Víceúčelové

• Run-length kódování  je jednoduché schéma, které poskytuje dobrou kompresi pro data, která obsahují mnoho opakujících se hodnot.
• LZW  - používá se v gif a mnoha dalších.
• Deflate  – používá se v gzip, pokročilé verzi zipu, a jako součást procesu komprese PNG .
• LZMA  - používá se v 7-zip .

Komprese zvuku

• Apple Lossless  – ALAC (Apple Lossless Audio Codec)
• Audio Lossless Coding  – také známé jako MPEG-4 ALS
• Přímý přenos datového proudu  - DST
• Dolby TrueHD
• DTS-HD Master Audio
• Bezeztrátový zvukový kodek  - FLAC
• Bezztrátové balení Meridian  -MLP
• Opičí audio  - Opičí audio opice
• OptimFROG
• RealPlayer  - RealAudio Lossless
• Zkraťte  -SHN
• TAK  - (T)om's verlustfreier (A)udio (K)ompressor (německy)
• TTA  - True Audio Lossless
• WavPack  - WavPack bezeztrátový
• WMA  bezeztrátový

Komprese grafiky

• ABO  - Adaptivní binární optimalizace
• BTPC
• CALIC
• OSÁDKA
• CTW
• DPCM
• GIF  – (bezeztrátový pouze pro obrázky s 256 barvami nebo méně)
• JBIG2  - (ztrátové nebo žádné černobílé obrázky)
• Lossless JPEG  – (Rozšíření standardu komprese JPEG, který poskytuje bezeztrátovou kompresi)
• JPEG-LS  – (standard bezztrátové/téměř ztrátové komprese)
• JPEG 2000  - (v režimu bezztrátové komprese)
• LOCO-I
• MRP
• PGF  - Progressive Graphics File (komprese se ztrátou / bez ztráty)
• PNG  – přenosná síťová grafika
• PWC
• TIFF  – (s výjimkou režimů ztrátové komprese [1] )
• TMW
• Truevision TGA
• HD Photo  – (včetně bezztrátové kompresní metody)
• FLIF – bezplatný  bezztrátový formát obrázku

Komprese videa

• Animační kodek
• Video kodek CamStudio
• CorePNG
• FFV1
• Huffyuv  - omezeno na YUY2 a RGB, není kompatibilní s ffvhuff, originál nebyl aktualizován od roku 2002
• FFvhuff  - vylepšená komprese huffyuv, podporuje také YV12, zpětně kompatibilní s původním kodekem
• lagarith
• LCL
• Bezztrátový video kodek MSU
• Bezeztrátový kodek Qbit
• čiré video
• TSCC  - TechSmith Screen Capture Codec
• Waveletová komprese
• Motion JPEG 2000

Komprese textu

• PPM - HA  archivátor (od Harryho Hirvoly), využívající algoritmus PPM, je známý svým vysokým kompresním poměrem na textových souborech; v tomto parametru překonal první verze RAR , které se objevily o několik let později . To je důvod, proč CD jako " Knihovna do kapsy " populární na konci 90. let používaly HA.

Příklady algoritmů

• Rodina Lempel-Zivových algoritmů
• RLE (kódování délky běhu)

Příklady formátů a jejich implementací

• univerzální - Zip , 7-Zip , RAR , GZip , PAQ atd.
• zvuk - FLAC (Free Lossless Audio Codec), Monkey's Audio (APE), TTA (True Audio), TTE , LA (LosslessAudio), RealAudio Lossless , WavPack atd.
• obrázky - PNG
• video - Huffyuv .

Viz také

• Ztrátová komprese dat (ztrátová)
• Bezeztrátová komprese zvuku

Poznámky

1. ↑ Specifikace TIFF v6 (downlink) . Datum přístupu: 18. prosince 2010. Archivováno z originálu 3. července 2012. (neurčitý) 

Odkazy

• Bezztrátové kódování videa v Linuxu
• Krátké srovnání běžných bezztrátových audio kodeků