Az adattömörítés típusai. Tömörítés. Szükséges ez a mi korunkban? Mikor van szükség adattömörítésre?

Manapság sok felhasználó aggódik az információk tömörítési folyamata miatt, hogy szabad helyet takarítson meg a merevlemezén. Ez az egyik legtöbb hatékony módszerek hasznos tárhely felhasználásával.

A modern felhasználók gyakran szembesülnek a merevlemezen lévő szabad hely hiányával. Sokan megpróbálnak törölni, hogy legalább egy kis szabad helyet felszabadítsanak merevlemez minden felesleges információ. A haladóbb felhasználók speciális tömörítési algoritmusokat használnak az adatmennyiség csökkentésére. Ennek a folyamatnak a hatékonysága ellenére sok felhasználó még csak nem is hallott róla. Próbáljuk megérteni, mit értünk adattömörítés alatt, milyen algoritmusok használhatók erre, és milyen előnyökkel jár mindegyik.

Miért kell tömöríteni az információkat?

Manapság az információtömörítés meglehetősen fontos eljárás, amely minden számítógép-felhasználó számára szükséges. Manapság minden felhasználó megengedheti magának, hogy megvásároljon egy modern adattároló eszközt, amely nagy mennyiségű memória használatát teszi lehetővé. Az ilyen eszközök általában nagy sebességű csatornákkal vannak felszerelve az információk sugárzására. Érdemes azonban megjegyezni, hogy minden évben a kötet szükséges a felhasználók számára egyre több az információ. Alig tíz évvel ezelőtt egy szabványos videofilm mérete nem haladta meg a 700 megabájtot. Napjainkban a HD minőségű filmek mennyisége elérheti a több tíz gigabájtot.

Mikor van szükség adattömörítésre?

Nem kell sokat várnia az információtömörítési folyamattól. De még mindig vannak olyan helyzetek, amikor az információtömörítés egyszerűen szükséges és rendkívül hasznos. Nézzünk meg néhány ilyen esetet.

1. Átutalás email.

Nagyon gyakran vannak olyan helyzetek, amikor nagy mennyiségű adatot kell küldenie e-mailben. A tömörítésnek köszönhetően jelentősen csökkentheti a méretet átvitt fájlokat. Azok a felhasználók, akik mobileszközöket használnak információk küldésére, különösen értékelni fogják ennek az eljárásnak az előnyeit.

2. Adatok közzététele weboldalakon és portálokon.

A tömörítési eljárást gyakran használják a különféle internetes forrásokon való közzétételhez használt dokumentumok mennyiségének csökkentésére. Ezzel jelentősen megtakaríthatja a forgalmat.

3. Megtakarítás szabad hely lemezen.

Ha nem lehetséges új adattárolási eszközöket hozzáadni a rendszerhez, a tömörítési eljárással szabad lemezterületet takaríthat meg. Előfordul, hogy a felhasználó költségvetése rendkívül korlátozott, és nincs elég szabad hely a merevlemezen. Itt jön a segítség a tömörítési eljárás.

A fent felsorolt ​​helyzeteken kívül még mindig nagyon sok olyan eset van, amikor az adattömörítési folyamat nagyon hasznos lehet. Csak a leggyakoribbakat soroltuk fel.

Információtömörítési módszerek

Minden meglévő módszereket Az információtömörítés két fő kategóriába sorolható. Ezek a veszteségmentes tömörítés és a veszteségmentes tömörítés. Az első kategória csak akkor releváns, ha az adatok helyreállítására van szükség nagy pontosság anélkül, hogy az eredeti információ egyetlen bitjét is elveszítené. Az egyetlen eset, amikor ezt a megközelítést kell alkalmazni, a tömörítés szöveges dokumentumok.

Abban az esetben, ha nincs különösebb szükség a tömörített információk legpontosabb helyreállítására, biztosítani kell bizonyos tömörítési veszteségekkel járó algoritmusok alkalmazásának lehetőségét. A veszteséges tömörítési algoritmusok fő előnye a könnyű implementáció. Ezenkívül az ilyen algoritmusok meglehetősen magas tömörítési arányt biztosítanak.

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

A veszteséges tömörítési algoritmusok jobb fájltömörítést biztosítanak, miközben elegendő információt tartanak meg a helyreállításhoz. Az ilyen algoritmusok használata a legtöbb esetben alkalmas analóg adatok, például hangok vagy képek tömörítésére. Ilyen esetekben a végeredmény jelentősen eltérhet az eredetitől. A speciális felszerelés nélküli személy azonban észre sem veszi ezt a különbséget.

Tömörítés információvesztés nélkül

A veszteségmentes tömörítési algoritmusok lehetővé teszik az eredeti adatok legpontosabb visszaállítását. Az esetleges veszteségek kizárva. Azonban, ez a módszer Van egy jelentős hátránya: ilyen algoritmusok használatakor a tömörítés nem túl hatékony.

Univerzális módszerek

Vannak speciális módszerek is, amelyek segítségével a merevlemezeken tárolt információkat tömöríthetjük, hogy csökkentsük azok méretét. Ezek az úgynevezett univerzális módszerek. Összességében három technológia különböztethető meg.

1. Áramlás átalakítás.

A bejövő tömörítetlen információk leírása a már konvertált fájlokon keresztül történik. Ebben a folyamatban nem számítanak ki valószínűségeket. A karakterkódolás csak azon fájlok alapján történik, amelyek már átestek a feldolgozási folyamaton.

