Teoría de la información y la compresión de cadenas

El problema de la compresión sin perdida consiste en implementar la codificación (únicamente decodificable) de un alfabeto, que asigna a cada cadena de símbolos del alfabeto el código de menor longitud posible. Encontrar esta representación de menor tamaño de un conjunto de datos puede ahorrar costos en el espacio de almacenamiento, tiempo en transferencia de los datos o número de operaciones en su procesamiento, dentro de un computador. Lo anterior hace de la compresión sin perdida un objetivo razonable dentro de las Ciencias de la Computación y representa un reto importante durante el desarrollo de muchas soluciones tecnológicas. La teoría de la información, por su parte, ha establecido el formalismo matemático necesario para el estudio de medidas cuantitativas de información como la entropía de Shannon y ha encontrado su lugar dentro de la implementación de la compresión sin perdida al proveer algunas de las herramientas teóricas necesarias para el estudio de los modelos que describen las fuentes de datos en la teoría de la codificación. Por otro lado, la cercana relación que se ha encontrado entre la teoría de la información y la teoría de la compresión sin perdida ha motivado a muchos autores a ingeniar formas de medir a través de la compresión de archivos la información en ellos. Lo que ha resultado en interesantes aplicaciones de la compresión sin perdida en el aprendizaje automático, particularmente, en la clasificación de textos escritos en lenguaje natural o cadenas de ADN. En este escrito, se presenta una revisión monográfica acerca de cómo la teoría de la información se aplica a la compresión sin perdida. Para esto, se presentan algunas de las implementaciones de la compresión sin perdida en la teoría de códigos y sus respectivos análisis. Las demostraciones, gráficas, algoritmos e implementaciones en este escrito generalizan algunos de los hechos más importantes acerca de codificaciones binarias que se han enunciado en la literatura, al caso general de alfabetos de tamaños arbitrarios. Finalmente, se presenta una aplicación de la compresión sin perdida al aprendizaje automático de máquina, para la clasificación del lenguaje natural, mediante la aplicación del algoritmo de codificación LZ77 para estimar algunas medidas de información bien conocidas en la literatura, las cuales se emplean como medida de distancia para comparar los lenguajes entre sí. El resultado de la clasificación es presentado en la forma de árboles filogenéticos del lenguaje natural

• Fecha de publicación: 2022
• Institución: Universidad del Rosario
• Repositorio: Repositorio EdocUR - U. Rosario
• Idioma: spa
• OAI Identifier: oai:repository.urosario.edu.co:10336/38216
• Acceso en línea: https://doi.org/10.48713/10336_38216; https://repository.urosario.edu.co/handle/10336/38216
• Palabra clave: Teoría de la información; Teoría de la codificación; Compresión de archivos; Entropía de Shannon; Aprendizaje automático de máquina; Codificación de Huffman; Procesamiento del lenguaje natural; Árboles filogenéticos del lenguaje natural; Principio de máxima entropía; Divergencia Kullback-Leibler; Procesos estocásticos; Contenido de información de Hartley; Information theory; Coding theory; File compression; Machine learning; Shannon's entropy; Huffman coding; LZ77; Natural language processing; Phylogenetic trees of natural language; Principle of maximum entropy; Kullback-Leibler divergence; Stochastic processes
• License: Attribution-NonCommercial-ShareAlike 4.0 International