TÖMÖRÍTÉS

Miért van igény tömörítésre?
A számítógépes alkalmazások egyre nagyobb adatállományokkal dolgoznak. Ezek tárolása helyigényes, továbbítása pedig a korlátozott sávszélesség miatt időigényes. Bár folyamatosan növekszik a rendelkezésre álló tárolóterület és ennek fajlagos ára is csökken, valamint egyre nagyobb sávszélesség áll rendelkezésre elérhető áron, célszerű a gazdaságosabb tárolás és továbbítás érdekében állományainkat a lehető legkisebb méretben tárolni. Erre szolgál a tömörítés.

Mi teszi lehetővé a tömörítést?
A számítógépen használt állományok szinte mindig több jelet tartalmaznak, mint amennyi az általuk hordozott információ megjelenítéséhez szükséges lenne azaz szinte mindig redundánsak. A redundancia hasznos is lehet, ha szándékosan alakították vagy növelték a redundanciát, például hibajavító kóddal. Ebben az esetben állományaink valamennyire védettek a sérüléssel szemben. (Sérülés esetén éppen a szándékolt többlet ad lehetőséget a helyreállításra.) Az állományok a redundancia csökkentése, kiküszöbölése révén kisebb méretűvé alakíthatóak. A tömörítés lényege tehát a redundancia minimálisra csökkentése, ideális esetben teljes kiküszöbölése.

Veszteséges és veszteségmentes tömörítés
A tömörítési eljárások egyik fajtája megfordítható (reverzibilis), azaz a tömörítő (vagy ahhoz rendelhető) eljárással pontosan visszaállítható az eredeti jelsorozat, Veszteségmentes tömörítéssel kell adatokat, szövegeket, adatbázisokat és programokat tömöríteni. A tömörítők másik csoportja a tömörítendő jelsorozat bizonyos elemeit egyszerűen kihagyja a tömörítés során. A tömörített adatokból így teljes pontossággal nem állítható helyre a tömörítetlen jelsorozat. Az esetek többségében azonban ez elfogadható; álló- vagy mozgóképek, hangok esetében komponensek kerülnek kihagyásra, melyek az állomány „élvezeti értékét" nem befolyásolják számottevően. Veszteséges tömörítéssel általában sokkal nagyobb tömörítési arány érhető el.

Hibakezelés
A tömörített állomány redundanciája minimális, hibás állapotának felismerése, javítása tehát problémás. Ezért szokás a tömörített jelsorozatról speciális matematikai algoritmussal ellenőrző összeget készíteni. Az algoritmus - a titkosításban, hitelesítésben is használatos ilyen - jellemzője, hogy tetszőleges nagy jelsorozatról állandó, kisméretű jelsorozatot generál, hogy az eredeti jelsorozat apró változása az ellenőrző összeget változtatja meg és, hogy elvileg kizárt azonos ellenőrző összeg két, különböző jelsorozathoz. Az algoritmus ismeretében elkészül ez az ellenőrző összeg (CRC, Cyclic Redundancy Checking), majd átvitel, feldolgozás előtti kicsomagolás után ismét. Ha e kettő nem egyezik, akkor a tömörített anyag sérült! A CRC csak hibaellenőrzésre való. Léteznek hibajavító megoldások is, de ezek természetüknél fogva ismét csak növelik a redundanciát, és ezzel csökkentik a tömörítés hatékonyságát!

Tömörítési algoritmusok

Igen sok tömörítési eljárást dolgoztak ki. Ezek közös jellemzője, hogy adott feltételek, meghatározott jellegű adatsorozat esetén nyújtják a legjobb tömörítési arányt és/vagy legkisebb a futásidejük.

Blokkméret kihasználása
A tárolóterület helyfoglalását csökkenti. Az adatállományaink kötött hosszúságú tárolóterület-egységekben kerülnek rögzítésre, ezek a blokkok. Egy blokkban cs egy állomány (egy állománynak a része) lehet. Ha pl. 512 byte a blokkméret, ennél kisebb állományok (vagy azok, melyek byte-ban mért hosszát a blokkmérettel osztva maradékot adnak) felhasználatlan byte-okat hagynak. Amennyiben több állományt „összefogunk", akkor a tárolás folyamatossá, felhasználatlan byte-októl mentessé tehető. A TAR tömörítés ezen az elven működik.

RLE (Run Length Encoding), futamhossz kódolás
Azonos jelekből álló sorozatokat tartalmazó adatsorozat tömörítésének egyszerű módszere. Ez a tömörítés egy-egy jelsorozatot két jellel helyettesít: az egyik j a sorozatot alkotja, a másik az ismétlődés száma. A kódolás akkor eredmény tömörítést, ha az ismétlődő jelsorozat kettőnél több (azonos) jelből áll. Veszt segmentes tömörítés.
Problémát jelent, hogy a tömörített állományban/állapotban meg kell különböztetni az adatot és az ismétlődést jelző számot. Erre általában speciális jel használnak (ez azonban tovább rontja a tömörítés hatásfokát). Ennek alapján több alváltozata is használatos az RLE algoritmusnak.

LZW (Lempel-Ziv-Welch) algoritmus
Ábrahám Lempel és Jacob Ziv 1978-ban publikált egy tömörítésre szánt algoritmust LZ78 néven. Terry Welch írta le ennek továbbfejlesztett változatát 1984-ben, ez lett az LZW algoritmus. Ez is veszteségmentes tömörítés.
Igen elterjedt, a Unix-rendszerek egyik tömörítő segédprogramja, valamint a GIF képállomány tárolási formátuma is ezt használja, de pl. PDF adatábrázolás is alkalmazhat ilyen tömörítő algoritmust. Ennek az algoritmusnak ismertek módosulatai: az elsőnek publikált LZ77-et eredeti szerzői egy évre rá LZ78 néven írva ismét közreadták; ehhez hasonlóan az alapalgoritmus továbbfejlesztései James Storer és Thomas Szymanski által közzétett LZSS algoritmus, valamint fent is említett LZW eljárás is. Az LZW algoritmus az ismétlődő jelsorozatokat tömöríti.

Huffman-kódolás
ódszer alapötlete az, hogy a tömörítendő jelsorozatban lehetséges jelek nem mindegyike bukkan fel azonos gyakorisággal. Amennyiben a gyakoribb jeleket rövidebb bináris jelsorozattal ábrázoljuk, akkor ez tömörítést eredményezhet még akkor is, ha ezért cserébe a ritkábban felbukkanó jeleket az alapértelmezett-hosszabb jellel kell ábrázolni. Szokás az ilyen tömörítőket statisztikai tömörítőnek is nevezni. Ezek is veszteségmentes tömörítési eljárások. Első lépésben a tömörítendő jelek gyakoriságát kell megállapítani. Akóvetkező lépésben bináris fa készül. Fontos, hogy egy tömörítendő jelsorozathoz csak egyetlen bináris fa rajzolható, ez a kitömörítés egyértelműségének kulcsa. A harmadik lépésben a fa minden éléhez 0 vagy 1 lesz hozzárendelve. A negyedik, befejező lépésben minden levél kódját képezzük úgy, hogy a gyökértől a levélig sorba tesszük a 0-s és l-es jeleket. Az így kialakuló ún. kódszavakat használva az eredeti jelsorozatnál a tömörített kisebb lehet.
A módszernek két fő változata ismert. A statikusnak nevezett változatban kétszer kell a tömörítendő adatokat végigolvasni: az elsőben a kódszótár készül, a másodikban a tömörítés. E kétszeri olvasás hátrány, az is, hogy a kódszótárt a tömörített adathoz kell csatolni, de egészében gyors a módszer. A másik lehetséges mód az, hogy tömörítés közben készül a statisztika. Ez a dinamikus mód, amely csak átlagos eloszlású tömörítendő jelsorozatra ad jó eredményt.

Aritmetikai kódolás
Veszteségmentes statisztikai eljárás. Az alapötlet igen régi, Claude E. Shannon 1948-ban publikálta, de fokozott számolás- és számábrázolás-igénye erősen gátolja elterjedését. A tömörítendő jelsorozat elemeihez adott számtartomány egy részintervallumát rendeljük a tömörítendő jelsorozatban való előfordulásának arányában.
Tömörített fájlformátumok JPEG
Képek tömörítésére használatos veszteséges tömörítés. A képek színváltozásának adataiból hagy el értéket, mivel az emberi szem a fényességváltozásra érzékenyebb. A 8 x 8-as blokkokban hajt végre transzformációt, majd az így kapott értékeket rendezi és Huffman-kódolással tömöríti. (A blokkokra bontás miatt, nagy tömörítési arány esetén jelentkezik a képek „kikockásodása".)

MP3 (MPEG-1/2 Audio Layer 3)
Veszteséges, hangok tömörítésére alkalmazott módszer. 1992-ben fejlesztette ki a Fraunhofer Institute. Igen jól tömörít, a hanghatást kevéssé rontja. Az emberi hallás szelektivitására épít, azaz bizonyos hangok más hangok elnyomását (közeli frekvenciákon csak az intenzívebb hangot érzékeljük) kihasználva hagy ki a tömörítendő jelsorozatból jeleket. A tömörítés fontos - de nem kizárólagos -jellemzője a bitsűrűség, azaz annak megadása, hogy másodpercenként hány bináris számjegy tárolódik. Minél nagyon ez az érték, annál jobb a hangzásminőség. Korábban ez egy zeneszámra állandó volt, újabban dinamikusan változtatják a tömörítők.

WMA (Windows Media Audio)
A Microsoft által hangok tömörítésére kidolgozott veszteséges tömörítő eljárás. Jobban tömörít, mint az MP3, de később jelent meg, ezért támogatottsága nem annyira elterjedt.

MPEG (Motion Picture Experts Group)
Veszteséges, mozgóképek tömörítésére kidolgozott szabványcsalád. Több változatából az 1998-ban közreadott MPEG-4 a legelterjedtebb.

Fraktáltömörítés
Veszteséges tömörítési eljárás, amely azon alapul, hogy a természetben előforduló jelsorozatokban minták, pontosabban önhasonló minták fordulnak elő. (Önhasonló: kevés és egyszerű transzformációval, pl. nyújtás, eltolás és elforgatás, az önhasonló minták azonossá tehetők.) Összevethető a hatékonysága a JPEG tömörítéssel, de élesebb kontúrok esetén jobb eredményt ad.

Önkicsomagoló állomány
Probléma lehet, ha a csomag készítéséhez használt tömörítő (kicsomagoló) ott, ahol a csomag tartalmát fel kellene használni, nem áll rendelkezésre. Ennek megelőzésére lehetséges olyan tömörített állományt létrehozni, amely a tömörített adatok mellett tartalmaz egy rövid futtatható programot is, aminek egyetlen célja a mellé csomagolt tömörített állomány helyreállítása. Ezek az önkibontó vagy önkicsomagoló, azaz SFX (SelF eXtracting) állományok.

Többszeletes tömörítvény
Problémát jelent, ha a tömörített állomány mérete nagyobb, mint ami egy adathordozóra ráfér. Ilyen helyzetek megoldására a tömörítő programok módot adnak arra, hogy a tömörített adatokat több (akár az adathordozó kapacitásával egyező méretű) fájl formájában állítsuk elő. Lehetséges olyan csomagot készíteni, amely több állományból áll. Ezeknek a szeleteknek (köteteknek) a mérete beállítható, vagy ezt a méretet az adathordozó mérete határozza majd meg. Ennek a hajlékonylemezes adathordozó elterjedt használata során volt fokozott jelentősége.

Röptömörítés
A tömörítendő jelsorozat kétféle módon alakítható át tömörített jelsorozattá: az egyik során előbb átolvassa a tömörítő a tömörítendő jeleket, majd kialakítja a tömörített jelsorozatot, a másik módszer során a tömörítendő jelek olvasása során röptében hozza létre a tömörített jelet. Legalább ilyen fontos az ellentettje, amikor a tömörített állomány kicsomagolása a fájl olvasásával egy menetben történik meg. Sok futtatható, végrehajtható állomány esetében alkalmazzák ezt a módszert.

File- és drive tömörítés
A tömörítés egyik fontos felhasználási területe az adattárolási helyigény csökkentése. Ennek egyik megközelítési módja az, hogy állományainkat, esetleg azok egy-egy csoportját tömörítjük tárolás előtt, majd kitömörítjük felhasználás előtt. Lehetséges a használt tároló teljes tartalmát tömöríteni, ennek során minden olvasás előbb kitömörítést igényel, illetve minden írás betömörítéssel jár.

Programok, állományformátumok
Néhány gyakrabban használt tömörítő program és tömörített file-formátum: ZIP: igen elterjedt, veszteségmentesen tömörített állománytípus. Számtalan program használja, pl. Windows alatt WinZIP
ARJ: Róbert K. Jung által készített azonos nevű programmal készíthető tömörítvény, veszteségmentes tömörítést valósít meg. Elterjedt program Windows alatt.
Igen sok opciója van a tömörítvény létrehozatalához. A programnak van freeware és kereskedelmi változata, utóbbi több szolgáltatással rendelkezik. RAR: Eugène Roshal hasonló nevű programjának állománytípusa, veszteségmentes tömörítést tartalmaz. A RAR formátumot több-kevesebb korlátozással több más tömörítő is kezeli.
JPG: JPEG, azaz veszteséges tömörítés, képek tömörítésére használatos. A kép minőségromlása árán igen nagy tömörítés érhető el ilyen állománytípusban. Sok képkezelő program ír és olvas ilyen formátumban, illetve a hardvereszközök (szkenner, digitális fényképezőgép) is ilyen formában rögzítik a képet. MP3: veszteséges hangtömörítés, számtalan program alkalmazza ezt a formátumot (is), pl. Audiograbber.