2. Statisztikai tömörítés.

Ez a fajta információtömörítési folyamat további két típusra osztható: blokk módszerekre és adaptív módszerekre. Blokk-algoritmusok használatakor minden egyes információblokk külön-külön kerül kiszámításra, és hozzáadódik a már tömörített blokkhoz. Az adaptív algoritmusok a valószínűségek kiszámítását foglalják magukban a tömörítési folyamat során már feldolgozott információk alapján. Ez a fajta módszer magában foglalja az adaptív Shannon-Fano algoritmust.

3. Blokk transzformáció.

A tömörítési folyamat során az összes átalakított információ több különálló blokkba kerül szétosztásra. Az információ holisztikus átalakulása zajlik.

Meg kell jegyezni, hogy egyes módszerek, különösen azok, amelyek több blokk átrendezésén alapulnak, a lemezen tárolt információ mennyiségének csökkenéséhez vezethetnek. A lényeg az, hogy megértsük, hogy a feldolgozás után a lemezen tárolt információk szerkezete javul és optimalizálódik. Ennek eredményeként a későbbi tömörítés más módszerekkel és algoritmusokkal könnyebb és gyorsabb lesz.

Információk tömörítése másoláskor

A megvalósítás egyik legfontosabb összetevője Tartalékmásolat Az információ az az eszköz, amelyen az információt továbbítják. Minél nagyobb mennyiségű információra van szüksége, annál nagyobb eszközt kell használnia. A szabad hely hiányának problémája az információtömörítési eljárással megoldható.

A biztonsági mentés során az adattömörítés jelentősen csökkentheti azt az időt, amelyet a felhasználó a szükséges információk másolására fordít. Ez lehetővé teszi a szabad hely hatékonyabb kihasználását is cserélhető adathordozó. A tömörítési eljárás során a másolt információk gyorsabban és tömörebben kerülnek cserélhető adathordozóra.

Ezzel megtakaríthatja a nagyobb meghajtó vásárlásához szükséges pénzt. Ezen túlmenően, ha a szükséges információkat további tömörítésnek veti alá, csökkenti a felhasznált adatok kiszolgálóra szállítására fordított időt. Ugyanez vonatkozik az információk hálózaton keresztüli másolására is. Biztonsági mentés céljából az információk egy vagy több fájlba tömöríthetők.

Minden csak az információ tömörítésére használt programtól függ. A tömörítő segédprogram kiválasztásakor ügyeljen arra, hogy a választott program hogyan képes az adatok tömörítésére. A tömörítés hatékonysága a konvertálandó információ típusától is függ. Például a szöveges fájlok és dokumentumok tömörítési hatékonysága elérheti a 90%-ot. Ám a képek tömörítésekor csak néhány százalékos hatékonyság érhető el.

Következtetés

Ma, az információs korszakban, annak ellenére, hogy szinte minden felhasználó hozzáfér a nagy sebességű adatátviteli csatornákhoz és médiához nagy kötetek, az adattömörítés kérdése továbbra is aktuális. Vannak helyzetek, amikor az adattömörítés egyszerűen szükséges művelet. Ez különösen vonatkozik az adatok e-mailben történő küldésére és az információk internetes közzétételére.

ARCHIVÁTOROK

Információ tömörítés a fájlban tárolt információk átalakításának folyamata az adatredundancia csökkentésével. Ennek a folyamatnak az a célja, hogy csökkentse az adatok által elfoglalt mennyiséget.

Archív fájl egy speciálisan létrehozott fájl, amely egy vagy több fájlt tömörített formában tartalmaz.

Tömörítési arány: K c = V c / V o *100%

K c- tömörítési arány, V c- hangerő tömörített fájl, V o– kezdeti fájlméret.

A tömörítési arány a következőktől függ:

1) a használt program - archiváló,

2) tömörítési módszer,

3) a forrásfájl típusa: szöveg, grafika, videó, hang stb.

A fájlokat be- és kicsomagoló programokat archiválóknak nevezzük. A leggyakoribbak: ARJ, ZIP, RAR. Az archív fájlok kiterjesztése megegyezik a létrehozásukhoz használt archiváló nevével.

Az archiválók lehetővé teszik önkicsomagoló archív fájlok létrehozását, pl. Kicsomagolásukhoz nem kell elindítani az archiváló programot, mert maguk is tartalmaznak egy kicsomagoló programot. Ezeket az archívumokat SFX archívumoknak nevezzük
(Önkivonás). Az ilyen fájlok kiterjesztése *.EXE.

Az információtömörítés elvei

Minden szövegben ismétlődő karakterek vannak. Lehetőség van egy karakter és az ismétlések számának megadására. Ennek az algoritmusnak a hatékonysága még nagyobb, ha grafikus fájlokra alkalmazzák. Ha ránézünk a monitorra, sok ismétlődő, azonos színű pontot láthatunk. A formátum az információtömörítés ezen elvén alapul. grafikus fájlok PCX. A modern archívumok nemcsak az ismétlődő karaktereket emelik ki, hanem a karakterláncokat és az egyes szavakat is.

Ha a szöveg nem használja a PC ábécé összes karakterét, akkor ezek kódolásához használhat egy bájtot, 8 bitet vagy ennél kisebb számot. Ezt az elvet alkalmazzák a távíró készülékekben, ahol csak oroszokat használnak nagybetűvel, 5 bit elegendő reprezentációjukhoz, ami lehetővé teszi, hogy két bájtban három karaktert írjunk.

3. A következő elv azt a mintát használja, amellyel a szövegben található betűk találkoznak különböző frekvenciák. Például ebben a szövegben a szóköz a leggyakoribb karakter, az „a” és „és” szimbólumok nagyon gyakoriak. Ezek a gyakran előforduló karakterek rövid bitsorozatként ábrázolhatók, míg más karakterek hosszabb sorozatként kódolhatók. Például:

4. Fizikailag a PC lefoglal helyet a fájlok fürtökben való elhelyezéséhez a lemezen – 4 kB-os blokkokban. Nem lehet kevesebbet kiemelni. Például, ha egy fájl 8193 bájt méretű (8 kB és 1 bájt), akkor fizikailag 16 kB vagy 16 384 bájtot fog elfoglalni. Fájlok egy csoportjának egyesítésével megtakaríthatja ezeket a maradékokat. Ez nagy megtakarítást jelent kis fájlok becsomagolásakor.

Összességében a fájlok külön elhelyezésekor 6 kB nem kerül felhasználásra, ami a fájlok tartalmának 100%-a. A második esetben 2 kB, 33% marad kihasználatlanul.

Archiváló zip

Fájlok csomagolása pkzip [kulcsok]<имя архива>[fájl elérési útja]

Kulcsok: -rp archiválás alkönyvtárakkal a struktúra megőrzése mellett

S P.W.D. archív jelszavas védelem (PWD)

Fájlok hozzáadása az archívumhoz

M helyezze át a fájlokat az archívumba

V archívum tartalmának megtekintése

Ha egy könyvtárban lévő összes fájl archiválásra kerül, akkor meg kell adni a maszkot *.*

Pkunzip fájlok kicsomagolása [kapcsolók]<имя архива>[fájlnevek]

Kulcsok: -d kicsomagolás alkönyvtárakkal a szerkezet megőrzése mellett

SPWD archív jelszó (PWD)

Archiváló arj

arj<команда>[kulcsok]<имя архива>[fájlnevek]

Az arj archiváló esetében egy fájl hajtja végre a kicsomagolást és a becsomagolást is.

Csapatok: a archiválás

e kicsomagolás a könyvtárstruktúra megőrzése nélkül

x kicsomagolás a szerkezet megőrzése mellett

l archívum tartalmának megtekintése

m áthelyezi a fájlokat az archívumba

d fájl törlése az archívumból

Kulcsok: -r alkönyvtárak csomagolása a szerkezet megőrzése mellett

V az archívum kötetekre bontása kötetre (ha van megadva)

a szabványos hajlékonylemezek mérete (360, 720, 1200, 1440) kilobájtban, a nem szabványos floppy lemezek mérete bájtban van megadva

Többkötetes archívum kicsomagolásakor a V betű jelenik meg

G P.W.D. archív jelszó ( P.W.D.)

Fájlok csomagolása

Fájlok kicsomagolása

©2015-2019 oldal
Minden jog a szerzőket illeti. Ez az oldal nem igényel szerzői jogot, de ingyenesen használható.
Az oldal létrehozásának dátuma: 2016-08-08

Az információtömörítési algoritmusok fejlesztése az alkalmazott matematika egyik ágába tartozik. A természetes redundancia kiküszöbölésének elvén alapulnak.

Az információtömörítési módszereket hagyományosan két nem átfedő osztályra osztják: veszteséges tömörítésÉs tömörítés információvesztés nélkül.

Veszteséges tömörítés azt jelenti, hogy a tömörített archívum kicsomagolása után a kapott adatok kissé eltérnek a kezdeti adatoktól. Nyilvánvaló, hogy minél nagyobb a tömörítési arány, annál nagyobb a veszteség, és fordítva.

Természetesen az ilyen algoritmusok nem alkalmazhatók szöveges dokumentumokra, adatbázistáblákra és programokra. Az egyszerű formázatlan szövegben előforduló kisebb torzításokat valahogy még túl lehet élni, de a program egy bites torzítása is teljesen működésképtelenné teszi.

Ugyanakkor vannak olyan adatok, amelyekben az információ néhány százalékát feláldozhatja a több tízszeres tömörítés érdekében, például fényképek, video- és hanganyagok. Az ilyen adatok tömörítése és ezt követő kicsomagolása során bekövetkező információvesztés valamilyen további „zaj” megjelenéseként érzékelhető.

A veszteséges tömörítési algoritmusok közé tartoznak az olyan algoritmusok, mint pl JPEG(fotóképek tömörítésekor használatos) és MPEG(videó és hang tömörítésére használják). A veszteséges tömörítési algoritmusokat csak fogyasztói feladatokhoz használják.

A megengedett tömörítési veszteség mértéke általában szabályozható, ami lehetővé teszi az optimális méret/minőség arány elérését. A képernyőn történő reprodukálásra szánt fényképes illusztrációkban az információ 5%-os elvesztése általában nem kritikus, esetenként 20-25%-os veszteség is elviselhető.

Mód tömörítés információvesztés nélkül szöveges dokumentumokkal és programokkal való munka során használatosak, és nem engedik meg az információvesztést. Csak a redundanciájának megszüntetésén alapulnak.

1. példa Az ukrán nyelv 32 betűből, tíz számból és körülbelül egy tucat írásjelből és egyéb speciális karakterből áll. Csak írott szöveghez nagybetűvel(mint a táviratokban) hatvan elég lenne különböző jelentések. Azonban minden karaktert általában egy bájt kódol, amely 8 bitet tartalmaz, és 256 különböző kódot képes kifejezni. Ez az elbocsátás első oka. A „távíró” szöveghez elég lenne karakterenként hat bit.

