Tömörítők

Időnként szükség lehet arra, hogy az állományainkat kisebb helyen tároljuk, mint amennyi a tárolásukhoz szükséges. Ez furcsán hangzik de nem elképzelhetetlen. Gondoljuk végig, hogy az információt nem feltétlenül a legtömörebben tároljuk, ha minden adatot 8 bites egységekben vagy azok többszörösében tárolunk. Vannak esetek, amikor ennél tömörebb tárolás érhető el, ha olyan kódolást választunk, ahol különböző hosszúságú kódokat használunk.

A Huffman-kódolás

A legelterjedtebb kódolási módszer lényege éppen az, hogy az egyes byte-értékek általában nem azonos számban szerepelnek egy adott állományban. Egy szöveges állományban a betűket és írásjeleket megszámolva például jelentős eltérések tapasztalhatók az egyes betűk gyakorisága között. Erre építve a sűrűn előforduló értékekhez rövid, a ritkán előforduló értékekhez hosszabb kódot rendelve, jelentősen le lehet rövidíteni az állomány méretét. Tapasztalati adatok szerint az elérhető megtakarítás 20-90% lehet.

A módszer lényege a következő: számoljuk meg, hogy melyik érték pontosan hányszor szerepel az adott állományban. Ezután minden értékhez rendeljünk egy megfelelő bináris kódot úgy, hogy minél sűrűbben fordul elő egy érték, annál rövidebb legyen ez a kód. Ezután az így kapott kódokkal helyettesítsük az eredeti 8 bites kódokat.

Ebben az esetben azonban fellép egy probléma: hogyan fogjuk visszakapni az eredeti értékeket? Erre a válasz az, hogy a tömörített állomány elején egy táblázatban elhelyezzük a kódolás kulcsát, vagyis, hogy melyik kód milyen értéket jelent. A probléma ekkor azonban még nincs megoldva: felmerül ugyanis a kérdés, hogy hogyan fogjuk a folyamatos bitsorozatban megtalálni az egyes értékeket jelentő kódok határát?

Nos ennek a problémának a megoldásához olyan kódokat kell alkalmazni, amelyek lehetővé teszik, hogy a bitsorozat elejétől kezdve egyértelmű legyen, hogy ha egy kódot felismertünk, akkor az egészen biztosan nem lehet egy másik alkalmazott kódnak az eleje. Vagyis olyan kódokat kell alkalmazni, amelyek közül egyik sem tartalmazza a baloldalán valamely másik kódot.

Ilyen kódolás mellett már gond nélkül megoldható, hogy a bitsorozaton elindulva, minden bitnél kizárjuk azokat a kódokat, amelyeknél éppen az a bit tér el az eddigiektől, míg az eddigiek egyeztek. A végén elérünk két kódhoz, amelynek már csak egyetlen bitje tér el; ezek közül az egyik kizárásra kerül, a másik a keresett kód. Az is lehet, hogy egy adott bitnél csak egy kód egyezik – amely itt véget is ér – míg a többi, ennél hosszabb kód a másik bitértéket tartalmazza ezen a ponton.

Egy ilyen kódolást prefix-kódnak neveznek a szakemberek. Előállítására nagyon egyszerű módszert alkalmaznak: Építsünk fel egy fát a következő szabályok szerint:

1. Keressük meg a két legkisebb gyakoriságú értéket vagy részfát
2. Ezeket a fészfákat használva készítsünk egy új részfát úgy, hogy felveszünk egy új gyökeret, és ennek baloldali és jobboldali leszármazottjává tesszük a részfákat. Ezzel gyakorlatilag összevontunk két részfát, amelyek helyett a továbbiakban az új részfa szerepel.
3. Az újonnan létrejött részfa gyakorisága legyen a két eredeti részfa gyakoriságának az összege.
4. Ha egynél több részfa van még, akkor folytassuk mindezt az első lépéstől

Amikor már csak egyetlen részfánk van, akkor az egy olyan fa, ahol a legközelebb a gyökérhez a leggyakoribb értékeket jelentő levelek vannak, míg a legmesszebb a legritkább értéket jelentő levelek.

