Kompresní metoda ACBAssociative Coder of Buyanovsky

autor: George Buyanovsky

připravil Tomáš Skopal

podle knihy „Data Compression“ od D. Salomona,

1997, Springer, New York

ACB – Hlavní rysy

• slovníková bezeztrátová komprese

• velmi efektivní (lepší než RAR)

• vhodná pro kompresi textu

• relativně pomalá

• efektivita značně závislá na následném kódování

• není do detailu zveřejněna

Context & content

• posuvné okno podobně jako u LZ 77

text: swiss miss is missing

context

content

• každý posun okna o jeden znak vytvoří novou položku context-content :ss m|iss is mis

Context & content

• posuvné okno podobně jako u LZ 77

text: swiss miss is missing

context

content

• každý posun okna o jeden znak vytvoří novou položku context-content :ss m|iss is mis

s mi|ss is miss

Context & content

• posuvné okno podobně jako u LZ 77

text: swiss miss is missing

context

content

• každý posun okna o jeden znak vytvoří novou položku context-content :ss m|iss is mis

s mi|ss is miss mis|s is missi

Kontextový slovník

Struktura slovníku• je tvořen položkami kontext-content

• setříděná historie všech kontextů-contentů zdrojového textu

• položka je zatřizována lexikálně podle svého kontextu vůči kontextům položek ve slovníku – a to zprava doleva

...swiss |m ...swi|ss m ...s|wiss m ...swis|s m ...swiss|m ...sw|iss m

kontextycontenty

Kontextový slovník

Stav slovníku• je tvořen identicky pro kompresi i dekompresi

• narůstá o jednu položku pro každý zpracovaný znak textu (tj. na konci zpracování textu o n znacích má n položek)

• realizován ukazateli do zdroj. textu

...swiss |m ...swi|ss m ...s|wiss m ...swis|s m ...swiss|m ...sw|iss m

kontextycontenty

Základní metoda ACB

Aktuální stav slovníku: 1 …swiss |m 2 …swi|ss m 3 …s|wiss m 4 …swis|s m 5 …swiss| m 6 …sw|iss m

Nová položka: swiss m|iss is missing

zpracovaný text

nový kontext

Stav po šesti zpracovaných znacích (stejný u komprese i dekomprese) …

Základní metoda ACB

Algoritmus jednoho kroku komprese

Aktuální stav slovníku: 1 …swiss |m 2 …swi|ss m 3 …s|wiss m 4 …swis|s m 5 …swiss| m 6 …sw|iss m

Nová položka kontext: swiss m content: iss is m…

položka 2

2. Nalezení vzdálenosti nejvíce podobného contentu ve slovníku od pozice nalezeného kontextu (poloměr hledání) :položka 6, vzdálenost 4

4

1. Nalezení nejvíce podobného kontextu ve slovníku (zprava doleva) :

Základní metoda ACB

Algoritmus jednoho kroku komprese

Aktuální stav slovníku: 1 …swiss |m 2 …swi|ss m 3 …s|wiss m 4 …swis|s m 5 …swiss| m 6 …sw|iss m

Nová položka kontext: swiss m content: iss is m…

4

3. Zjištění délky shodné části obou contentů :

4. Zjištění prvního neshodného znaku v aktuálním contentu :5. Na výstup jde trojice [vzdálenost, délka, znak]

tj:4

4

´i´

[4, 4, ‘i’]

Základní metoda ACB

Algoritmus jednoho kroku komprese

Aktuální stav slovníku: 1 …swiss |m 2 …swi|ss m 3 …s|wiss m 4 …swis|s m 5 …swiss| m 6 …sw|iss m

Nová položka kontext: swiss m content: iss is m…

6. Přidáme do slovníku nové položky, které vznikly postupným rozšířením (posunutím) kontextu o nově zakódované znaky :…swiss m|iss i…swiss mi|ss i…swiss mis|s i…swiss miss| i…swiss miss |i

Základní metoda ACB

1 …swiss miss |i 2 …swiss |miss i 3 …swiss mi|ss i 4 …swi|ss miss i 5 …swiss m|iss i 6 …s|wiss miss i 7 …swiss mis|s i 8 …swis|s miss i 9 …swiss miss| i 10 …swiss| miss i 11 …sw|iss miss i

Stav slovníku s novýmipoložkami:

Základní metoda ACB

1. Nalezneme nejvíce podobný kontext ve slovníku (zprava doleva) :

Aktuální stav slovníku: 1 …swiss |m 2 …swi|ss m 3 …s|wiss m 4 …swis|s m 5 …swiss| m 6 …sw|iss m

