15 legnépszerűbb adattömörítési algoritmus

Az adattömörítési algoritmusok a fájlok méretének csökkentését jelentik az azonos vagy bizonyos mértékig hasonló adatok megtartása mellett. Ez úgy történik, hogy elvégzi a felesleges adatok eltávolítását vagy az adatok újbóli előállítását a nagyobb hatékonyság érdekében.

A tömörítéskor a veszteséges vagy veszteségmentes módszerek közül választhat. Ha a veszteséges módszerről beszélünk, az véglegesen törli az adatokat. Másrészt a veszteségmentes gondoskodik az eredeti adatokról. A választott típus attól függ, hogy milyen minőségű fájlokat szeretne.
Ez a cikk a veszteségmentes adattömörítési algoritmusok és a mélytanuláson alapuló kép- és videotömörítési algoritmusok keverékét tartalmazza.

A veszteségmentes adattömörítési algoritmusok általában az archiválás vagy bármilyen más kiváló minőségű funkció elvégzésére használt lények. Ezek az adattömörítési algoritmusok lehetővé teszik a fájlméret csökkentését. Azt is biztosítja, hogy a fájlok teljes mértékben visszaállíthatók, ha vissza kell állítani őket.

LZ77

Az LZ77-et 1977-ben jelentették be, és oly sok más veszteségmentes tömörítési algoritmus alapjának nevezték. Általában a “csúszóablak” módszerét használja. Ebben a módszerben gondoskodik egy szótárról, amely hármasokat használ a következők ábrázolására:

• Offset- Úgy nevezhető, mint a mondat tényleges kezdete és a fájl eleje.
• Run-lenggth-Az a karakterek mennyisége, amelyek segítenek a mondat létrehozásában.
• Deviating characters-These are the marketers that indicate a new phrase.

Ez tartalmazza annak jelzését, hogy a használt kifejezés teljesen megegyezik-e az eredeti kifejezéssel, és azt is meghatározza, hogy van-e eltérő karakter.

Amint egy fájlt elemez, a szótár dinamikusan frissül a tömörített adattartalom és a méret tükrözésére is.

LZR

Az LZR-t 1981-ben fejlesztették ki és jelentették be. Michael Rodeh jelentette be, majd később módosította. Az LZ77 adattömörítési algoritmus elsődleges alternatívájaként használható, de lehetőség van arra is, hogy a fájlon belüli bármely eltoláshoz használjuk. Ha nem lineárisan használjuk, akkor jelentős mennyiségű memóriatárolót igényel. Ez a feltétel teszi az LZ77 használatát jobb választássá. Ez az adattömörítési algoritmus egyszerűen megvalósítható, és hardveres megvalósítás esetén nagyon nagy teljesítményre képes.

Ez az algoritmus a széles körben használt Unix adattömörítési algoritmus segédprogram tömörítése, és a GIF képformátumban használják. Ez lett az első olyan adattömörítési algoritmus, amelyet széles körben használtak a számítógépeken. Egy nagyméretű angol nyelvű szövegfájlt az LZW-vel jellemzően az eredeti méretének körülbelül a felére lehet tömöríteni.

LZSS

A LZSS a Lempel Ziv Storer Szymanski rövidítése, 1982-ben fejlesztették ki és jelentették be. Ez egy olyan adattömörítési algoritmus, amely az LZ77-et fejleszti. Ez a tömörítési folyamat egy olyan módszer beépítésével történik, amely szemmel tartja, hogy egy helyettesítés csökkenti-e a fájl méretét. Ha nem csökken, akkor a bemenet az eredeti formájában marad. Emellett nem preferálja az eltérő karakterek használatát, és csak az eltolási hosszpárokat részesíti előnyben.

Ezt az algoritmust elsősorban a fájlok archiválására használják különböző formátumokban, mint például a RAR vagy a ZIP, vagy hálózati adatok tömörítésére.

Szótári kódolási technikának nevezhető. Az LZSS megpróbál egy szimbólumokból álló karakterláncot egy ugyanilyen karakterlánc szótári helyére való hivatkozással helyettesíteni. A legfontosabb különbség az LZ77 és az LZSS között az, hogy az LZ77-ben a szótári hivatkozás hosszabb lehetett, mint az általa helyettesített karakterlánc. Az LZSS-ben az ilyen hivatkozások elhagyásra kerülnek, ha a hossz kisebb, mint a “töréspont”.

Deflate

A Deflate egy veszteségmentes adattömörítési algoritmusú fájlformátum, amely az LZSS és a Huffman-kódolás kombinációját használja. Phil Katz tervezte 1993-ban. A Huffman-kódolás szintén egy algoritmus, amelyet 1952-ben fejlesztettek ki. Ez egy entrópia kódolási algoritmusként definiálható, amely segít a kód hozzárendelésében a karakterek gyakorisága alapján.

