XML tree structure compression using RePair

作者：

Highlights：

• A generalization to trees of Larsson and Moffat's RePair algorithm is presented.

• TreeRePair outperforms all previous grammar-based tree compressors.

• TreeRePair produces smaller grammars, runs faster, and is easier to understand.

• TreeRePair produces the smallest queryable memory representation of ordered trees.

摘要

Highlights•A generalization to trees of Larsson and Moffat's RePair algorithm is presented.•TreeRePair outperforms all previous grammar-based tree compressors.•TreeRePair produces smaller grammars, runs faster, and is easier to understand.•TreeRePair produces the smallest queryable memory representation of ordered trees.

论文关键词：XML,Tree structure compression,Memory representation

论文评审过程：Received 30 October 2012, Revised 19 May 2013, Accepted 26 June 2013, Available online 8 July 2013.

论文官网地址：https://doi.org/10.1016/j.is.2013.06.006