Índice de texto para una búsqueda de patrones espaciados más rápida
Autores: Hossen, Md Helal; Gibney, Daniel; Thankachan, Sharma V.
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Índice de texto para una búsqueda de patrones espaciados más rápida
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Eficiente
Ocurrencias
Brecha
índice
Tiempo de consulta
Subcadenas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 29
Citaciones: Sin citaciones
Revisitamos la siguiente versión del problema de indexación de cadenas con huecos, donde el objetivo es preprocesar un texto para permitir informar eficientemente todas las ocurrencias de un patrón con huecos en. Una ocurrencia de en se define como un par donde las subcadenas y coinciden y, respectivamente, con un hueco que se encuentra dentro del intervalo. Este problema tiene aplicaciones significativas en biología computacional y minería de textos. Un resultado de dificultad en este problema sugiere que cualquier índice con tiempo de consulta polilogarítmico debe ocupar un espacio cercano al cuadrático. En un estudio reciente [STACS 2024], Bille et al. presentaron un índice de espacio subcuadrático utilizando espacio, donde es un parámetro fijo en el momento de la construcción del índice. Su tiempo de consulta es, que es sublineal por ocurrencia cuando. Mostramos cómo lograr un tiempo de consulta sensible al hueco de utilizando el mismo espacio, donde denota el número de ocurrencias con hueco. Esto es más rápido cuando hay muchas ocurrencias con huecos pequeños.
Descripción
Revisitamos la siguiente versión del problema de indexación de cadenas con huecos, donde el objetivo es preprocesar un texto para permitir informar eficientemente todas las ocurrencias de un patrón con huecos en. Una ocurrencia de en se define como un par donde las subcadenas y coinciden y, respectivamente, con un hueco que se encuentra dentro del intervalo. Este problema tiene aplicaciones significativas en biología computacional y minería de textos. Un resultado de dificultad en este problema sugiere que cualquier índice con tiempo de consulta polilogarítmico debe ocupar un espacio cercano al cuadrático. En un estudio reciente [STACS 2024], Bille et al. presentaron un índice de espacio subcuadrático utilizando espacio, donde es un parámetro fijo en el momento de la construcción del índice. Su tiempo de consulta es, que es sublineal por ocurrencia cuando. Mostramos cómo lograr un tiempo de consulta sensible al hueco de utilizando el mismo espacio, donde denota el número de ocurrencias con hueco. Esto es más rápido cuando hay muchas ocurrencias con huecos pequeños.