基于规则前件发生树匹配的数据流预测方法

摘要

本发明公开了一种基于规则前件发生树匹配的数据流预测方法，用于解决现有数据流预测方法预测效率低的技术问题。技术方案是首先依据规则合并策略构建前件发生树，将前件进行分类并根据不同类别分别作为前件发生树的不同分支；其次根据之前构建好的前件发生树来搜索前件的发生，主要是先匹配和填充前件发生树再搜索前件发生，搜索结点发生的时刻，来填充time序列，再逆向遍历time序列，搜索前件的发生；最后根据前件发生树中前件的区间最小且非重叠发生情况进行预测。本发明按照规则合并策略合并序列规则前件，避免在数据流上所有规则前件的匹配，利用规则间已有的关联关系提高前件的匹配效率，节省了存储空间，进而提高了预测效率和精度。

主权项

一种基于规则前件发生树匹配的数据流预测方法，其特征在于包括以下步骤：(a)构建AOT：前件发生树是一棵根树，根结点为空，在第0层；其余每个结点代表事件的发生，从根结点到各子结点的路径代表情节规则的前件；每个结点维护以下信息：事件类型E、前件标记isAntd和前件所属类型type，前一事件指针以及后一事件指针；标记isAntd的结点还记录了该前件对应的后件预测信息；当搜索某一分支时，为每个结点分配Time队列，搜索结束删除各结点的队列；AOT的建立依赖于规则前件的合并，其具体构建AOT的步骤如下：第一步，将前件集A赋给AfterSame集，在字典序排列的前件集A中比较相邻前件，看是否是完全相同的前件，若是，将此前件从AfterSame集中删除，并将其后件预测信息记录到保留的前件，直到AfterSame的前件均是互不相同的；其中前件完全相同(Same)是指有两序列规则α、β，其前件可分别表示为l_α＝<e₁,e₂…e_k>、l_β＝<a₁,a₂…a_k>，若e_i＝a_i，1≤i≤k，则α和β是前件完全相同的规则；第二步，在AfterSame集中从左到右比较相邻前件，统计相同项的个数；若相同项个数超过2，表明是部分相同的前件，则将此前件放入LeftSame集，否则放入AfterLeftSame集；其中，前件左相同是指有两序列规则α、β，其前件可分别表示为l_α＝<e₁,e₂…e_p>、l_β＝<a₁,a₂…a_k>，若e_i＝a_i，1≤i≤n,n<k,n<p，则α和β是前件左相同的规则；第三步，在AfterLeftSame集中，使用广义后缀树求公共子序列算法，得到部分前件相同集和对应部分相同前件的公共部分集合CommonPart，其中前件部分相同是指有两序列规则α、β，其前件可分别表示为l_α＝<e₁,e₂…e_k>、l_β＝<a₁,a₂…a_q>，若e_i＝a_i，n≤i≤k,1<n≤k,k<q，则α和β是前件部分相同的规则；第四步，在AfterLeftSame集中剩余的前件则认为是完全不同的前件，放入Diff集；Diff集是指除了上述之外，完全不同的前件类型的集合；第五步，利用合并后的前件集合Diff、LeftSame、CommonPart和PartSame构建AOT；首先，将Diff集中前件构建AOT分支，将第一层结点的type值设为1；其次，遍历LeftSame集，保证各前件共享公共结点，将LeftSame集前件存入AOT的相邻分支，将第一层结点的type值设为2；最后，遍历CommonPart，构建新结点，且标记是公共部分，将第一层结点的type值设为3；接着构建CommonPart对应的PartSame前件集合，将第一层结点的type值设为4；此时各前件均已记录在AOT中，并在各前件的结束位置保留了其对应的后件预测信息；(b)基于AOT搜索前件发生：首先匹配和填充AOT，接着搜索前件发生；根据上述构建AOT时所确定的type类型，有相应的如下操作：若type为1，直接搜索各结点发生时刻，填充Time队列；再逆向搜索分支，从当前结点Time队列尾端出发，逆向遍历Time队列，并往上搜索各前继结点对应的Time时刻；根据给定的搜索区间，判断是否能够构成区间最小且非重叠发生；搜索结束，输出前件发生，释放各结点的Time队列；若type为2，直接搜索各结点发生时刻，填充Time队列；再按照逆向搜索策略搜索前件发生，搜索结束后输出前件发生，释放各结点的Time队列；若type为3，首先搜索CommonPart的前件分支，记录各结点的Time队列，将公共结点的Time队列复制到PartSame的其他前件分支，共享发生时刻；若CommonPart结束位置标识为前件，则按照逆向搜索策略搜索前件发生，搜索结束后输出前件发生；若type为4，找到已有Time队列的结点，向前或者向后搜索填充其他结点的Time队列，再按照逆向搜索策略搜索前件发生，搜索结束后输出前件发生，释放各结点的Time队列，直至某分支的第一层结点type不再为4；重复直到搜索结束；(c)预测结果：根据AOT中前件的区间最小且非重叠发生情况，依据其记录的后件预测信息进行预测；预测时对每一个规则，预测后件的发生区间；前件各发生的区间按照结束时刻由小到大排序，若没有后件发生，则在规则窗口宽度限制下，计算前件各发生对应的完整后件预测区间；若后件的一部分发生，则在规则窗口宽度限制下，计算前件各发生对应的剩余部分后件的预测区间；若后件完整发生，无论随后是否存在后件的其他完整或不完整发生，都应立即停止后件的匹配。