有限状态自动机生成方法、关键字匹配方法及装置和设备

摘要

本发明公开了一种有限状态自动机的生成方法、查询方法及装置和设备，其中生成方法包括：针对待生成的DFA的每个状态，在为该状态分配的内存空间中为该状态生成第一状态对应表，第一状态对应表用于记录向待生成的DFA输入ASCII字符表的每个字符时，待生成的DFA的下一状态的值为0或者为非0；针对待生成的DFA的每个状态，在为该状态分配的内存空间中为该状态生成第二状态对应表，第二状态对应表用于记录第一状态对应表记录的下一状态的值为非0时该下一状态的值；将所有状态的第一状态对应表和第二状态对应表作为待生成的DFA。与现有技术相比，本发明提供的有限状态自动机的生成方法生成的DFA，所占用的存储资源大大减少。

主权项

一种使用有限状态自动机进行关键字匹配的方法，其特征在于，包括：在当前状态下，接收输入的待查询的关键字中的一个字符；确定该字符在ASCII字符表中对应的十进制的字符n；所述n的取值范围为[0，N‑1]，所述N为ASCII字符表的字符总数；从当前状态的第一状态对应表中，获取第n+1个比特位记录的第一标识位或第二标识位；所述第一标识位用于指示向有限状态自动机DFA输入ASCII字符表中十进制为n的字符时所述DFA的下一个状态的值为0；所述第二标识位用于指示向所述DFA输入ASCII字符表中十进制为n的字符时所述DFA的下一个状态的值为非0；若获取到的第n+1个比特位记录为第一标识位，则跳转至状态0，等待接收所述待查询的关键字中的下一个字符；若获取到的第n+1个比特位记录为第二标识位，确定该字符对应的DFA的下一个状态的记录在所述第一状态对应表中所有DFA下一状态的值为非0的记录中的位序；在第二状态对应表中，获取相同位序的字节记录的该字符对应的DFA的下一个状态的值，根据获取到的所述下一个状态的值跳转至相应的下一状态，等待接收所述待查询的关键字中的下一个字符；输出所述待查询的关键字的匹配结果。