Rizs. 1. Morse kód

2. példa A nemzetközi ASCII karakterkódolásban ugyanannyi bit (8) van lefoglalva bármely karakter kódolásához. Ugyanakkor nyilvánvaló, hogy a leggyakrabban előforduló karaktereket érdemes kevesebb karakterrel kódolni. Tehát például be Morze kód a gyakran előforduló „E” és „T” betűk egy karakterrel vannak kódolva (egy ponttal, illetve egy kötőjellel). És az olyan ritka betűk, mint a „Yu” (--) és a „C” (- -), négy karakterrel vannak kódolva. A redundancia második oka a nem hatékony kódolás.

Az információtömörítést végző programok megadhatják saját kódolásukat (különböző a különböző fájlokat) és csatoljon a tömörített fájlhoz egy bizonyos táblázatot (szótárt), amelyből a kicsomagoló program megtanulja, hogyan ez a fájl bizonyos karakterek vagy csoportjaik kódolva vannak. Az információ átkódoláson alapuló algoritmusokat hívjuk Huffman algoritmusok.

Az ismétlődő fragmentumok jelenléte a redundancia harmadik alapja. Szövegekben ez ritka, de táblázatokban és grafikákban gyakori a kódok ismétlése. Így például, ha a 0-s szám hússzor megismétlődik egymás után, akkor nincs értelme húsz nulla bájtot tenni. Ehelyett egy nullát és 20-as együtthatót tesznek. Az ilyen ismétlődések azonosításán alapuló algoritmusokat metódusoknak nevezik. futáshossz kódolás(RLE,Run Length Encoding). A grafikus illusztrációkat különösen az azonos bájtok ismétlődő sorozatai különböztetik meg egymástól. A módszer meglehetősen hatékony grafikus képek bájt/pixel formátumban (például formátumok PCX vagy BMP).

Alkotás közben biztonsági másolatok A merevlemezeken van egy másik lehetőség a munkaterület megszerzésére a fájlok tömörítésekor, ami nem az információk redundanciájával, hanem a számítógép fájlrendszerének felépítésével kapcsolatos. Lényege abban rejlik, hogy bármilyen nagy vagy kicsi fájl csak egész számú klasztert foglalhat el a lemezen. BAN BEN fájlrendszer A merevlemezen lévő FAT16 nem tartalmazhat 65536-nál több klasztert (2 16). Ez azt jelenti, hogy az 1 és 2 GB közötti lemezek esetében a fürt mérete 32 KB.

Fájlok nagy csoportjának egyetlen fájlba tömörítése esetén a megtakarítás legalább 16 KB fájlonként csak azáltal, hogy csökkenti a fájlrendszer irracionális felépítéséből adódó veszteségeket.

FAT32 esetén az erősítés kisebb, de ebben az esetben a minimális fürtméret 4 KB, tehát ha nagy mennyiség kis fájlokat, akkor itt is van mit menteni.

Bár sokféle tömörítési módszer létezik, van néhány elvek és szabályok, amelyek minden tömörítési módszerben közösek. Ismerni és helyesen kell használni őket.

1. Minden tömörítésnek van határa, azok. Egy korábban tömörített fájl tömörítése a legjobb esetben sem eredményez nyereséget, és a legrosszabb esetben az eredményül kapott fájl méretének elvesztéséhez vezethet.

Helló! Elmagyaráznád egy kezdő felhasználónak, hogyan tömörítik a fájlokat a különböző archiválók? Legalábbis általánosságban. Különben nehezen tudom elképzelni, hogy ez hogyan is történhetett.

Vitalij

Teljesen igaza van, Vitalij, ezt tényleg nem olyan könnyű elképzelni, különösen, ha nem ismeri az algoritmust. De szerencsések a Computer magazin olvasói ;), mert valamikor nagyon érdekeltek az adattömörítési algoritmusok, és programozóként még saját archiválót is megpróbáltam írni.

Az adattömörítés az adatok algoritmikus átalakítása, amelyet annak mennyiségének csökkentése érdekében hajtanak végre. Az adattároló és adatátviteli eszközök ésszerűbb használatához használják. A tömörítési folyamatot adatcsomagolásnak vagy tömörítésnek is nevezik. A fordított eljárást adat-helyreállításnak (kicsomagolás, kicsomagolás) nevezik.

A tömörítés az eredeti adatokban lévő redundancia kiküszöbölésén alapul. A redundancia legegyszerűbb példája a töredékek ismétlődése a szövegben (például természetes vagy gépi nyelv szavai).

Kezdjük tehát azzal egyszerű példa. Tegyük fel, hogy van egy szöveges fájlunk, amely egy sort tartalmaz:

AAAGGDEEEEZHJUUUUUUKKKKKKKKKKK

A szöveg elég furcsa, egyetértesz, de most tömörítjük, és kevesebb helyet foglal. A tömörítés alapelve nagyon egyszerű, és a következőkben csapódik le: az egymást követő karakterek minden kombinációját egy ilyen karakter és annak ismétlődéseinek száma helyettesíti. Azok. tömörített forrásszövegünk így fog kinézni:

A3G2D1E4ZH2U3K4I3

