Research Project: Full-text search on multi-byte encoded documents

The Burrows Wheeler transform (BWT) has become popular in text compression, full-text search, XML representation, and DNA sequence matching. It is efficient to perform a full-text search on BWT encoded text using the BWT backward search concept. This paper aims to study different approaches for applying BWT on multi-byte encoded (e.g. UTF16) text documents. While previous work has studied BWT on word-based models, and BWT can be applied directly on multi-byte encodings (by treating the document as single-byte coded), there has been no extensive study on how to utilize BWT on multi-byte encoded documents for efficient full-text search. In addition, we are also interested in the side effects of these approaches, in terms of the impact on compression ratios when standard compression techniques are applied on top of BWT encoded documents. We demonstrate our findings using Chinese text documents. Our experiment results show that our extensions to the standard BWT method offer better compression ratios and/or faster search performance.

Author: Raymond K. Wong, Fengming Shi, Nicole Lam

Date: April, 2012

Report: PDF

Project source code: Download the zip file