SCM: Structural Contexts Model for Improving Compression in
Semistructured Text Databases
Joaquín Adiego, Gonzalo Navarro and Pablo de la Fuente
We describe a compression model for semistructured documents, called
Structural Contexts Model, which takes advantage of the context
information usually implicit in the structure of the text. The idea is
to use a separate semiadaptive model to compress the text that lies inside
each different structure type (e.g., different XML tag). The intuition
behind the idea is that the distribution of all the texts that belong to a
given structure type should be similar, and different from that of other
structure types. We test our idea using a word-based Huffman coding, which
is the standard for compressing large natural language textual databases,
and show that our compression method obtains significant improvements in
compression ratios. We also analyze the possibility that storing separate
models may not pay off if the distribution of different structure types
is not different enough, and present a heuristic to merge models with
the aim of minimizing the total size of the compressed database. This
technique gives an additional improvement over the plain technique. The
comparison against existing prototypes shows that our method is a competitive
choice for compressed text databases.
Finally, we show how to apply SCM over text chunks, which allows one to ajust
the different word frequencies as they change across the text collection.