Efficient Implementation and Empirical Evaluation of Compression by Substring Enumeration

• KANAI Sho

  Graduate School of Science and Technology, Gunma University

• YOKOO Hidetoshi

  Graduate School of Science and Technology, Gunma University

• YAMAZAKI Kosumo

  Graduate School of Science and Technology, Gunma University

• KANEYASU Hideaki

  Graduate School of Science and Technology, Gunma University

抄録

This paper gives an array-based practical encoder for the lossless data compression algorithm known as Compression by Substring Enumeration (CSE). The encoder makes use of the relation between CSE and the Burrows-Wheeler transform. We also modify the decoding algorithm to accommodate to the proposed encoder. Thanks to the proposed encoder and decoder, we can apply CSE to long data of more than tens of megabytes. We show compression results obtained when we perform experiments on such long data. The results empirically validate theoretical predictions on CSE.

収録刊行物

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E99.A (2), 601-611, 2016

  一般社団法人 電子情報通信学会

キーワード

• BWT
• CSE
• data compression
• lossless
• universal code

詳細情報

• CRID: 1390282681287732992
• NII論文ID: 130005121512
• DOI: 10.1587/transfun.e99.a.601
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E99.A/2/E99.A_601/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可