最大频长积字符串及其高效查找算法

• 作者: 严铭清 胡运发 陶晓鹏
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 频长积 最大频长积字符串 广义后缀树 Ukkonen算法
• 年，卷（期）: 2008,（11）
• 所属期刊栏目: 基金项目论文
• 页码范围: 3-5,22
• 页数: 4页
• 分类号: TP3
• 字数: 4627字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2008.11.002

摘要

在传统的字符串处理算法中往往分别考虑字符串的频度和长度.然而,在实际应用中,将字符串的频度和长度结合考虑是有意义的.基于这点我们提出了频长积的概念,规定字符串的频度和长度的乘积为字符串的频长积.并基于广义后缀树和Ukkonen算法,提出了时间复杂度为O(N)的查找算法.效率实验证实了该算法的高效性.语义实验表明,本算法找出的最大频长积字符串相比于最大频度字符串或最大长度字符串,其实际语义更为明确.这样的字符串在文本压缩、基因序列的分析以及其他注重语义的应用中将具有很高的应用价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡运发	复旦大学计算机与信息技术系	150	3430	27.0	54.0
2	陶晓鹏	复旦大学计算机与信息技术系	19	564	7.0	19.0
3	严铭清	复旦大学计算机与信息技术系	1	2	1.0	1.0