Fast Pattern Matching in Compressed Text using Wavelet Tree
Surya Prakash Mishra, Rajesh Prasad, Gurmit Singh · IETE Journal of Research · 2017
With the recent increase in the size of data, compression has become essential tool for handling massive data. Compression is usually more helpful in handling huge data over the networks, large text collections, and storing massive biological data. It is also useful in searching a pattern (of any kind) inside the huge data set. Compressed pattern matching (CPM) is the task of performing string matching in a compressed text without decompressing it. In this type of matching, pattern may or may not be compressed. This paper presents an efficient algorithm (WBTC_WT) for matching a pattern directly inside the compressed text. The proposed algorithm uses the tagged sub optimal code category of algorithm called word-based tagged code (WBTC) and a self-indexed data structure called wavelet tree. WBTC is used for encoding the text and wavelet tree provides fast searching over the compressed text. WBTC_WT removes the problem of false matches, encountered in some of the previous approaches and is able to match arbitrary portion of text without decompressing it. The proposed algorithm is implemented, analyzed, and compared with existing approaches on huge data set. From the simulation results, it is found that our algorithm outperforms the existing algorithms in most of the cases.