Így 22 karakter helyett 16 karaktert kaptunk. Természetesen az eredetihez hasonló szövegek meglehetősen ritkák, nem is beszélve a benne található hülyeségekről. De a tömörítésen átesett fájlok nemcsak szöveges fájlok, hanem mindenféle kép, zene, videó és program is.

Ez a példa meglehetősen leegyszerűsített, és nem tükrözi azt a hatékonyságot, amelyet az archiválók általában a tömörítés során tanúsítanak. Így 22/16 = 1,375-szeres tömörítést kaptunk, bár az archiválók általában 2-10 000-szeres tömörítésre képesek. Minden a fájl bájtértékeinek ismételhetőségétől függ.

Milyen típusú archiválók léteznek?

Például a felejthetetlen MS-DOS alatt voltak ARJ, PKZIP, HA, RAR, ARC, ACE archiválók és LZEXE és PKLITE programcsomagolók. Később azért operációs rendszer A Windowst a WinAce, a WinZIP, a WinRAR, a 7Zip és az általam ismert UPX csomagoló készítette.

A tömörítés lehet veszteséggel vagy anélkül. A veszteségmentes tömörítés lehetővé teszi az eredeti adatok bitről bitre történő visszaállítását. Ez a tömörítés szöveg, programok és különféle adatok egy rekeszbe történő becsomagolására szolgál, és a fent felsorolt ​​összes archiváló végzi.

A veszteséges tömörítést adaptív tömörítésnek nevezhetjük, és képek, videók és hangok csomagolására használják, mivel az ilyen adatok nagyon csekély veszteség nélkül tömöríthetők (csak körülbelül 2-szer).

A veszteséges tömörítésnek köszönhetően az adatmennyiség többszörös csökkenése érhető el, és a kicsomagolt adatok megjelenítésekor az ember alig fogja érezni a különbséget az eredeti között.

Mennyire vannak tömörítve a különböző fájlok?

Szöveg

Valóban, például a szöveges fájlok nagyon szorosan tömöríthetők. Így például Arkagyij és Borisz Sztrugackij „Nehéz istennek lenni” című, 354 329 bájt méretű könyvét a WinRAR archiváló 140 146 bájtra tömöríti, azaz. 2,5 alkalommal.

Programok

A programfájlokat is lehet tömöríteni. Ugyanakkor a tömörítést mind a sűrűbb lemeztároláshoz, mind a tömörítéshez használják, amelyben a program program marad, de indításkor kicsomagolja magát.

Erre vannak olyan programcsomagolók, mint az UPX és mások, például az enyém szöveg szerkesztő Az 524 288 bájt méretű Superpad.exe-t az UPX csomagoló 179 200 bájtra (2,9-szeres) tömöríti, és továbbra is programként önállóan futhat.

Képek

Egy egész cikket, vagy akár egynél többet is lehetne szentelni az adatok tömörítésének módszereinek leírására. Az a tény, hogy maga a kép nagyon rosszul van tömörítve, ha bájtonként tömörítik. És mégis sikerül. Főleg, ha a képnek sok sima háttere van.

Az egyik első képtömörítési algoritmus az RLE algoritmus volt, amelyet fentebb leírtam. PCX képtárolási formátumban használatos. Az RLE egy veszteségmentes tömörítési algoritmus. De bizonyos esetekben ez nem az adatmennyiség csökkenéséhez, hanem növekedéséhez vezethet.

Ezért az LZW bitenkénti tömörítési algoritmust javasolták, és a mai napig használják képtömörítésre. Maga az algoritmus sokkal hatékonyabb, mint az RLE, és nem biztosít veszteségeket. De mivel színpalettával rendelkező képekhez használják, a paletta adaptálásával, optimalizálásával (tömörítésével) jelentős tömörítési hatékonyságnövekedés érhető el.

Rizs. 1. Gyönyörű béka BMP formátumban

Összehasonlításképpen vegyünk egy gyönyörű békát (1. ábra), melynek felbontása 799x599 pixel (pont), és mentsük el különböző képtárolási formátumokba. Vegyük a fájlokat:

frog.bmp - mérete 1 437 654 bájt és itt valójában nincs tömörítés és minőségromlás, mivel a kép a hozzá rendelt bájtokat foglalja el formátumban: Szélesség x Magasság x 3 bájt pixelenként + BMP fájlformátum fejléce Valódi színminőség (24 bit/pixel). Azok. minden pontot három RGB komponens (piros, zöld és kék) képvisel, amelyek mindegyike egy bájtot foglal el.

frog24.png - 617 059 bájt, 2,33-szoros tömörítés és veszteségmentes - a PNG-24 formátum fő tulajdonsága. A BMP és a PNG adatok szinte azonosak.

Rizs. 2. Fog_256colors.gif fájl

frog_256colors.gif - 261 956 bájt (2. ábra), 5,48-szoros veszteséges tömörítés, alappaletta 256 szín (8 bit/pixel). Elég nehéz megkülönböztetni ezt a fájlt az eredetitől a BMP-ben, mint abban a játékban, a „Find the Ten Differences”-ben.

Rizs. 3. Fog_64colors.gif fájl

frog_64colors.gif - 187 473 bájt (3. ábra), 7,67-szeres veszteséges tömörítés, 64 színre tömörített alappaletta (6 bit/pixel). És itt már kifakultak a színek, de a kép eléggé hasonlít az eredetihez. Ez különösen észrevehető, ha a békaszemet nézi.

JPEG

