LZ77 kokkupakkimise demo

Jälgi, kuidas liikuv aken skannib vasakult paremale: igal sammul leiab see otsinguaknas pikima tagasiviite ja väljastab tokeni (nihe, pikkus, literaal).

Näidisarvutus — LZ77 kokkupakkimise demo

Ettevaade	[0..7] "abracada"
Väljastatud tokeneid: 1 / 6	5.18×
Väljundtokenid	(0,0,'a')

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Suurem aken aitab vähem, kui ta maksab 🖖

Näib ilmselge, et laiem otsinguaken pakib paremini, sest rohkem eellugu tähendab rohkem võimalusi vastet leida. Konks on selles, et iga üksik viit peab suutma osutada ükskõik kuhu selles aknas, nii et akna laiendamine pikendab kaugusevälja iga väljastatava viite jaoks — sealhulgas nende tuhandete jaoks, mis pidid ulatuma vaid mõne baidi tagasi. Kahekordista aken ja lisad neile kõigile ühe biti, ükskõik kas see tõi pikema vaste või mitte. Just see kompromiss on põhjus, miks DEFLATE, ZIP-i, PNG-i ja gzipi sisemine algoritm, jäi 32 KB peale pidama ja püsis seal aastakümneid: piisavalt kaugele, et tabada tavatekstis tegelikku kordumist, ja piisavalt lähedale, et nihked jääksid odavaks.

Kopeeri, ära korda 🖖

Kui algoritm jõuab tekstini, mida ta on juba lugenud, ei kirjuta ta seda uuesti välja. Selle asemel märgib ta lühidalt: „mine nihke jagu märke tagasi ja kopeeri sealt pikkuse jagu märke“. Iga märgend on kujul (offset, length, literal): tagasiviide koos ühe uue märgiga. Korduvaid sõnu või mustreid täis tekst muutub palju väiksemaks, juhuslikud andmed aga peaaegu ei tihene.

Kui üks token muutub pikaks jadaks 🖖

Vaste võib osutada vaid ühe märgi taha ja ikkagi kopeerida rohkem märke, kui neid sinna veel jõudnud on. offset 1 korral kopeerib dekooder iga baidi kohe, kui selle kirjutab, nii et üksainus token nagu (1, 5, ...) avab ühest a-st sõna aaaaaa. Nõnda tuleneb klassikaline seeriapikkuse kodeerimine (RLE) LZ77-st tasuta — „koopia" kattub tekstiga, mida alles luuakse. Proovi korduvat näidet, et näha, kuidas vastepiirkond ulatub praegusest positsioonist kaugemale.

Ülesanne täielikult lahendatud

"abracadabra" kuus elementi 16 tähemärgi pikkuse otsinguaknaga 5 sammu
Paneelil on pärast ühte tokenit näit 5,18×. Arvutage välja, mida see näitab pärast kõiki kuut. Sisend on "abracadabra", otsinguaken on 16 märki ja ettelugemispuhver on 8.
1. Token koosneb kolmest fikseeritud laiusega väljast, seega otsustavad selle maksumuse kaks seadistust, mitte andmed. Nihe peab adresseerima mis tahes positsiooni aknas, pikkus mis tahes väärtust kuni puhvri suuruseni ja literaal on töötlemata bait.
  
  $⌈ lo g_{2} (W + 1)⌉ + ⌈ lo g_{2} (B + 1)⌉ + 8 = ⌈ lo g_{2} 17 ⌉ + ⌈ lo g_{2} 9 ⌉ + 8 = 5 + 4 + 8 = 17 bits$
2. Kooder skaneerib vasakult paremale ja võtab pikima kattuvuse, mida aken pakub. Esimese kolme märgi taga ei asu midagi, seega 'a', 'b' ja 'r' maksumuseks on igaühel üks terve token, et neid üks kord öelda. Vaid viimane token tasub end ära, kopeerides sõne "abra" positsioonilt 0.
  
  $(0, 0, a) (0, 0, b) (0, 0, r) (3, 1, c) (5, 1, d) (7, 4, \emptyset)$
