En informática , un índice de subcadenas es una estructura de datos que proporciona una búsqueda de subcadenas en un texto o una colección de texto en tiempo sublineal . Si tienes un documento de longitud , o un conjunto de documentos de longitud total , puede localizar todas las apariciones de un patrón en hora. (Consulte la notación Big O ).
La frase índice de texto completo también se usa a menudo para un índice de todas las subcadenas de un texto. Pero es ambiguo, ya que también se usa para índices de palabras regulares, como archivos invertidos y recuperación de documentos . Ver búsqueda de texto completo .
Los índices de subcadenas incluyen:
- Árbol de sufijo
- Matriz de sufijo
- Índice de N-gramas, un archivo invertido para todos los N-gramas del texto
- Matriz de sufijos comprimidos [1]
- Índice FM
- Índice LZ
Referencias
- ^ R. Grossi y JS Vitter, Matrices de sufijos comprimidos y árboles de sufijos, con aplicaciones a la indexación de texto y la coincidencia de cadenas , SIAM Journal on Computing, 35 (2), 2005, 378-407.