A kódolás most már egyszerű: a jobb oldalra induló ágat számozzuk 0-val, a balra indulót 1-el (fordítva is működik). Ezután minden levélhez (és a hozzá tartozó értékhez) kódként azt a bináris sorozatot rendeljük, amit az ágakról a gyökértől a levél felé haladva leolvashatunk.

Az így kapott tömörítési módszert nagyon sok tömörítőprogram alkalmazza általános célú tömörítésre. Jellemzője, hogy minden egyes állományra külön kódolást kell alkalmazni, így a kódolás táblázatát el kell helyezni az állomány elején. Emiatt bizonyos esetekben előfordulhat, hogy a tömörített állomány nagyobb helyet foglal el, mint az eredeti. Ez akkor fordulhat elő, ha a tömörítési arány nagyon gyenge lett, és a táblázat által elfoglalt hely nagyobb, mint a nyereség volt a tömörítéssel. Szöveges állományok általában nagyon jól tömöríthetők, de például a képek nagyon rosszul tömöríthetők ezzel a módszerrel. Épp ezért a képek tömörítésére speciális tömörítési módszerek vannak.

Ismétlődésen alapuló képtömörítés

Képek tömörítésére példa lehet, amikor egy képen az egymást követő azonos színű képpontok felsorolása helyett csupán azt tároljuk, hogy hány képpont követi egymást ugyanazzal a színnel, és melyik ez a szín. A nagy méretű, azonos színű foltokat tartalmazó képek ezzel a módszerrel nagyon jól tömöríthetők.

Átlagoláson alapuló, roncsoló tömörítés

Vannak olyan képtömörítő eljárások is, amelyek a kép tartalmától független tömörítési arányt eredményeznek. Például ilyen eset, amikor a kép néhány szomszédos képpontjának színét átlagolják, és az így kapott, kevesebb képpontot tárolják.

Ez a módszer nagyon hatékony tömörítést eredményezhet, azonban van néhány hátránya. Ezek közül az egyik a kép minőségének esetleges romlása, hiszen csökken a felbontás, és ha az átlagolt képpontok között erős kontraszt volt, akkor a kép jelentősen elmosódhat. Ez elkerülhető azzal, ha az átlagolandó képpontok kiválasztása a kép elemzése után történik.

Az így tömörített kép azonban mindenképpen információ vesztéssel kerül tárolásra: az eredeti információmennyiséget már soha nem lehet belőle visszanyerni. Ezért az ilyen tömörítési módot szokták roncsoló tömörítésnek is nevezni. Képeknél ez nem feltétlenül probléma, de más esetekben az ilyen tömörítés megengedhetetlen.

A változás tárolása

Filmek esetén szokás alkalmazni azt a módszert, hogy az első képkocka után csak azokat a képpontokat tárolják el, amelyek az előző képkockához képest megváltoztak. Így egy nyugodtabb jelenetnél rengeteg helyet lehet megspórolni, általában adatvesztés nélkül. Ám egy nagyon mozgalmas jelenetnél az is előfordulhat, hogy semmi tömörítést nem lehet így elérni. Ilyenkor a képpont átlagolásának módszerével keresztezhető az eljárás – amely már adatvesztést eredményez. Ilyenkor egy gyengébb tömörítő, vagy túl nagy tömörítési arány elvárása azt eredményezheti, hogy a képen nagyobb négyzeteket lehet látni, amelyek a kép nyugodtabbá válásakor egyre kisebbé, egyre részletesebbé válnak.

Elterjedtebb általános célú tömörítők

Említsünk meg néhány általánosabb célú tömörítőt, amelyek bármilyen állományt képesek tömöríteni, vagy kibontani a tömörített archívumból.

Ilyen tömörítőprogramok, és a velük készült archívumot jelző kiterjesztések a következők:

• .zip kiterjesztést állít elő a Zip család, amelynek több változata is van. Ilyen volt a DOS-os pkzip/pkunzip (utóbbi a kicsomagolást végezte), de ilyen a Windows-os WinZip is. Linuxon hasonló elnevezéssel a zip/unzip program használható ezekhez az archívumokhoz (lásd: man zip).
• .arj: az ARJ nevű program által készített archívum. Elsősorban DOS/Windows gépeken használatos, UNIX rendszerekben nem feltétlenül érhető el ezeket kezelő program.
• .rar: a RAR nevű programmal készített archívum. Elsősorban DOS/Windows gépeken használatos, UNIX rendszerekben nem feltétlenül érhető el ezeket kezelő program.
• .gz vagy .z: a GNU tömörítője, amely az eddigiektől eltérően mindössze egyetlen állományt tömörít. UNIX rendszereken használatos elsősorban, de DOS/Windows rendszeren is elérhető lehet. Többet a man gzip parancs segítségével lehet róla megtudni.
• .tar a UNIX tar nevű programjával készült archívum. Ez valójában nem tömörített állomány, hanem egy olyan állomány, amely egyetlen állománnyá fog össze több állományt. Eredetileg arra a célra készült, hogy mágnesszalagos biztonsági mentésre lehessen előkészíteni az elmentendő állományokat. A neve is innen származik: tape archiver.
• .tar.gz vagy .tgz: a tar és a gzip együttes használatával tömörített állomány. Ez a tar használatával készül úgy, hogy az elkészült, egy állománnyá való összevonáson a gzip segítségével még egy tömörítést is végez a rendszer.

A tömörítőprogramok általában több állományt is tudnak tömöríteni egyszerre, és azokat egy archívumban helyezik el, megőrizve benne az eredti állományneveke, és esetleges könyvtáraikat is.

Egyetlen kivétel a fent említettek közül a gzip amely mindig csak egyetlen állományt tud tömöríteni, aminek neve végére odateszi a .gz végződést. Azonban UNIX rendszerekben mégis ezt használják a legtöbbet, mert a tar segítségével ez is használható több állomány összetömörítésére.

Ennek egyik megoldása, ha a tar végrehajtásakor kapott állományra ráeresztjük a gzip-et. Ennél azonban egyszerűbb, ha a tar-ra bízzuk a gzip meghívását. Ez utóbbi esetben szokták a kapott állományt a .tgz kiterjesztéssel ellátni, míg az előbbi esetben az eredetileg .tar kiterjesztés után a gzip teszi a .gz kiterjesztést, így kialakítva a .tar.gz végződést.

Mindkét esetben a kicsomagolás is történhet kétféleképpen: vagy a gunzip segítségével kicsomagoljuk a .tar állományt, és abból a tar-ral az állományokat, vagy a tar-t kérjük meg a teljes feladat levezényelésére.

Az egylépéses esetet és a csak egybemásolást lássuk röviden:

A tar parancs első paramétere kötőjelek nélkül a teendőket megadó opciók megadása. Ezután kell megadni a létrehozandó archívum nevét becsomagolás esetén, majd harmadik paraméterként azt az állománymegadást, amellyel megadott állományokat be kell csomagolni.

Az opciók közül a c adja meg, hogy archívumot akarunk létrehozni. Ezután meg kell adni még az f opciót is, hogy állományba csomagoljon. Ha ezt nem adnánk meg, akkor a második paraméterként nem állományt kellene megadni, hanem annak a mágnesszalagos egységnek az elérési útját, amelyre az állományokat ki kell írni. Ha a gzip segítségével tömöríteni is szeretnénk az archívumot, akkor adjuk még meg a z betűt is. Nagy Z is használható, de ebben az esetben lehet, hogy már nem a gzip, hanem annak továbbfejleszett, g2zip nevű változatát fogja használni a tömörítéshez.

Például a mail könyvtárban található levelek összecsomagolására a következő parancs alkalmas egy levelek.tar nevű állományba:

Ugyanez a levelek.tgz nevű állományba tömörítve:

A kicsomagolás során a c helyett az x betűt kell szerepeltetni, és a harmadik paraméter elhagyható (ha mégis szerepel, akkor az ott megadott állományokat keresi meg az archívumban, és csak azokat csomagolja ki, tehát nem a célkönyvtárt lehet vele megadni).

Tehát az előző példák kicsomagolása a következő parancsokkal lehetséges:

A harmadik paraméterben az állományok megadása szóközzel elválasztott listában is lehetséges, vagyis minden további paraméter egy-egy becsomagolandó illetve kicsomagolandó állományt jelent.

Következik: A Midnight Commander