Los códigos basados en gramática o la 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érdida . [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-hard, [2] por lo que se proponen muchos algoritmos de transformación de gramática 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 .
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 de compresión universal sin pérdida. 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 de compresión gramatical clásico que traduce secuencialmente un texto de entrada en un CFG, y luego el CFG producido es codificado por un codificador aritmético.
Re-Pair [6] es un algoritmo voraz que utiliza la estrategia de sustitución de la primera más frecuente. El rendimiento de compresión es potente, 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 por entropía una regla para capturarlas. (En general, la SLG de compresión óptima no es irreducible, y el Problema de Gramática Más Pequeña es diferente del problema de compresión SLG real).
^ Kieffer, JC; Yang, E.-H. (2000), "Códigos basados en gramática: una nueva clase de códigos fuente universales sin pérdida", IEEE Trans. Inf. Theory , 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, S2CID 6900082
^ Kieffer, JC; Yang, E.-H.; Nelson, G.; Cosman, P. (2000), "Compresión universal sin pérdida mediante coincidencia de patrones multinivel", IEEE Trans. Inf. Theory , 46 (4): 1227–1245, doi :10.1109/18.850665, S2CID 8191526
^ Ziv, J.; Lempel, A. (1978), "Compresión de secuencias individuales mediante codificación de velocidad variable", IEEE Trans. Inf. Theory , 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, S2CID : 2957960
^ Larsson, NJ; Moffat, A. (2000), "Compresión basada en diccionarios sin conexión" (PDF) , Actas del IEEE , 88 (11): 1722–1732, doi :10.1109/5.892708
^ Conrad, Kennon J.; Wilson, Paul R. (2016). "Compresión gramatical Ziv-Lempel: cómo lograr relaciones de compresión de texto de clase PPM con velocidad de descompresión de clase LZ". Conferencia sobre compresión de datos (DCC) de 2016. pág. 586. doi :10.1109/DCC.2016.119. ISBN978-1-5090-1853-6. Número de identificación del sujeto 3116024.
Enlaces externos
Discusión y ponencia 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
Códigos de re-emparejamiento
Re-Pair codifica una versión de Gonzalo Navarro.
GrammarViz 2.0: implementación de Sequitur, Re-Pair y Re-Pair paralelo en Java.