XML Compression via Directed Acyclic Graphs
XML Compression via Directed Acyclic Graphs
复制标题
通过有向无环图进行 XML 压缩
DOI：
10.1007/s00224-014-9544-x
复制
发表时间：
2014
影响因子：
0.5
通讯作者：
E. Noeth
中科院分区：
文献类型：
--
作者：
M. Bousquet-Mélou;M. Lohrey;S. Maneth;E. Noeth
未排序节点标记的树可以使用它们的最小dag（有向无环图）来表示。对于XML，由于重复标记，这实现了高压缩比。未排序的树通常通过第一个子/下一个兄弟（fcns）编码的二叉树表示。我们研究了最小dag与最小dag编码二叉树在大小（=边数）上的差异。一个主要的发现是二叉树的dag的大小永远不可能小于最小dag大小的平方根，并且有匹配这个边界的例子。我们引入了一种新的组合结构，混合dag，它保证小于（或等于）两个dag的大小。有趣的是，我们通过实验发现，对于通过dag进行XML压缩，最后一个子/前一个兄弟编码要比fcns编码好得多。我们在给定的一组标签（在均匀分布下）上，根据它们的精确生成函数和它们的渐近行为，确定了未排序和二元标签的平均大小。
Unranked node-labeled 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, thehybrid 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.
登录
查看更多内容
半结构化数据的类型检查
DOI：
--
发表时间：
2001
期刊：
International Workshop/Symposium on Database Programming Languages
影响因子：
--
作者：
Dan Suciu
通讯作者：
Dan Suciu
影响因子：
3.7
作者：
Lohrey, Markus;Maneth, Sebastian;Mennicke, Roy
通讯作者：
Mennicke, Roy
影响因子：
0.8
作者：
N. Dershowitz;S. Zaks
通讯作者：
S. Zaks
XML 自动机 - 一项调查
DOI：
--
发表时间：
2007
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
T. Schwentick
通讯作者：
T. Schwentick
DOI：
--
发表时间：
2004
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
J. Marckert
通讯作者：
J. Marckert