文献

J-GLOBAL ID：201502214445994413   整理番号：15A0937320

根付き順序木の圧縮における分割型文法とオイラー文字列との比較

著者 (5件)： 劉立偉 (大連交通大 理) ,  森智弥 (京大 化研 バイオインフォマティクスセ) ,  趙楊 (産業技術総合研 創薬分子プロファイリング研究セ) ,  林田守広 (京大 化研 バイオインフォマティクスセ) ,  阿久津達也 (京大 化研 バイオインフォマティクスセ)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 115  号： 112(IBISML2015 1-26)  ページ： 245-246  発行年： 2015年06月16日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 辺にラベルの付いた根付き順序木を圧縮する手法として文法に基づく手法を検討する。木文法としては文脈自由文法(CFG)を拡張したSimple Elementary Ordered Tree Grammar(SEOTG)と呼ばれる分割型文法を使用する。一方で根付き順序木はオイラー文字列として文字列に変換できるので,オイラー文字列をCFGに基づいて圧縮する。本研究では与えられた根付き順序木のみを生成する最小のSEOTGのサイズと,変換後のオイラー文字列のみを生成する最小のCFGのサイズとを比較し,ある特定の木に対しては,76頂点までであるが,頂点数の増加とともにサイズの差も大きくなることを報告する。(著者抄録)

シソーラス用語： *木【グラフ】 ,  *圧縮 ,  *文脈自由文法 ,  文字列 ,  分析 ,  ラベル付け【画像】
準シソーラス用語： Euler文字列 ,  *根付き順序木 ,  比較分析 ,  *分割型文法

分類 (1件)： 記号処理  (JE03000Q)

引用文献 (2件)：

• Akutsu, T.: A Bisection Algorithm for Grammar-based Compression of Ordered Trees, Information Processing Letters, pp. 815-820 (2010).
• Zhao, Y., Hayashida, M., Cao, Y., Hwang, J. and Akutsu, T.: Grammar-based Compression Approach to Extraction of Common Rules Among Multiple Trees of Glycans and RNAs, BMC Bioinformatics, Vol. 16, p. 128 (2015).

タイトルに関連する用語 (4件)： 根付き ,  順序木 ,  文法 ,  文字列