字符分布特征对带有通配符串匹配问题的影响

• 作者: 王海平 胡学钢 郭丹 项泰宁
• 来源期刊: 计算机应用研究
• 关键词: 字符分布 串匹配 期望模型 通配符 长度约束
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 356-361
• 页数: 6页
• 分类号: TP391.1
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2016.02.008

摘要

近年来,字符串匹配问题被不断扩展.其中,具有代表性的是在模式中引入可变长度的通配符,称之为PMWL问题.针对此问题,已有工作分析了在不同的模式特征下,匹配数Ω随文本长度增加呈指数级增长.同时考虑文本分布特征和模式特征,建立了期望模型E(Ω)=nDπ(P),其中n为文本长度,D为模式中各通配符跨度的乘积,π(P)为基于字符分布的模式出现概率.实验部分,在人工随机数据和DNA真实数据上验证了E(Ω)的准确性,得到预测误差率分别为1.8％ ～3.2％和4.7％～7.8％;在不同字符分布中,分析了模式模长和通配符跨度对匹配数Ω的影响.E(Ω)模型揭示了Ω的增长趋势不一定呈指数级,而取决于π(P)和D的共同影响,且E(Ω)模型能够在线性时间内得到近似完备解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡学钢	合肥工业大学计算机与信息学院	314	3156	27.0	39.0
2	王海平	合肥工业大学计算机与信息学院	9	43	4.0	6.0
3	郭丹	合肥工业大学计算机与信息学院	20	113	6.0	10.0
4	项泰宁	合肥工业大学计算机与信息学院	2	4	1.0	2.0