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

DCA - metoda antislovníku

Základní informace

Historie

Metodu navrhli v roce 1998 M. Crochemore, F. Mignosi, A. Restivo, S. Salemi.

Popis

Algoritmus využívá antislovníku (antidictionary - AD), tedy množiny slov (určité maximální délky), které se v nezakódovaném textu nenachází. V antislovníku však nejsou zbytečně všechna taková slova, ale pouze minimální zakázaná slova (minimal forbidden words - MFW). MFW je takové slovo u[1..n], že u se nevyskytuje ve vstupním textu, ale u[1..n-1] i u[2..n] se ve vstupním textu vyskytují.

Při samotném kódování se postupuje tak, že pokud kóduji i-tý znak vstupu a v antislovníku existuje slovo v[1..n] takové, že v[1..n-1] je suffixem dosud zpracovaného vstupu, nemusím i-tý znak vstupu vůbec kódovat, protože tento znak se dá při rozkódování zjistit právě pomocí onoho suffixu a antislovníku. Ostatní bity vstupu se normálně opisují na výstup.

Popis appletu

Při stavbě faktorového automatu se právě zkoumaný uzel označí modře a nově přidávaný červeně. Po jeho dokončení se modře označí uzly, které mají pouze jednoho následníka. Poté se vytvoří červeně označené uzly do páru.

Dále se během kódování pod slovníkem zobrazuje množina všech suffixů již zpracovaného vstupu rozšířená o znak "0" resp. "1", napsaný červenou barvou.

Pseudokód


 1:  function Tvorba AD (vstupní slovo w, max. délka slova v AD l)
 2:  begin
 3:     vytvoř strom všech faktorů vstupního slova délky maximálně l
 4:     hodnotou každého uzlu stromu je slovo, které je odpovídajícím 
 5:       faktorem (slovem na cestě stromem)
 6:     for each (uzel U stromu) do 
 7:      begin
 8:        if (U má pouze jednoho následníka) then 
 9:         begin
10:           nechť h je ohodnocení jediné hrany vedoucí z U (h ∈ {0,1})
11:           vytvoř uzel U' a označ jej jako forbidden word
12:           veď hranu z U do U' ohodnocenou ¬h
13:           vytvoř suffix-link - hranu vedoucí z U (ohodnoceného slovem s[1..n]) 
14:             do U'' ohodnoceného slovem s[2..n] (pokud takový U'' neexistuje,
15:             zkus s[3..n] atd.) 
16:         end
17:      end
18:     for each (uzel U, který je forbidden word) do 
19:      begin
20:        nechť P je přímý předek uzlu U
21:        nechť S je uzel, do kterého vede suffix-link z P
22:        nechť h je ohodnocení hrany z P do U
23:        if ((existuje uzel T takový, že do něj vede z S hrana ohodnocená h) 
24:          and (T není forbidden word)) then
25:         begin
26:           označ U jako minimal forbidden word - MFW
27:         end
28:      end
29:     vrať množinu ohodnocení všech uzlů označených MFW - antislovník AD
30:  end
31:  
32:  function Zakóduj slovo (antislovník AD, vstupní slovo w)
33:  begin
34:     nechť v = ε {zpracovaný vstup}
35:     nechť g = ε {výstup}
36:     for (i := 1 to |w|) do
37:      begin
38:        nechť M0 = množina všech přípon slova v rozšířených o 0 na konci
39:        nechť M1 = množina všech přípon slova v rozšířených o 1 na konci
40:        if ((M0 ∪ M1) ∩ AD ≠ Ø) then 
41:           g := g.wi
42:        v := v.wi
43:      end
44:     output(obsah g)
45:  end

Odkazy

  1. M. Crochemore, F. Mignosi, A. Restiva a S. Salemi: Text Compression Using Antidictionaries. 1998

Ukázka