順序木に対する逐次的な可逆圧縮手法

• Item type: SIG Technical Reports(1)
• 公開日: 2004-05-21
• タイトル: 順序木に対する逐次的な可逆圧縮手法
• タイトル / 言語: en
• タイトル: Sequential Algorithm for Comprerssing Ordered Tree without Loss
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Computer and Media Technologies Hiroshima City University
• 著者所属: Faculty of Infromation Sciences
• 著者所属: Faculty of Infromation Sciences
• 著者所属(英): en
• 著者所属(英): Department of Computer and Media Technologies, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Faculty of Information Sciences, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Faculty of Information Sciences, Hiroshima City University
• 著者名: 加藤廣一郎; 内田, 智之; 中村, 泰明
• 著者名(英): Kouichiro, Katoh; Tomoyuki, Uchida; Yasuaki, Nakamura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ネットワークや記憶装置技術の急激な発達とともに，厳密な構造を持たないが，木構造を持っている木構造データとよばれるデータが急増している．多くの巨大な木構造データを構造的に解析するには多くの時間を要するため，木構造データを構造を保持しながらできる限り可逆的に圧縮することができれば，その解析時間の短縮が望める．そこで，逐次的に与えられる木構造データを可逆的に圧縮する効率のよい手法を提案することを目的とする．本稿では，子に順番がつけられている根付き木である順序木で木構造データを表現する．そこで，逐次的に与えられる順序木に対する圧縮を定式化し，文字列上の圧縮手法の一つであるLZSS手法をもとに，順序木に対する逐次可逆圧縮アルゴリズムを提案する．さらに，高速な解凍アルゴリズムについても提案する．また，これらのアルゴリズムを計算機上に実装し，人工データを用いた評価実験の結果について報告する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Due to the rapid growth of Information Technologies, electronic data which have no rigid structure but have tree structures have been rapidly increasing and each of them has become larger. Such data is called tree structured data. In general, analyzing large tree structured data is a time-consuming process in data mining. If we reduce the size of input data without loss of information including structural features, we can speed up such a heavy process. The purpose of this paper is to present an efficient lossless compression algorithm for sequential tree structured data. Tree structured data are represented by rooted trees each of whose internal node has ordered children. Such a tree is called an ordered tree. Firstly, we give a concept of lossless compression for an ordered tree. Secondly, based on a LZSS method which is one of lossless compression methods over strings, we present sequential algorithm for sequentially compressing a large ordered tree without loss. Moreover, we also present an efficient decompression algorithm for compressed ordered tree. Finally, in order to evaluate the performance of our algorithms, we report some experimental results.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2004, 号 52(2004-AL-095), p. 9-16, 発行日 2004-05-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会