Algoritmul Sequitur

Algoritmul Sequitur (sau algoritmul Neville-Manning ) este un algoritm recursiv dezvoltat de Craig Neville-Manning și Ian Witten în 1997 [1] . Algoritmul creează o structură ierarhică ( gramatică fără context ) dintr-o secvență de caractere discrete. Algoritmul funcționează în spațiu liniar în timp liniar. Poate fi folosit în aplicații de compresie a datelor [2] .

Restricții

Algoritmul Sequitur construiește o gramatică prin înlocuirea unei noi reguli cu fraze repetate într-o anumită secvență și, prin urmare, oferă o scurtă reprezentare a secvenței. De exemplu, dacă secvența este

algoritmul dă

Când se uită la un șir de intrare, algoritmul urmează două reguli pentru generarea eficientă a gramaticii: unicitatea unei perechi de caractere și utilizarea regulii .

Unicitatea unei perechi de simboluri

Când un caracter nou este selectat din secvență, acesta este adăugat la ultimul caracter selectat și se formează o nouă pereche de caractere . Dacă o astfel de pereche a fost formată înainte, este generată o nouă regulă pentru a înlocui ambele apariții ale perechilor de caractere.

Acest lucru asigură că perechea apare cel mult o dată în gramatică. De exemplu, în secvența S→abaaba, după vizualizarea primelor patru caractere, se formează perechi ab, ba, aa . Când este selectat al cincilea caracter, noua pereche „ab” a fost deja formată. Prin urmare, ambele perechi de „ab” sunt înlocuite în S cu o nouă regulă (să zicem, A). Acum gramatica devine S→AaAa, A→ab și procesul continuă până când nu mai există perechi duplicate.

Folosind regula

Această restricție asigură că toate regulile sunt folosite de mai multe ori în părțile corecte ale gramaticii. Adică, dacă o regulă apare o singură dată, aceasta ar trebui eliminată din gramatică și trebuie făcută înlocuirea corespunzătoare. De exemplu, în exemplul de mai sus, dacă se caută ultimul caracter și se aplică regula unicității pentru „Aa”, atunci gramatica va produce S→BB, A→ab, B→Aa . Acum regula „A” apare o singură dată în B→Aa . Deci A este eliminat și în cele din urmă gramatica devine S→BB, B→aba .

Această restricție vă permite să reduceți numărul de reguli din gramatică.

Descrierea metodei

Algoritmul funcționează prin analizarea secvenței de caractere terminale și construirea unei liste cu toate perechile de caractere citite. Când perechea apare a doua oară, ambele perechi sunt înlocuite cu caracterul non-terminal creat , lista de perechi de caractere este actualizată pentru a se potrivi cu noua secvență și navigarea continuă. Dacă perechile de simboluri non-terminale apar numai în definiția simbolului nou creată, simbolul este înlocuit cu definiția sa și eliminat din lista simbolurilor non-terminale. Când scanarea este finalizată, secvența transformată poate fi interpretată ca regula de nivel superior în gramatică pentru secvența originală. Definițiile regulilor pentru simbolurile non-terminale pot fi găsite în lista de perechi. Aceste definiții de reguli pot conține ele însele simboluri suplimentare non-terminale, ale căror definiții pot fi găsite în aceeași listă de perechi [3] .

Vezi și

• Gramatică fără context

• Comprimarea datelor

• Comprimarea datelor fără pierderi

• Straight Grammar

• Codificarea perechilor de octeți

Note

1. ↑ Nevill-Manning, Witten, 1997-1 .
2. ↑ Nevill-Manning, Witten, 1997-2 , pp. 3–11.
3. ↑ GrammarViz 2.0 - Implementarea Sequitur și Sequitur paralel în Java

Literatură

• Nevill-Manning CG , Witten IH Identificarea structurii ierarhice în secvențe: un algoritm de timp liniar. - 1997. - . - arXiv : cs/9709102 .

• Nevill-Manning CG , Witten IH Linear-Time, Incremental Hierarchy Inference for Compression // Proceedings DCC '97. Conferință de compresie a datelor. - 1997. - ISBN 978-0-8186-7761-8 . - doi : 10.1109/DCC.1997.581951 .

Link -uri

• sequitur.info - implementarea algoritmului Sequitur în C++, Java și alte limbaje