Sequitur (o algoritmo de Nevill-Manning–Witten ) 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 un espacio y tiempo lineales. Puede utilizarse en aplicaciones de software de compresión de datos . [2]
El algoritmo sequitur construye una gramática sustituyendo frases repetidas en la secuencia dada por nuevas reglas y, por lo tanto, produce una representación concisa de la secuencia. Por ejemplo, si la secuencia es
El algoritmo producirá
Al escanear la secuencia de entrada, el algoritmo sigue dos restricciones para generar su gramática de manera eficiente: unicidad del diagrama y utilidad de la regla .
Siempre que se escanea un nuevo símbolo de la secuencia, se le añade el último símbolo escaneado para formar un nuevo digrama . Si este digrama se ha formado antes, se crea una nueva regla para reemplazar ambas apariciones de los digramas. Por lo tanto, se asegura de que ningún digrama ocurra más de una vez en la gramática. Por ejemplo, en la secuencia S→abaaba , cuando ya se escanearon los primeros cuatro símbolos, los digramas formados son ab, ba, aa . Cuando se lee el quinto símbolo, se forma un nuevo digrama 'ab' que ya existe. Por lo tanto, ambas instancias de 'ab' se reemplazan por una nueva regla (por ejemplo, A) en S. Ahora, la gramática se convierte en S→AaAa, A→ab , y el proceso continúa hasta que no exista ningún digrama repetido en la gramática.
Esta restricción asegura que todas las reglas se usen más de una vez en los lados derechos de todas las producciones de la gramática, es decir, si una regla ocurre solo una vez, debe eliminarse de la gramática y su ocurrencia debe sustituirse con los símbolos a partir de los cuales se creó. Por ejemplo, en el ejemplo anterior, si uno escanea el último símbolo y aplica la unicidad de digrama 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, A se elimina y finalmente la gramática se convierte en
Esta restricción ayuda a reducir el número de reglas en la gramática.
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 ocurrencia 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 el escaneo 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 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]
{{cite journal}}: Requiere citar revista |journal=( ayuda )