文章基本信息

标题：LZ77 Factorisation of Trees
本地全文：下载
作者：Pawel Gawrychowski ; Artur Jez
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：65
页码：35:1-35:15
DOI：10.4230/LIPIcs.FSTTCS.2016.35
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We generalise the fundamental concept of LZ77 factorisation from strings to trees. A tree is represented as a collection of edge-disjoint fragments that either consist of one node or has already occurred earlier (in the BFS order). Similarly as for strings, such a collection uniquely determines the tree, so by minimising the number of fragments we obtain a compressed representation of the tree. We show that our generalisation has several useful properties of the standard LZ77 factorisation: it can be computed in polynomial time and its simpler variant in linear time; its size is not larger than the smallest grammar for a tree; it can be transformed (in linear time) into a tree grammar of size O(rg log(n/(rg))), where n is the size of the tree, g the size of the smallest grammar for this tree and r the maximal arity of the nodes in the tree, which matches a recent bound of Jez and Lohrey [STACS 2014], but with a simpler and more modular proof.
关键词：Tree grammars; Grammar compression; LZ77; SLP; Tree compression