Hispanopedia Wiki
Articulo de referencia

Código basado en gramática

Gramática lineal (con símbolo inicial ß) para la segunda oración de la Declaración de Independencia de los Estados Unidos . Cada carácter azul representa un símbolo no terminal ...

Hispanopedia WikiContenido en espanolLectura gratuita
Gramática lineal (con símbolo inicial ß) para la segunda oración de la Declaración de Independencia de los Estados Unidos . Cada carácter azul representa un símbolo no terminal ; se obtuvieron mediante 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 que se basan en la idea de construir una gramática libre de contexto (GLC) para la cadena que se va a comprimir. Algunos ejemplos incluyen algoritmos de compresión de datos universales sin pérdida . [ 1 ] Para comprimir una secuencia de datosincógnita=incógnita1⋯incógnitanorte{\displaystyle x=x_{1}\cdots x_{n}}, una transformación de código basada en gramáticaincógnita{\displaystyle x}en una gramática libre de contextoGRAMO{\displaystyle G}El problema de encontrar la gramática más pequeña para una secuencia de entrada ( problema de la gramática más pequeña ) es conocido por ser NP-difícil, [ 2 ] por lo que se han propuesto muchos algoritmos de transformación de gramáticas desde puntos de vista teóricos y prácticos. Generalmente, la gramática producidaGRAMO{\displaystyle G}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 bloques , 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é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 estacionaria y ergódica con un alfabeto finito.

Algoritmos prácticos

Los programas de compresión que se describen a continuación están disponibles a través de enlaces externos.

  • Sequitur [ 5 ] es un algoritmo clásico de compresión de gramática que traduce secuencialmente un texto de entrada a una CFG, y luego la CFG producida es codificada por un codificador aritmético.
  • Re-Pair [ 6 ] es un algoritmo voraz que utiliza la estrategia de sustitución del elemento más frecuente primero. Su rendimiento de compresión es potente, aunque requiere un gran espacio de memoria principal.
  • GLZA , [ 7 ] que construye una gramática que puede ser reducible, es decir, que contiene repeticiones, donde el costo de codificación entrópica de "deletrear" las repeticiones es menor que el costo de crear y codificar entrópicamente una regla para capturarlas. (En general, la SLG óptima para compresión no es irreducible, y el Problema de la Gramática Más Pequeña es diferente del problema real de compresión de SLG).

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érdidas", IEEE Trans. Inf. Theory , 46 (3): 737– 754, Bibcode : 2000ITIT...46..737K , doi : 10.1109/18.841160
  2. ↑ Charikar, M.; Lehman, E.; Liu, D.; Panigrahy, R.; Prabharakan, M.; Sahai, A.; Shelat, A. (2005), "The Smallest Grammar Problem", IEEE Trans. Inf. Theory , 51 (7): 2554– 2576, Bibcode : 2005ITIT...51.2554C , 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. Theory , 46 (4): 1227–1245 , Bibcode : 2000ITIT...46.1227K , doi : 10.1109/18.850665 , S2CID 8191526 
  4. ↑ Ziv, J.; Lempel, A. (1978), "Compresión de secuencias individuales mediante codificación de tasa variable", IEEE Trans. Inf. Theory , 24 (5): 530– 536, Bibcode : 1978ITIT...24..530Z , doi : 10.1109/TIT.1978.1055934 , hdl : 10338.dmlcz/142945
  5. ↑ Nevill-Manning, CG; Witten, IH (1997), "Identifying Hierarchical Structure in Sequences: A linear-time algorithm", 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 diccionario sin conexión" (PDF) , Actas del IEEE , 88 (11): 1722– 1732, Bibcode : 2000IEEEP..88.1722L , doi : 10.1109/5.892708
  7. ↑ 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 . 
  • Discusión y documento de GLZA
  • Descripción de códigos basados ​​en gramática con un ejemplo
  • Códigos Sequitur Archivados el 13/10/2008 en Wayback Machine
  • Códigos de reparación
  • Re-Pair codifica una versión de Gonzalo Navarro.
  • GrammarViz 2.0 : implementación de Sequitur, Re-Pair y Re-Pair paralelo en Java.
Lecturas relacionadas
6 articulos
Gramática linealUna gramática lineal (a veces abreviada como SLG) es una gramática formal que genera exactamente una cadena. [ 1 ] En consecuencia, no se ramifica ...Declaración de Independencia de los Estados UnidosDeclaración de Independencia de los Estados UnidosLa Declaración de Independencia , formalmente titulada La Declaración Unánime de los Trece Estados Unidos de América tanto en la versión impresa co...Símbolos terminales y no terminalesSímbolos terminales y no terminalesEn los lenguajes formales , los símbolos terminales y no terminales forman parte del vocabulario de una gramática formal . El vocabulario es un con...Comprimirgzip es un formato de archivo y una aplicación de software que se utiliza para la compresión y descompresión de archivos . El programa fue creado p...Compresión de datosCompresión de datos{{ cite book }} {{ cite book }} {{ citation }}Gramática libre de contextoGramática libre de contextoEn la teoría del lenguaje formal , una gramática libre de contexto ( GLC ) es una gramática formal cuyas reglas de producción se pueden aplicar a u...