Különleges helyet foglal el a képtömörítésben és -tárolásban JPEG formátum. Ezért szeretnék különös figyelmet fordítani rá. JPEG algoritmus legalkalmasabb valósághű jeleneteket tartalmazó fényképek és festmények tömörítésére sima átmenetek fényerő és szín. A JPEG-et legszélesebb körben a digitális fényképezésben, valamint képek interneten keresztüli tárolására és továbbítására használják.

Másrészt a JPEG nem alkalmas rajzok, szövegek és karaktergrafikák tömörítésére, ahol a szomszédos pixelek közötti éles kontraszt észrevehető műtermékekhez vezet. Az ilyen képeket célszerű veszteségmentes formátumban, például TIFF, GIF, PNG vagy RAW formátumban menteni.

A JPEG (a többi torzítástömörítési módszerhez hasonlóan) nem alkalmas képek tömörítésére többlépcsős feldolgozás során, mivel minden közbenső feldolgozási eredmény mentésekor torzítások jelennek meg a képekben.

A JPEG nem használható olyan esetekben, amikor a minimális veszteség is elfogadhatatlan, például csillagászati ​​vagy orvosi képek tömörítésekor. Ilyen esetekben a JPEG szabvány által biztosított veszteségmentes JPEG tömörítési mód (amit a legtöbb népszerű kodek sajnos nem támogat), vagy a JPEG-LS tömörítési szabvány javasolt.

A JPEG tömörítési algoritmus leírása meglehetősen bonyolult, így aki akarja, az elolvashatja a http://el-izdanie.narod.ru/gl4/4-3.htm oldalon. Nos, összehasonlításképpen tömörítsük az eredeti képünket ezzel különböző szinteken tulajdonságok:

frog100%.jpg - 216 168 bájt, tömörítés 6,65-szeres, állítólag 0% veszteség, i.e. 100%-os képminőség, de ezzel nem is számolnék. Higgye el, vannak különbségek, bár szemmel abszolút megkülönböztethetetlenek.

frog60%.jpg - 85 910 bájt, tömörítés 16,7-szeres, i.e. a képminőség 60%, de a kép ismét ugyanolyannak tűnik, bár ha alaposan megnézi az egységes háttérrel vagy apró részletekkel rendelkező területeket, akkor elmosódottság vagy négyzet alakú monokróm szegmensek formájában észlelhető műtermékek.

frog20%.jpg - 36 426 bájt, tömörítés 39,5-szeres, képminőség az eredeti kép 20%-a, de a kép még így is képes megtéveszteni a képzetlen szemet, de egységes háttér előtt jól láthatóak az egyszínű szögletes szegmensek, ill. az apró részletek teljesen elvesztik világos körvonalait.

MPEG

Ez az egyik legkorábbi és legelterjedtebb videotárolási formátum. Többször modernizálva. De leegyszerűsítve azt mondhatjuk, hogy az algoritmus nagyon hasonlít a tömörítéshez, mint a JPEG-ben, de figyelembe véve azt a tényt, hogy a videó első képkockája mindig az eredeti és az eredeti, a következő képkockák pedig csak a különbséget tárolják előző és következő képkockák. Ennek köszönhetően minden következő képkocka előre jelezhető a dekompresszió szempontjából (4. és 5. ábra).

Rizs. 4. Eredeti videokockák

Rizs. 5. Képkockák közötti különbség mozgáskompenzációs algoritmusok használata nélkül

Az egyik legerősebb technológia a tömörítési arány növelésére a mozgáskompenzáció. Bármilyen modern rendszer videotömörítés esetén az adatfolyam következő képkockái az előző képkockák területeinek hasonlóságát használják a tömörítési arány növelésére.

A képkockában lévő objektumok (vagy maga a kamera) mozgása miatt azonban a szomszédos képkockák közötti hasonlóság használata nem volt teljes. A mozgáskompenzációs technológia lehetővé teszi a hasonló területek megtalálását, még akkor is, ha azok az előző képkockához képest el vannak tolva.

A mozgáskompenzáció a videoadatok feldolgozásához és tömörítéséhez használt egyik fő algoritmus. Az algoritmus a szomszédos képkockák hasonlóságát használja fel egy videósorozatban, és mozgásvektorokat keres egyes részek képek (általában 16x16 és 8x8 méretű blokkok).

A kompenzáció használata lehetővé teszi a tömörítés többszörös növelését a redundancia eltávolításával a keretek egyező részei formájában. Nem csak tömörítésre használják, hanem videó szűrésére, képkocka sebesség változtatására stb.

Szinte minden videóban a szomszédos képkockák hasonlóak, közös objektumaik vannak, amelyek általában eltolódnak egymáshoz képest. Az pedig teljesen természetes, hogy a videót úgy akarjuk kódolni, hogy az objektumok ne legyenek többször kódolva, hanem egyszerűen leírják néhány elmozdulásukat.

Ugyanakkor a kép úgynevezett kulcskockákra oszlik – ezek több másodpercig sorban futó képkockák csoportjai. Az ilyen kulcskockák időtartamának szabályozásával a tömörítés hatékonyan szabályozható.

Például, ha a film cselekménye nem dinamikus, akkor a kulcskockák időtartama több másodperc is lehet. Ha a film dinamikus jeleneteket tartalmaz, akkor ilyen pillanatokban a kulcskockák időtartama lerövidíthető, és a gyorsan változó kép tömörítése hatékonyabb lesz.

