Gramática lineal

Una gramática lineal (a veces abreviada como SLG) es una gramática formal que genera exactamente una cadena. ^{[ 1 ]} En consecuencia, no se ramifica (cada no terminal tiene solo una regla de producción asociada) ni forma bucles (si el no terminal A aparece en una derivación de B , entonces B no aparece en una derivación de A ). ^{[ 1 ]}

Áreas de utilidad

Las gramáticas lineales se utilizan ampliamente en el desarrollo de algoritmos que se ejecutan directamente sobre estructuras comprimidas (sin descompresión previa). ^{[ 2 ]}^{: 212}

Las SLG son de interés en campos como la complejidad de Kolmogorov , la compresión de datos sin pérdidas , el descubrimiento de estructuras y las estructuras de datos comprimidas .

El problema de encontrar una gramática libre de contexto (o equivalentemente: una SLG) de tamaño mínimo que genere una cadena dada se denomina problema de la gramática más pequeña .

Las gramáticas lineales (más precisamente: gramáticas de cadenas libres de contexto lineales) se pueden generalizar a gramáticas de árboles libres de contexto lineales . Estas últimas se pueden usar convenientemente para comprimir árboles . ^{[ 2 ]}^{: 212}

Definición formal

Una gramática libre de contexto G es una SLG si:

1. Para cada N no terminal , existe como máximo una regla de producción que tiene a N como su lado izquierdo, y

2. El grafo dirigido G =< V , E >, definido por V siendo el conjunto de no terminales y ( A , B ) ∈ E siempre que B aparezca en el lado derecho de una regla de producción para A , es acíclico .

Una definición matemática del formalismo más general de las gramáticas de árboles libres de contexto de línea recta se puede encontrar en Lohrey et al. ^{[ 2 ]}^{: 215}

Un SLG en forma normal de Chomsky es equivalente a un programa de línea recta .

Lista de algoritmos que utilizan SLG

El algoritmo Sequitur construye una gramática lineal para una cadena dada.
El algoritmo Lempel-Ziv-Welch crea una gramática libre de contexto de una manera tan determinista que solo es necesario almacenar la regla de inicio de la gramática generada.
Codificación de pares de bytes
El algoritmo Grammatical-Ziv-Lempel (GLZA), ^{[ 3 ]} , crea una gramática libre de contexto de baja entropía mediante un método recursivo y relativamente voraz de creación de reglas gramaticales. A menudo logra resultados de velocidad de descompresión en función del tamaño de los archivos de texto que se encuentran dentro de la frontera de Pareto.
Reemplazo iterativo de repetición (IRR): búsqueda de gramáticas más pequeñas en secuencias grandes y aplicación al ADN Rafael Carrascosaa, François Costeb, Matthias Galle, Gabriel Infante-Lopeza ^{[ 4 ]}

Véase también

Código basado en gramática : algoritmo de compresión de datos sin pérdidas
Gramática no recursiva : una gramática que no forma bucles, pero puede ramificarse; generando un lenguaje finito en lugar de un lenguaje unitario.

Referencias

1 2 Florian Benz y Timo Kötzing, “Una heurística eficaz para el problema gramatical más pequeño”, Actas de la decimoquinta conferencia anual sobre computación genética y evolutiva - GECCO '13, 2013. ISBN 978-1-4503-1963-8doi : 10.1145/2463372.2463441 , pág. 488
1 2 3 Markus Lohrey; Sebastian Maneth; Manfred Schmidt-Schauß (2009). "Reducción de parámetros en árboles comprimidos con gramática". Proc. FOSSACS (PDF) . LNCS. Vol. 5504. Springer. pp. 212–226 .
↑ Conrad, Kennon J.; Wilson, Paul R. (2016). "Compresión gramatical Ziv-Lempel: Logrando índices de compresión de texto de clase PPM con velocidad de descompresión de clase LZ". Conferencia de compresión de datos de 2016 (DCC) . pág. 586. doi : 10.1109/DCC.2016.119 . ISBN 978-1-5090-1853-6. S2CID 3116024 .
↑ "Búsqueda de gramáticas más pequeñas en secuencias grandes y su aplicación al ADN" (PDF) . www.irisa.fr .

[GECCO-1] 1 2 Florian Benz y Timo Kötzing, “Una heurística eficaz para el problema gramatical más pequeño”, Actas de la decimoquinta conferencia anual sobre computación genética y evolutiva - GECCO '13, 2013. ISBN 978-1-4503-1963-8doi : 10.1145/2463372.2463441 , pág. 488

[Lohrey.Maneth.Schmidt.2009-2] 1 2 3 Markus Lohrey; Sebastian Maneth; Manfred Schmidt-Schauß (2009). "Reducción de parámetros en árboles comprimidos con gramática". Proc. FOSSACS (PDF) . LNCS. Vol. 5504. Springer. pp. 212–226 .

[3] Conrad, Kennon J.; Wilson, Paul R. (2016). "Compresión gramatical Ziv-Lempel: Logrando índices de compresión de texto de clase PPM con velocidad de descompresión de clase LZ". Conferencia de compresión de datos de 2016 (DCC) . pág. 586. doi : 10.1109/DCC.2016.119 . ISBN 978-1-5090-1853-6. S2CID 3116024 .

[4] "Búsqueda de gramáticas más pequeñas en secuencias grandes y su aplicación al ADN" (PDF) . www.irisa.fr .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]