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

Character distribution in string matching with wildcards and length constraints

作　　者：王海平[1] 郭丹[1] 项泰宁 胡学钢[1] 

机构地区：[1]合肥工业大学计算机与信息学院,合肥230009

出　　处：《计算机应用研究》2016年第2期356-361,共6页Application Research of Computers

基　　金：国家自然科学基金资助项目(61305062);国家自然科学基金-港澳学者合作研究基金资助项目(61229301);博士后面上基金资助项目(2012M511403);安徽省自然科学基金资助项目(1308085QF102)

摘　　要：近年来，字符串匹配问题被不断扩展。其中，具有代表性的是在模式中引入可变长度的通配符，称之为PMWL问题。针对此问题，已有工作分析了在不同的模式特征下，匹配数卵随文本长度增加呈指数级增长。同时考虑文本分布特征和模式特征，建立了期望模型E（Ω）=nDπ（P），其中n为文本长度，D为模式中各通配符跨度的乘积，π（P）为基于字符分布的模式出现概率。实验部分，在人工随机数据和DNA真实数据上验证了E（Ω）的准确性，得到预测误差率分别为1．8％-3．2％和4．7％～7．8％；在不同字符分布中，分析了模式模长和通配符跨度对匹配数n的影响。E（Ω）模型揭示了n的增长趋势不一定呈指数级，而取决于π（P）和D的共同影响，且E（Ω）模型能够在线性时间内得到近似完备解。Recently, with the development of bioinformatics, information retrieval and other fields, string matching problem was extended with different conditions, especially, the introduction of the problem of pattern matching with wildcards and length constraints （ PMWL）. Existing results show that the number of occurrences Ω performed the exponential growth with the size of text T by analyzing the pattern characteristic. Based on both character distribution characteristic and pattern characteris- tic, this paper proposed an expectation model E（Ω） = nDπ（ P）, where n was the length of text T, D was the product of all gap in pattern and π（P） was the character distribution probability of P in T. Experiments demonstrate that the model predic- tion error rate are 1.8% ~ 3.2% and 4.7% ~ 7.8% on artificial random texts and DNA sequences respectively, the influence of text length, pattern length and the length of wildcards on Ω in different character distributions. E（Ω） reveals thatΩ not necessarily performs the exponential growth with the size of T, and E（Ω） can effectively obtain an approximate optimal solu- tion in linear time.

关 键 词：字符分布 串匹配 期望模型 通配符 长度约束 

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]