DocumentCode
2477942
Title
Pattern matching in BWT-transformed text
Author
Adjeroh, Don ; Mukherjee, Amar ; Bell, Tim ; Powell, Matt ; Zhang, Nan
Author_Institution
Dept. of Comput. Sci. & Electr. Eng., West Virginia Univ., Morgantown, WV, USA
fYear
2002
fDate
2002
Firstpage
445
Abstract
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.
Keywords
data compression; string matching; text analysis; wavelet transforms; BWT-transformed text; compressed pattern matching problem; compressed representation; inverse transformation process; lexically similar contexts; lexicographic ordering; minimal decompression; permutation; text string; wavelet transform; Computer science; Costs; Decoding; Filtering algorithms; Matched filters; Pattern matching; Performance evaluation; Phased arrays; Testing; USA Councils;
fLanguage
English
Publisher
ieee
Conference_Titel
Data Compression Conference, 2002. Proceedings. DCC 2002
ISSN
1068-0314
Print_ISBN
0-7695-1477-4
Type
conf
DOI
10.1109/DCC.2002.999988
Filename
999988
Link To Document