3. Paneelil olev suhe on jooksev näit ning jagab kogu sisendi seni toodetud väljundiga. Pärast ühte tokenit kaalub see ühteteist märki seitsmeteistküne biti vastu, mistõttu see algabki nii kõrgetelt väärtustelt.
  
  $\frac{11 \times 8}{1 \times 17} = \frac{88}{17} = 5.18 \times$
4. Kuus tokenit, igaüks seitseteist bitti, teeb 102 bitti 88-bitise sisendi vastu. Kodeering on suurem kui asi, mida see kodeerib.
  
  $\frac{11 \times 8}{6 \times 17} = \frac{88}{102} = 0.86 \times$
5. Tasuvuspiir on ühe jagamise kaugusel. Token maksab 17 bitti ja ostab mingi arvu märke, mille väärtus on igaühel 8 bitti, seega võidab skeem vaid siis, kui keskmine token liigub edasi rohkem kui 17/8 märki — ja nendest kuuest teeb seda vaid viimane.
  
  $\frac{N}{T} > \frac{17}{8} = 2.125, \frac{N}{T} = \frac{11}{6} = 1.83$
Vastus

Paneel kuvab 5,18× pärast esimest tokenit ja 0,86× pärast kuuendat: sama sõne, sama kodeering, mõlemal pool arvu 1,0. Meeles pidamist vääriv näitaja on 2,125 märki tokeni kohta, mis on lihtsalt tokeni laius jagatud kaheksaga, ja see ongi kogu katse selle kohta, kas LZ77 aitab antud sisendit. Lisaks määravad need andmed hinna nupule, mis näib tasuta. Otsinguakna laiendamine 64-le lisab kaks bitti igale nihkeväljale ja selle sõne puhul ei leia see üldse pikemat kattuvust — liigendus on ikka samad kuus tokenit — seega langeb suhe väärtusele 0,77×. Iga haardeulatuse dubleerimine maksab ühe biti lisaks igal tokenil, olgu see kasutatud või mitte.

$\frac{N}{T} > \frac{⌈ lo g _{2} ( W + 1 )⌉ + ⌈ lo g _{2} ( B + 1 )⌉ + 8}{8}$

Õpitee

Käsitsi tihendamine

Viib edasi Burrows-Wheeler sümbolite asemel fraasides mõõdetavad kordused: tagasiviite, mis ütleb, kui kaugele tagasi minna ja kui palju kopeerida.

Allikad (1)

The algorithm, and the offset-1 trick block 3 turns on: J. Ziv and A. Lempel, "A universal algorithm for sequential data compression." IEEE Transactions on Information Theory 23(3), 337–343, 1977.

42Mathi meeskond · Uuendatud 2026-08-17

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

abracadabra → 6 tokenit - „abracadabra“: 6 märgendit 11 märgi kohta. Viimane neist läheb 7 märki tagasi ja kopeerib 4 märki ehk kogu „abra“ ühe viitega.
aabaabaabaab → 3 tokenit - „aabaabaabaab“: 4 märgendit 12 märgi kohta. Üks neist läheb vaid 3 märki tagasi, kuid kopeerib 7, nii et vaste ulatub parajasti kirjutatavast märgist edasi. Nii saame saripikkuskodeeringu pealekauba.
the quick brown fox → 16 tokenit - „the quick brown fox“: 16 märgendit 19 märgi kohta ning pikim vaste on kõigest üks täht. Nii lühikeses tekstis pole peaaegu millelegi tagasi viidata.
ATGATCGATCG → 5 tokenit - „ATGATCGATCGATCG“: 6 märgendit 15 aluse kohta. Viies viide läheb 4 märki tagasi ja kopeerib 7, kattudes iseendaga, sest ATCG kordusperiood on täidetavast vastest lühem.