Tree Compression Using String Grammars
Tree Compression Using String Grammars
复制标题
使用字符串语法进行树压缩
DOI：
10.1007/s00453-017-0279-3
复制
发表时间：
2016
期刊：
影响因子：
1.1
通讯作者：
Eric Nöth
中科院分区：
文献类型：
--
作者：
Moses Ganardi;Danny Hucke;Markus Lohrey;Eric Nöth
我们研究的压缩表示的排序树的（字符串）直线程序（SLP）的前序遍历，并比较它与良好的研究表示的直线上下文无关树文法（也被称为树直线程序或TSLP）。虽然SLP可能是指数更简洁的TSLP，我们表明，许多简单的树查询仍然可以有效地执行SLP，如计算树的高度，树导航，或布尔表达式的评价。树遍历的其他问题变得棘手，例如模式匹配和树自动机的评估。这些问题仍然可以在多项式时间内解决TSLP。
We study the compressed representation of a ranked tree by a (string) straight-line program (SLP) for its preorder traversal, and compare it with the well-studied representation by straight-line context free tree grammars (which are also known as tree straight-line programs or TSLPs). Although SLPs may be exponentially more succinct than TSLPs, we show that many simple tree queries can still be performed efficiently on SLPs, such as computing the height of a tree, tree navigation, or evaluation of Boolean expressions. Other problems on tree traversals turn out to be intractable, e.g. pattern matching and evaluation of tree automata. These problems can be still solved in polynomial time for TSLPs.
登录
查看更多内容
叶语言和字符串压缩
DOI：
10.1016/j.ic.2011.01.009
发表时间：
2011
期刊：
Inf. Comput.
影响因子：
--
作者：
Markus Lohrey
通讯作者：
Markus Lohrey
压缩词的字面洗牌
DOI：
10.1007/978-0-387-09680-3_6
发表时间：
2008
期刊：
Inf. Comput.
影响因子：
--
作者：
A. Bertoni;C. Choffrut;R. Radicioni
通讯作者：
R. Radicioni
用于重复文本集合的更快压缩后缀树
DOI：
10.1007/978-3-319-07959-2_36
发表时间：
2014
期刊：
Inf. Comput.
影响因子：
--
作者：
G. Navarro;Alberto Ordóñez Pereira
通讯作者：
Alberto Ordóñez Pereira
DOI：
10.1016/j.ic.2013.01.002
发表时间：
2011
期刊：
Higher-Order and Symbolic Computation
影响因子：
--
作者：
Markus Lohrey;Christian Mathissen
通讯作者：
Christian Mathissen
通过有向无环图进行 XML 压缩
影响因子：
0.5
作者：
M. Bousquet-Mélou;M. Lohrey;S. Maneth;E. Noeth
通讯作者：
E. Noeth