Tree structure compression with RePair

Details Tree structure compression with RePair Tree structure compression with RePair

2010-07-30

arxiv.org/abs/1007.5406v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this work we introduce a new linear time compression algorithm, called "Re-pair for Trees", which compresses ranked ordered trees using linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars and allow basic tree operations, like traversal along edges, to be executed without prior decompression. Our algorithm can be considered as a generalization of the "Re-pair" algorithm developed by N. Jesper Larsson and Alistair Moffat in 2000. The latter algorithm is a dictionary-based compression algorithm for strings. We also introduce a succinct coding which is specialized in further compressing the grammars generated by our algorithm. This is accomplished without loosing the ability do directly execute queries on this compressed representation of the input tree. Finally, we compare the grammars and output files generated by a prototype of the Re-pair for Trees algorithm with those of similar compression algorithms. The obtained results show that that our algorithm outperforms its competitors in terms of compression ratio, runtime and memory usage.

Affiliated with

Also associated with

No associations

Rating

Tree structure compression with RePair does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tree structure compression with RePair, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tree structure compression with RePair will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-700526