Sequitur-algoritmi

Sequitur-algoritmi on rekursiivinen ja ahne algoritmi, joka päättelee sille annetun syötteen suhteellisen optimaalisesti pakkaavan kontekstivapaan kieliopin. Algoritmin kompleksisuus on luokkaa $O(n)$, missä n on syötteenä annetun symbolijonon pituus. Algoritmi käy sille annetun syötteen läpi aloittaen syötteen alusta ja lopettaen syötteen loppuun. Tästä seuraa, että:

• Pakattavan symbolijonon loppuun voidaan lisätä symboleja joko algoritmin ajoaikana tai sen jälkeen niin, etteivät päätellyn kieliopin matemaattiset ominaisuudet muutu. Jos algoritmi on käynnistettävä uudestaan, on algoritmin muuttujien tila pääteltävä tallennetusta kieliopista.
• Kieliopista ei tule aivan yhtä optimaalinen kuin jos luotavat säännöt valittaisiin joka iteraatiolla ahneesti koko aineiston pohjalta, kuten eräissä muissa kieliopin päättelyalgoritmeissa.

Algoritmista on muutamia muunnelmia, jotka pystyvät takaisinkytkennän avulla päättelemään kontekstivapaita kielioppeja, joissa:

• voi olla yhtä nonterminaalia kohti useita sellaisia sääntöjä, joissa kyseinen nonterminaali on säännön oikealla puolella.
• sama nonterminaali voi esiintyä yhtä aikaa sekä säännön vasemmalla että oikealla puolella.

Aiheesta muualla

• Nevill-Manning, C.G. (1996) "Inferring Sequential Structure Ph.D. dissertation. (Arkistoitu – Internet Archive)