Katz tervezte az eredeti algoritmust is, amelyet a Deflate adatfolyamok felépítéséhez használnak. Ahogy az RFC dokumentumban is szerepelt, a Deflate fájlokat előállító algoritmusról széles körben úgy gondolták, hogy szabadalmakkal nem védett módon megvalósítható. Ez vezetett a széleskörű használatához, a ZIP fájlformátum mellett, amelynek megtervezése Katz fő célja volt. A szabadalom már nem elérhető.

LZMA

Az LZMA a Lempel Ziv Markov-lánc algoritmus rövidítése, és 1998-ban tervezték és adták ki. Az LZ77 módosításának is mondható. Ez a módosítás a -Zip archiválóhoz készült .7z formátummal. A lánctömörítés olyan módszerét alkalmazzák, amely a módosított LZ77-et nem bájt-, hanem bit-szinten valósítja meg. A megjelenő kimenet további feldolgozásra kerül aritmetikai kódolással a további tömörítés elvégzése érdekében.

A többi tömörítési lépés teljesítménye a pontos megvalósítástól függ. Ez az adattömörítési algoritmus szótári tömörítési sémát használ, amely némileg nagyon hasonlít az Abraham Lempel és Jacob Ziv által 1977-ben közzétett LZ77 algoritmushoz. Magas tömörítési arányt és változó tömörítési szótárméretet is kínál. Míg a dekompresszió sebessége továbbra is nagyon hasonló a többi általánosan használt tömörítési algoritmushoz.

LZMA2

Az LZMA2-t 2009-ben tervezték és adták ki. Az LZMA módosításaként is definiálható. Jobbá teszi az LZMA-t azáltal, hogy nagyobb többszálas képességekkel javítja a teljesítményét. Az LZMA2 az inkompresszibilis adatok jobb kezelését is biztosítja. Ez egy egyszerű konténerformátum, amely tömörítetlen adatokat és LZMA-adatokat egyaránt tartalmazhat, méghozzá több különböző LZMA-kódolási paraméterrel.

Az LZMA2 támogatja a tetszőlegesen skálázható, többszálú tömörítést és dekompressziót, valamint a részben tömöríthetetlen adatok hatékony tömörítését. Ugyanakkor lehetnek biztonsági problémái, és nem biztonságos és kevésbé hatékony lehet, mint az LZMA. Egyszerű szavakkal, ez hasznos lehet az Ön számára, de igen, nem olyan biztonságos az LZMA-hoz képest.

Multi-Layer Perceptron (MLP)-alapú tömörítés

Az MLP olyan technológiaként definiálható, amely több neuronréteget használ a bemeneti, feldolgozási és kimeneti adatok megadására. Megvalósítható a dimenziócsökkentési feladatokra és az adatok tömörítésére is. Az MLP-alapú algoritmust először 1988-ban fejlesztették ki, és csatlakozik a már meglévő eljárásokhoz:

• Bináris kódolás- szabványos két szimbólumos kódolás.
• Kvantálás- a bemenet problémái egy folytonos halmazból egy diszkrét halmazba.
• Térbeli tartományi transzformáció – az adatok pixelenkénti módosítása.

Az optimális bináris kód meghatározásához az MLP algoritmus a fenti folyamatok kimeneteit használja fel egy dekompozíciós neurális hálózatba.

Az algoritmust továbbá olyan intuitív technikákkal módosították, amelyek lehetővé tették az adatok pontos közelítését teljesen a szomszédos adatok alapján a backpropagáción keresztül. Nagyon hasznos lehet a kép- és videóadatok tömörítésében.

Dee Coder- Deep Neural Network Based Video Compression

A Deep Coder egy Convolutional Neural Network (CNN) alapú keretrendszerként van definiálva. Ez teszi az ábrázolást alternatívává azokkal a videotömörítési technikákkal szemben, amelyeket már olyan régóta használunk. A prediktív és a maradék jelek különböző Convolutional Neural Networks (CNN) hozza által használt ez a modell.

A jellemzőtérképek bináris folyamba történő kódolását skalár kvantálással és egy nagyon régi és hagyományos fájltömörítési algoritmussal, a Huffman-kódolással végzi. Azt állítják, hogy ez a modell a jól ismert H.264/AVC videokódolási szabványhoz képest kiváló teljesítményt képes nyújtani.

Konvolúciós neurális hálózat (CNN) – alapú tömörítés

