Estructuras de indexación de cadenas

Las estructuras de indexación de cadenas preprocesan un texto en un formato de búsqueda —árboles de prefijos (tries), árboles de sufijos o arreglos de sufijos— para que muchas consultas posteriores de patrones, y preguntas sobre repeticiones y subcadenas comunes, puedan ser respondidas rápidamente.

Definition

Una estructura de indexación de cadenas es una estructura de datos construida a partir de un texto (o conjunto de cadenas) que permite consultas eficientes sobre el texto —como si un patrón ocurre y dónde, la subcadena repetida más larga, o la subcadena común más larga de dos textos— típicamente representando los prefijos o sufijos del texto.

Scope

Este tema cubre las estructuras de datos que indexan cadenas para una consulta repetida rápida: los árboles de prefijos (tries) para conjuntos de cadenas, los árboles de sufijos que representan todos los sufijos de un texto para la búsqueda de patrones en tiempo lineal, los arreglos de sufijos como su contraparte eficiente en espacio, y las estructuras de soporte como el arreglo de prefijos comunes más largos. Trata sus algoritmos de construcción y las consultas que aceleran, y excluye la coincidencia de patrones de una sola vez, que no preprocesa el texto.

Core questions

• ¿Cómo organiza un árbol de prefijos (trie) un conjunto de cadenas para la búsqueda basada en prefijos?
• ¿Cómo representa un árbol de sufijos todos los sufijos para que las consultas de patrones tomen un tiempo proporcional a la longitud del patrón?
• ¿Cómo logran los arreglos de sufijos una potencia similar con menos memoria?
• ¿Qué algoritmos de construcción construyen estas estructuras de manera eficiente, idealmente en tiempo lineal?
• ¿Qué problemas de texto (repeticiones, subcadenas comunes) resuelven estos índices de manera elegante?

Key concepts

• árbol de prefijos (trie)
• árbol de sufijos
• arreglo de sufijos
• arreglo de prefijos comunes más largos
• construcción en línea
• subcadena repetida más larga
• subcadena común más larga
• compensaciones espacio-tiempo

Key theories

Árboles de sufijos y construcción en tiempo lineal

Un árbol de sufijos representa de forma compacta cada sufijo de un texto, permitiendo buscar un patrón en un tiempo proporcional a su longitud; el algoritmo de Ukkonen lo construye en línea en un tiempo lineal con respecto a la longitud del texto.

Arreglos de sufijos como un índice eficiente en espacio

Un arreglo de sufijos almacena el orden ordenado de todos los sufijos en un arreglo de enteros simple; combinado con un arreglo de prefijos comunes más largos, permite una búsqueda rápida de patrones utilizando mucha menos memoria que un árbol de sufijos.

Clinical relevance

Los índices de texto impulsan la búsqueda a gran escala y la bioinformática: los arreglos de sufijos y los índices comprimidos relacionados son la base de los alineadores de lectura de genomas y los motores de búsqueda de texto completo, los árboles de prefijos (tries) soportan el autocompletado y las tablas de enrutamiento IP, y estas estructuras hacen que las consultas repetidas sobre textos masivos sean prácticas donde el reescaneo sería prohibitivo.

History

Peter Weiner introdujo los árboles de sufijos en 1973, con construcciones en tiempo lineal más simples por McCreight (1976) y Ukkonen (1995). Manber y Myers introdujeron los arreglos de sufijos en 1990 como una alternativa más eficiente en espacio, y trabajos posteriores sobre índices comprimidos y FM extendieron estas ideas a textos y genomas muy grandes.

Key figures

• Peter Weiner
• Edward McCreight
• Esko Ukkonen
• Udi Manber
• Gene Myers
• Dan Gusfield

Seminal works

• ukkonen1995
• manber1993
• gusfield1997

Frequently asked questions

¿Cuándo se debe usar un arreglo de sufijos en lugar de un árbol de sufijos?

Los arreglos de sufijos utilizan considerablemente menos memoria que los árboles de sufijos y tienen un buen comportamiento de caché, lo que los hace preferibles para textos grandes como los genomas. Los árboles de sufijos exponen más estructura directamente y pueden hacer que algunos algoritmos sean conceptualmente más simples, pero a un costo de espacio mayor; los arreglos de sufijos más un arreglo de prefijos comunes más largos recuperan la mayor parte de esa potencia.

¿Para qué sirve un árbol de prefijos (trie)?

Un árbol de prefijos (trie) almacena un conjunto de cadenas por prefijos compartidos, lo que permite una búsqueda rápida de prefijos, autocompletado y recorrido ordenado. Es adecuado para diccionarios, sugerencias de autocompletado y la coincidencia de prefijos más largos, como en el enrutamiento IP, donde las claves comparten inicios comunes.