Código basado en gramática

Los códigos basados en la gramática o la compresión basada en la gramática son algoritmos de compresión basados en la idea de construir una gramática libre de contexto (CFG) para que la cadena se comprima. Los ejemplos incluyen algoritmos universales de compresión de datos sin pérdida . ^[1] Para comprimir una secuencia de datos ${\ Displaystyle x = x_ {1} \ cdots x_ {n}}$ , un código basado en gramática transforma ${\ Displaystyle x}$ en una gramática libre de contexto ${\ Displaystyle G}$ . Se sabe que el problema de encontrar la gramática más pequeña para una secuencia de entrada ( problema gramatical más pequeño ) es NP-hard, ^[2] por lo que se proponen muchos algoritmos de transformación gramatical desde puntos de vista teóricos y prácticos. Generalmente, la gramática producida ${\ Displaystyle G}$ se comprime aún más mediante codificadores estadísticos como la codificación aritmética .

Gramática en línea recta (con el símbolo de inicio ß) para la segunda oración de la Declaración de Independencia de los Estados Unidos . Cada carácter azul denota un símbolo no terminal ; se obtuvieron a partir de una compresión gzip de la oración.

Ejemplos y caracteristicas

La clase de códigos basados en gramática es muy amplia. Incluye códigos de bloque , variaciones del código Lempel-Ziv de análisis incremental , ^[3] el algoritmo de coincidencia de patrones multinivel (MPM), ^[4] y muchos otros nuevos algoritmos universales de compresión sin pérdidas. Los códigos basados en la gramática son universales en el sentido de que pueden alcanzar asintóticamente la tasa de entropía de cualquier fuente ergódica estacionaria con un alfabeto finito.

Algoritmos prácticos

Los siguientes programas de compresión están disponibles en enlaces externos.

Sequitur ^[5] es un algoritmo de compresión gramatical clásico que traduce secuencialmente un texto de entrada a un CFG, y luego el CFG producido es codificado por un codificador aritmético.
Re-Pair ^[6] es un algoritmo codicioso que utiliza la estrategia de sustitución más frecuente-primero. El rendimiento de compresión es poderoso, aunque el requisito de espacio de memoria principal es muy grande.
GLZA , ^[7] que construye una gramática que puede ser reducible, es decir, contener repeticiones, donde el costo de codificación de entropía de "deletrear" las repeticiones es menor que el costo de crear y codificar entropía una regla para capturarlas. (En general, la SLG de compresión óptima no es irreducible, y el problema gramatical más pequeño es diferente del problema de compresión SLG real).

Ver también

Referencias

^ Kieffer, JC; Yang, E.-H. (2000), "Códigos basados en gramática: una nueva clase de códigos fuente universales sin pérdidas", IEEE Trans. Inf. Teoría , 46 (3): 737–754, doi : 10.1109 / 18.841160
^ Charikar, M .; Lehman, E .; Liu, D .; Panigrahy, R .; Prabharakan, M .; Sahai, A .; Shelat, A. (2005), "El problema gramatical más pequeño", IEEE Trans. Inf. Teoría , 51 (7): 2554-2576, doi : 10.1109 / tit.2005.850116
^ Kieffer, JC; Yang, E.-H .; Nelson, G .; Cosman, P. (2000), "Compresión universal sin pérdidas mediante coincidencia de patrones multinivel" , IEEE Trans. Inf. Teoría , 46 (4): 1227-1245, doi : 10.1109 / 18.850665
^ Ziv, J .; Lempel, A. (1978), "Compresión de secuencias individuales mediante codificación de velocidad variable", IEEE Trans. Inf. Teoría , 24 (5): 530–536, doi : 10.1109 / TIT.1978.1055934 , hdl : 10338.dmlcz / 142945
^ Nevill-Manning, CG; Witten, IH (1997), "Identificación de la estructura jerárquica en secuencias: un algoritmo de tiempo lineal", Journal of Artificial Intelligence Research , 7 (4): 67-82, arXiv : cs / 9709102 , doi : 10.1613 / jair.374 , hdl : 10289/1186
^ Larsson, Nueva Jersey; Moffat, A. (2000), "Compresión basada en diccionario sin conexión" (PDF) , Proceedings of the IEEE , 88 (11): 1722–1732, doi : 10.1109 / 5.892708
^ Conrad, Kennon J .; Wilson, Paul R. (2016), "Compresión gramatical Ziv-Lempel: Lograr relaciones de compresión de texto de clase PPM con velocidad de descompresión de clase LZ", IEEE Data Compression Conference : 586, doi : 10.1109 / DCC.2016.119 , ISBN 978-1-5090-1853-6

enlaces externos

Discusión y ponencia sobre GLZA
Descripción de códigos basados en gramática con ejemplo
Códigos secuenciales
Volver a emparejar códigos
Re-Pair codifica una versión de Gonzalo Navarro.
GrammarViz 2.0 : implementación de Sequitur, Re-Pair y Re-Pair en paralelo en Java.

[1] Kieffer, JC; Yang, E.-H. (2000), "Códigos basados en gramática: una nueva clase de códigos fuente universales sin pérdidas", IEEE Trans. Inf. Teoría , 46 (3): 737–754, doi : 10.1109 / 18.841160

[2] Charikar, M .; Lehman, E .; Liu, D .; Panigrahy, R .; Prabharakan, M .; Sahai, A .; Shelat, A. (2005), "El problema gramatical más pequeño", IEEE Trans. Inf. Teoría , 51 (7): 2554-2576, doi : 10.1109 / tit.2005.850116

[3] Kieffer, JC; Yang, E.-H .; Nelson, G .; Cosman, P. (2000), "Compresión universal sin pérdidas mediante coincidencia de patrones multinivel" , IEEE Trans. Inf. Teoría , 46 (4): 1227-1245, doi : 10.1109 / 18.850665

[4] Ziv, J .; Lempel, A. (1978), "Compresión de secuencias individuales mediante codificación de velocidad variable", IEEE Trans. Inf. Teoría , 24 (5): 530–536, doi : 10.1109 / TIT.1978.1055934 , hdl : 10338.dmlcz / 142945

[5] Nevill-Manning, CG; Witten, IH (1997), "Identificación de la estructura jerárquica en secuencias: un algoritmo de tiempo lineal", Journal of Artificial Intelligence Research , 7 (4): 67-82, arXiv : cs / 9709102 , doi : 10.1613 / jair.374 , hdl : 10289/1186

[6] Larsson, Nueva Jersey; Moffat, A. (2000), "Compresión basada en diccionario sin conexión" (PDF) , Proceedings of the IEEE , 88 (11): 1722–1732, doi : 10.1109 / 5.892708

[7] Conrad, Kennon J .; Wilson, Paul R. (2016), "Compresión gramatical Ziv-Lempel: Lograr relaciones de compresión de texto de clase PPM con velocidad de descompresión de clase LZ", IEEE Data Compression Conference : 586, doi : 10.1109 / DCC.2016.119 , ISBN 978-1-5090-1853-6

[1]