保存字符串匹配规则及利用保存规则进行字串匹配的方法

摘要

本发明公开了一种保存字符串匹配规则的方法，该方法将待保存的规则的关键字分为若干段子关键字，各段子关键字分别与相应的叶子编号串联形成字串，然后，以该字串为关键字在规则树中构建叶子，从而将规则的关键字以及规则的数据部分插入规则树中保存；本发明还公开了一种利用规则树进行字符串匹配的方法，该方法将待匹配的字符串分为若干段子关键字，各段子关键字与相应的叶子编号串联形成字串，在上述的规则树中查找这些字串的最长前缀匹配，从而实现字符串的匹配过程。该方法能够实现保存长字符串匹配规则，并且由于在利用规则树保存规则时不需要子树，因此可以减少硬件资源的占用，提高处理能力。

主权项

1、一种保存字符串匹配规则的方法，其特征在于，该方法包括以下步骤：步骤A：以L-M为单位将当前待保存在规则树中的规则的关键字分为S段子关键字，其中，在所分得的S段子关键字中，除第S段子关键字之外的各段子关键字的长度均等于L-M，第S段子关键字的长度小于或等于L-M，L为规则树所保存规则中关键字的最长长度，M为叶子编号的长度，所分得的段数S为自然数；步骤B：自第1段子关键字开始，到第S-1段子关键字为止，顺序执行步骤B1和步骤B2，其中，第1段子关键字的上一级叶子编号为0；步骤B1：当前子关键字前串联上一级叶子的叶子编号，形成新的字串，判断规则树中是否已有以该新字串为关键字的叶子，如果没有，则在规则树中生成一个以该新字串为关键字的叶子，并为该新生成的叶子分配唯一的叶子编号，将该新生成叶子的级联标志置为级联，然后将该新生成叶子置为当前叶子；如果有，且该找到的叶子的级联标志为级联，则将该找到的叶子置为当前叶子；步骤B2：将步骤B1中所处理的子关键字的下一段子关键字作为当前子关键字，将步骤B1中所处理的子关键字的叶子编号作为当前的上一级叶子编号，返回执行步骤B1；步骤C：第S段子关键字前串联上一级叶子的叶子编号，形成新的字串，判断规则树中是否已有以该新字串为关键字的叶子，如果没有，则在规则树中生成一个以该新字串为关键字的叶子，然后将待保存规则中的数据内容写入该叶子，如果有，直接将待保存规则中的数据内容写入该叶子。