logo móvil
Contáctanos

Í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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro