logo móvil
Contáctanos

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

Descargar PDF

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


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 .

Otros recursos que podrían interesarte

Temas Virtualpro