Az eredeti kép 100-as minőséggel (méret: 38,9 KB)
Ugyanaz a kép tömörítve (csaknem 97%-kal kevesebb
információ, 1,2 KB)
Ugyanaz, erős tömörítés után (csaknem 98,5%-kal kevesebb
információ, 662 bájt)
Tömörítés
Az adattömörítés a számítógépes tudományágak egy területe, melynek célja az adatok feldolgozása oly módon, hogy azok minél kevesebb helyet foglaljanak, vagy minél gyorsabban lehessen őket továbbítani. Ez oly módon lehetséges, hogy a valós világ adatai többnyire igen redundánsan és nem a lehető legtömörebb formában reprezentálódnak.
Alapvetően kétféle adattömörítési megoldás létezik:
Egyik igen egyszerű módja a tömörítésnek például a futamhossz-tömörítés, amikor is egymást követő adatokat egyetlen kóddal és az előfordulás számával helyettesítünk. Ez példa a veszteségmentes tömörítésre is, amikor a tömörített adatból később egy fordított eljárással pontosan visszanyerhető az eredeti adat. Az olyan adatoknál, mint a szöveges dokumentumok (néhány esettől eltekintve), követelmény a veszteségmentes tömörítés, hiszen akár egyetlen bit változás is megváltoztathatja a szöveg jelentését.
Más esetekben – például hangok vagy képek tömörítésénél – csekély, a felhasználó számára nem észrevehető veszteség megengedhető, ilyenkor tehát veszteséges eljárások is alkalmazhatóak. Ezen gyakorta jelentkező esetek a tömörítés hatásosságára széles választékot kínálnak a felhasználónak, attól függően, hogy inkább kevéssé tömörített jó minőségű vagy jobban tömörített, de nagyobb veszteséget hagyó tömörítési eljárást kíván alkalmazni. Az ehhez hasonló esetekben, tehát képek vagy hangok tömörítésénél egyúttal az emberi érzékszervek érzékenysége határozhatja meg az adattömörítés módját, hisz megengedhető olyan veszteség, amely számunkra nem észrevehető változást okoz csupán.
Sok adattömörítési rendszer jól vizsgálható a négyállapotú modellel.
Az adattömörítéssel szoros összefüggésben álló területek a kódelmélet és a kriptográfia. Ezekhez az információ-elmélet és az algoritmusos információ-elmélet nyújtanak elméleti hátteret. Amikor az adat tömörítése jelformák alakításaként jelentkezik, gyakran jelfeldolgozási módszereket alkalmazunk. Az adattömörítés ötlete szorosan kapcsolódik a matematika ritka mátrixok témájához, a statisztikai következtetésekhez és részben a maximum likelihood módszerhez.
A veszteségmentes tárolásra a legelterjedtebb forma a Lempel-Ziv (LZ) tömörítési módszer. Ennek egy sebességben és tömörítési arányban optimalizált változata a DEFLATE. Ez utóbbit használja a PKZIP, gzip és a PNG. Az LZW-t az Unisys szabadalmaztatta 2003-ban, melyet a GIF fájlokban használt és ami ezek elavulását eredményezte. Az LZ eljárások egy dinamikus táblát alkalmaznak a redundáns adat ábrázolására, melyet aztán Huffman kódolással tömörítenek.
A hangok tömörítését audiotömörítésnek nevezik, ahol is pszichoakusztikai módszereket alkalmaznak, hogy a nem hallható komponenseket kiszűrjék, s így a tömörítés hatékonyságát jelentősen növeljék.
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é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):
A bitsorozatokat létrehozó algoritmusok:
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.
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:
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).
Két alapkoncepció létezik veszteséges tömörítésre:
Egyes rendszerekben a két technikát kombinálják, és transzformációs kodekkel tömörítik a prediktív kodek hibajelét.
A veszteséges módszerek használatának az az előnye a veszteségmentes módszerekhez képest, hogy sok esetben a veszteséges tömörítés sokkal kisebb fájlt képes előállítani, mint bármely veszteségmentes, és még így is kellően jó minőséget ér el.
A veszteséges módszereket általában a hang-, kép- és videotömörítés során használják. A tömörítési arány (tehát a tömörített fájl mérete a tömörítetlenhez képest) általában a videók esetében a legjobb (akár 300:1 is lehet látható minőségromlás nélkül), hanganyagnál ez az érték 10:1 körül mozog. A veszteségesen tömörített képeknél is gyakori a 10:1-es tömörítési arány, de a minőségromlás itt vehető észre talán a legkönnyebben.
A veszteségesen tömörített fájl bitszinten teljesen különböző lehet az eredetitől, ugyanakkor az emberi szem vagy fül számára nehéz lehet megkülönböztetni őket. A legtöbb veszteséges tömörítő figyelembe veszi az emberi test anatómiai felépítését: például, hogy az emberi szem bizonyos frekvenciájú fényt lát csak. A hangtömörítés során pedig felhasználják az emberi hallás pszichoakusztikus modelljét, ami tartalmazza, hogy az emberi fül milyen hangmagasságokra érzékenyebb, vagy hogy az egyszerre megszólaló frekvenciák hogyan maszkolják egymást.
|
Az eredeti kép 100-as minőséggel (méret: 38,9 KB)
|
Ugyanaz a kép tömörítve (csaknem 97%-kal kevesebb
információ, 1,2 KB)
|
Ugyanaz, erős tömörítés után (csaknem 98,5%-kal kevesebb
információ, 662 bájt)
|
A fenti képek demonstrálják, hogyan csökkenti a fájlméretet a veszteséges tömörítés. A kép egy levelibékáról készült kép 128×128 képpontnyi részlete.
Bár a harmadik kép minősége nagyon rossz, a béka még mindig felismerhető. A jó veszteséges tömörítési algoritmusok képesek arra, hogy a „kevésbé fontos” információkat kidobják, a „lényeges” információkat pedig meghagyják az eredeti fájlból.
Technikai értelemben, egy szöveg méretének csökkentése a magánhangzók eltávolításával szintén veszteséges tömörítésnek tekinthető. A szöveg általában még így is értelmezhető marad, a mássalhangzók nyújtatta kontextus segítségével. A kutatók félig-meddig viccesen veszteséges tömörítést végeztek akkor is, amikor a hosszú szavakat a szövegben közel azonos jelentésű rövidebb szavakra cserélték [1], bár ez már inkább a veszteséges adatkonverzió kategóriájába tartozik.
Vissza a tetejére! Vissza a tartalom választó menübe! Felhasznált Irodalom