adattömörítés
Ebben a kifejezést, vannak más célra, lásd. Tömörítés.
Az adattömörítés (Engl adattömörítést.) - algoritmikus konverzió. termelt csökkentése érdekében a kötet az általuk elfoglalt. Használt hatékonyabb felhasználása adattároló és szállító eszközök. Szinonimák - adatcsomag. tömörítés. tömörítési kódolás. forrás kódolás. Kapcsolat nevezett eljárás adatmentés (a kibontás, dekompressziós).
A kompressziós alapul kiküszöbölve redundancia. tartalmazta az eredeti adatokat. A legegyszerűbb példa a redundancia az ismétlés a szövegben töredékek (például szavak egy természetes vagy gépi kódú). Az ilyen redundancia általában eliminálódik cseréje ismétlődő szekvencia a már kódolt referencia-fragmenst, jelezve a hossza. Egy másik típusú redundancia annak a ténynek köszönhető, hogy néhány érték a tömörített adatokat gyakrabban fordulnak elő, mint a többiek. Csökkentése adatmérettől hogy kicseréljük gyakran előforduló adatok rövid kód szó, és ritka - hosszú (entrópiakódolás). Adat tömörítés, nem rendelkeznek azzal a tulajdonsággal redundancia (például egy véletlen jelet, vagy fehér zaj. A kódolt üzeneteket) lehetetlen elvileg veszteség nélkül.
Veszteségmentes tömörítést lehetővé teszi, hogy teljes mértékben helyreállítani az eredeti üzenetet, mert nem csökkenti az információ mennyiségét benne, annak ellenére, hogy a csökkenő hosszúságú. Ez a lehetőség csak akkor merül fel, ha a valószínűségek a sor üzenetek nem egyenletes eloszlásban, például az elméletileg lehetséges az előző kódolási üzenetek gyakorlatilag nem fordul elő.
Alapelvei adattömörítési
Az alapja minden tömörítési eljárás modell adatforrás, vagy pontosabban, a redundancia modell. Más szóval, a tömörítés használ néhány előzetes ismerete, hogy milyen adatok tömörítése. Nincs ilyen információ a forrás, akkor nem tud semmilyen feltételezéseket az átalakítás, ami csökkentené a üzenetek mennyisége. A redundancia modell lehet statikus, változatlan minden tömörített üzenetet vagy építeni, vagy paraméteres lépésben tömörítés (és helyreállítás). Módszerek a bemeneti adatok alapján változás modellje redundancia, az úgynevezett adaptív. Nonadaptive általában nagyon speciális algoritmusokat használnak az adatok, amelyek jól meghatározott és állandó tulajdonságokkal. A túlnyomó többsége algoritmusok kellően általános, hogy vagy olyan mértékben alkalmazkodó.
Minden adat tömörítési technikák vannak osztva két fő csoportra:
Jellemzői tömörítési algoritmusok és azok alkalmazhatóságát
tömörítési arány
Képarány - A fő jellemzője a tömörítési algoritmus. Ez úgy definiáljuk, mint a térfogataránya a tömörített adatok az eredeti térfogatra tömörítetlen adatok, hogy: k = S c S o >>>>. ahol k - tömörítési arány, így - térfogata az eredeti adatokat, és Sc - tömörített térfogatának. Tehát minél nagyobb a tömörítési arány, az algoritmus hatékonyan. Meg kell jegyezni:
- ha k = 1, az algoritmus nem termel tömörítés, azaz, egy kimeneti üzenet térfogatával egyenlő a bemeneti;
- Ha k> 1, az algoritmus egy üzenetet generál nagyobb tömörítetlen, tehát teljesít „káros” munkát.
A helyzet k <1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n бит составляет ровно 2 n. число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет не больше 2 n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить. Однако даже когда алгоритм сжатия увеличивает размер исходных данных, легко добиться того, чтобы их объём гарантировано не мог увеличиться более, чем на 1 бит. Тогда даже в самом худшем случае будет иметь место неравенство:
k ⩾ S o S o + 1> 1 >>>
Ezt az alábbiak szerint: ha az összeg a tömörített adat kisebb, mint az eredeti térfogat, vissza tömörített adatokat, hozzátéve, hogy „1”, különben vissza az eredeti adatokat az oldathoz hozzáadunk „0”).
A tömörítési arány lehet állandó (néhány audió tömörítési algoritmusok, képek, és így tovább. F. Például az A-törvény. Μ-törvény. ADPCM. Csonkolt blokk kódolás), és a változók. A második esetben, akkor lehet meghatározni, vagy egy adott üzenetet, vagy otsenon bizonyos kritériumoknak:
- közepes (általában néhány vizsgálati adatok);
- a maximális (legjobb esetben tömörítés);
- minimális (legrosszabb eset tömörítés);
vagy bármilyen más. Veszteséges tömörítési arány tehát erősen függ a minőségi vagy kompressziós megengedhető hiba. ami általában működik, mint a paraméter az algoritmus. Általában, állandó tömörítési arány csak akkor képesek adatok tömörítési technikák veszteséges.
Elfogadhatósága veszteségek
A fő szempont az közötti különbségek tömörítési algoritmusok a fentiekben ismertettük a jelenléte vagy hiánya veszteségeket. Általában veszteségmentes tömörítési algoritmusok egyetemes abban az értelemben, hogy azok alkalmazása természetesen lehetőség van bármilyen típusú adatot, míg alkalmazásának lehetőségét veszteséges tömörítés kell földelni. Bizonyos típusú adatok a korrupció nem elvben elfogadható. köztük
Rendszer követelmények algoritmusok
Különböző algoritmusok megkövetelheti különböző mennyiségű források a számítógépes rendszer, amelyen végre:
- RAM (a közbenső adatok);
- a nem-felejtő memória (a programkód és állandók);
- CPU időt.
Általában ezek a követelmények összetettségétől függ és „intelligens” algoritmus. Az általános tendencia: a hatékonyság és a sokoldalúság az algoritmus, a magas követelményeket támaszt a számítási erőforrások teszi. Azonban bizonyos esetekben, egyszerű és kompakt algoritmusok jobban működnek, mint komplex és sokoldalú. Rendszer követelmények határozzák meg a fogyasztói adottságok: a kevésbé igényes algoritmus, annál egyszerűbb és így kompakt, megbízható és olcsó rendszer, akkor végre kell hajtani.
Mivel a tömörítés és kicsomagolás algoritmusok párban dolgoznak, amelynek értéke az arány a rendszer követelményeinek nekik. Gyakran bonyolult lehet egy olyan algoritmus egyszerűsítése jelentősen eltérő. Tehát három lehetőség van:
Tömörítési algoritmusok ismeretlen formátumú adat
Két fő megközelítés tömörítés ismeretlen formátum:
- Minden lépésnél, a tömörítési algoritmus vagy más összenyomható szimbólum kerül a kimenő pufferben kompressziós jeladó van (egy speciális zászló, zászló, nem volt tömörítve), vagy egy csoport több karakter helyébe összenyomható utalás egybeesik egy csoport már kódolt szimbólumok. Mivel a helyreállítás a tömörített adatokat, így nagyon gyors, ez a megközelítés gyakran használják létre önkicsomagoló programot.
- Minden összenyomható karaktereket egyszer vagy minden egyes alkalommal előfordulásuk statisztika gyűlt össze a kódolt adatokat. Mindezek alapján a statisztikák kiszámításához valószínűségi érték a következő karaktert kell kódolni (vagy karaktersorozatot). Ezt követően alkalmazza az egyik vagy másik fajta entrópiakódolás. így például, az aritmetikai kódolás vagy Huffman-kódolás. hogy képviselje a közös rövid szekvenciák kódszót, és ritka - hosszabb.