Pattern matching in BWT-transformed text
Donald Adjeroh, Amar Mukherjee, Tim Bell, M. Powell, N. Zhang · 2003
Summary form only given. The compressed pattern matching problem is to locate the occurrence(s) of a pattern P in a text string T using a compressed representation of T, with minimal (or no) decompression. The BWT performs a permutation of the characters in the text, such that characters in lexically similar contexts will be near to each other. The motivation for our approach is the observation that the BWT provides a lexicographic ordering of the input text as part of its inverse transformation process.