XML compression via directed acyclic graphs
From MaRDI portal
Abstract: Unranked trees can be represented using their minimal dag (directed acyclic graph). For XML this achieves high compression ratios due to their repetitive mark up. Unranked trees are often represented through first child/next sibling (fcns) encoded binary trees. We study the difference in size (= number of edges) of minimal dag versus minimal dag of the fcns encoded binary tree. One main finding is that the size of the dag of the binary tree can never be smaller than the square root of the size of the minimal dag, and that there are examples that match this bound. We introduce a new combined structure, the hybrid dag, which is guaranteed to be smaller than (or equal in size to) both dags. Interestingly, we find through experiments that last child/previous sibling encodings are much better for XML compression via dags, than fcns encodings. We determine the average sizes of unranked and binary dags over a given set of labels (under uniform distribution) in terms of their exact generating functions, and in terms of their asymptotical behavior.
Recommendations
Cites work
- Algorithmics on SLP-compressed strings: a survey
- Analytic combinatorics
- Automata for XML -- a survey
- Enumerations of ordered trees
- scientific article; zbMATH DE number 177816 (Why is no real title available?)
- scientific article; zbMATH DE number 1149447 (Why is no real title available?)
- scientific article; zbMATH DE number 1150567 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- scientific article; zbMATH DE number 3383914 (Why is no real title available?)
- scientific article; zbMATH DE number 2241906 (Why is no real title available?)
- On programming of arithmetic operations
- Parameter reduction and automata evaluation for grammar-compressed trees
- Random access to grammar-compressed strings
- Singularity Analysis of Generating Functions
- The average height of binary trees and other simple trees
- The complexity of tree automata and XPath on grammar-compressed trees
- The rotation correspondence is asymptotically a dilatation
- Variations on the Common Subexpression Problem
Cited in
(22)- A bijection of plane increasing trees with relaxed binary trees of right height at most one
- Compacted binary trees admit a stretched exponential
- Distinct fringe subtrees in random trees
- Asymptotic enumeration of compacted binary trees of bounded right height
- Constructing small tree grammars and small circuits for formulas
- Size-optimal top dag compression
- Compression of unordered XML trees
- Approximation of smallest linear tree grammar
- Efficiency of lossless compression of a binary tree via its minimal directed acyclic graph representation
- scientific article; zbMATH DE number 7360256 (Why is no real title available?)
- Average case analysis of leaf-centric binary tree sources
- Tight bounds for top tree compression
- Comparison of XML compression techniques
- Compaction for two models of logarithmic‐depth trees: Analysis and experiments
- Simplifications of Uniform Expressions Specified by Systems
- Slowing down top trees for better worst-case compression
- Asymptotic analysis and efficient random sampling of directed ordered acyclic graphs
- Asymptotics of relaxed k-ary trees
- On the number of distinct fringe subtrees in binary search trees
- From tree automata to string automata minimization
- Constant-time tree traversal and subtree equality check for grammar-compressed trees
- Compressed structures for partial derivative automata constructions
This page was built for publication: XML compression via directed acyclic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q269349)
