Block Trees
| dc.contributor.author | Belazzougui, Djamal | |
| dc.contributor.author | Cáceres, Manuel | |
| dc.contributor.author | Gagie, Travis | |
| dc.contributor.author | Gawrychowski, Paweł | |
| dc.contributor.author | Kärkkäinen, Juha | |
| dc.contributor.author | Navarro, Gonzalo | |
| dc.contributor.author | Ordóñez, Alberto | |
| dc.contributor.author | Puglisi, Simon J. | |
| dc.contributor.author | Tabei, Yasuo | |
| dc.date.accessioned | 2023-10-31T14:48:13Z | |
| dc.date.available | 2023-10-31T14:48:13Z | |
| dc.date.issued | 2021-05 | |
| dc.description.abstract | Let string S[1..n] be parsed into z phrases by the Lempel-Ziv algorithm. The corresponding compression algorithm encodes S in 𝒪(z) space, but it does not support random access to S. We introduce a data structure, the block tree, that represents S in 𝒪(z log(n/z)) space and extracts any symbol of T in time 𝒪(log(n/z)), among other space-time tradeoffs. By multiplying the space by the alphabet size, we also support rank and select queries, which are useful for building compressed data structures on top of S. Further, block trees can be built in a scalable manner. Our experiments show that block trees offer relevant space-time tradeoffs compared to other compressed string representations for highly repetitive strings. | |
| dc.identifier.issn | 0022-0000 | |
| dc.identifier.uri | https://dl.cerist.dz/handle/CERIST/996 | |
| dc.publisher | ELSEVIER | |
| dc.relation.ispartofseries | Journal of Computer and System Sciences; 117 | |
| dc.relation.pages | 1-22 | |
| dc.structure | CAlcul Parallèle et Applications | |
| dc.subject | Compressed data structures | |
| dc.subject | Repetitive string collections | |
| dc.subject | Lempel-Ziv compression | |
| dc.title | Block Trees | |
| dc.type | Article |