Adaptive Compression of Graph Structured Text
John R. Gilbert, David M. Abrahamson · DCC · 2008
In this paper we introduce an adaptive technique for compressing small quantities of text which are organized as a rooted directed graph. We impose a constraint on the technique such that data encountered during a traversal of any valid path through the graph must be recoverable without requiring the expansion of data that is not on the path in question. While compression can be applied independently to the text at each node using well known techniques, we propose exploiting inter-node context to improve results when using adaptive dictionary based compression methods. The technique we present (Graph LZW) determines the set of nodes which are guaranteed to be encountered before reaching node x while traversing any valid path in the graph, and uses them as a basis for conditioning an LZW dictionary for the compression/expansion of the data in x.