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

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

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