Õppetund
Teooria — Jooksupikkuskodeerimine (RLE)
Jadapikkuskodeerimine asendab iga maksimaalse ühesuguste sümbolite jada ühe paariga (sümbol, arv). Näidikule ei jõua tekst, vaid kaks arvu: N märki ja R jada. Kõik ülejäänud arvud lehel on nende kahe jagatis.
Mida iga sümbol tähendab
N- sisendmärkide arv — see, kui pikk on sinu kirjutatu, ei muud.
R- jadade arv, see tähendab ühe korduva sümboli maksimaalsete plokkide arv. R kasvab ühe võrra igal pool, kus kaks naabrit erinevad: loetakse piire, mitte märke.
L̄N/R, keskmine jada pikkus. See ongi ainus suurus, mis tulemuse otsustab.ratioN/2R, see tähendabL̄/2. Üle 1 on väljund sisendist väiksem.
Kust valem tuleb
- Loe jadasid, mitte märke. Stringis
0010111100001111erinevad naabrid viies kohas, seega on kuus jada ja rida näitabR=6. - Kodeeritud suurus on
2Rja ei midagi muud. Millest jadad koosnevad, ei jõua arvutusse kunagi — kuus jada maksavad kaksteist ühikut, olgu need pikslid, tähed või numbrid. - Jaga:
ratio = N/2R = L̄/2. Tasakaalupunkt on seegaL̄ = 2ja see on täpselt saavutatav — kirjutaAABBja tulbad näitavad 4 baiti sisse, 4 baiti välja. - Kaks suunda ei ole sümmeetrilised. Ülespoole piiri ei ole: üksainus miljoni märgi pikkune jada kodeerub üheks paariks. Allapoole on põrand
0.50×ja sellest madalamale ei saa, sest halvim, mida sisend teha suudab, on anda igale märgile oma jada.
Kuidas nähtut lugeda
Kõik neli näidet on täpselt kuusteist märki pikad, mistõttu tasub neid lugeda ühe komplektina. Pildirida annab kolm jada ja 6 baiti. Klassikalised jadad annab neli ja 8. Bitimask annab kuus ja 12. Halvim juht annab kuusteist ja 32. Sisse sama pikkus, välja 6 kuni 32 baiti — viiekordne vahe, mille otsustab üksnes R. Kirjuta siis hello world: üksteist märki, kümme jada, 20 baiti. Tavaline tekst asub selle vahemiku alumises otsas, ja just seepärast on jadapikkuskodeerimine kompressorite osa, mitte kompressor omaette.
- Eeldab
- Et paar maksab täpselt 2 ühikut, et sümbol ja arv on ühelaiused ning et arv võib olla kui tahes suur. Päris kodeerijad annavad arvule kindla laiuse — ühe baidi, seega 255 — ja peavad pikema jada mitmeks paariks murdma, mis tõstab tasakaalupunkti veidi üle 2. Ühelaiuse eeldus kukub kõige selgemalt läbi just seal, kus see meetod on parim: 1-bitises faksis on sümbol üks bitt, arv aga mitte.
- Ei kehti, kui
- Põrand
0.50×ei ole viga, mida annaks välja projekteerida. Kadudeta kodeerija peab olema pööratav, nii et erinevad sisendid annaksid erinevad väljundid; lühikesi sõnesid, kuhu kujutada, on aga vähem kui pikki. Iga skeem, mis lühendab kas või ühte sisendit, pikendab seetõttu mõnda teist. See on loendamisfakt, mitte jadapikkuskodeerimise omadus. PackBits kolmandas ülaltoodud tähelepanekus surub oma halvima juhu ühele juhtbaidile 128 kohta — alla 1% — ja kaugemale ei jõua keegi, sest põrandat saab lõputult alandada, kuid mitte kunagi saavutada. See meetod lihtsalt kannab seda kulu väljaspool, näidikul, mille liikumist saab jälgida.
Ülesanne täielikult lahendatud
-
AAAAAABBBCCDDDDD käigupikkuse kodeerimine neljaks paariks 5 sammu
Käituskodeerimine teisendab jada AAAAAABBBCCDDDDD neljaks paariks. Arvuta välja tihendusaste ja seejärel täpne tingimus, mille korral see skeem muudab faili suuremaks.
-
Kodeering on ilmselge: asenda iga seeria märgiga ja selle pikkusega. Kuusteist märki koondub neljaks paariks.
-
Selle skeemi mis tahes sisendit kirjeldavad kaks arvu — selle pikkus ja seeriate arv — ning nende suhe on seeria keskmine pikkus. Siin on see 4.
-
Nüüd loenda ausalt. Iga paar maksab kaks sümbolit, ühe märgi ja ühe arvu, seega on väljund 2R sisendi N vastu. Miski muu andmete juures ei loe.
-
Skeem annab seega võidu täpselt siis, kui 2R < N, mis teiseneb tingimuseks, et seeria keskmine pikkus on üle 2. Siin 8 vastu 16 — puhas pooleks tegemine — ja otsuselida paneelil ütleb sama asja ühe sümboliga.
-
Sellest künnisest allpool see kaotab ning kui seeria keskmine pikkus on 1, kaotab see maksimaalselt: iga märk muutub paariks, dubleerides faili suuruse.
Vastus
Tööriist kuvab N = 16 ja R = 4, seeria keskmiseks pikkuseks 4 ja võiduks 2×. See tingimus ongi peaasi: RLE tihendab parajasti siis, kui seeriate keskmine pikkus on üle kahe, ning see on üks väheseid tihendusskeeme, mille tasakaalupunkt on üksainus silmaga kontrollitav arv. Kirjuta kasti ABCD ja vaata, kuidas see paisub kahekordseks. See pole puudus — seetõttu püsib RLE kasutusel vaid seal, kus seeriad on ehituslikult tagatud: faksi skaneerimisridadel, hõredatel bittkaartidel ja JPEG lamedatel aladel pärast kvantimist, mitte kunagi tavatekstis.
-
Õpitee
Käsitsi tihendamine
Allikad (3)
- Insight block 3 — PackBits, and the control byte that bounds its worst case: Adobe Systems, TIFF Revision 6.0, section 9 (PackBits Compression), 1992 — the format where Apple's variant became a standard compression mode.
- The run lengths themselves as the thing to be coded: S. W. Golomb, "Run-length encodings (Corresp.)." IEEE Transactions on Information Theory 12(3), 399–401, 1966.
- And the earlier paper that measured how long runs in real pictures actually are: J. Capon, "A probabilistic model for run-length coding of pictures." IRE Transactions on Information Theory 5(4), 157–163, 1959.