Improving Parse Trees for Efficient Variable-to-Fixed Length Codes

• Item type: Journal(1)
• 公開日: 2011-12-15
• タイトル: Improving Parse Trees for Efficient Variable-to-Fixed Length Codes
• タイトル / 言語: en
• タイトル: Improving Parse Trees for Efficient Variable-to-Fixed Length Codes
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：情報爆発時代におけるIT基盤技術
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Hokkaido University
• 著者所属: Hokkaido University／Presently with Yahoo Japan Corporation
• 著者所属: Hokkaido University
• 著者所属: Fujitsu Laboratories Ltd.
• 著者所属: Fujitsu Laboratories Ltd.
• 著者所属(英): en
• 著者所属(英): Hokkaido University
• 著者所属(英): en
• 著者所属(英): Hokkaido University / Presently with Yahoo Japan Corporation
• 著者所属(英): en
• 著者所属(英): Hokkaido University
• 著者所属(英): en
• 著者所属(英): Fujitsu Laboratories Ltd.
• 著者所属(英): en
• 著者所属(英): Fujitsu Laboratories Ltd.
• 著者名: Satoshi, Yoshida; Takashi, Uemura; Takuya, Kida; Tatsuya, Asai; Seishi, Okamoto
• 著者名(英): Satoshi, Yoshida; Takashi, Uemura; Takuya, Kida; Tatsuya, Asai; Seishi, Okamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We address the problem of improving variable-length-to-fixed-length codes (VF codes). A VF code that we deal here with is an encoding scheme that parses an input text into variable length substrings and then assigns a fixed length codeword to each parsed substring. VF codes have favourable properties for fast decoding and fast compressed pattern matching, but they are worse in compression ratio than the latest compression methods. The compression ratio of a VF code depends on the parse tree used as a dictionary. To gain a better compression ratio we present several improvement methods for constructing parse trees. All of them are heuristical solutions since it is intractable to construct the optimal parse tree. We compared our methods with the previous VF codes, and showed experimentally that their compression ratios reach to the level of state-of-the-art compression methods.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.20(2012) No.1 (online); DOI http://dx.doi.org/10.2197/ipsjjip.20.238; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We address the problem of improving variable-length-to-fixed-length codes (VF codes). A VF code that we deal here with is an encoding scheme that parses an input text into variable length substrings and then assigns a fixed length codeword to each parsed substring. VF codes have favourable properties for fast decoding and fast compressed pattern matching, but they are worse in compression ratio than the latest compression methods. The compression ratio of a VF code depends on the parse tree used as a dictionary. To gain a better compression ratio we present several improvement methods for constructing parse trees. All of them are heuristical solutions since it is intractable to construct the optimal parse tree. We compared our methods with the previous VF codes, and showed experimentally that their compression ratios reach to the level of state-of-the-art compression methods.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.20(2012) No.1 (online); DOI http://dx.doi.org/10.2197/ipsjjip.20.238; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 52, 号 12, 発行日 2011-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764