壓縮后綴數組構造算法的改進.pdf

1、給定一個有窮字符集∑，假設S是由∑中的n個字符組成的文本串，P則是由∑中的m個字符組成的模式串。模式匹配就是查找模式串P在文本串S中符合特定條件的所有出現。在巨大數據集的模式匹配問題中，采用索引機制可以有效地提高匹配速度。在建立索引的過程中，要考慮查找速度和空間開銷的平衡，既要保證較高的查找速度又要有合理的空間開銷。 后綴數組作為一種常用的文本索引機制，因其簡單的結構和較好的空間效率，已成為模式匹配算法的基礎數據結構。但是，它也

2、有著文本索引機制共有的缺陷：實現快速查詢的算法仍使用了較多的空問。為了解決這一問題，Grossi和Vitter對后綴數組進行壓縮，在實現O(m／log∣∑∣n+log∣∑∣εn)的查找時間的同時，最多只需要(ε-1+O(1))nlog∣∑∣位的存儲空間。其中ε為任意常數，且0<ε≤1。 本文提出了一種新的構造壓縮后綴數組的方法：對原文本串s每logn位一組進行劃分，每組只保存一個絕對地址，把后綴數組的存儲空間降為O(n)位。同時