stringtranslate.com

Código basado en gramática

Gramática de línea recta (con el símbolo inicial ß) 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.

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.

Véase también

Referencias

  1. ^ 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
  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érdida mediante coincidencia de patrones multinivel", IEEE Trans. Inf. Theory , 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. Theory , 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, S2CID  : 2957960
  6. ^ 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
  7. ^ 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. ISBN 978-1-5090-1853-6. Número de identificación del sujeto  3116024.

Enlaces externos