一种全文索引的压缩方法  

A Compressed Suffix Automaton for Full Text Indexing

作　　者：杨炜鸿[1,2] 张猛[1] 

机构地区：[1]吉林大学计算机科学与技术学院,吉林长春130012 [2]吉林工商学院信息工程分院,吉林长春130062

出　　处：《情报科学》2010年第11期1710-1713,共4页Information Science

基　　金：国家自然科学基金项目(60873235);教育部中央高校基本科研业务费(200903186);吉林省科技厅自然基金项目(20101522);吉林省教育厅项目(2009599;2010400)

摘　　要：全文索引广泛应用于数据库、数据压缩、模式匹配算法以及信息生物学等领域。本文研究了后缀自动机全文索引结构,针对后缀自动机空间占用大的问题提出了一种边压缩方法。该方法通过后缀链接函数模拟实现自动机的跳转边,从而删除部分跳转边。在最终的压缩结构中,跳转边的数量与状态数量一致,而在后缀自动机中跳转边的数量是状态数量的一倍。证明了对于因子判定等问题,压缩的后缀自动机与后缀自动机具有相同的时间复杂度。Full text indexes are widely used in areas such as data base,data compression,pattern matching and bioinformatics.We present in this paper a compression method for suffix automata.By deleting some transaction edges,the suffix automata can still work like the original suffix automata without losing performance.The compressed suffix automata have edges with the number similar with that of states while in the original ones the number of edges is twice of that of states.We also proved that using the compressed suffix automata the membership problem for the factor set of a given word can be solved linear time.

关 键 词：文本索引 后缀自动机 压缩 

分 类 号：G350[文化科学—情报学]