Evaluación práctica de los factores de Lyndon a través de la reordenación del alfabeto
Autores: Albertini, Marcelo K.; Louza, Felipe A.
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Evaluación práctica de los factores de Lyndon a través de la reordenación del alfabeto
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Ordenaciones del alfabeto
Factorización de Lyndon
Conjuntos de datos
Algoritmos
índices
Permutaciones aleatorias del alfabeto
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 17
Citaciones: Sin citaciones
Evaluamos la influencia de diferentes ordenamientos de alfabetos en la factorización de Lyndon de una cadena. Los experimentos con conjuntos de datos muestran que para la mayoría de los reordenamientos de alfabetos, el número de factores de Lyndon suele ser pequeño, y la longitud del factor de Lyndon más largo puede ser tan grande como la cadena de entrada, lo cual es desfavorable para algoritmos e índices que dependen del número de factores de Lyndon. Presentamos resultados con permutaciones aleatorias de alfabetos que pueden ser utilizadas como línea base para evaluar la efectividad de heurísticas y métodos diseñados para modificar la factorización de Lyndon de una cadena mediante el reordenamiento del alfabeto.
Descripción
Evaluamos la influencia de diferentes ordenamientos de alfabetos en la factorización de Lyndon de una cadena. Los experimentos con conjuntos de datos muestran que para la mayoría de los reordenamientos de alfabetos, el número de factores de Lyndon suele ser pequeño, y la longitud del factor de Lyndon más largo puede ser tan grande como la cadena de entrada, lo cual es desfavorable para algoritmos e índices que dependen del número de factores de Lyndon. Presentamos resultados con permutaciones aleatorias de alfabetos que pueden ser utilizadas como línea base para evaluar la efectividad de heurísticas y métodos diseñados para modificar la factorización de Lyndon de una cadena mediante el reordenamiento del alfabeto.