【摘要】 本文提出一种改进的QS算法IQS。基于CPU进行一次字节长度的字符比较和进行一次机器字长长度的整数比较所花费的时间完全相同的事实,以及QS算法对当前尝试中比较顺序和匹配失败位置不关心的特点,IQS将字符比较映射到整数域进行。由于比较次数被成倍减少,算法的平均复杂度被降低,效率相应得到提高。在真实语料上的实验结果表明,IQS算法的匹配速度明显高于QS算法。更多还原

【Abstract】 This paper suggests an Improved Quick Search(IQS) algorithm for string matching.Because CPU spends same time on a comparison between two characters whose length is 8 bits as between two integers whose length equal to machine word length.And because QS algorithm doesn’t care about the position of mismatch at each attempt,IQS algorithm carries out the comparisons in the integer field rather than one character by one character.Since the comparisons are reduced manifold,the average complexity of algorithm decreases and the efficiency of algorithm increases correspondingly.Tests on an actual corpus show that IQS algorithm is more efficient than QS algorithm.更多还原