Searching BWT compressed text with the Boyer-Moore algorithm and binary search
Searching BWT compressed text with the Boyer-Moore algorithm and binary search
复制标题
使用 Boyer-Moore 算法和二分搜索搜索 BWT 压缩文本
DOI：
10.1109/dcc.2002.999949
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
D. Adjeroh
中科院分区：
文献类型：
--
作者：
T. Bell;M. Powell;A. Mukherjee;D. Adjeroh
本文探讨了在使用Burrows-Wheeler变换压缩的文件中进行在线精确模式匹配的两种技术。我们研究了两种方法。第一个是将Boyer-Moore算法（1977）应用于转换后的字符串。第二种方法是基于这样的观察，即转换有效地包含了原始文本的所有子字符串的排序列表，可以使用二进制搜索的变体来进行非常快速的搜索。对于少量查询，这两种方法都比解压缩和搜索方法快，即使对于大量查询，二进制搜索也要快得多。
This paper explores two techniques for on-line exact pattern matching in files that have been compressed using the Burrows-Wheeler transform. We investigate two approaches. The first is an application of the Boyer-Moore algorithm (1977) to a transformed string. The second approach is based on the observation that the transform effectively contains a sorted list of all substrings of the original text, which can be exploited for very rapid searching using a variant of binary search. Both methods are faster than a decompress-and-search approach for small numbers of queries, and binary search is much faster even for large numbers of queries.