TY - GEN
T1 - From run length encoding to LZ78 and back again
AU - Tamakoshi, Yuya
AU - I, Tomohiro
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
PY - 2013
Y1 - 2013
N2 - In this paper, we present efficient algorithms for interconversion between Lempel-Ziv 78 (LZ78) encoding and run length encoding (RLE). We show how, given an RLE of size n for a string S, we can compute the corresponding LZ78 encoding of size m for S in Ο((n + m) log σ) time, where σ is the number of distinct characters appearing in S. We also show how, given an LZ78 encoding of size m for a string S, we can compute the corresponding RLE of size n in Ο(n + m) time. Both algorithms use Ο(m) extra working space.
AB - In this paper, we present efficient algorithms for interconversion between Lempel-Ziv 78 (LZ78) encoding and run length encoding (RLE). We show how, given an RLE of size n for a string S, we can compute the corresponding LZ78 encoding of size m for S in Ο((n + m) log σ) time, where σ is the number of distinct characters appearing in S. We also show how, given an LZ78 encoding of size m for a string S, we can compute the corresponding RLE of size n in Ο(n + m) time. Both algorithms use Ο(m) extra working space.
UR - https://www.scopus.com/pages/publications/84881059248
UR - https://www.scopus.com/pages/publications/84881059248#tab=citedBy
U2 - 10.1109/DCC.2013.22
DO - 10.1109/DCC.2013.22
M3 - Conference contribution
AN - SCOPUS:84881059248
SN - 9780769549651
T3 - Data Compression Conference Proceedings
SP - 143
EP - 152
BT - Proceedings - DCC 2013
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2013 Data Compression Conference, DCC 2013
Y2 - 20 March 2013 through 22 March 2013
ER -