一种全文索引的压缩方法

《一种全文索引的压缩方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第202108卷年第1111月期情报科学Vo1．28，No．1INovember。2010一种全文索引的压缩方法杨炜鸿，张猛(1．吉林大学计算机科学与技术学院，吉林长春l30012；2．吉林工商学院信息工程分院，吉林长春130062)摘要：全文索引广泛应用于数据库、数据压缩、模式匹配算法以及信息生物学等领域。本文研究了后缀自动机全文索引结构。针对后缀自动机空间占用大的问题提出了一种边压缩方法。该方法通过后缀链接函数模拟实现自动机的跳转边，从而删除部分跳转边。在最终的压缩结构中，跳转边的数量与状态数量一致，而在后缀自动机中跳转边的数量是状态数量的一倍。证明了

2、对于因子判定等问题，压缩的后缀自动机与后缀自动机具有相同的时间复杂度。关键词：文本索引；后缀自动机；压缩中图分类号：G350文献标识码：A文章编号：10o7—7634(2010)l1一l710一o4ACompressedSuffixAutomatonforFullTextIndexingYANGWei-hongLZHANGMeng(1．CollegeofComputerScienceandTechnology,JilinUniversi~．"，Changchun130012，China；2．BranchSchoolofInformationEngineer

3、ing，JilinBusinessandTechnologyCollege，Changchun130012，China)Abstract：Fulltextindexesarewidelyusedinareassuchasdatabase，datacompression，patternmatchingandbioinformatics．Wepresentinthispaperacompressionmethodforsuffixautomata．Bydeletingsometransactionedges，thesuffixautomatacanstillw

4、orkliketheoriginalsuffixautomatawithoutlosingperformance．Thecompressedsuffixautomatahaveedgeswiththenumbersimilarwiththatofstateswhileintheoriginalonesthenumberofedgesistwiceofthatofstates．Wealsoprovedthatusingthecompressedsuffixautomatathemembershipproblemforthefactorsetofagivenw

5、ordcanbesolvedlineartime．Keywords：fulltextindex；sufixautomaton；compression，效地实现全文索引的主要功能，如高效地判定一个1背景指定模式是否出现在一个文本中，给出模式在文本中出现的次数以及枚举模式在文本中所有的出现位全文索引广泛地应用于数据库、数据压缩、模式置【51。后缀自动机是一种多功能数据结构，它是最小匹配算法以及信息生物学等领域。近年来研究者提的能够识别一个串全部后缀的有限状态自动机【6】。出了多种全文索引结构，包括后缀树[1-31-．后缀自动后缀自动机具有线性的空间复杂，而且存

6、在在线线机】、后缀数组[71及压缩索引[8qo]等。这些结构可高性构造算法。后缀自动机在模式匹配算法应用广泛，收稿日期：2010—08—19基金项目：国家自然科学基金项目(60873235)；教育部中央高校基本科研业务费(200903186)；吉林省科技厅自然基金项目(20101522)；吉林省教育厅项目(2009599、2010400)作者简介：杨炜鸿(1974一)女，吉林长春人，硕士，讲师，主要从事计算机网络研究；张猛，本文通信作者(1974一)，男，吉林长春人，博士，副教授，主要从事网络安全、分布式计算研究．1l期一种全文索引的压缩方法171l许多高

7、性能算法均采用后缀自动机及其变体IH-16]作[f)】。由于depth(q，)

8、简化各种基于后缀自动机算法的描述。占用。对于删除的部分跳转边，可通