多模式搜寻的方法与系统

摘要

本发明提供一种多模式搜寻的方法与系统，此系统包括：第一处理单元、第一存储器单元及第二处理单元。第一处理单元根据多个模式字串来建立关键字树，并针对关键字树中的每一节点来建立跳表，此跳表包括多个索引字以及对应这些索引字的多个识别编号，这些识别编号为处于所针对的节点且以这些索引字为索引时，应进入的下一个节点的识别编号。第二处理单元根据第一存储器单元所储存的所有节点的跳表，采用AC演算法来比对一输入字串中是否包含有上述模式字串之一。本发明使用第二处理单元及跳表来执行搜寻，因此可改进系统整体的效能。

主权项

1. 一种多模式搜寻的方法，用以比对一输入字串中是否包含有多个模式字串其中之一，所述模式字串用以建立一关键字树，该关键字树包括多个节点以及多个边缘，每一边缘以一标示字来标示，每一节点以一识别编号来代表，该关键字树的第一个节点为一根节点，其特征在于，该方法包括下列步骤：针对该关键字树中的每一节点建立一跳表，该跳表包括多个索引字以及对应所述索引字的多个识别编号，所述识别编号为处于该节点且以所述索引字为索引时，应进入的下一个节点的识别编号；令一观察节点为该根节点；步骤一：依序输入该输入字串中的字，以获得一目标字；步骤二：以该目标字为索引，从该观察节点的跳表中，获得对应该目标字的该识别编号，再令该观察节点变为该识别编号所代表的节点；步骤三：判断该观察节点是否为一输出节点，当该观察节点为该输出节点时，输出该输出节点对应的模式字串；以及重复上述步骤一至步骤三的动作，直至该输入字串结束为止。