Código basado en gramática

Algoritmo de compresión de datos sin pérdidas

Gramática lineal (con símbolo inicial ß) para la segunda oración de la Declaración de Independencia de Estados Unidos . Cada carácter azul indica un símbolo no terminal ; se obtuvieron a partir de una compresión gzip de la frase.

Los códigos basados ​​en gramática o compresión basada en gramática son algoritmos de compresión basados ​​en la idea de construir una gramática libre de contexto (CFG) para la cadena que se va a comprimir. Los ejemplos incluyen algoritmos universales de compresión de datos sin pérdidas . ^[1] Para comprimir una secuencia de datos , un código basado en gramática se transforma en una gramática libre de contexto . Se sabe que el problema de encontrar una gramática más pequeña para una secuencia de entrada ( problema de gramática más pequeña ) es NP-difícil, ^[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 se comprime aún más mediante codificadores estadísticos como la codificación aritmética . ${\displaystyle x=x_{1}\cdots x_{n}}$ ${\displaystyle x}$ ${\displaystyle G}$ ${\displaystyle G}$

Ejemplos y características

La clase de códigos basados ​​en gramática es muy amplia. Incluye códigos de bloque , el algoritmo de coincidencia de patrones multinivel (MPM), ^[3] variaciones del código de análisis incremental Lempel-Ziv , ^[4] y muchos otros nuevos algoritmos universales de compresión sin pérdidas. Los códigos basados ​​en 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 programas de compresión de los siguientes están disponibles en enlaces externos.

• Sequitur ^[5] es un algoritmo clásico de compresión gramatical que traduce secuencialmente un texto de entrada a un CFG, y luego el CFG producido se codifica mediante 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 potente, aunque el requisito de espacio en la 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 entropía de "deletrear" las repeticiones es menor que el costo de crear y codificar entropía una regla para capturarlas. (En general, el 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

• codificador de diccionario
• inducción gramatical
• Gramática lineal

Referencias

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, S2CID  6900082
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, S2CID  8191526
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 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, S2CID  2957960
6. Larsson, Nueva Jersey; Moffat, A. (2000), "Compresión basada en diccionario sin conexión" (PDF) , Actas del 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". Conferencia de compresión de datos (DCC) de 2016 . pag. 586. doi : 10.1109/DCC.2016.119. ISBN 978-1-5090-1853-6. S2CID  3116024.

enlaces externos

• Discusión y documento de GLZA
• Descripción de códigos basados ​​en gramática con ejemplo.
• Códigos Sequitur Archivado el 13 de octubre de 2008 en Wayback Machine.
• 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 paralelo en Java.