Sensibilidad a la compresión de la transformación de Burrows-Wheeler y su variante biyectiva
Autores: Jeon, Hyodam; Köppl, Dominik
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Sensibilidad a la compresión de la transformación de Burrows-Wheeler y su variante biyectiva
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Transformación de Burrows-Wheeler
Método de compresión de datos reversible
Eficiencia de compresión
Variante biyectiva
Reordenamiento del alfabeto
Sensibilidad a la compresión
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 21
Citaciones: Sin citaciones
La Transformación de Burrows-Wheeler (BWT) es un método de compresión de datos ampliamente utilizado y reversible, que forma la base de varios algoritmos de compresión y estructuras de indexación. Investigaciones previas han analizado la sensibilidad de los métodos de compresión y medidas de repetitividad a ediciones de un solo carácter, especialmente en alfabetos binarios. Sin embargo, el impacto de tales modificaciones en la eficiencia de compresión de la variante biyectiva de BWT (BBWT) sigue siendo en gran parte inexplorado. Este estudio extiende trabajos previos examinando la sensibilidad a la compresión tanto de BWT como de BBWT cuando se aplican a alfabetos más grandes, incluyendo la reordenación del alfabeto. Establecemos límites teóricos sobre el aumento en el tamaño de compresión debido a modificaciones de caracteres en secuencias estructuradas como palabras de Fibonacci. Nuestros límites inferiores diseñados ponen la sensibilidad de BBWT en la misma escala que la de BWT, con cambios en el tamaño de compresión mostrando patrones de crecimiento multiplicativo logarítmico y aditivo de raíz cuadrada dependiendo del tipo de edición y los datos de entrada. Estos hallazgos contribuyen a una comprensión más profunda de las medidas de repetitividad.
Descripción
La Transformación de Burrows-Wheeler (BWT) es un método de compresión de datos ampliamente utilizado y reversible, que forma la base de varios algoritmos de compresión y estructuras de indexación. Investigaciones previas han analizado la sensibilidad de los métodos de compresión y medidas de repetitividad a ediciones de un solo carácter, especialmente en alfabetos binarios. Sin embargo, el impacto de tales modificaciones en la eficiencia de compresión de la variante biyectiva de BWT (BBWT) sigue siendo en gran parte inexplorado. Este estudio extiende trabajos previos examinando la sensibilidad a la compresión tanto de BWT como de BBWT cuando se aplican a alfabetos más grandes, incluyendo la reordenación del alfabeto. Establecemos límites teóricos sobre el aumento en el tamaño de compresión debido a modificaciones de caracteres en secuencias estructuradas como palabras de Fibonacci. Nuestros límites inferiores diseñados ponen la sensibilidad de BBWT en la misma escala que la de BWT, con cambios en el tamaño de compresión mostrando patrones de crecimiento multiplicativo logarítmico y aditivo de raíz cuadrada dependiendo del tipo de edición y los datos de entrada. Estos hallazgos contribuyen a una comprensión más profunda de las medidas de repetitividad.