LZ77 ja LZ78 ovat häviöttömiä pakkausalgoritmeja , jotka julkaistiin israelilaisten matemaatikoiden Abraham Lempelin ja Yaakov Zivin julkaisuissa vuosina 1977 ja 1978 . Nämä algoritmit ovat tunnetuimpia muunnelmia LZ* -perheestä , joka sisältää myös LZW , LZSS , LZMA ja muita algoritmeja.
Molemmat algoritmit ovat sanakirjamenetelmiä, toisin kuin muut redundanssin vähentämismenetelmät, kuten RLE ja aritmeettinen pakkaus . LZ77 on "liukuikkuna"-algoritmi, joka vastaa LZ78:ssa ensimmäisen kerran ehdotetun sanakirjalähestymistavan implisiittistä käyttöä.
Voidaan sanoa, että LZ* -perheen algoritmit ovat monimutkaisempi yleistys RLE :ssä käytetystä yksinkertaisesta ja intuitiivisesta tiedonpakkausmenetelmästä . Tämän algoritmin ymmärtämiseksi on välttämätöntä ymmärtää sen kaksi komponenttia: liukuva ikkunaperiaate ja sattumakoodausmekanismi .
Liukuvan ikkunan periaatteen mukainen koodausmenetelmä ottaa huomioon jo kohdatut tiedot, eli tiedot, jotka kooderi ja dekooderi ovat jo tiedossa (sanoman merkkijonon toinen ja sitä seuraavat esiintymät korvataan linkkien kautta sen ensimmäiseen esiintymiseen).
Tämän periaatteen vuoksi LZ*-algoritmeja kutsutaan joskus liukuikkunoiden pakkausmenetelmiksi. Liukuvaa ikkunaa voidaan pitää puskurina (tai monimutkaisempana dynaamisena tietorakenteena), joka on järjestetty muistamaan ja käyttämään aiemmin "sanottuja" tietoja. Siten LZ77:n mukainen pakkauskoodausprosessi muistuttaa ohjelman kirjoittamista, jonka komennot mahdollistavat pääsyn "liukuvan ikkunan" elementteihin ja lisää pakatun sekvenssin arvojen sijaan viittauksia näihin arvoihin. "liukuikkunassa". Liukuvan ikkunan kokoa voidaan muuttaa dynaamisesti ja se voi olla 2, 4 tai 32 kilotavua. On myös huomattava, että kooderin ikkunan koko voi olla pienempi tai yhtä suuri kuin dekooderin ikkunan koko, mutta ei päinvastoin.
Yllä oleva koodausprosessin vertailu "ohjelmointiin" voi johtaa ennenaikaiseen johtopäätökseen, että LZ77-algoritmi kuuluu kontekstin mallinnusmenetelmiin . Siksi on huomattava, että LZ77-algoritmi luokitellaan yleensä sanakirjatietojen pakkausmenetelmäksi , kun termiä "dynaaminen sanakirja" käytetään "liukuvan ikkunan" käsitteen sijaan.
Ennen kuin siirrymme koodausmekanismin tarkasteluun, selvennetään vastaavuuden käsite ( englannin kielestä match ). Tarkastellaan N elementin sarjaa. Jos sekvenssin kaikki elementit ovat uniikkeja, sellainen sekvenssi ei sisällä yhtä toistuvaa elementtiä tai toisin sanoen sekvenssissä ei ole vähintään kahta samanlaista tai yhteneväistä elementtiä.
Normaalissa LZ77-algoritmissa ottelut koodataan pariksi:
Jatkamalla jo annettua analogiaa ohjelmoinnin kanssa, huomaamme, että useimmissa LZ77-algoritmille omistetuissa artikkeleissa koodattu pari tulkitaan juuri käskynä kopioida merkkejä liukuvasta ikkunasta tietystä paikasta tai kirjaimellisesti seuraavasti: "Palaa offset- arvo merkkipuskuriin ja kopioi merkin pituusarvo
Vaikka tämä tulkinta saattaa tuntua intuitiiviselta pakollisille ohjelmoijille , se kertoo vain vähän LZ77-algoritmin luonteesta pakkausmenetelmänä. Tämän pakkausalgoritmin erikoisuus on, että koodatun pituus-offset- parin käyttö ei ole vain hyväksyttävää, vaan myös tehokasta tapauksissa, joissa pituusarvo ylittää offset-arvon.
Esimerkki kopiokomennolla ei ole täysin ilmeinen: "Palaa 1 merkki taaksepäin puskurissa ja kopioi 7 merkkiä nykyisestä paikasta alkaen." Kuinka voit kopioida 7 merkkiä puskurista, kun puskurissa on tällä hetkellä vain 1 merkki? Seuraava koodausparin tulkinta voi kuitenkin selventää tilannetta: jokainen 7 seuraava merkki on sama (vastaa) niitä edeltävää 1 merkkiä.
Tämä tarkoittaa, että jokainen merkki voidaan määrittää yksiselitteisesti siirtämällä takaisin puskurissa - vaikka annettu merkki ei olisi vielä puskurissa, kun nykyinen pituus-offset- pari dekoodataan . Tällainen koodattu pari olisi merkkijonon (pituusarvon määrittämä) moninkertainen toisto (määritelty offset-arvolla), joka on RLE :n yleisempi muoto .
Valitut merkit eivät ole koodausjärjestyksessä.
Toisin kuin LZ77, joka toimii jo vastaanotettujen tietojen kanssa, vuonna 1978 ehdotettu LZ78 [1] keskittyy tietoihin, jotka vain vastaanotetaan (LZ78 ei käytä "liukuvaa" ikkunaa, se tallentaa sanakirjan jo katsotuista lauseista). Algoritmi lukee viestin merkkejä, kunnes kertynyt osamerkkijono sisällytetään kokonaan yhteen sanakirjalauseista. Heti kun tämä merkkijono ei enää vastaa vähintään yhtä sanakirjalausetta, algoritmi luo koodin, joka koostuu sanakirjassa olevan merkkijonon indeksistä, joka sisälsi syötemerkkijonon viimeiseen syötettyyn merkkiin asti, ja merkistä, joka rikkoi osuman. Sitten syötetty osamerkkijono lisätään sanakirjaan. Jos sanakirja on jo täynnä, niin vertailuissa vähiten käytetty lause poistetaan siitä alustavasti.
Olkoon merkkijono ACAGAATAGAGA annettu.
| Sanakirja | Lue rivin sisältö | Koodi |
|---|---|---|
| A | <0,A> | |
| A=1 | C | <0,C> |
| A = 1 C = 2 |
AG | <1,G> |
| A = 1, C = 2 AG = 3 |
AA | <1,A> |
| A = 1, C = 2 AG = 3, AA = 4 |
T | <0, T> |
| A = 1, C = 2, AG = 3 AA = 4, T = 5 |
AGA | <3,A> |
| A = 1, C = 2, AG = 3 AA = 4, T = 5, AGA = 6 |
G | <0,G> |
| A=1, C=2, AG=3, AA=4 T=5, AGA=6, G=7 |
A | <1,EOF> |
Työn tuloksena tulee sekvenssi: <0, A><0, C><1, G><1, A><0, T><3, A><0, G><1, EOF> .
| Puristusmenetelmät _ | |||||||
|---|---|---|---|---|---|---|---|
| Teoria |
| ||||||
| Häviötön |
| ||||||
| Audio |
| ||||||
| Kuvat |
| ||||||
| Video |
| ||||||