Algoritmus Sequitur (neboli Neville-Manningův algoritmus ) je rekurzivní algoritmus vyvinutý Craigem Neville-Manningem a Ianem Wittenem v roce 1997 [1] . Algoritmus vytváří hierarchickou strukturu ( bezkontextovou gramatiku ) ze sekvence diskrétních znaků. Algoritmus pracuje v lineárním prostoru v lineárním čase. Lze jej použít v aplikacích pro kompresi dat [2] .
Algoritmus Sequitur vytváří gramatiku nahrazením nových pravidel pro opakované fráze v dané sekvenci, a proto poskytuje krátkou reprezentaci sekvence. Například pokud je sekvence
S→abcab,algoritmus dává
S→AcA, A→ab.Při pohledu na vstupní řetězec se algoritmus řídí dvěma pravidly pro efektivní generování gramatiky: jedinečnost dvojice znaků a použití pravidla .
Když je ze sekvence vybrán nový znak, přidá se k poslednímu vybranému znaku a vytvoří se nový pár znaků . Pokud byl takový pár vytvořen již dříve, vygeneruje se nové pravidlo, které nahradí oba výskyty párů znaků.
Tím je zajištěno, že se dvojice v gramatice vyskytuje maximálně jednou. Například v sekvenci S→abaaba se po zhlédnutí prvních čtyř znaků vytvoří dvojice ab, ba, aa . Když je vybrán pátý znak, nový pár „ab“ již byl vytvořen. Proto jsou oba páry 'ab' nahrazeny v S novým pravidlem (řekněme A). Nyní se gramatika změní na S→AaAa, A→ab a proces pokračuje, dokud nezůstanou žádné duplicitní páry.
Toto omezení zajišťuje, že všechna pravidla jsou použita více než jednou ve správných částech gramatiky. To znamená, že pokud se pravidlo vyskytne pouze jednou, mělo by být z gramatiky odstraněno a měla by být provedena příslušná náhrada. Například ve výše uvedeném příkladu, pokud je vyhledán poslední znak a je aplikováno pravidlo jedinečnosti pro 'Aa', pak gramatika dá S→BB, A→ab, B→Aa . Nyní se pravidlo 'A' vyskytuje pouze jednou v B→Aa . Takže A je odstraněno a nakonec se gramatika stane S→BB, B→aba .
Toto omezení umožňuje snížit počet pravidel v gramatice.
Algoritmus funguje tak, že se podívá na posloupnost koncových znaků a vytvoří seznam všech párů přečtených znaků. Když se pár objeví podruhé, oba páry jsou nahrazeny vytvořeným nekoncovým znakem , seznam párů znaků je aktualizován tak, aby odpovídal nové sekvenci, a procházení pokračuje. Pokud se dvojice neterminálních symbolů vyskytují pouze v nově vytvořené definici symbolu, je symbol nahrazen svou definicí a odstraněn ze seznamu neterminálních symbolů. Po dokončení skenování lze transformovanou sekvenci interpretovat jako pravidlo nejvyšší úrovně v gramatice pro původní sekvenci. Definice pravidel pro neterminální symboly lze nalézt v seznamu dvojic. Tyto definice pravidel mohou samy o sobě obsahovat další neterminální symboly, jejichž definice lze nalézt ve stejném seznamu dvojic [3] .
| Kompresní metody | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Bezztrátový |
| ||||||
| Zvuk |
| ||||||
| snímky |
| ||||||
| Video |
| ||||||