基于字母表压缩的扩展有限自动机构造方法

摘要

本发明公开了一种基于字母表压缩的扩展有限自动机(ACFA，Alphabet Compression Based Extend Finite Automaton)构造方法，该方法为：选用合适的规则集在字母表压缩的扩展有限自动机中进行验证试验；读入规则集，通过字母表压缩的扩展有限自动机构造方法构造有限自动机并同时生成状态集；通过字母表压缩的扩展有限自动机匹配方法对每个状态集分别进行字母表划分并压缩其迁移表。与扩展有限自动机XFA相比，ACFA在迁移边上减少95.6％，在存储空间大小上减少了90.7％，而在匹配时间上仅增加了23.6％。因此，ACFA是一种快速且存储高效的正则表达式匹配方法，较已有的正则表达式匹配方法更加适合于高速深度包检测。

主权项

一种基于字母表压缩的扩展有限自动机构造方法，其特征在于，该方法为：1)选用合适的规则集在字母表压缩的扩展有限自动机中进行验证试验；2)读入规则集，通过字母表压缩的扩展有限自动机构造方法构造有限自动机并同时生成状态集；3)通过字母表压缩的扩展有限自动机匹配方法对每个状态集分别进行字母表划分并压缩其迁移表。