论文部分内容阅读
随着大数据时代来临,人们越来越多地利用海量数据中所蕴含的信息来解决各种问题。由于数据量的巨大,信息处理会遇到很多困难,比如数据的存储,查询,信息的提取等等。本文研究了数据处理中的一个重要问题——压缩文本的搜索。主要目标是改进现有模式匹配算法,使其能够直接在LZ系列算法压缩的文本上进行搜索,省去了解压的过程。本文的研究针对当前最为流行的无损压缩方案:LZ78算法和LZW算法。由于这些压缩方案的存储形式类似,都是由一个明确的未压缩的字符和一个向前查找的索引构成,这使其可由某些基于后缀匹配的搜索算法直接处理,这样的结构可以不需要把文本完全解压就能够对压缩形式的字符串进行读取。根据这些特征,本文对一些模式匹配算法进行了改进,使它们能够直接在压缩文本上进行搜索。本文改进了利用BM算法直接在LZ系列压缩文本上进行搜索的方案,主要是使用由BM算法衍生出的的Sunday算法和Horspool算法。这些算法在匹配过程中,尽可能大距离地移动匹配窗口,忽略一些文本字符,从而加快匹配速度。针对LZ系列压缩文本的存储形式,摒弃BM算法的好后缀规则,简化算法执行过程。同时在LZ系列压缩文本上的字符尽管能够直接读取,但是由于存储方式不同,在读取的效率上也有所区别。因此在两个个算法的匹配顺序上针对匹配窗口内的压缩字符的不同存储形式进行调整。对Horspool算法的改进都因为匹配顺序的不同提出了两种不同的方案:Horspool-I和Horspool-II。而在Sunday算法中,用来和模式串进行匹配查找计算匹配窗口移动距离的标志字符处于匹配窗口外,所以Sunday算法的匹配顺序没有更多的选择,只有一种方案。另外,本文针对LZW算法的压缩过程进行了改进,构建一个新的查询数组。并利用查询数组的特性提出了新的搜索方案。直接在压缩文本中查找符合模式串前缀的字符串,直接在压缩文本上查找这些满足条件的索引。简化搜索过程,完全不需要进行解压过程。对于几种方案本文进行了效率分析。搜索算法的执行效率常常受限于实验文本的随机性不能充分证明。本文选取了不同领域的文本文件,同时使用长度依次递增的模式串在文本上进行查找。根据算法执行时间的长短来判断算法性能优劣。本文通过实验将三个改进的算法与先解压再搜索的方法进行了对比,结果表明新方法在执行速度上有较大优势。同时由于这种直接搜索的方法不需要对文件进行解压,也节省了大量的存储空间,便于传输和储存。而三个改进的搜索算法也各有特点。改进的Horspool算法一般情况下都能保证较高的效率,执行时间明显小于传统方法。而改进的Sunday算法并不善于处理模式串长度较短的匹配问题,但在处理长模式串的时候会获得很好的效果。利用查询数组的搜索方案针对重复率不高的文本有很好的效果。