基于KMP算法的串口通讯协议解析

通常的串口通讯协议解析过程在帧头判断时需要O(n)的时间复杂度,这对有严格时间限制的一类系统而言十分不利,若能将此过程的时间复杂度降低至Θ(1),则会给后续处理留下宝贵时间。这篇文章在分析串口通讯中上层协议的一般模式后,展示了一种常用的协议解析策略,分析了其优缺点,提出了一种基于K-M-P算法的协议解析策略。该策略具有算法形式上的统一,在不计预处理的前提下,其算法时间复杂度由原来的O(n)降低到Θ(1),效率比原策略有明显的提高。运用此策略,程序的控制结构可以被简化,从而使在解析串口通讯协议时,程序逻辑清晰,正确性容易得到验证。