文献

J-GLOBAL ID：201602207890354220   整理番号：16A0216037

部分文字列数え上げによる圧縮の効率的実現と実験的評価

Efficient Implementation and Empirical Evaluation of Compression by Substring Enumeration

著者 (4件)： KANAI Sho (Graduate School of Sci. and Technol., Gunma Univ.) ,  YOKOO Hidetoshi (Graduate School of Sci. and Technol., Gunma Univ.) ,  YAMAZAKI Kosumo (Graduate School of Sci. and Technol., Gunma Univ.) ,  KANEYASU Hideaki (Graduate School of Sci. and Technol., Gunma Univ.)
資料名： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web)  (IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web))
巻： E99.A  号： 2  ページ： 601-611 (J-STAGE)  発行年： 2016年 
JST資料番号： U0466A  ISSN： 1745-1337  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文は,部分文字列数え上げによる圧縮(CSE)として知られる無損失データ圧縮アルゴリズムに対する,アレイ利用実用的符号器を与える。この符号器は,CSEとBurrows-Wheeler変換の間の関係を利用する。また復号化アルゴリズムも修正し,提案した符号器を扱えるようにする。提案した符号器と復号器のお陰で,CSEを数十メガバイト以上の長いデータに適用できる。このような長いデータについて実験を行った際に得た,圧縮結果を示す。この結果は,CSEに関する理論的予測の妥当性を実験的に示す。(翻訳著者抄録)

シソーラス用語： *データ圧縮 ,  マッチング ,  *符号器 ,  復号器 ,  *データ ,  実験 ,  並列演算 ,  高速アルゴリズム ,  漸近挙動 ,  データ変換 ,  数学的変換 ,  部分集合 ,  符号
準シソーラス用語： *無損失圧縮 ,  文字列マッチング ,  *大規模データ ,  評価実験 ,  アレイ処理 ,  漸近最適性 ,  *可逆圧縮 ,  ユニバーサル符号

分類 (1件)： 符号理論  (ND02030R)

引用文献 (21件)：

• [1] M.I. Abouelhoda, S. Kurtz, and E. Ohlebusch, “The enhanced suffix array and its applications to genome analysis,” Algorithms in Bioinformatics, Lecture Notes in Computer Science, vol.2452, pp.449-463, Springer Berlin Heidelberg, Berlin, Heidelberg, 2002.
• [2] T. Asano, S. Bereg, and D. Kirkpatrick, “Finding nearest larger neighbors,” Efficient Algorithms, Lecture Notes in Computer Science, vol.5760, pp.249-260, Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.
• [3] M. Béliveau and D. Dubé, “Improving compression via substring enumeration by explicit phase awareness,” Proc. 2014 Data Compression Conference, p.399, 2014.
• [4] T. Beller, S. Gog, E. Ohlebusch, and T. Schnattinger, “Computing the longest common prefix array based on the Burrows-Wheeler transform,” J. Discrete Algorithms, vol.18, pp.22-31, 2013.
• [5] M. Burrows and D.J. Wheeler, “A block-sorting lossless data compression algorithm,” SRC Research Report, 124, 1994.

タイトルに関連する用語 (3件)： 文字列 ,  実験 ,  評価