Fast Insertion and Deletion in Compressed Texts
Stefan Böttcher, Alexander Bültmann, Rita Hartel, Jonathan Schlüßler · 2012
Text compression techniques like bzip2 lack the possibility to delete the nth word or to insert text be-fore the nth word of compressed texts without prior decompression of the compressed texts. We present a text compression technique that supports fast insertion into and deletion from compressed texts without full decompression of the compressed text. Our approach combines Indexed Reversible Transformation (IRT) [1], Run-Length-Encoding (RLE), and the Wavelet Tree (WT). For a reasona-ble size of inserted or deleted texts (more details are given in [2]), our approach is faster than modifying uncompressed text preceded by a decompression step and followed by a compression step.