文件名称：论文研究-改进的AAC多模式实时匹配算法.pdf
文件大小：572KB
文件格式：PDF
更新时间：2022-10-01 10:58:58
论文研究
AAC算法（Advanced AC）是使用最为广泛的多模式串匹配算法，匹配性能高，匹配时间稳定。针对AAC算法为判定转移目标状态是否为终结状态，在匹配时每读入一个字符都要访问output表，代价较高的问题，通过两种方法改进了AAC算法。第一种方法为拷贝自动机中的终结状态，将其附加在AAC自动机后，并将原自动机中指向终结状态的转移目标修改为附加状态，直接根据转移目标位置判断当前状态是否是终结状态，从而提出Advanced AC with Additive state（AACA）算法。第二种改进方法为将自动机中指向终结状态的状态转移值置为负数，根据转移目标的值直接判断目标状态是否为终结状态，从而提出Advanced AC with Negative state（AACN）算法。以上两种改进算法只有在发现模式匹配时才需进行output表的访问。实验数据表明：AACA和AACN算法性能均高于AAC算法，特别在中小规模匹配上，性能提升更为明显。