| 字符分布特征对带有通配符串匹配问题的影响 |
| |
| 引用本文： | 王海平,郭丹,项泰宁,胡学钢. 字符分布特征对带有通配符串匹配问题的影响[J]. 计算机应用研究, 2016, 33(2) |
| |
| 作者姓名： | 王海平 郭丹 项泰宁 胡学钢 |
| |
| 作者单位： | 合肥工业大学,合肥工业大学,合肥工业大学,合肥工业大学 |
| |
| 基金项目： | 国家自然科学基金资助项目;港澳学者合作研究基金项目;博士后面上基金项目;安徽省自然科学基金 |
| |
| 摘 要： | 近年来，字符串匹配问题被不断扩展。其中，具有代表性的是在模式中引入可变长度的通配符，本文称之为PMWL问题。针对此问题，已有工作分析了在不同的模式特征下，匹配数Ω随文本长度增加呈指数级增长。本文同时考虑文本分布特征和模式特征，建立了期望模型E(Ω)＝n*D*π(P)，其中n为文本长度，D为模式中各通配符跨度的乘积，π(P)为基于字符分布的模式出现概率。实验部分，在人工随机数据和DNA真实数据上验证了E(Ω)的准确性，得到预测误差率分别为1.8%~3.2%和4.7%~7.8%；在不同字符分布中，分析了模式模长和通配符跨度对匹配数Ω的影响。E(Ω)模型揭示了Ω的增长趋势不一定呈指数级，而取决于π(P)和D的共同影响。此外，E(Ω)模型能够在线性时间内得到近似完备解。
|
| 关 键 词： | 字符分布，串匹配，期望模型，通配符，长度约束 |
| 收稿时间： | 2014-10-17 |
| 修稿时间： | 2015-12-29 |
Character Distribution in Pattern Matching with Wildcards and Length Constraints |
| |
| wang hai-ping,guo dan,xiang tai-ning and hu xue-gang. Character Distribution in Pattern Matching with Wildcards and Length Constraints[J]. Application Research of Computers, 2016, 33(2) |
| |
| Authors: | wang hai-ping guo dan xiang tai-ning hu xue-gang |
| |
| Affiliation: | Hefei University of Technology,,Hefei University of Technology,Hefei University of Technology |
| |
| Abstract: | |
| |
| Keywords: | Character Distributions Pattern Matching Expectation Model Wildcard Length Constraints |
|
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
