Matriz de sufijo

En informática , una matriz de sufijos es una matriz ordenada de todos los sufijos de una cadena . Es una estructura de datos utilizada, entre otros, en índices de texto completo, algoritmos de compresión de datos y en el campo de la bibliometría .

Las matrices de sufijos fueron introducidas por Manber y Myers (1990) como una alternativa simple y eficiente en el espacio a los árboles de sufijos . Gaston Gonnet los había descubierto de forma independiente en 1987 con el nombre de matriz PAT ( Gonnet, Baeza-Yates & Snider 1992 ).

Li, Li y Huo (2016) proporcionaron el primer algoritmo de construcción de matrices de sufijos de tiempo en el lugar que es óptimo tanto en el tiempo como en el espacio, donde en el lugar significa que el algoritmo solo necesita espacio adicional más allá de la cadena de entrada y la matriz de sufijos de salida. ${\ Displaystyle {\ mathcal {O}} (n)}$ ${\ Displaystyle {\ mathcal {O}} (1)}$

Las matrices de sufijos mejoradas (ESA) son matrices de sufijos con tablas adicionales que reproducen la funcionalidad completa de los árboles de sufijos conservando el mismo tiempo y complejidad de memoria. ^[1] La matriz de sufijos para un subconjunto de todos los sufijos de una cadena se llama matriz de sufijos dispersos . ^[2] Se han desarrollado múltiples algoritmos probabilísticos para minimizar el uso de memoria adicional, incluido un tiempo óptimo y un algoritmo de memoria. ^[3]

Sea una -cadena y denote la subcadena de rango de a inclusive. ${\ Displaystyle S = S [1] S [2] ... S [n]}$ ${\ textstyle n}$ ${\ Displaystyle S [i, j]}$ ${\ Displaystyle S}$ ${\ Displaystyle i}$ ${\ Displaystyle j}$

La matriz de sufijos de ahora se define como una matriz de números enteros que proporcionan las posiciones iniciales de los sufijos de en orden lexicográfico . Este medio, una entrada contiene la posición de partida de la -ésima sufijo más pequeño y por lo tanto para todos : . ${\ Displaystyle A}$ ${\ Displaystyle S}$ ${\ Displaystyle S}$ ${\ Displaystyle A [i]}$ ${\ Displaystyle i}$ ${\ Displaystyle S}$ ${\ Displaystyle 1 <i \ leq n}$ ${\ Displaystyle S [A [i-1], n] <S [A [i], n]}$