Vol.28 No.5 曲文龙等：基于广义后绶树的事件序列频繁情节挖超算法 ·491· S是一组按时间（或空间）有序排列的事件 邻).一种方法是采用窗口定义情节的最大持续 定义3情节a定义为一个三元组(V,≤， 期maxduring,.以情节在所有窗口中的出现频率 g),其中V情节中结点的集合，≤是V上的偏 作为其支持度，此方法的缺点是无法发现超过窗 序，g:V→E是情节中的结点到对应事件类型的 口宽度的频繁情节并且对不同长度的频繁情节使 映射，即在情节中事件g(V)的出现必须满足偏 用统一的窗口.另一方法限制相邻事件的最大时 序≤定义的顺序.|a|表示情节a的长度，|a|的 间间隔maxgap,则包含k个事件的情节的窗口宽 值为情节中的结点数V.情节可以用有向无环 度为(k-1)×maxgap,在事件序列S=(s,T, 图(DAG)表示，见图2 T)中窗口总数为T。-T,+win-1.此方法可发 B 现任意长度的情节，其支持度按下式计算： ⑧ ④⑧© A D fr(a,S,wim)=|S.∈w(S,win)la∈Sl W(S,win)! © (1) 图2情节a,月和y 其中，W(S,win)为所有宽度为win=(k-1)× Flg.2 Eplsodes a,B and y maxgap的窗口集合，Sw表示情节发生的窗口子 序列. 如果关系≤为全序（即Hx,y∈V,必有x≤ y或y≤x),则称a为串行情节，例如a.如果关 2频繁情节广义后缀树 系≤为空（即Hx,yEV,x≠y不存在x≤y或y ≤x),则称为并行情节，例如B.同时包含串行并 后缀树是一棵表示每个序列后缀的一种树状 行的情节称混合情节例如Y.如果g:V→E为 数据结构，主要应用于字符串匹配领域].事件 序列频繁情节发现和字符串模式匹配具有内在相 单射则称为a单射情节，即情节a中不存在重复 似性，所以本文对后缀树结构进行改造，称为频繁 发生的事件. 情节广义后缀树，并应用于频繁情节模式发现. 定义4给定情节B=（V,≤'，g)和a= (V,≤，g),如果存在一个单射f:V'→V,使得 一个长为n的字符串S共有n+（n-1)+ …+1=（n2+n)/2=O(n2)个子字符串S[i. 对于Vv∈V'都有g'(v)=g(f(v)成立，并且 ](1≤i≤j≤n),由于一些子串可能相等，事实 Vv,w∈V',≤'w都有f(v)≤f(w)成立，则 上可以利用后级树在O(n)空间列举其所有后缀 称情节a为情节B的一个子情节，记为二a,子 子串. 情节DAG是情节DAG的子图.例如图1中B 定义7长为n的字符串S的后缀树是一颗 是y的子情节. 有n个叶结点的根树，每一内部结点至少有两个 定义5设B=(V,≤'，g)是a=(V,≤， 孩子结点，每个边用一非空子串标记，每一结点发 g)的子情节且|β|<|a,设单射为f:V→V,若 出的边子串的起始字符均不同.对于每一叶结点 存在v,u∈V(v≠u),使得存在f(v')=v(v'∈ i,从根结点到叶结点经历的每个边标记子串的连 V')但不存在f(u')=u(u'∈V'),必有u≤v不 接，对应从第i个位置开始的字符串S的后缀， 成立，则称为a的前缀子情节，称a为B扩充情 松散后缀树：每边对应一个字符，每个结点至 节.当|a|=|B|+1时，则称β为a的相邻前缀 少包含一个孩子结点，本文数据结构基于松散后 子情节，称a为B相邻扩充情节. 缀树.图3给出了字符串ABCAB$的后缀树和 定义6给定情节a=(V,≤，g)和事件序 松散后缀树，$表示串结束符. 列S=(A,t1),（A2,t2),…,（An,tn),T 利用广义后缀树发现频繁场的主要思想如 T),如果存在一个从情节结点到事件的单射h: 下： V→{1，…，n},使得对x∈V都有g(x)= (1)采用广义后缀树发现和存放频繁情节， Ah()成立，并且对x,yEV(x≠y,x≤y)都有 实现共享前缀压缩.构造件序列的完全后缀树 th(r)<th(y)成立，则称情节在件序列的一次发 可以简单的用于频繁情节发现，但需要存放所有 生 出现的情节，需占用大其内存空间.为了发现至 为发现兴趣情节，必须对限制情节中事件的 少出现minsupp次的频繁情节，必须采用相应策 发生的时间接近度加以限制（但不一定全部相 略裁剪树的规模，实际上只需构建至少有minsuppo V l . o 2 8 N . 5 曲文龙等 : 荃于 广义后级树 的事件序列频萦情节挖掘算法 S 是 一 组按时间 或空间 ) 有序排列 的事件 ( . 定义 3 情 节 a 定义为一 个三元 组 ( V , ( , g ) , 其中 v 情 节 中结 点的集合 , 镇 是 v 上 的偏 序 , :g v ~ E 是情节中的结点到对应 事件类型 的 映射 , 即在情节中事件 g ( v )的 出现 必 须满足 偏 序簇 定 义的顺序 . }aI 表示情 节 a 的长 度 , }al 的 值为情节中的结点数 } V I . 情节可以 用有向无 环 图 ( D A G )表示 , 见 图 2 . 邻) . 一种方 法 是 采用 窗 口 定 义 情节的最 大持续 期 m ax d ur in g , 以情 节在所 有窗 口 中的出 现 频 率 作为其支持度 , 此 方法 的缺 点是 无法 发现 超过 窗 口 宽度的频 繁情节并且对不同长 度的频繁情节使 用统一 的窗口 . 另一方法限 制相邻事件的最 大时 间间隔 m a x ga p , 则包含 k 个事件的情节的窗 口 宽 度为 ( 走 一 l ) x m a x g a p , 在 事件序 列 S = ( : , T , , T e ) 中窗口 总数为 T 。 一 T : + w in 一 1 . 此方法 可发 现 任意长度的情节 , 其支持度按下 式计算 : f r ( a , S , w i n ) = } S w 任 w ( s , w i n ) } a 任 S w } Iw ( S , w i n ) l "@O 图 2 情节 a . 月和 下 F lg . 2 E P l s 闭es a , 月 a n d y 如果 关系( 为全序 ( 即 V x , y 任 v , 必 有 x 簇 y 或 y 成 x ) , 则称 a 为串行情节 , 例如 a . 如果关 系蕊 为空 (即 V x , y 任 v , x 笋 y 不 存在 x 成 y 或 y 成 x ) , 则称为并行情节 , 例如 夕 . 同时包含串行并 行的情节称混 合情节例如 y . 如果 g : v ~ E 为 单射则称为 a 单射情 节 , 即情节 a 中不存在 重 复 发生 的事件 . 定义 4 给定 情节 口= ( ’V , 成 ` , g ’ ) 和 。 = ( v , 簇 , g ) , 如果存在一 个单射 f : v ` ~ v , 使得 对于 V v 任 V ` 都有 g ` ( v ) = g ( f ( v ) )成立 , 并且 V v , w 任 v ’ , v 镇 ’ w 都有 f ( v ) 镇 f ( w )成立 , 则 称情节 。 为情节夕的一个子情节 , 记为 夕二 。 . 子 情节 DA G 是情 节 DA G 的子 图 . 例如 图 1 中 月 是 y 的子情节 . 定义 5 设 月= ( v ` , 镇 ’ , g ’ ) 是 。 = ( v , 簇 , g )的子情节且 }夕! < } 。 } , 设单射为 f : V’ ~ v , 若 存在 v , “ 任 v ( v 笋 “ ) , 使得 存在 f( ’v ) 二 v( v’ 任 v ` )但不 存在 f ( u ` ) = u ( v ` 任 v ` ) , 必有 u 簇 v 不 成立 , 则称 夕为 口 的前缀子情节 , 称 。 为月扩充情 节 . 当 } 。 } = }月} 十 1 时 , 则称 月为 。 的相 邻前缀 子情节 , 称 。 为月相邻扩充情节 . 定义 6 给 定情节 。 = ( v , 蕊 , g ) 和 事件序 列 S = ( ( A l , t l ) , ( A Z , t Z ) , … , ( A , , r , ) , T s , T e > , 如果存在 一个从 情节结点到 事件的单射 h : v ~ 11 , … , n } , 使得 对 V x 任 V 都有 g ( x ) = A * ( , )成立 , 并且对 V x , y 任 v ( x 笋 y , x 镇 y )都有 t * ( , ) < t 、 ( , )成立 , 则 称情节 在 事件序列 的一 次 发 生 . 为发现兴 趣情 节 , 必 须对 限 制情节中 事件的 发生 的时间接近 度 加 以 限 制 ( 但 不 一 定 全 部 相 ( 1 ) 其中 , w ( S , w i n ) 为所有宽度为 w i n = ( 无 一 l ) x m a x ga p 的 窗 口 集合 , S w 表示 情节发生 的窗 口 子 序列 . 2 频繁情节广义后缀树 后缀 树是一棵表示每个序列后缀 的一种树状 数据结构 , 主要 应用于 字符串匹配 领 域 [,] . 事件 序列频繁情节发现 和 字符串模式 匹配具 有内在相 似性 , 所以本文对 后缀 树结构进 行改造 , 称为频繁 情节广义后缀树 , 并应 用于 频繁情 节模式发现 . 一个长 为 , 的字符串 S 共有 , 十 ( n 一 1 ) 十 … + 1 = ( n Z + , ) / 2 = o ( , 2 )个子 字符 串 s [ i 二 j l l( 成 i 镇 j 毛 , ) , 由于 一 些 子 串可能相 等 , 事实 上可以利 用后 缀树在 O ( n ) 空 间列 举其所有后 缀 子 串 . 定义 7 长 为 n 的字符串 S 的后 缀 树是 一颗 有 n 个叶结点的根树 . 每一 内部结点至 少有两个 孩子结点 , 每个边 用一 非空 子 串标记 , 每一结点发 出的边子 串的起始字符均不 同 . 对 于每一 叶结点 i , 从根结点到 叶结点经 历 的每个边标记子 串的连 接 , 对应 从第 i 个 位置 开 始的字符串 S 的后 缀 . 松散 后缀树 : 每边 对应 一 个字 符 , 每个结点至 少包含一 个 孩子结点 . 本文数据结构基 于 松散后 缀树 . 图 3 给出 了字符串 A B 以B $ 的后 缀 树和 松散后缀树 , $ 表示 串结束符 . 利用 广 义 后 缀 树发 现 频 繁场 的主 要 思 想 如 下 : ( 1) 采用 广 义后 缀树发现 和 存放频 繁情 节 , 实现共享前缀压 缩 . 构造 事件序列 的完全 后缀 树 可 以简单的 用于 频 繁情 节 发现 , 但 需要 存放所有 出现 的情节 , 需 占用大 量 内存空 间 . 为 了发 现 至 少 出现 m isn 叩p 次的频 繁情节 , 必 须 采 用 相应 策 略 裁剪树的规模 , 实际 上 只需构建至少 有m isn u p p