Hispanopedia WikiSequitur (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 espacio y tiempo lineales. Puede utilizarse en aplicaciones de software de compresión de datos . [ 2 ]
Restricciones
El algoritmo sequitur construye una gramática sustituyendo las 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
- S→abcab,
El algoritmo producirá
- S→AcA, A→ab.
Al analizar la secuencia de entrada, el algoritmo sigue dos restricciones para generar su gramática de manera eficiente: la unicidad del digrama y la utilidad de la regla .
Unicidad del diagrama
Cada vez 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 ya se ha formado anteriormente, se crea una nueva regla para reemplazar ambas ocurrencias del digrama. Por lo tanto, se asegura que ningún digrama aparezca más de una vez en la gramática. Por ejemplo, en la secuencia S→abaaba , cuando los primeros cuatro símbolos ya se han escaneado, 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.
Utilidad de reglas
Esta restricción garantiza que todas las reglas se utilicen más de una vez en los lados derechos de todas las producciones de la gramática; es decir, si una regla aparece solo una vez, debe eliminarse de la gramática y su aparición debe sustituirse por los símbolos a partir de los cuales se crea. Por ejemplo, en el ejemplo anterior, si se analiza el último símbolo y se aplica la unicidad de digramas para 'Aa', la gramática producirá: S→BB, A→ab, B→Aa . Ahora bien, la regla 'A' aparece solo una vez en la gramática en B→Aa . Por lo tanto, A se elimina y finalmente la gramática se convierte en
- S→BB, B→aba .
Esta restricción ayuda a reducir el número de reglas en la gramática.
Resumen del método
El algoritmo funciona escaneando una secuencia de símbolos terminales y creando una lista de todos los pares de símbolos que ha leído. Cuando se descubre una segunda aparición de un par, ambas apariciones se reemplazan en la secuencia por un símbolo no terminal inventado , la lista de pares de símbolos se ajusta para coincidir 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 se elimina de los símbolos no terminales definidos. Una vez completado el escaneo, la secuencia transformada puede interpretarse como la regla de nivel superior en una gramática para la secuencia original. Las definiciones de las reglas para los símbolos no terminales que contiene se pueden encontrar en la lista de pares de símbolos. Dichas definiciones de reglas pueden contener a su vez símbolos no terminales adicionales cuyas definiciones de reglas también se pueden leer en otras partes de la lista de pares de símbolos. [ 3 ]
Véase también
Referencias
- ↑ Nevill-Manning, CG ; Witten, IH (1997). "Identifying Hierarchical Structure in Sequences: A linear-time algorithm". arXiv : cs/9709102 . Bibcode : 1997cs........9102N .
{{cite journal}}: Para citar una revista se requiere|journal=( ayuda ) - ↑ Nevill-Manning, CG ; Witten, IH (1997). "Inferencia jerárquica incremental en tiempo lineal para compresión". Actas de la DCC '97. Conferencia de Compresión de Datos . págs. 3–11 . CiteSeerX 10.1.1.30.2305 . doi : 10.1109/DCC.1997.581951 . ISBN 978-0-8186-7761-8. S2CID 14324301 .
- ↑ GrammarViz 2.0 – Implementaciones de Sequitur y Sequitur paralelo en Java, descubrimiento de patrones de series temporales basados en Sequitur
Enlaces externos
- sequitur.info – la implementación de referencia del algoritmo Sequitur en C++, Java y otros lenguajes.
- Algoritmos de compresión sin pérdidas
- Compresión de datos
