logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro