文献

J-GLOBAL ID：202302224031067397   整理番号：23A2458484

リペアを用いたXMLツリー構造圧縮【JST・京大機械翻訳】

XML tree structure compression using RePair

著者 (3件)： Lohrey Markus (Universitaet Leipzig, Institut fuer Informatik, Germany) ,  Maneth Sebastian (University of Oxford, Department of Computer Science, UK) ,  Mennicke Roy (Technische Universitaet Ilmenau, Institut fuer Theoretische Informatik, Germany)
資料名： Information Systems  (Information Systems)
巻： 38  号： 8  ページ： 1150-1167  発行年： 2013年 
JST資料番号： H0277C  ISSN： 0306-4379  CODEN： INSYD6  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： XMLツリー構造は,整然とした非ランク木を用いて便利に表現できる。XMLマークアップの反復性により,これらのツリーは,最小有向非巡回グラフ(DAG)または直線文脈フリー(SLCF)ツリー文法のような辞書ベース法を用いて効果的に圧縮できる。最小SLCFツリー文法は最小DAGよりも一般的に小さいが,P=NPがなければ多項式時間で計算できない。ここでは,ツリーRePairと呼ばれる小型SLCFツリー文法を計算するための新しい線形時間アルゴリズムを提示し,それが最良の既知の以前のアルゴリズムBPLEXを大幅に凌ぐことを示した。ツリーRePairは,LarssonとMoffatのRePairストリング圧縮アルゴリズムのツリーに対する一般化である。SLCFツリー文法は,樹木の効率的メモリ表現として使用できる。ツリーRePairを用いて,著者らは,著者らが認識する順序付けツリーの最小クエリ可能メモリ表現を作り出すことができた。一般的に使用されるXML文書の大規模コーパスに関する調査では,ツリーRePair文法上のツリートラバースは,ポインタ構造よりも14倍遅く,スクシンクトツリーよりも5倍遅く,一方,メモリ消費は,それぞれ1/43および1/6であった。ファイル圧縮に関して,ツリーRePair文法のHuffmanベース符号化が,最良既知XMLファイルコンプレッサに匹敵する圧縮比を与えることを示した。Copyright 2023 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *記憶装置 ,  符号化 ,  圧縮比 ,  ツリー構造 ,  文法 ,  木【グラフ】 ,  辞書 ,  文書 ,  線形時間アルゴリズム ,  ポインタ
準シソーラス用語： DAG【グラフ】 ,  多項式時間 ,  XML文書 ,  クエリー ,  順序づけ , 【Automatic Indexing@JST】

著者キーワード (3件)： XML ,  ツリー構造圧縮 ,  メモリ表現

分類 (1件)： 数理言語学  (JB05000V)

タイトルに関連する用語 (3件)： リペア ,  XML ,  ツリー構造