计算机应用 ›› 2012, Vol. 32 ›› Issue (11): 3082-3088.DOI: 10.3724/SP.J.1087.2012.03082

• 计算机软件 • 上一篇    下一篇

Sunday算法效率分析

潘冠桦,张兴忠   

  1. 太原理工大学 计算机科学与技术学院,太原 030024
  • 收稿日期:2012-05-03 修回日期:2012-06-22 发布日期:2012-11-12 出版日期:2012-11-01
  • 通讯作者: 潘冠桦
  • 作者简介:潘冠桦(1987-),男,山西运城人,硕士,主要研究方向:嵌入式系统、字符串匹配;张兴忠(1964-),男,山西汾阳人,副教授,主要研究方向:嵌入式系统、软件工程。

Study on efficiency of Sunday algorithm

PAN Guan-hua,ZHANG Xing-zhong   

  1. College of Computer Science and Technology, Taiyuan university of Technology, Taiyuan Shanxi 030024, China
  • Received:2012-05-03 Revised:2012-06-22 Online:2012-11-12 Published:2012-11-01
  • Contact: PAN Guan-hua

摘要: 针对Sunday算法的过程比较复杂,难以构建马尔可夫链的问题,提出一种新的根据算法的匹配次数差求平均效率的方法。首先选定初等算法作为效率分析的基准算法,使用马尔可夫链得出初等算法比较精确的平均效率估计公式;然后根据相应的概率公式计算出初等算法和Sunday算法匹配过程的差值;将两者结合,得出Sunday算法平均效率估计公式。实验结果表明,由此公式计算的估计值可以代表实际匹配次数的平均值。

关键词: Sunday算法, 算法效率, 马尔可夫链, 初等算法, 平均匹配次数

Abstract: Given the characteristic that the Sunday algorithm is too complex to construct Markov chains, a new method according to the difference of matching number in the algorithms was proposed to compute the average efficiency. Firstly, the naive algorithm was chosen as the foundation, and its accurate average efficiency was computed by Markov chains. Secondly, the difference of the two algorithms was computed by the corresponding knowledge in probability theory. The two results were combined to get the equation which represented the average efficiency of Sunday algorithm. The experimental results show that the estimated value computed by the equation is the average number of the matching times.

Key words: Sunday algorithm, algorithm efficiency, Markov chain, naive algorithm, average matching number

中图分类号: