Az adattömörítés általános módszerei - stadopedia
Jelenleg nagyszámú adattömörítési módszert fejlesztettek ki, amelyek mindegyikének előnyei és hátrányai vannak. A hosszú távú kódolásnak nevezett eljárás a legjobb hatást biztosítja az ugyanazon elemek hosszú sorozatait tartalmazó tömörítéskor. Valójában a sorozat hossza kódolásakor az ilyen szekvenciát az ismétlődő elemet jelző kód és annak ismétléseinek száma váltja fel. Például annak jelzésére, hogy egy bitkészlet 253 egységből áll, majd 118 nullával és 87 egységgel rendelkezik, kevesebb helyre van szükség, mint az összes 458 bitet felsorolni.
Bizonyos esetekben az információ olyan blokkokból áll, amelyek kissé eltérnek egymástól. Például a film keretei egymás után. Ilyen esetekben a relatív kódolási módszert alkalmazzák. Ezzel a megközelítéssel az egymás után következő blokkok közötti különbségeket rögzítik, nem pedig a blokkokat, vagyis az egyes blokkokat kódolják az előző blokthoz való viszonyuk alapján.
Az adatméret csökkentésének másik módja a frekvenciafüggő kódolás, amelyben az információelem kódhossza fordítottan arányos az elem használatának gyakoriságával. Ezek a kódok a változó hosszúságú kódok példái, ami azt jelenti, hogy az információelemek különböző hosszúságú szekvenciákkal vannak ábrázolva, ellentétben azokkal a kódokkal, mint például a Unicode, amelyben az összes szimbólumot 16 bites szekvenciák képviselik. Angolul az e, t, a és i betűket gyakrabban használják, mint a z, q és x betűket. Ezért a szöveg angol nyelvű kódolásakor helyet takaríthat meg a memóriában, ha rövid bitkészleteket használ az első betűkhöz és a hosszabb ideig a másodikhoz. Ennek eredményeként olyan kódot kapunk, amelyben a szöveg rövidebb lesz, mint egy fix hosszúságú kódban, például ASCII vagy Unicode. David Huffman az algoritmus felfedezőjeként ismeretes, amelyet széles körben használnak frekvenciafüggő kódok létrehozására. Ezért szinte az összes ma használt frekvenciafüggő kód a Huffman kód.
Bár a sorozathossz-kódolást, a relatív kódolást és a frekvenciafüggő kódolást az adatok kódolásának közös módszereivel neveztük el, mindegyiküknek még mindig van saját alkalmazási területe. Ezzel szemben a Lempel-Ziv kódolási rendszer, amelyet Abraham Lempel és Jakob Ziva alkotóinak neveztek el, egy egyetemesebb rendszer. Valójában a webfelhasználók (lásd a 3. fejezetet) láthatták vagy használják a szervizprogramot, amelyben a Lempel-Ziva módszer tömörített fájlok létrehozására szolgál zip fájlokként. A Lempel-Ziva kódolási rendszer egy példa az adaptív szótárkódolással történő kódolásra. A rendszerben található szótár olyan szabványos blokkok halmaza, amelyből egy üzenet épül fel, amelyet tömöríteni kell. Ha angolul szeretnénk tömöríteni a szöveget, akkor az ilyen szabványblokkok az ábécé betűi. Ha már kódolt adatokat szeretnénk tömöríteni, akkor a szabványblokkok 0 és 1 lesz. Az adaptív kódolással a szótár változhat a kódolás során. Például az angol szöveg esetében az üzenet egy részének kódolásával dönthetünk az ing és a szótár felvételéről. Mostantól minden alkalommal, amikor a szöveg találkozik, vagy a, a kódolással egyszerre, és nem hároman érheti el a szótárat. A Lempel-Ziva módszer lehetővé teszi, hogy intelligens módon és hatékonyan igazítsa a szótárat az adatok kódolásához (vagy tömörítéséhez).
Mint mondtuk az 1.4 fejezetben, egy másodperc zenei hang, amelyet másodpercenként 44 100 minta mintavételezéssel digitalizáltunk, több mint egymillió bitet igényel a memóriában. Az ilyen követelmények elfogadhatók a CD-ken elhelyezett zenei felvételek számára, de a filmek felvételének megkísérlése a hang és a kép kombinációját kihívja a technológia képességeinek. Ezért az ISO szervezet részeként működő Motion Picture Experts Group (Motion Picture Experts Group) kifejlesztett egy adatcsomagolási eljárást, amely jelentősen csökkenti a memóriaigényeket. Az egyik ilyen szabvány MP3 (MPEG-1 Audio Layer-3) néven ismert, és lehetővé teszi, hogy 12-1-es tömörítési arányt érjen el. Az MP3 szabvány szerint a zenei rekordok mérete olyan méretre redukálható, amely gazdaságosan továbbítható az interneten keresztül. Ez a lehetőség azzal fenyeget, hogy radikálisan megváltoztatja a felvételi iparágat.
Vegyük például példaként, hogy hogyan lehet tömöríteni egy üzenetet a Lempel-Ziv algoritmus speciális esetével, amelyet LZ77-nek nevezünk. Kezdjük egy egyszerű idézettel az üzenet kezdeti részével. Ezután képzeljük el az üzenet többi részét háromszoros sorrendben (amely két egész számot tartalmaz, majd egy karaktert az üzenetből). Mindegyik ilyen hármas azt írja le, hogy miként lehet az üzenet következő részének felépítését az előző alapján. Ezért a szótár, amelyből az üzenet épül, magából az üzenetből áll.
Például, vegyük figyelembe az xyxxyzy (5. 4, x) tömörített üzenetet, amely a kezdeti xyxxyzy szegmensből áll, majd egy tripla (5, 4, x). Az xyxxyzy-lánc egy olyan üzenet része, amely már kiterjesztett formában van. Annak érdekében, hogy az üzenet többi részét telepítsük, meg kell értenünk a tripletet (5, 4, x), amint azt az 1. ábra mutatja. 1.27. A hármas első száma megmutatja, hány karaktert kell visszamenni a kibővített láncba. Esetünkben öt karaktert visszaadunk a második balra x. Ebben a pozícióban elkezdjük a kibontott lánc végére a karakterek hozzáadását. A második szám megmutatja, hány karaktert szeretne hozzáadni a sorozathoz. Ebben az esetben ez a szám 4, ezért az xxyz karaktereket a kiterjesztett lánc vége felé és az xyxxyzyxxyz-t kapjuk. Végül adja hozzá a hármas utolsó karakterét a lánc végéhez. Példánkban ez a x karakter a dekódolt karakterlánc vége felé van rendelve. Ennek eredményeképpen megkapjuk az expandált xyxxyzyxxyzx üzenetet.
Most tegyük fel, hogy ki kell bővítenünk az xyxxyzy üzenetet (5. 4, x) (0, 0, w) (8. b.y). Az első hármas dekódolásával kezdjük, mint korábban, xyxxyzyxxyzx (0, 0, w) (8. 6, y). Most, a második hármas kibontakozásának eredményeként kapjuk a xyxxyzyxxyzxw láncot (8, 6, y). Megjegyezzük, hogy a hármas (0, 0 w) értéket használtuk, mert a w szimbólum még nem jelent meg az üzenetben. Végül, dekrypt az utolsó három és kap a kiterjesztett üzenet xyxxyzyxxyzxwzyxxyzy.
Az üzenet LZ77 algoritmussal való tömörítéséhez először írja át az üzenet kezdeti szegmensét, majd keresse meg a szegmens leghosszabb láncát, amely megfelel az üzenet többi részének. Ez a lánc tartalmazza az első három. A következő tripletek ugyanúgy alakulnak ki.
Végül észre kell venned, hogy ezek a példák nem tükrözik teljes mértékben az adatcsomag folyamatát, mert a szóban forgó triók csak az üzenet rövid szegmenseit reprezentálják. Azonban helyes feltételezni, hogy a hosszú bináris kódokban a tripletek hosszú szegmenseket fognak képviselni, aminek következtében az adatok tömörítése jelentős lesz.
Az 1.4 fejezetben megemlítették, hogy a modern digitális átalakítók által létrehozott rasztergrafikonban a kép általában három bájt / pixel formátumban jelenik meg, ami nagy és nehéz feldolgozni a raszteres grafikus fájlokat. A memóriaigény csökkentése érdekében számos tömörítési sémát fejlesztettek ki. Az egyiket a CompuServe által kifejlesztett GIF (Graphic Interchange Format rövidítés). Ez a tömörítési szabvány megoldja a problémát azzal, hogy csökkenti a képponthoz hozzárendelhető színek számát 256-ra. Ez azt jelenti, hogy az egyes képpontok értékét egy bájt, nem három számmal ábrázolhatjuk. A 256 képpontos értékek mindegyikére egy paletta nevű tábla használatával térképezik fel a piros, zöld és kék színek egyes kombinációit. A képpaletta megváltoztatásával megváltoztathatjuk a kép színeit.
A GIF-képek egyikének színe általában "átlátszó" értéket kap, azaz a képnek a képhez tartozó bármelyik részén keresztül, amelyen a szín látható. Ennek a funkciónak és a GIF formátum viszonylagos egyszerűségének köszönhetően számítógépes játékokban használják, ahol több képet mozgatnak a képernyőn.
A képek másik tömörítési szabványát JPEG-nek hívják. A közös fotográfiai szakértői csoport (Joint Photographic Experts Group), az ISO szervezet része. A JPEG hatékony volt a színes fényképek megjelenítéséhez. Valójában ez a szabvány elfogadja a modern digitális fényképezőgépek gyártóit, és ígéretes, hogy sokáig hatást gyakorol a digitális képek terén.
Valójában a JPEG szabvány többféle módon ábrázolja a képeket, amelyek mindegyikének saját feladata van. Például olyan esetekben, amikor szélsőséges pontosságra van szükség, a JPEG formátum olyan "veszteségmentes" módszert biztosít, amelyben a képkódolás során semmilyen információvesztés nem fordul elő. Ezen algoritmus szerint a szomszédos képpontok közötti különbséget tárolja, nem pedig a pixelintenzitást. Ez a megközelítés azon a feltételezésen alapul, hogy a legtöbb esetben a szomszédos képpontok közötti különbséget rövidebb bináris kódokkal lehet ábrázolni, mint az értékük (ez a relatív kódolás egy példája). A különbségeket változó hosszúságú kóddal rögzítik.
Sajnos ennek a módszernek a alkalmazása nem nyújt olyan képeket, amelyek mérete könnyen megváltoztatható, ezért ritkán használják. Ehelyett az alap JPEG szabványt használja, amely csökkenti a képkód méretét, két paraméter segítségével meghatározza a pixelállapotot: a fényerőt és a színt.
Ennek az elválasztásnak az oka, hogy az emberi szem érzékenyebb a fényerő változásaira, mint a színváltozásokra. Vegyük például, két kék háttér, különböző csak, hogy az egyik tartalmazza a kis fényes pont, és a második kis zöld pont, amely azonos fényerő, mint a fényerő a háttérben. Az emberi szem gyorsan megtalálja a fényes pontot, mint a zöld. Az alapformátum az emberi szem tulajdonságát használja, és a fényerő minden összetevőjét kódolja, de a kép négyzetes méretű blokkokra oszlik, és csak az egyes blokkok átlagos színét rögzíti. Ezért a végső nézetben a gyors fényviszonyok változása megmarad, de a gyors színváltozások törlődnek. A módszer előnye abban a tényben rejlik, hogy minden egyes blokk négy pixel meghatározott csupán hat értékre (négy a luminancia és a szín 2) és nem tizenkét, mintha egy pixel határozza meg három érték.
További terület kerül mentésre a fényerő és a színváltozás során, és nem a tényleges értékek. Ennek az az oka, mint a módszer a „veszteségmentes”, hogy a kép beolvasási eltérés mértéke a szomszédos képpontok lehet egy bináris kód rövidebb, mint az egyik, hogy szükséges lenne rögzíteni a tényleges színét értékeket. Valójában ezeket a különbségeket a diszkrét koszinusz-transzformációnak nevezett matematikai módszerrel rögzítjük. Ezt a könyvet nem fogjuk figyelembe venni. A végső bináris kódot egy változó hosszúságú kódmódszerrel tömörítjük.
Röviden, a kiindulási JPEG szabvány képes kódolni kiváló minőségű színes képeket készít a bináris kód, amely körülbelül hússzor kevesebb memóriát igényel, mint a méret kód „három bájt pixelenként” kifejezés sok szkennerek. Ezért a JPEG szabvány egyre népszerűbb. Néhány alkalmazásformátum azonban különböző formátumokat használ. Például a GIF formátum nagyobb, mint a JPEG, amely azonos színű és világos határfelületű blokkokból áll, mint például a színes rajzfilmek.