English
předchozí hlavní stránka obsah další

ACB (Associative Coder of Buyanovsky)

Základní informace

Popis

Popis algoritmu

  1. Aktuální kontext je porovnán s položkami slovníku (jejich kontextovou částí) (zprava doleva).
  2. Aktuální kontent je porovnán s kontenty položek slovníku (normálně - zleva doprava).
  3. Na výstup zapíšeme trojici (d, count, ch).
    • d - vzdálenost nalezeného nejpodobnějšího kontentu a nejvíce odpovídajícího kontextu (může být záporná).
    • count - počet shodných písmen (chceme co největší, ale může být 0).
    • ch - následující (1. neshodující se) znak v look-ahead bufferu (jako u LZ77).
  4. Aktualizujeme slovník (přidání nových frází, rozšíření kontentů).
  5. Posunem okénko o count + 1 pozic doprava.

Struktura slovníku

  • Je tvořen položkami kontext-kontent.
  • Setříděná historie všech kontextů-kontentů 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.

Stav slovníku

  • Je tvořen identicky pro kompresi i dekompresi.
  • Bývá často realizován ukazateli do zdroj. textu.

Parametry metody

  • Maximální délka kontextu.
  • Maximální délka kontentu.

Kódování výstupu

  • Jednotlivé trojice (d, count, ch) se mohou do výstupu kódovat například Huffmanovým kódem.

Pseudokód


 1:  begin
 2:     nastavení pozice výhledového okénka v textu
 3:     while (!EOF) do
 4:      begin
 5:        int i := pozice nejlépe shodujícího se kontextu ve slovníku 
 6:        int j := pozice nejlépe shodujícího se kontentu ve slovníku 
 7:        int count := počet shodných znaků od začátku s nalezeným kontentem
 8:        char ch = znak na pozici count +1 
 9:        output(j-i, count, ch) 
10:        aktualizuj slovník(vlož nové stavy a rozšiř kontenty)   
11:        posuň výhledové okénko o count + 1 pozic doprava
12:      end 
13:  end

Odkazy

  1. D. Salomon: Data Compression. Springer, New York, 1997.
  2. G. Buyanovsky: Asociative coding. Monitor, 8:10-19, 1994.
  3. Josef Troch: Algoritmus ACB.

Ukázka