Árboles de Sufijos Comprimidos en Memoria Secundaria
Norma Herrera and Gonzalo Navarro
Los índices en bases de datos de texto permiten resolver eficientemente
la búsqueda de una secuencia de caracteres en grandes volúmenes de texto.
Dado que el índice de una base de datos de texto ocupa
más espacio que el texto indexado, el diseño de índices comprimidos
para memoria secundaria es un tema de creciente interés.
Uno de los índices en memoria secundaria para texto más relevante es
el Compact Pat Tree que consiste en representar un árbol de
sufijos en memoria secundaria y en forma compacta.
Uno de los principales problemas de este índice es el desperdicio de
espacio. En este artículo presentamos
una implementación práctica del Compact Pat Tree y modificaciones
en el diseño del mismo que permiten reducir el desperdicio de
espacio manteniendo su eficiencia.