A CNN-eket különböző rétegekből álló neurális hálózatokként definiálják. Ezt elsősorban a képek felismerésére és a jellemző felismerésére használják. Abban a pillanatban, amikor tömörítésre alkalmazza, ezek a hálózatok konvolúciót használnak a szomszédos pixelek közötti kapcsolat kiszámításához. Ha összehasonlítjuk az MLP-alapú algoritmusokkal, a CNN-ek jobb tömörítési eredményeket mutatnak, mint azok.

Ez jobb szuperfelbontási teljesítményt és műtárgycsökkentést is biztosít. Ezen túlmenően a CNN-alapú adattömörítő algoritmusok javítják a JPEG-képek minőségét. Ez a csúcsjel-zaj arány és a szerkezeti hasonlóság csökkentésével történik.

A CNN-alapú tömörítés a High-Efficiency Video Coding szabvány teljesítményével is össze tud jönni. Ez az entrópia becslés alkalmazásával történik. Ez is nagyon hasznos lehet a fájlok tömörítésének elvégzésében.

Generative Adversarial Network (GAN)- Based Compression

A GAN-ok a neurális hálózatok alternatívájaként definiálhatók, amelyek két egymással versengő hálózatot használnak. Ez a pontosabb elemzések és előrejelzések előállítása érdekében történik. A GAN-alapú algoritmusokat először 2017-ben fejlesztették ki. Ezek az adattömörítési algoritmusok a hagyományos, általánosan használt módszerekhez, például a JPEG-hez vagy a WebP-hez képest több mint két és félszer kisebb fájlokat képesek tömöríteni.

A GAN-alapú algoritmusok valós idejű tömörítésre használhatók a párhuzamos feldolgozás együttes alkalmazásával. Ez az algoritmus úgy működik, hogy a képeket teljes mértékben a leginkább egyező jellemzők alapján tömöríti.

A dekódoláskor az ezen jellemzők által készített előrejelzések alapján a képek rekonstruálódnak. Ha összehasonlítjuk a CNN-alapú tömörítéssel, akkor a GAN-alapú tömörítés az adverzális veszteség kiküszöbölésével nagyon jó minőségű képeket eredményez Önnek.

Prediction by partial matching (PPM)

A PPM egy adaptív statisztikai adattömörítési technika, amely kontextusmodellezésen és előrejelzésen alapul. Ezek a modellek a tömörítetlen szimbólumfolyam korábbi szimbólumainak egy halmazát használják a folyam következő szimbólumának előrejelzésére. A PPM algoritmusok arra is használhatók, hogy az adatokat klaszterelemzés során előre jelzett csoportosításokba sorolják.
A korábbi szimbólumok száma, n, határozza meg a PPM modell sorrendjét, amelyet PPM(n)-ként jelölünk.

Léteznek olyan korlátlan változatok is, ahol a kontextusnak nincs hosszkorlátozása, és amelyeket PPM-ként jelölünk. Ha az összes n kontextusszimbólum alapján nem lehet előrejelzést készíteni, akkor n – 1 szimbólummal próbálkozunk. Ez a folyamat addig ismétlődik, amíg egyezést nem találunk, vagy nem marad több szimbólum a kontextusban. Ekkor egy rögzített előrejelzés készül.
A PPPM tömörítési implementációk egyéb részletekben is nagymértékben eltérnek egymástól. A tényleges szimbólumválasztást általában aritmetikai kódolással rögzítik, bár lehetséges Huffman-kódolás vagy akár valamilyen szótárkódolási technika alkalmazása is.

Futáshosszúság-kódolás (RLE)

Az RLE a veszteségmentes adattömörítés egyik formája, amelyben az adatfutamok (olyan sorozatok, amelyekben ugyanaz az adatérték sok egymást követő adatelemben fordul elő) egyetlen adatértékként és számlálásként kerülnek tárolásra, nem pedig az eredeti futásként. Ez leginkább olyan adatoknál hasznos, amelyek sok ilyen futást tartalmaznak.

Egyszerű grafikus képek, például ikonok, vonalrajzok, Conway’s Game of Life és animációk. Nem hasznos olyan fájlok esetében, amelyek nem tartalmaznak sok lefutást, mivel jelentősen megnövelheti a fájl méretét.

Az RLE-t használhatjuk a CompuServe által támogatott korai grafikus fájlformátumra is, amely fekete-fehér képek tömörítésére szolgált, de széles körben kiszorította a későbbi Graphics Interchange Format (GIF). Az RLE a Windows 3.x-ben kevéssé használt képformátumra is utal, amelynek kiterjesztése rule, azaz Run Length Encoded Bitmap, és amelyet a Windows 3.x indítóképernyőjének tömörítésére használtak.

