SEQUITUR är en algoritm som härleder en hierarkisk struktur från en sekvens av diskreta symboler genom att ersätta upprepade fraser med en grammatisk regel som genererar frasen, och fortsätta denna process rekursivt. Resultatet är en hierarkisk representation av den ursprungliga sekvensen, som ger insikter i dess lexiska struktur. Algoritmen drivs av två begränsningar som minskar grammatikens storlek och producerar struktur som en biprodukt. SEQUITUR bryter ny mark genom att arbeta stegvis. Dessutom möjliggör metodens enkla struktur ett bevis på att den fungerar i rum och tid som är linjär i storleken på inmatningen. Vår implementation kan bearbeta 50.000 symboler per sekund och har applicerats på en lång rad verkliga sekvenser.
En grammatikinduktionsteknik som är nära relaterad till vårt arbete är SEQUITUR REF, en algoritm som härleder en hierarkisk struktur från en sekvens av diskreta symboler.
Identifying Hierarchical Structure in Sequences: A linear-time algorithm
{'venue': 'Journal of Artificial Intelligence Research, Vol 7, (1997), 67-82', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}