Bidirectional Wavelet Index Representation using Wavelet Matrix

A wavelet tree is a data structure that enables the encoding of symbol sequences across an alphabet Σ of size σ. It recursively divides a string into two parts until uniformity is achieved. The spatial efficacy of the wavelet tree is influenced by an increase in the value of σ. The pointer-less wavelet tree was developed to decrease the spatial requirements of the wavelet tree; however, its practical performance is inadequate and its theoretical complexity remains constant. The wavelet matrix is an alternative method that concatenates the bitmaps hierarchically while preserving all the characteristics of the wavelet tree. Nevertheless, it operates significantly more efficiently in practice. This investigation introduces a wavelet matrix methodology for the recovery of the bidirectional wavelet index. The modification is effective, as demonstrated by our experiment, which demonstrates that the bidirectional wavelet index, which is generated using the wavelet matrix, reduces the time required to search through queries.