bzip2

A bzip2 egy ingyenes és nyílt forráskódú adattömörítő program, amely a Burrows-Wheeler algoritmust használja. Csak egyes fájlokat tömörít, és nem fájlarchiváló. Julian Seward fejlesztette és Federico Mena karbantartja. Seward 1996 júliusában tette közzé a bzip2 első nyilvános kiadását, a 0.15-ös verziót. A tömörítő stabilitása és népszerűsége a következő években egyre nőtt, és Seward 2000 végén kiadta az 1.0-s verziót.

A projekt 2010 óta kilenc évnyi frissítési szünetet követően. 2019. június 4-én Federico Mena elfogadta a bzip2 projekt karbantartását. A bzip2 100 és 900 kB közötti méretű blokkokban tömöríti az adatokat.

A Burrows-Wheeler transzformációt használja a gyakran ismétlődő karaktersorozatok azonos betűkből álló karakterláncokká alakítására. Ezután move-to-front transzformációt és Huffman-kódolást alkalmaz. A bzip2 őse, a bzip a Huffman-kódolás helyett aritmetikai kódolást használt. A változtatásra egy szoftverszabadalmi korlátozás miatt került sor.

Huffman-kódolás

A Huffman-kódolás az optimális előtagkódolás egy sajátos típusa, amelyet általában veszteségmentes adattömörítésre használnak. Egy ilyen kód megtalálásának vagy használatának folyamata a Huffman-kódolás felhasználásával történik, amely egy olyan algoritmus, amelyet David A. Huffman fejlesztett ki, amikor még az MIT-n doktorált, és amelyet 1952-ben publikált az “A Method for the Construction of Minimum-Redundancy Codes” című munkájában.

A Huffman-algoritmus kimenete egy változó hosszúságú kódtáblának tekinthető egy forrásszimbólum (például egy karakter egy fájlban) kódolására. Az algoritmus ezt a táblázatot a forrásszimbólum minden lehetséges értékének becsült valószínűségéből vagy előfordulási gyakoriságából (súlyából) származtatja.

A többi entrópia kódolási módszerhez hasonlóan a gyakoribb szimbólumok általában kevesebb bitet használnak, mint a kevésbé gyakori szimbólumok. A Huffman-módszer hatékonyan megvalósítható. A kód megtalálása a bemeneti súlyok számával lineáris időben történik, ha ezek a súlyok rendezettek.

ZStandard

A Zstandard (vagy zstd) egy veszteségmentes adattömörítési algoritmus, amelyet Yann Collet fejlesztett ki a Facebooknál. A Zstd a referencia implementáció C nyelven. 2016. augusztus 31-én szabad szoftverként kiadták az implementáció 1. verzióját.
A Zstandard-t úgy tervezték, hogy a DEFLATE algoritmushoz (1991-ben kifejlesztett és az eredeti ZIP és gzip programokban használt) hasonló tömörítési arányt adjon, de gyorsabb legyen, különösen a dekompresszió esetében. A tömörítési szintek a negatív 5-től (leggyorsabb) a 22-ig (leglassabb tömörítési sebesség, de legjobb tömörítési arány) hangolhatóak.

A Zstd a maximális tömörítési szinten az LZMA, az LZAHM és a PPM tömörítési arányához közeli tömörítési arányt biztosít. Jobban teljesít, mint az LZA vagy a bzip2. A Zstandard eléri a jelenlegi Pareto-határt, mivel gyorsabban dekomprimál, mint bármely más, jelenleg elérhető, hasonló vagy jobb tömörítési arányú algoritmus

A szótáraknak nagy hatása lehet a kis fájlok tömörítési arányára, ezért a Zstandard képes a felhasználó által megadott tömörítési szótárat használni. Emellett képzési módot is kínál, amely képes szótárat generálni egy mintahalmazból.

Következtetés

Ezek az adattömörítési algoritmusok segítenek a fájlméret optimalizálásában. A különböző típusú adattömörítési algoritmusok különböző eredményeket biztosítanak. Ha azonban itt nem találja meg a megfelelő algoritmust, nézze meg ezt az útmutatót, és finomítsa a keresést. Algoritmusokból nincs hiány, de specifikusnak kell lennie, amikor a projektjéhez megfelelő algoritmust keresi.

Remélem, ez a cikk hasznos volt az Ön számára az igényeinek megfelelő legjobb adattömörítési algoritmus kiválasztásában. Köszönjük, hogy elolvasta ezt a cikket. Akkor is nézd meg a Legjobb titkosítási és zárolási algoritmusok.

Stay Tuned