Práctica gramatical de compresión basada en repeticiones máximas
Autores: Furuya, Isamu; Takagi, Takuya; Nakashima, Yuto; Inenaga, Shunsuke; Bannai, Hideo; Kida, Takuya
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Práctica gramatical de compresión basada en repeticiones máximas
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Análisis
Reparación
Algoritmo
Repeticiones maximales
Gramáticas
MR-RePair
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 34
Citaciones: Sin citaciones
Este estudio presenta un análisis de RePair, que es un algoritmo de compresión gramatical conocido por su esquema simple, además de ser prácticamente efectivo. En primer lugar, mostramos que el proceso principal de RePair, es decir, la sustitución paso a paso de los pares de símbolos más frecuentes, funciona dentro de las repeticiones maximales más frecuentes correspondientes. Luego, revelamos la relación entre las repeticiones maximales y las gramáticas construidas por RePair. Sobre la base de este análisis, proponemos además una nueva variante de RePair, llamada MR-RePair, que considera la sustitución única de las repeticiones maximales más frecuentes en lugar de la sustitución consecutiva de los pares más frecuentes. Los resultados de los experimentos comparando el tamaño de las gramáticas construidas y el tiempo de ejecución de RePair y MR-RePair en varios corpus de texto demuestran que MR-RePair construye gramáticas más compactas que RePair, especialmente para textos altamente repetitivos.
Descripción
Este estudio presenta un análisis de RePair, que es un algoritmo de compresión gramatical conocido por su esquema simple, además de ser prácticamente efectivo. En primer lugar, mostramos que el proceso principal de RePair, es decir, la sustitución paso a paso de los pares de símbolos más frecuentes, funciona dentro de las repeticiones maximales más frecuentes correspondientes. Luego, revelamos la relación entre las repeticiones maximales y las gramáticas construidas por RePair. Sobre la base de este análisis, proponemos además una nueva variante de RePair, llamada MR-RePair, que considera la sustitución única de las repeticiones maximales más frecuentes en lugar de la sustitución consecutiva de los pares más frecuentes. Los resultados de los experimentos comparando el tamaño de las gramáticas construidas y el tiempo de ejecución de RePair y MR-RePair en varios corpus de texto demuestran que MR-RePair construye gramáticas más compactas que RePair, especialmente para textos altamente repetitivos.