Poslední položka kontext: swiss m content: neznámý trojice: [4,4,´i´]

položka 2

2. Z prvního členu trojice [v,d,z] a nalezené položky spočítáme pozici položky podobného contentu:

v=4 položka 6 4

Algoritmus jednoho kroku dekomprese

Základní metoda ACB

Aktuální stav slovníku: 1 …swiss |m 2 …swi|ss m 3 …s|wiss m 4 …swis|s m 5 …swiss| m 6 …sw|iss m

Poslední položka kontext: swiss m content: neznámý trojice: [4,4,´i´]

4

Algoritmus jednoho kroku dekomprese3. Z druhého členu trojice a nalezeného contentu získáme textový řetězec :d=4 „iss „

4. Řetězec pošleme spolu s třetím členem trojice na výstup :

5. Doplníme slovník stejně jako u komprese

i=´i´ „iss i„

Základní metoda ACB

Parametry metody:

• max. délka kontextu

• max. délka contentu

• poloměr hledání contentu

Vylepšená metoda ACB

…your |swiss mis …your swiss |mis …your swiss mi|s …your swi|ss mis …your swiss m|is …yo|ur swiss mis …young mis|creant… …unusual mis|fortune… …plain mis|ery… …no swiss mis|spelled it so… …no swiss mis|s is mistaken… …or swiss mis|read it to……your swiss mis|s is missing… …always mis|placed it… …your swis|s mis

1. V každém kroku vytvoříme asociativní seznam tak, že ze slovníku vybereme všechny ty položky, jejichž kontexty se shodují s aktuálním kontextem v alespoň k znacích.

Aktuální položka (řetězec S):

…your swiss mis|s is mistress…

pro k = 9

Vylepšená metoda ACB

Aktuální položka (řetězec S):

…your swiss mis|s is mistress…

2. Tento seznam setřídíme zleva doprava a zjistíme, mezi které položky padne řetězec S.

1. swiss mis|read it to…2. swiss mis|s is missing…3. swiss mis|s is mistaken…4. swiss mis|s is trouble…5. swiss mis|spelled it so…

3. swiss mis|s is mistaken…S. swiss mis|s is mistress…4. swiss mis|s is trouble…

Vylepšená metoda ACB

3. Nyní budeme pracovat s trojicí řetězců jako s bitovými poli. A protože jsou setříděné, mohou nastat dva případy.

a)3. xx…x0zz…z0AS. xx…x0zz…z1B4. xx…x1CC…

b)3. xx…x0CC…S. xx…x1zz…z0B4. xx…x1zz…z1A

xx…x – bity, ve kterých se shodují všechny tři řetězcezz…z – bity, ve kterých se shoduje řetězec S s jedním z

ostatních řetězců

Vylepšená metoda ACB

4. Na výstup jde trojice [m,b,l], kde m je index předchozí položky před S, b je hodnota podtrženého bitu a l je délka řetězce zz…z

a)3. xx…x0zz…z0AS. xx…x0zz…z1B4. xx…x1CC…

b)3. xx…x0CC…S. xx…x1zz…z0B4. xx…x1zz…z1A

Vylepšená metoda ACB

Dekomprese proběhne opět inverzně.

Kódování – statistika trojic

Referenční příklad:

Textový (html) soubor, 250 kB, povídka v češtině,

Abeceda: znaky hodnot ASCII

Základní metoda ACB

• Konečný výsledek komprese je podstatně závislý na konečném kódování

Kódování – statistika trojicposloupnost prvních členů

trojic

Ovlivňuje zejména parametr ‘poloměr hledání contentu’

Content offset (prvních 5000 trojic)

-128

-78

-28

22

72

122

Rozsah

hodnot

Kódování – statistika trojicčetnost prvních členů trojic

Četnosti hodnot offsetů (prvních 50 000 troj ic)

1

10

100

1000

10000

Rozsah hodnot

Po

čet

výsk

ytů

(lo

gar

itm

ické

měř

ítko

)

Kódování – statistika trojicposloupnost druhých členů

trojicDélky contentů (prvních 5000 trojic)

0

5

10

15

20

25

Rozsah hodnot

Kódování – statistika trojicčetnost druhých členů trojic

Četnosti délek contentů (prvních 50 000 troj ic)

1

10

100

1000

10000

100000

Roz sah hodnot

Po

čet

výsk

ytů

(lo

gar

itm

ické

měř

ítko

)

Odkazy

Buyanovsky G., Associative Coding, Monitor, duben 1994

Moskva, č. 8

Salomon D., Data Compression, 1997, Springer, New York

Web:

http://www.ms.mff.cuni.cz/~jtro8667/vytvory/acb/acb.htm