Y. Shibata, M. Takeda. A. Shinohara, and S. Arikawa, Pattern Matching in Text Compressed by Using Antidictionaries. Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science.
Decompression is very fast and requires small work space.
Moreover, it is easy to decompress an arbitrary part of the original text. However, it has not been so popular since the compression is rather slow and the compression ratio is not as good as other methods such as Lempel-Ziv type compression. In this paper, we bring out a potential advantage of BPE compression. We show that it is very suitable from a practical view point of compressed pattern matching , where the goal is to find a pattern directly in compressed text without decompressing it explicitly. Experimental results show that pattern matching in BPE compressed text is even faster than matching in the original text.