Ez egy szerkesztői próbalap, nem enciklopédia-cikk

A veszteségmentes tömörítés az adattömörítési algoritmusok egy osztálya, ami lehetővé teszi a tömörített adatból az eredeti adatok pontos rekonstrukcióját. Párja a veszteséges tömörítés, amikor az eredeti adatok nem mindig állíthatók pontosan helyre – ezt főleg a multimédia területén használják.

Veszteségmentes tömörítést számos program használ. Legnyilvánvalóbb előfordulási helyük az archív fájlformátumok, mint például a népszerű ZIP, a unixos gzip, vagy a 7z formátum. Gyakran veszteséges tömörítési eljárások részeként is előfordul.

Veszteségmentes tömörítést akkor alkalmaznak, ha fontos, hogy az eredeti és a kicsomagolt adat bitről bitre megegyezzen, illetve ha nem tudni, hogy az esetleges eltérések kritikusak-e. Tipikus példák a futtatható állományok vagy a forráskódok. Néhány képformátum, köztük a PNG csak veszteségmentes tömörítést használ, míg egy TIFF vagy MNG fájl veszteséges és veszteségmentes tömörítést is tartalmazhat. A GIF veszteségmentes tömörítést használ, de a legtöbb megvalósításában csak 8 bites színmélységgel, így egy true color képet először kvantálni kell (gyakran dithering használatával) mielőtt GIF-be lehetne kódolni. A kvantálás veszteséges módszer, de maga a tömörítés veszteségmentes.

A veszteségmentes tömörítés technikái

A veszteségmentes tömörítési módszereket aszerint csoportosíthatjuk, hogy milyen jellegű adaton végeznek tömörítést. A három fő adattípus tömörítés szempontjából: szöveg, kép és hang. Elvileg bármelyik általános célú veszteségmentes tömörítési algoritmust (az általános célú itt azt jelenti, hogy bármilyen bináris inputot tudnak kezelni), az algoritmusok jó része nem tud jelentős tömörítést elérni más adattípuson, mint amire tervezték. Például a hangadatok (egy WAV fájl) nagyon rosszul tömöríthetők hagyományos szövegtömörítő algoritmusokkal.

A veszteségmentesen tömörítő programok általában kétfajta algoritmust használnak: az egyik generál egy statisztikai modellt a bemeneti adatokból, a másik pedig a modell felhasználásával bitsorozatokat rendel a bemeneti adatokhoz oly módon, hogy a „valószínűbb” (tehát gyakrabban előforduló) adatoknak rövidebb bitsorozatot feleltessen meg, mint a „valószínűtlenebb” adatoknak. Sokszor csak az első algoritmust nevezik néven, a másodikat adottnak veszik vagy nem nevesítik.

Statisztikai modellkészítő algoritmusok szöveges bemeneti adatokra (vagy szöveg-jellegű bináris adatokra, mint amilyenek a futtatható fájlok):

Burrows-Wheeler transzformáció (blokkos rendezéssel előfeldolgozza a szöveget, ami a tömörítést hatékonyabbá teszi), például a bzip és a bzip2 használja
LZ77 és LZ78, a DEFLATE tömörítési algoritmus használja
LZW

A bitsorozatokat létrehozó algoritmusok:

Huffman-kódolás (a DEFLATE algoritmus is használja)
aritmetikai kódolás

A fenti módszerek előfordulnak a legkülönbözőbb nyílt forrású és kereskedelmi programokban, leggyakrabban az LZW és variánsai. Néhány algoritmus szabadalmi védelem alatt áll az USA-ban, és más országokban ahol lehetséges algoritmusokat szabadalmaztatni. Ezeket licencelni kell a jogszerű használathoz. Éppen az LZW tömörítés bizonyos fajtáira vonatkozó szabadalmak, és a szabadalom tulajdonosának, a Unisysnek a praktikái miatt szólították fel az információszabadságért küzdők az 1990-es évek közepétől az embereket, hogy váltsák fel a GIF formátumot a PNG-vel, ami elkerüli a jogi csapdát, és még kisebb fájlméretet is nyújt. A Unisys szabadalma 2003-ban elévült.

A szöveges adatokon jó hatásfokkal működő veszteségmentes tömörítési technikák sokszor elég jó eredményt nyújtanak palettázott képekre is, de léteznek más technikák, amik szöveg esetében gyengén teljesítenek, viszont egyszerű bittérképes grafikáknál hasznosak. Ezeken túl vannak képekre specializált tömörítő algoritmusok, amik például kihasználják, hogy a képen 2 dimenzióban egymáshoz közel eső részek általában azonos vagy közel azonos színűek, és hogy a színes képek általában a teljes színskála csak egy korlátozott kis részét használják ki.

A veszteségmentes hangtömörítés elég speciális terület. Az idetartozó algoritmusok kihasználhatják az adatok hullám-jellegéből adódó ismétlődő mintázatait – lényegében modelleket állítva fel a „következő” érték megbecslésére, és elkódolni a (remélhetőleg kicsi) eltérést a becsült és a tényleges érték között.

Ha az eltérés a becsült és a tényleges érték között (azaz a „hiba”) általában kicsi, akkor bizonyos differencia-értékek (például 0, +1, −1) nagyon gyakoriak lehetnek, amit ki lehet használni, és le lehet tárolni őket kevesebb biten is.

