一种全文索引的压缩方法

分享到

【作者】杨炜鸿，张猛
【作者单位】吉林大学计算机科学与技术学院；吉林工商学院信息工程分院
【年份】2010
【卷号】第11期
【页码】1710-1713
【ISSN】1007-7634
【关键词】文本索引后缀自动机压缩
【摘要】全文索引广泛应用于数据库、数据压缩、模式匹配算法以及信息生物学等领域。本文研究了后缀自动机全文索引结构,针对后缀自动机空间占用大的问题提出了一种边压缩方法。该方法通过后缀链接函数模拟实现自动机的跳转边,从而删除部分跳转边。在最终的压缩结构中,跳转边的数量与状态数量一致,而在后缀自动机中跳转边的数量是状态数量的一倍。证明了对于因子判定等问题,压缩的后缀自动机与后缀自动机具有相同的时间复杂度。
【基金】国家自然科学基金;吉林省教育厅项目
【文献类型】期刊