-
公开(公告)号:CN106469218B
公开(公告)日:2019-11-19
申请号:CN201610811459.9
申请日:2016-09-08
Applicant: 中国科学院信息工程研究所
IPC: G06F16/22
Abstract: 本发明公开了一种基于位图的布尔表达式存储、匹配方法和系统。本发明存储阶段:针对多个布尔表达式的各个子项,对其相应的布尔表达式序号和所在位置进行存储,并按照子项值的大小升序排序,同时记录每个布尔表达式子项数目;对子项值建立索引。匹配阶段:开辟数组位向量bitmap存储每个布尔表达式的匹配情况,将每个能匹配的布尔表达式所对应的位置置为1,判断bitmap中1的个数是否与其子项数目一致,若一致,则输出对应序号,并将bitmap[k]置为‑1以防止重复匹配该布尔表达式,否则继续匹配下一文本项。本系统包括系统预处理部件、存储子项部件、构建索引部件、访问信息部件和返回信息部件。本发明大大提高了查询效率。
-
公开(公告)号:CN104881439B
公开(公告)日:2019-03-22
申请号:CN201510236364.4
申请日:2015-05-11
Applicant: 中国科学院信息工程研究所
IPC: G06F16/903 , G06F16/908
Abstract: 本发明涉及一种空间高效的多模式串匹配方法和系统。首先提出了一种新的存储模式串的数据结构—HashTrie,利用位向量表将原模式串矩阵存储为一维表的形式,避开传统方法存储自动机的状态转移矩阵问题;利用递归的哈希函数方法求出这个特殊的位向量表,以达到节约存储空间的目的;在哈希函数计算过程中,利用位运算技巧,将其转化为简单高效的位与运算操作;另外在HashTrie构造和关键词查找过程中均使用Rank技术,提高了搜索的空间效率和时间效率。本发明极大地降低了内存开销和预处理时间,更能满足实时入侵检测系统对规则生效的时效性要求,更适合于模式串集合规模较大、模式串长度较短的多模式串实时匹配问题。
-
公开(公告)号:CN106469218A
公开(公告)日:2017-03-01
申请号:CN201610811459.9
申请日:2016-09-08
Applicant: 中国科学院信息工程研究所
IPC: G06F17/30
Abstract: 本发明公开了一种基于位图的布尔表达式存储、匹配方法和系统。本发明存储阶段:针对多个布尔表达式的各个子项,对其相应的布尔表达式序号和所在位置进行存储,并按照子项值的大小升序排序,同时记录每个布尔表达式子项数目;对子项值建立索引。匹配阶段:开辟数组位向量bitmap存储每个布尔表达式的匹配情况,将每个能匹配的布尔表达式所对应的位置置为1,判断bitmap中1的个数是否与其子项数目一致,若一致,则输出对应序号,并将bitmap[k]置为-1以防止重复匹配该布尔表达式,否则继续匹配下一文本项。本系统包括系统预处理部件、存储子项部件、构建索引部件、访问信息部件和返回信息部件。本发明大大提高了查询效率。
-
公开(公告)号:CN104881439A
公开(公告)日:2015-09-02
申请号:CN201510236364.4
申请日:2015-05-11
Applicant: 中国科学院信息工程研究所
IPC: G06F17/30
Abstract: 本发明涉及一种空间高效的多模式串匹配方法和系统。首先提出了一种新的存储模式串的数据结构HashTrie,利用位向量表将原模式串矩阵存储为一维表的形式,避开传统方法存储自动机的状态转移矩阵问题;利用递归的哈希函数方法求出这个特殊的位向量表,以达到节约存储空间的目的;在哈希函数计算过程中,利用位运算技巧,将其转化为简单高效的位与运算操作;另外在HashTrie构造和关键词查找过程中均使用Rank技术,提高了搜索的空间效率和时间效率。本发明极大地降低了内存开销和预处理时间,更能满足实时入侵检测系统对规则生效的时效性要求,更适合于模式串集合规模较大、模式串长度较短的多模式串实时匹配问题。
-
-
-