A bisection algorithm for grammar-based compression of ordered trees

Tatsuya Akutsu

首页> 外文期刊>Information Processing Letters >A bisection algorithm for grammar-based compression of ordered trees

【24h】

A bisection algorithm for grammar-based compression of ordered trees

机译：一种基于二分法的基于语法的有序树压缩

获取原文

获取原文并翻译 | 示例

获取外文期刊封面封底 >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

In this paper, we consider grammar-based compression for rooted ordered trees. For that purpose, we define an elementary ordered tree grammar (EOTG) by extending CFG, and then present a polynomial time algorithm which approximates the smallest EOTG within a factor of O(n~(5/6)). We also show that the grammar and algorithm can be modified for unordered trees of bounded degree.

机译：在本文中，我们考虑对有序有序树进行基于语法的压缩。为此，我们通过扩展CFG定义基本有序树语法（EOTG），然后提出一种多项式时间算法，该算法在O（n〜（5/6））因子内近似最小的EOTG。我们还表明，可以对有界度的无序树进行语法和算法修改。

著录项

来源
《Information Processing Letters》 |2010年第19期|P.815-820|共6页
作者
Tatsuya Akutsu;
展开▼
作者单位

Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto 611-0011, Japan;

展开▼
收录信息美国《科学引文索引》(SCI);美国《工程索引》(EI);
原文格式 PDF
正文语种 eng
中图分类
关键词
approximation algorithms; graph algorithms; tree grammars; data compression;

机译：近似算法;图算法树语法数据压缩;

相似文献

外文文献
中文文献
专利

1. Integer programming-based method for grammar-based tree compression and its application to pattern extraction of glycan tree structures [J] . Yang Zhao, Morihiro Hayashida, Tatsuya Akutsu BMC Bioinformatics . 2010,第SUPPLEMENTa11期

机译：基于整数编程的基于树的树压缩方法及其在聚糖树结构模式提取中的应用
2. Grammar-Based Compression of Unranked Trees [J] . Gascon Adria, Lohrey Markus, Maneth Sebastian, Theory of computing systems . 2020,第1期

机译：基于语法的未排序树压缩
3. Universal Tree Source Coding Using Grammar-Based Compression [J] . Ganardi Moses, Hucke Danny, Lohrey Markus, IEEE Transactions on Information Theory . 2019,第10期

机译：使用基于语法的压缩的通用树源编码
4. An Effective Grammar-Based Compression Algorithm for Tree Structured Data [C] . Kazunori Yamagata, Tomoyuki Uchida, Takayoshi Shoudai, Inductive Logic Programming . 2003

机译：一种有效的基于语法的树状结构数据压缩算法
5. On the design and analysis of grammar-based data compression algorithms. [D] . Jia, Yunwei. 2002

机译：基于语法的数据压缩算法的设计与分析。
6. Integer programming-based method for grammar-based tree compression and its application to pattern extraction of glycan tree structures [O] . Yang Zhao, Morihiro Hayashida, Tatsuya Akutsu 2010

机译：基于整数编程的基于树的树压缩方法及其在聚糖树结构模式提取中的应用
7. A bisection algorithm for grammar-based compression of ordered trees [O] . Akutsu Tatsuya 2010

机译：一种基于二分法的基于语法的有序树压缩

A bisection algorithm for grammar-based compression of ordered trees

摘要

著录项

相似文献

相关主题

期刊订阅