为了提高检索效率,大概有两种思路:
对文本做预处理,比如:BWT
对字符串做预处理,比如:KMP、Boyer-Moore
BWT
[IR] BWT+MTF+AC 中已经介绍了BWT (Burrows–Wheeler_transform)数据转换算法,
这种变换方式不仅方便压缩,同时对pattern search也带来了意想不到的好处。
事实上,BWT形式的数据,可以仅还原局部数据,而非必须还原完整的文件。
这个完整的搜索过程叫做:FM-index,包括三部分,①BWT(T),②checkpoint data,③一个简化了的SA[]数组。