Índice de subcadena

En informática , un índice de subcadenas es una estructura de datos que permite la búsqueda de subcadenas en un texto o colección de textos en tiempo sublineal . Una vez construido a partir de un documento o conjunto de documentos, un índice de subcadenas puede utilizarse para localizar todas las ocurrencias de un patrón en tiempo lineal o casi lineal con respecto al tamaño del patrón, sin dependencia o con una dependencia logarítmica únicamente respecto al tamaño del documento. ^{[ 1 ]}

La expresión « índice de texto completo» se usa a menudo para referirse a índices de subcadenas. Sin embargo, esto resulta ambiguo, ya que también se utiliza para índices de palabras comunes, como archivos invertidos y recuperación de documentos . Véase «búsqueda de texto completo» .

Estas estructuras de datos suelen tratar el texto y el patrón como cadenas sobre un alfabeto fijo, y buscan ubicaciones donde el patrón aparece como una subcadena del texto. Los símbolos del alfabeto pueden ser caracteres (por ejemplo, en Unicode ), pero en aplicaciones prácticas para la recuperación de texto puede ser preferible tratar las palabras ( con raíz ) de un documento como los símbolos de su alfabeto, ya que esto reduce la longitud tanto del texto como del patrón, medida en número de símbolos. ^{[ 2 ]}

Entre las estructuras de datos específicas que se pueden utilizar como índices de subcadenas se incluyen:

• El árbol de sufijos , un árbol de raíz de los sufijos de la cadena, que permite realizar búsquedas de subcadenas símbolo por símbolo ^{[ 1 ] [ 3 ]}
• El autómata de sufijos , el autómata finito determinista mínimo que reconoce subcadenas de un texto dado, está estrechamente relacionado con el árbol de sufijos y se puede construir mediante variantes de los mismos algoritmos. ^{[ 4 ]}
• El array de sufijos , un array ordenado de las posiciones iniciales de los sufijos de la cadena, permite realizar búsquedas de subcadenas mediante búsqueda binaria ^{[ 1 ] [ 3 ].} Ampliar un array de sufijos con un array LCP de las longitudes de los prefijos comunes de sufijos consecutivos permite realizar la búsqueda símbolo por símbolo, igualando el tiempo de búsqueda del árbol de sufijos. ^{[ 5 ]}
• El array de sufijos comprimidos , una estructura de datos que combina la compresión de datos con el array de sufijos, permite que la estructura se almacene en un espacio sublineal en la longitud del texto ^{[ 1 ] [ 3 ]}
• El índice FM , otro índice de subcadenas comprimidas basado en la transformada de Burrows-Wheeler y estrechamente relacionado con la matriz de sufijos ^{[ 6 ].}