Name
Abstract | ||
|---|---|---|
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 O((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 O(n + m) time. Both algorithms use O(m) extra working space. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/DCC.2013.22 | DCC |
Keywords | Field | DocType |
extra working space,lz78 encoding,distinct character,run length,corresponding rle,size m,size n,efficient algorithm,length encoding,frequency modulation,compression algorithms,run length encoding,encoding,computational complexity,rle,time complexity | Combinatorics,Working space,Run-length encoding,Theoretical computer science,Truncated binary encoding,Mathematics,Computational complexity theory,Encoding (memory) | Conference |
ISSN | ISBN | Citations |
1068-0314 | 978-1-4673-6037-1 | 6 |
PageRank | References | Authors |
0.46 | 9 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuya Tamakoshi | 1 | 6 | 0.79 |
| Tomohiro I | 2 | 148 | 22.06 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 902 | 79.24 |