论文研究 字符分布特征对带有通配符串匹配问题的影响.pdf

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