Compresión de texto en tiempo lineal mediante sustitución por el más largo primero
Autores: Nakamura, Ryosuke; Inenaga, Shunsuke; Bannai, Hideo; Funamoto, Takashi; Takeda, Masayuki; Shinohara, Ayumi
Idioma: Inglés
Editor: Molecular Diversity Preservation International
Año: 2009
Acceso abierto
Artículo científico
2009
Compresión de texto en tiempo lineal mediante sustitución por el más largo primero
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Compresión de texto
Basada en gramática
Factor de repetición más largo
Algoritmo de tiempo lineal
Estructura de datos
LFS
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 27
Citaciones: Sin citaciones
Consideramos la compresión de texto basada en gramática con (), donde las ocurrencias no superpuestas de un factor repetido más largo del texto de entrada son reemplazadas por un nuevo símbolo no terminal. Presentamos el primer algoritmo de tiempo lineal para LFS. Nuestro algoritmo emplea una nueva estructura de datos llamada . También tratamos con una versión más sofisticada de LFS, llamada , que permite una mejor compresión. También se presenta el primer algoritmo de tiempo lineal para LFS2.
Descripción
Consideramos la compresión de texto basada en gramática con (), donde las ocurrencias no superpuestas de un factor repetido más largo del texto de entrada son reemplazadas por un nuevo símbolo no terminal. Presentamos el primer algoritmo de tiempo lineal para LFS. Nuestro algoritmo emplea una nueva estructura de datos llamada . También tratamos con una versión más sofisticada de LFS, llamada , que permite una mejor compresión. También se presenta el primer algoritmo de tiempo lineal para LFS2.