Aproximación de ratios de RePair, LongestMatch y Greedy en cadenas unarias
Autores: Hucke, Danny; Reh, Carl Philipp
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Aproximación de ratios de RePair, LongestMatch y Greedy en cadenas unarias
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmo
Gramática
Ratio de aproximación
Palabra de entrada
Peor caso
Cota superior
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 37
Citaciones: Sin citaciones
Un compresor basado en gramática es un algoritmo que recibe una palabra y produce una gramática libre de contexto que solo genera esta palabra. El ratio de aproximación para una sola palabra de entrada es el tamaño de la gramática producida para esta palabra dividido por el tamaño de la gramática más pequeña para esta palabra. El ratio de aproximación en el peor caso de un compresor basado en gramática para una longitud de palabra dada es el mayor ratio de aproximación sobre todas las palabras de entrada de esa longitud. En este trabajo, estudiamos el ratio de aproximación en el peor caso de los algoritmos , y en cadenas unarias, es decir, cadenas que solo hacen uso de un símbolo. Nuestra principal contribución es mostrar el límite superior mejorado de para el ratio de aproximación en el peor caso de . Además, también mostramos el límite inferior de para el ratio de aproximación en el peor caso de , y que y tienen un ratio de aproximación en el peor caso de .
Descripción
Un compresor basado en gramática es un algoritmo que recibe una palabra y produce una gramática libre de contexto que solo genera esta palabra. El ratio de aproximación para una sola palabra de entrada es el tamaño de la gramática producida para esta palabra dividido por el tamaño de la gramática más pequeña para esta palabra. El ratio de aproximación en el peor caso de un compresor basado en gramática para una longitud de palabra dada es el mayor ratio de aproximación sobre todas las palabras de entrada de esa longitud. En este trabajo, estudiamos el ratio de aproximación en el peor caso de los algoritmos , y en cadenas unarias, es decir, cadenas que solo hacen uso de un símbolo. Nuestra principal contribución es mostrar el límite superior mejorado de para el ratio de aproximación en el peor caso de . Además, también mostramos el límite inferior de para el ratio de aproximación en el peor caso de , y que y tienen un ratio de aproximación en el peor caso de .