Sekvenční algoritmus - Sequitur algorithm

Sequitur (nebo Algoritmus Nevill-Manninga) je rekurzivní algoritmus vyvinutý společností Craig Nevill-Manning a Ian H. Witten v roce 1997[1] který vyvozuje hierarchickou strukturu (bezkontextová gramatika ) ze sledu diskrétních symbolů. Algoritmus pracuje v lineárním prostoru a čase. Může být použit v komprese dat softwarové aplikace.[2]

Omezení

Algoritmus sequitur konstruuje gramatiku nahrazením opakujících se frází v dané posloupnosti novými pravidly, a proto vytváří stručné vyjádření posloupnosti. Například pokud je sekvence

S → abcab,

algoritmus vyprodukuje

S → AcA, A → ab.

Při skenování vstupní sekvence se algoritmus řídí dvěma omezeními pro efektivní generování gramatiky: jedinečnost digramu a nástroj pravidla.

Digramova jedinečnost

Kdykoli je ze sekvence naskenován nový symbol, je k němu připojen poslední naskenovaný symbol a vytvoří se nový digram. Pokud byl tento digram vytvořen dříve, je vytvořeno nové pravidlo, které nahradí oba výskyty digramů. Proto zajišťuje, že se žádný digram v gramatice nevyskytuje vícekrát. Například v pořadí S → abaaba, když jsou již naskenovány první čtyři symboly, vytvořené digramy jsou ab, ba, aa. Po přečtení pátého symbolu se vytvoří nový digram 'ab', který již existuje. Proto jsou oba výskyty 'ab' nahrazeny novým pravidlem (řekněme A) v S. Nyní se gramatika stává S → AaAa, A → aba proces pokračuje, dokud v gramatice neexistuje žádný opakovaný digram.

Utilita pravidla

Toto omezení zajišťuje, že všechna pravidla budou použita vícekrát na pravých stranách všech produkcí gramatiky, tj. Pokud se pravidlo vyskytne pouze jednou, mělo by být z gramatiky odstraněno a jeho výskyt by měl být nahrazen symboly z který je vytvořen. Například ve výše uvedeném příkladu, pokud člověk naskenuje poslední symbol a použije jedinečnost digramu pro 'Aa', pak gramatika vytvoří: S → BB, A → ab, B → Aa. Nyní se pravidlo 'A' v gramatice v vyskytuje pouze jednou B → Aa. Proto je A odstraněn a nakonec se stane gramatika

S → BB, B → aba.

Toto omezení pomáhá snížit počet pravidel v gramatice.

Shrnutí metody

Algoritmus pracuje skenováním sekvence koncové symboly a sestavení seznamu všech párů symbolů, které si přečetlo. Kdykoli je objeven druhý výskyt páru, jsou dva výskyty v pořadí nahrazeny vynálezem neterminální symbol, seznam párů symbolů je upraven tak, aby odpovídal nové posloupnosti, a skenování pokračuje. Pokud je párový neterminální symbol použit pouze v definici právě vytvořeného symbolu, je použitý symbol nahrazen jeho definicí a symbol je odstraněn z definovaných neterminálních symbolů. Jakmile je skenování dokončeno, transformovaná sekvence může být interpretována jako pravidlo nejvyšší úrovně v gramatice pro původní sekvenci. Definice pravidel pro neterminální symboly, které obsahuje, najdete v seznamu párů symbolů. Tyto definice pravidel mohou samy obsahovat další neterminální symboly, jejichž definice pravidel lze také číst odkudkoli v seznamu párů symbolů.[3]

Viz také

Reference

  1. ^ Nevill-Manning, C.G.; Witten, I.H. (1997). "Identifikace hierarchické struktury v sekvencích: Algoritmus lineárního času". arXiv:cs / 9709102. Bibcode:1997cs ........ 9102N. Citovat deník vyžaduje | deník = (Pomoc)
  2. ^ Nevill-Manning, C.G.; Witten, I.H. (1997). "Lineární čas, přírůstková hierarchická inference pro kompresi". Sborník DCC '97. Konference o kompresi dat. s. 3–11. CiteSeerX  10.1.1.30.2305. doi:10.1109 / DCC.1997.581951. ISBN  978-0-8186-7761-8.
  3. ^ GrammarViz 2.0 - Sequitur a paralelní Sequitur implementace v Javě, objevování vzorů časových řad založených na Sequitur

externí odkazy