壓縮后綴數(shù)組構(gòu)造算法的改進.pdf

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

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