欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
全文索引广泛应用于数据库、数据压缩、模式匹配算法以及信息生物学等领域。本文研究了后缀自动机全文索引结构,针对后缀自动机空间占用大的问题提出了一种边压缩方法。该方法通过后缀链接函数模拟实现自动机的跳转边,从而删除部分跳转边。在最终的压缩结构中,跳转边的数量与状态数量一致,而在后缀自动机中跳转边的数量是状态数量的一倍。证明了对于因子判定等问题,压缩的后缀自动机与后缀自动机具有相同的时间复杂度。
英文摘要：
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.
同期刊论文项目
同项目期刊论文
期刊信息
位置：