高速かつ省領域な線形時間LZ分解アルゴリズム

スポンサーリンク

概要

• 論文の詳細を見る

• We present a new algorithm for computing the Lempel-Ziv Factorization (LZ77) of a given string of length N in linear time, that utilizes only N log N + O(1) bits of working space, i.e., a single integer array, for constant size integer alphabets. This greatly improves the previous best space requirement for linear time LZ77 factorization (Karkkainen et al. CPM 2013), which requires two integer arrays of length N. Computational experiments show that despite the added complexity of the algorithm, the speed of the algorithm is only around twice as slow as previous fastest linear time algorithms.

• 2013-10-30

著者

• Hideo Bannai

  Department Of Informatics Kyushu University

• Keisuke Goto

  Department of Informatics

• Keisuke Goto

  Department of Informatics, Kyushu University|Japan Society for the Promotion of Science (JSPS)

• Keisuke Goto

  Department of Electrical and Electronic Engineering, Faculty of Engineering, Muroran Institute of Technology, 27-1 Mizumoto, Muroran, Hokkaido 050-8585, Japan

関連論文

• Variable Length Don't-Care Pattern Matching Problems on Compressed Texts
• 圧縮テキスト上でのq-gram非重複頻度の効率的な計算とその応用
• 高速かつ省領域な線形時間LZ分解アルゴリズム

スポンサーリンク