A kulcskockák a médialejátszókban is leegyszerűsítik és felgyorsítják a visszatekerést, mivel minden kulcskocka fejléce tartalmaz egy hivatkozást (a videofájl elejéhez képest bájteltolás) a következő kulcskép elejére.

Hang és zene

A hang és a zene lehet veszteségmentes vagy veszteséges WAV formátumban tárolva. Például a WAV formátum (Windows PCM) nem biztosít tömörítést, és úgymond eredetiben tárolja a hangjelet.

A WAV (ACM Waveform) formátum lényegében egy konténer, és képes tárolni az MPEG layer 3 algoritmussal tömörített hangot, vagy MP3 formátumban tárolni zenét, bár sok más formátum létezik, OGG, FLAC stb.

Nincs időm a hangtömörítési algoritmusokról beszélni, ráadásul lapunkban korábban volt egy csodálatos cikk erről a témáról.

Az adattömörítési módszerek fejlődésének meglehetősen hosszú története van, amely jóval az első számítógép megjelenése előtt kezdődött. Ez a cikk megpróbál rövid áttekintést adni a főbb elméletekről, elképzelésekről és azok megvalósításáról, a teljesség igénye nélkül. Részletesebb információk találhatók például a Krichevsky R.E. , Ryabko B.Ya. Witten I.H. , Rissanen J., Huffman D.A., Gallager R.G. , Knuth D.E. , Vitter J.S. satöbbi.

Az információtömörítés egy meglehetősen hosszú múltra visszatekintő probléma, sokkal hosszabb, mint a számítástechnika fejlődésének története, amely (történelem) általában párhuzamosan futott az információ kódolási és titkosítási problémájának fejlődéstörténetével. Minden tömörítési algoritmus egy bemeneti információfolyamon működik, amelynek minimális egysége egy bit, maximális egysége pedig több bit, bájt vagy több bájt. A tömörítési folyamat célja általában az, hogy valamilyen transzformációval egy kezdetben nem kompakt bemeneti adatfolyamból egy kompaktabb kimeneti információs adatfolyamot nyerjünk. A tömörítési folyamatok főbb műszaki jellemzői és munkájuk eredményei a következők:

A tömörítés mértéke (tömörítési érték) vagy az eredeti és a kapott folyamok térfogatának aránya (aránya);

Tömörítési sebesség - egy bizonyos mennyiségű információ tömörítésére fordított idő egy bemeneti adatfolyamból, mielőtt egyenértékű kimeneti adatfolyamot kapnánk;

A tömörítési minőség egy olyan érték, amely megmutatja, hogy a kimeneti adatfolyam milyen szorosan van tömörítve, ha újratömörítést alkalmaznak rá ugyanazzal vagy más algoritmussal.

Az információtömörítés problémájának többféle megközelítése létezik. Némelyiknek nagyon összetett elméleti matematikai alapja van, mások az információáramlás tulajdonságain alapulnak, és algoritmikusan meglehetősen egyszerűek. Minden adattömörítést vagy -tömörítést megvalósító megközelítés és algoritmus úgy van kialakítva, hogy csökkentse a kimeneti információfolyam mennyiségét bitekben a reverzibilis vagy irreverzibilis transzformáció segítségével. Ezért mindenekelőtt az adatok jellegével vagy formátumával kapcsolatos kritérium szerint minden tömörítési módszer két kategóriába sorolható: reverzibilis és irreverzibilis tömörítés.

Az irreverzibilis tömörítés a bemeneti adatfolyam olyan transzformációját jelenti, amelyben a kimeneti adatfolyam egy bizonyos információformátum alapján egy bizonyos szempontból a bemeneti adatfolyamhoz külső jellemzőiben nagyon hasonló objektumot képvisel, de attól eltér. hangerő. A bemeneti és kimeneti folyamok közötti hasonlóság mértékét az objektum bizonyos tulajdonságainak (azaz tömörített és tömörítetlen információnak, valamilyen meghatározott adatformátumnak megfelelően) egy adott információfolyam által reprezentált megfelelési foka határozza meg. Ilyen megközelítéseket és algoritmusokat használnak például olyan rasztergrafikus fájlokból származó adatok tömörítésére, amelyek alacsony fokú bájtismétlést tartalmaznak az adatfolyamban. Ez a megközelítés a grafikus fájl formátum szerkezeti tulajdonságát és azt a képességet használja fel, hogy egy hozzávetőlegesen hasonló megjelenítési minőségben (az emberi szem általi észleléshez) hasonló grafikus képet többféle (vagy inkább n) módon mutasson be. Ezért az ilyen algoritmusokban a tömörítés mértéke vagy nagysága mellett a minőség fogalma is felmerül, mert Mivel az eredeti kép a tömörítési folyamat során megváltozik, a minőség az eredeti és a kapott képek közötti megfelelés mértékeként értelmezhető, szubjektív módon értékelve az információs formátum alapján. A grafikus fájlok esetében ez a megfeleltetés vizuálisan kerül meghatározásra, bár vannak megfelelő intelligens algoritmusok és programok is. Az irreverzibilis tömörítés nem használható olyan területeken, ahol szükség van a bemeneti és kimeneti adatfolyam információs szerkezetének pontos egyezésére. Ezt a megközelítést a video- és fényképinformációk bemutatására szolgáló népszerű formátumokban valósítják meg, amelyek JPEG és JFIF algoritmusok, valamint JPG és JIF fájlformátumok néven ismertek.