Néha hasznos, ha egy fájl két verziója között csak a különbséget tömörítjük (vagy a videotömörítésben egy kép verziói között). Ezt a technikát delta-kódolásnak nevezik (a görög Δ betűből, amit a matematikában gyakran különbség jelölésére használnak), de általában csak akkor hívják így, ha mindkét változat önmagában is értelmes. Például, a hiba tömörítését az előbb említett hangtömörítési séma esetében leírhatnánk az eredeti és a becsült hanghullám közti delta-kódolásként, ám a hullámforma közelítő, becsült alakja nem használatos a tömörítésen kívüli semmilyen kontextusban.

Veszteségmentes tömörítési módszerek

Hangtömörítés

Apple Lossless – ALAC (Apple Lossless Audio Codec)
Direct Stream Transfer – DST
Free Lossless Audio Codec – FLAC
Meridian Lossless Packing – MLP
Monkey's Audio – Monkey's Audio APE
RealPlayer – RealAudio Lossless
Shorten – SHN
TTA – True Audio Lossless
WavPack – WavPack lossless
WMA Lossless – Windows Media Lossless

Képtömörítés

ABO – Adaptive Binary Optimization
GIF
PNG – Portable Network Graphics
JPEG-LS – (veszteségmentes/közel veszteségmentes tömörítési szabvány)
JPEG 2000 – (tartalmaz veszteségmentes tömörítést is)
JBIG2 – (fekete-fehér képek veszteségmentes és veszteséges tömörítésére)
RLE (a PCX fájlformátum használja)
TIFF
WMPhoto – (tartalmaz veszteségmentes tömörítést is)

Videotömörítés

A veszteségmentes tömörítés bizonyos fájlok méretét csak megnövelni tudja

A veszteségmentes tömörítés nem tud valamilyen tömörítési arányt garantálni minden lehetséges bemeneti adatra. Más szavakkal kifejezve, bármely (veszteségmentes) adattömörítési algoritmus esetében lesz olyan bemeneti adathalmaz, aminek a méretét az algoritmus nem képes csökkenteni. Ez könnyen belátható elemi matematikai eszköz segítségével (megszámlálással), a következőképpen:

Tekintsünk minden fájlt valamilyen tetszőleges hosszúságú bitsorozatként
Tegyük fel, hogy van egy tömörítési algoritmus, ami minden fájlt átalakít egy másik, az eredetinél nem hosszabb fájllá, és hogy legalább egy fájlt az eredetinél kisebb méretre fog összenyomni.
Legyen $M$ a legkisebb olyan szám, ahol az $M$ bit hosszúságú $F$ fájl rövidebbre nyomódik össze. Legyen $N$ az $F$ fájl tömörített változatának a hossza, bitben megadva.
Mivel $N<M$ , ezért minden $N$ bit hosszú fájl megtartja méretét a tömörítés során. $2^{N}$ db. ilyen fájl létezik. Az $F$ -fel együtt így $2^{N}+1$ fájlunk van, amik mind tömöríthetők valamelyik fájllá a $2^{N}$ darab $N$ bit hosszúságú fájl közül.
De $2^{N}$ kisebb $2^{N}+1$ -nél, tehát létezik olyan $N$ bit hosszú fájl, ami egynél több különböző bemenet tömörített alakjaként jelentkezik. A fájlt tehát nem lehet megbízhatóan kicsomagolni (a két eredeti közül melyiket kéne eredményezze a kibontásnak?), amiből az következik, hogy az eredeti feltételezésünk az algoritmus veszteségmentes voltáról hibás volt.
Kijelenthetjük, hogy az eredeti hipotézis, miszerint a tömörítés egyetlen fájl méretét sem növeli, hamis.

Bármely veszteségmentes tömörítési algoritmus, ami egyes fájlok méretét csökkenti, néhány fájl méretét növelni fogja, de nem kell, hogy túlzottan megnövelje őket. A legtöbb elterjedt algoritmusnak van egy "escape" (menekülés) üzemmódja, amiben kikapcsolja a normális kódolást azokra a fájlokra, amik hosszabbak lennének elkódolva, mint eredetileg. Így a méretnövekedés csak az a pár bit vagy bájt, ami közli a kicsomagoló algoritmussal, hogy a normál kódolás ki van kapcsolva a teljes fájlra nézve. Például a deflate-tel tömörített fájlok soha nem nőnek meg 5 bájtnál többel 65 535 bemeneti bájtonként.

A bizonyítás fő tanulsága nem az, hogy nagyot lehet veszíteni, csak annyi, hogy nem lehet mindig győzni. Ha választunk egy algoritmust, szükségképpen implicite kiválasztjuk a fájlok egy részhalmazát, amiken számottevő tömörítést tud végezni.

Ha egy fájlt nem sikerül kisebbre összetömöríteni, annak leggyakoribb oka az, hogy egy tömörítési algoritmus végeredménye kerül egy másik tömörítési algoritmus bemenetére (például egy tömörített hang- vagy képfájlt adunk egy zip archívumhoz).

Lásd még

Veszteséges tömörítés

Hangtömörítés
David A. Huffman
Entrópia, illetve Shannon-entrópiafüggvény
Kolmogorov-bonyolultság
Lossless Transform Audio Compression (LTAC)

Források

[[Kategória:Tömörítő algoritmusok]] [[de:Verlustfreie Datenkompression]]