Sequitur (o algoritmo de Nevill-Manning ) es un algoritmo recursivo desarrollado por Craig Nevill-Manning e Ian H. Witten en 1997 [1] que infiere una estructura jerárquica ( gramática libre de contexto ) a partir de una secuencia de símbolos discretos. El algoritmo opera en espacio y tiempo lineales. Se puede utilizar en aplicaciones de software de compresión de datos . [2]
El algoritmo sequitur construye una gramática sustituyendo frases repetidas en la secuencia dada con nuevas reglas y por lo tanto produce una representación concisa de la secuencia. Por ejemplo, si la secuencia es
Al escanear la secuencia de entrada, el algoritmo sigue dos restricciones para generar su gramática de manera eficiente: la unicidad del digram y la utilidad de las reglas .
Siempre que se escanea un nuevo símbolo de la secuencia, se le añade el último símbolo escaneado para formar un nuevo dígrama . Si este digrama se formó antes, entonces se crea una nueva regla para reemplazar ambas apariciones de los digramas. Por lo tanto, asegura que ningún digram aparezca más de una vez en la gramática. Por ejemplo, en la secuencia S → abaaba , cuando los primeros cuatro símbolos ya están escaneados, los digramas formados son ab, ba, aa . Cuando se lee el quinto símbolo, se forma un nuevo digram 'ab' que ya existe. Por lo tanto, las dos instancias de 'ab' son reemplazados por una nueva norma (por ejemplo, A) en S . Ahora, la gramática se convierte en S → AaAa, A → ab , y el proceso continúa hasta que no existe un digram repetido en la gramática.
Esta restricción asegura que todas las reglas se usen más de una vez en el lado derecho de todas las producciones de la gramática, es decir, si una regla ocurre solo una vez, debe ser eliminada de la gramática y su ocurrencia debe ser sustituida por los símbolos de que se crea. Por ejemplo, en el ejemplo anterior, si uno escanea el último símbolo y aplica la unicidad del digram para 'Aa', entonces la gramática producirá: S → BB, A → ab, B → Aa . Ahora, la regla 'A' ocurre solo una vez en la gramática en B → Aa . Por lo tanto, se elimina A y finalmente la gramática se convierte en
El algoritmo funciona escaneando una secuencia de símbolos terminales y construyendo una lista de todos los pares de símbolos que ha leído. Siempre que se descubre una segunda aparición de un par, las dos ocurrencias se reemplazan en la secuencia por un símbolo no terminal inventado, la lista de pares de símbolos se ajusta para que coincida con la nueva secuencia y la exploración continúa. Si el símbolo no terminal de un par se usa solo en la definición del símbolo recién creado, el símbolo usado se reemplaza por su definición y el símbolo se elimina de los símbolos no terminales definidos. Una vez que se ha completado el escaneo, la secuencia transformada se puede interpretar como la regla de nivel superior en una gramática para la secuencia original. Las definiciones de reglas para los símbolos no terminales que contiene se pueden encontrar en la lista de pares de símbolos. Esas definiciones de reglas pueden contener en sí mismas símbolos no terminales adicionales cuyas definiciones de reglas también se pueden leer desde otra parte de la lista de pares de símbolos. [3]