为了提高检索效率,大概有两种思路:

  • 对文本做预处理,比如:BWT

  • 对字符串做预处理,比如:KMP、Boyer-Moore


 

BWT

[IR] BWT+MTF+AC 中已经介绍了BWT (Burrows–Wheeler_transform)数据转换算法,

这种变换方式不仅方便压缩,同时对pattern search也带来了意想不到的好处。

 

事实上,BWT形式的数据,可以仅还原局部数据,而非必须还原完整的文件。

这个完整的搜索过程叫做:FM-index,包括三部分,①BWT(T),②checkpoint data,③一个简化了的SA[]数组。

网友评论