权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Quantitative Aspects of Grammar-Based Compression

基于语法的压缩的定量方面

基本信息

批准号：
261105198
负责人：
Professor Dr. Markus Lohrey
金额：
--
依托单位：
Department Elektrotechnik und Informatik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2014
资助国家：
德国
起止时间：
2013-12-31 至 2021-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/261105198?language=en
关键词：
Quantitative Aspects Grammar Based Compression

项目摘要

Grammar-based compression has been studied in the last two decades from a theoretical as well as practical point of view. Except for the family of Lempel-Ziv compressors, only few precisequantitative statements on the performance of grammar-based compressors are known. A good example are the so called global compressors (e.g. RePair) which show an excellent performance in practice, but which also exhibit a big gap between the known upper and lower bounds on the compression ratio. For grammar-based tree compressors the existing research gap is even larger. The main goal of the project is dithe development of new techniques for deriving precise quantitative statements on the compression ratio of grammar-based string and tree compressors. In this second project phase, the focus will be on the approximation ratio of global grammar-based compressors, and the analysis of grammar-based tree compressors. In particular, the average case analysis of the size of minimal DAGs (directed acyclic graphs) for trees with respect to various probability distributions will be studied in more detail. Universal tree compression is our main application of this research direction.

在过去的二十年里，人们从理论和实践的角度对基于语法的压缩进行了研究。除了 Lempel-Ziv 压缩器系列之外，关于基于语法的压缩器性能的精确定量陈述很少为人所知。一个很好的例子是所谓的全局压缩器（例如RePair），它在实践中表现出出色的性能，但在已知的压缩比上限和下限之间也表现出很大的差距。对于基于语法的树压缩器，现有的研究差距甚至更大。该项目的主要目标是开发新技术，以得出基于语法的字符串和树压缩器的压缩比的精确定量陈述。在第二个项目阶段，重点将放在基于全局语法的压缩器的近似比以及基于语法的树压缩器的分析上。特别是，将更详细地研究树的最小 DAG（有向无环图）大小相对于各种概率分布的平均情况分析。通用树压缩是我们这个研究方向的主要应用。

项目成果

期刊论文数量（9）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Grammar-Based Compression of Unranked Trees

DOI：
10.1007/s00224-019-09942-y
发表时间：
2018-02
期刊：
Theory of Computing Systems
影响因子：
0.5
作者：
Adrià Gascón;Markus Lohrey;S. Maneth;C. Reh;K. Sieber
通讯作者：
Adrià Gascón;Markus Lohrey;S. Maneth;C. Reh;K. Sieber

The Smallest Grammar Problem Revisited

重温最小的语法问题

DOI：
10.1109/tit.2020.3038147
发表时间：
2020
期刊：
IEEE Transactions on Information Theory
影响因子：
2.5
作者：
Hideo Bannai;Momoko Hirayama;Danny Hucke;Shunsuke Inenaga;Artur Jeż;Markus Lohrey;Carl Philipp Reh
通讯作者：
Carl Philipp Reh

On the Collection of Fringe Subtrees in Random Binary Trees