An FPGA Architecture for Text Search Using a Wavelet-Tree-Based Succinct-Data-Structure

摘要

Succinct data structures are introduced to efficiently solve a given problem while representing the data using as little space as possible. The full potential of the succinct data structures have not been utilized in the software-based implementations. This paper discusses an FPGA-based hardware architecture for text search that uses succinct data structures. We proposes a hardware-oriented data structure and its decoding method. The proposed architecture can be used in text searches using up to 4.3GB large text files.