Fast and Efficient Text Searching in Compressed Data Using Burrows–Wheeler Transform
Sanjeev Kumar, Mukund Pratap Singh · 2023
There is an exponential growth in the amount of digitally available data. The volumes of new material published on the Internet between 2010 and 2020 are higher than those produced throughout human history. A large part of these data is made up of text, which includes a series of symbols representing text, code, audio, images, visual images, time series and biological patterns. With the recent growth of data volume, compression has now become a crucial tool for dealing with large amounts of data. To minimize the storage, processing and transmission cost of these data, some data compression techniques are used. For searching the text over these compressed data, full decompression is required which takes so much time. So, a specialized data compression techniqueis required to store these data efficiently, which also allows searching text directly on compressed data without full decompression. In this chapter a new approach Succinct Burrows–Wheeler transform (S-BWT) is proposed for efficient storage and searching of text data based on Burrows–Wheeler transform (BWT). BWT is a new data structure library that compresses the data very efficiently also allows searching the text over compressed data directly without decompression. From experiments, it is confirmed that proposed approach outperform w.r.t. other state-of-the art approaches for fast and efficient searching in compressed data.