Un Prototipo para la Consulta sobre Documentos Transformados con LZCS
Joaquín Adiego, Gonzalo Navarro, and Pablo de la Fuente.
En este artículo presentamos nuevos algoritmos de consulta sobre
documentos comprimidos mediante la transformación LZCS, que permite
realizar algunas de las operaciones más habituales de XPath. La
transformación LZCS permite comprimir sin pérdida colecciones de
documentos XML. LZCS está inspirado en las técnicas Lempel-Ziv
cuya idea subyacente es la de reemplazar subárboles por apuntadores a
ocurrencias previas de los mismos y, por consiguiente, nuestros algoritmos
intentan reutilizar el trabajo realizado sobre estos subárboles
redundantes. Los algoritmos se han implementado en un prototipo denominado
lzcs-grep. La principal ventaja de lzcs-grep es que permite
procesar los documentos comprimidos obteniendo unos tiempos de respuesta muy
pequeños en combinación con unas necesidades memoria muy bajas.
Nuestros resultados experimentales muestran que lzcs-grep es
competitivo respecto a otros procesadores de XPath incluso sobre documentos
sin comprimir y presentando el mejor comportamiento cuando se aplica sobre
los respectivos documentos comprimidos.