A reverzibilis tömörítés mindig a kimeneti információfolyam térfogatának csökkenéséhez vezet anélkül, hogy az információtartalma megváltozna, pl. - információstruktúra elvesztése nélkül. Sőt, a kimeneti adatfolyamból rekonstrukciós vagy kitömörítési algoritmus segítségével megkapható a bemenet, és a helyreállítási folyamatot dekompressziónak vagy kitömörítésnek nevezzük, és csak a kicsomagolás után alkalmasak az adatok belső formátumának megfelelő feldolgozásra.

A reverzibilis algoritmusokban a kódolás mint folyamat statisztikai szempontból is szemlélhető, ami még hasznosabb, nemcsak tömörítési algoritmusok felépítésére, hanem hatékonyságuk felmérésére is. Minden reverzibilis algoritmus esetében létezik a kódolási költség fogalma. A kódolási költség egy kódszó átlagos hosszát jelenti bitben. A kódolási redundancia egyenlő a kódolás költsége és entrópiája közötti különbséggel, és egy jó tömörítési algoritmusnak mindig minimalizálnia kell a redundanciát (ne feledje, hogy az információ entrópiája a rendezetlenség mértéke). Shannon alapvető tétele az információkódolásról azt mondja, hogy „a kódolás költsége mindig nem kevesebb, mint a forrás entrópiája, bár tetszőlegesen közel lehet hozzá”. Ezért minden algoritmus esetében mindig van egy bizonyos határ a tömörítés mértékének, amelyet a bemeneti folyam entrópiája határoz meg.

Térjünk most közvetlenül a reverzibilis algoritmusok algoritmikus jellemzőire, és vegyük figyelembe az adattömörítés legfontosabb elméleti megközelítéseit, amelyek a kódolórendszerek megvalósításához és az információtömörítési módszerekhez kapcsolódnak.

Tömörítés soros kódolási módszerrel

Az információk visszafordítható módon történő tömörítésének legismertebb egyszerű megközelítése és algoritmusa a Run Length Encoding (RLE). Az ebben a megközelítésben alkalmazott módszerek lényege, hogy a láncokat vagy ismétlődő bájtok sorozatait vagy azok sorozatait egy kódoló bájttal és az ismétléseik számának számlálójával helyettesítik. Minden hasonló módszerrel csak az a probléma, hogy meghatározzuk, hogy a kitömörítő algoritmus hogyan tudna megkülönböztetni egy kódolt sorozatot a többi kódolatlan bájtsorozattól a kapott bájtfolyamban. A probléma megoldását általában úgy érik el, hogy a kódolt láncok elejére jelöléseket helyeznek el. Ilyen címkék lehetnek pl. jellemző értékek bitek a kódolt sorozat első bájtjában, a kódolt sorozat első bájtjának értéke stb. Ezek a módszerek általában elég hatékonyak a rasztergrafikus képek (BMP, PCX, TIF, GIF) tömörítésére, mert az utóbbiak elég sok ismétlődő bájtsorozat hosszú sorozatát tartalmazzák. Az RLE módszer hátránya a meglehetősen alacsony tömörítési arány vagy a fájlok kódolásának költsége kis számú sorozattal, és ami még rosszabb, kis számú ismétlődő bájttal a sorozatban.

Tömörítés az RLE módszer használata nélkül

Az RLE módszer használata nélküli adattömörítési folyamat két szakaszra osztható: modellezésre és valójában kódolásra. Ezek a folyamatok és a végrehajtási algoritmusaik meglehetősen függetlenek és változatosak.

Kódolási folyamat és módszerei

A kódolás általában egy karakterfolyam (esetünkben bájtok vagy nibble-ek) feldolgozását jelenti valamilyen ábécében, és a karakterek megjelenési gyakorisága az adatfolyamban eltérő. A kódolás célja ennek az adatfolyamnak a minimális hosszúságú bitfolyammá alakítása, amit a bemeneti folyam entrópiájának csökkentésével érünk el a szimbólumfrekvenciák figyelembevételével. Az adatfolyam ábécéjéből származó karaktereket reprezentáló kód hosszának arányosnak kell lennie a bemeneti adatfolyamban lévő információ mennyiségével, és az adatfolyam karaktereinek bitekben kifejezett hossza nem lehet 8 többszöröse, vagy akár változó sem. Ha ismerjük a bemeneti adatfolyam ábécéjéből származó szimbólumok előfordulási gyakoriságának valószínűségi eloszlását, akkor optimális kódolási modell konstruálható. A különféle fájlformátumok nagy száma miatt azonban a feladat sokkal bonyolultabbá válik. Az adatszimbólumok gyakorisági eloszlása ​​előre nem ismert. Ebben az esetben be Általános nézet, két megközelítést alkalmaznak.

Az első a bemeneti adatfolyam megtekintése és az összegyűjtött statisztikák alapján egy kódolás létrehozása (ehhez két áthaladás szükséges a fájlon – az egyik a statisztikai információk megtekintéséhez és gyűjtése, a második a kódolás, ami némileg korlátozza az ilyen algoritmusok hatókörét, mert Ily módon a , kiküszöböli a távközlési rendszerekben használatos egymenetes on-the-fly kódolás lehetőségét, ahol esetenként ismeretlen az adatmennyiség, és annak újraküldése vagy elemzése indokolatlanul sokáig tarthat). Ebben az esetben a használt kódolás statisztikai sémája a kimeneti adatfolyamba kerül. Ezt a módszert statikus Huffman kódolásnak nevezik.