Non-Overlapping LZ77 Factorization and LZ78 Substring Compression Queries with Suffix Trees
| Autor: | Dominik Köppl |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
substring compression query
longest previous non-overlapping factor table application of suffix trees non-overlapping Lempel–Ziv factorization lossless compression Lempel–Ziv-78 factorization Industrial engineering. Management engineering T55.4-60.8 Electronic computers. Computer science QA75.5-76.95 |
| Zdroj: | Algorithms, Vol 14, Iss 2, p 44 (2021) |
| Druh dokumentu: | article |
| ISSN: | 1999-4893 |
| DOI: | 10.3390/a14020044 |
| Popis: | We present algorithms computing the non-overlapping Lempel–Ziv-77 factorization and the longest previous non-overlapping factor table within small space in linear or near-linear time with the help of modern suffix tree representations fitting into limited space. With similar techniques, we show how to answer substring compression queries for the Lempel–Ziv-78 factorization with a possible logarithmic multiplicative slowdown depending on the used suffix tree representation. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|