根据定义拜德的文章：
BIDE: Efficient Mining of Frequent Closed Sequences
定理2（backscan搜索空间剪枝）：
让前缀序列为
N序列，Sp=e1e2...en。如果∃i(1≤i≤n)并且存在项e′
它出现在前缀的每一个第i个半最大周期中Sp在SDB中，我们可以安全地停止生长前缀Sp。
证明：
因为项目e′
在前缀Sp中的第i个半最大周期中出现。SDB，我们可以获取新前缀S′p=e1e2...ei−1e′ei...en(1<i≤n)或S′p=e′e1e2...en(i=1)，以及(Sp ⊂ S′p)保持。任何本地经常项目(supSDB(Sp)=supSDB(S′p))w.r.t.
前缀e′′也是一个本地常见的项目w.r.t.Sp，同时S′p和(〈Sp,e′′〉⊂〈S′p,e′′〉)保持。
这意味着没有希望挖掘频繁的闭合序列
前缀(supSDB(〈Sp,e′′〉)=supSDB(〈S′p,e′′〉))。
我理解，例如，如果我有一个cc模式，我找到一个模式，比如在模式的第二个最大周期内，比如在cc和cc之间，每一个序列都包含cc，那么我就可以停止增长，因为我可以使用向后扩展来生成，这将有相同的支持，但是时间更长。因此，通过向前扩展Sp得到的任何模式肯定都不是封闭模式，因为它缺少AB。这就是为什么我必须停止增长e'并等待prefixspan随着前向扩展而增长C的原因。我不明白为什么最大周期必须限制在半最大周期在此上下文中以及为什么测试半最大周期是可以的。这篇文章没有真正的解释知道吗？你能写一个例子，用最大周期代替半最大周期来减少闭合的频繁模式吗？
最佳答案
我想我得到了答案。下面是一个示例，它在max period中有新事件，但在semi max period中没有：
[AxByB,AqBtyB], AB
2nd max period: [xBy,qBty] -> By
2nd semi-max period: [x,q] -> 0
所以根据它，我不能停止生长，因为在同样的支持下，在半最大周期内没有。另一方面，在相同的支撑下，最大周期内存在着
AB，因此我们可以从e'向后延伸到e'模式。但我发现我们也可以从前伸到前伸。如果重叠较多，例如通过A{By}B这样的模式，我们将得到相同的结论；我们可以将具有前向扩展的初始AB增长到AB{yB}，但不能将任何字符添加到半最大周期AB，因为我们无法从ABAB达到具有前向扩展的初始AB，并且prefixspan仅使用前向扩展来增长模式。因此，例如，如果我们在相同的支持下发现AB{*A*B}在A{*}B的第二个半最大周期，那么我们必须停止生长AB，等待prefixspan以x的方式生长AB，并继续生长AB模式而不是AxB模式。离岸价。我们在这里寻找封闭的频繁模式，而不是频繁模式，因此我们可以这样安全地修剪搜索空间我不确定是否有可能设计一个频繁模式挖掘算法，它既可以向前扩展，也可以向后扩展。也许稍后我会尝试为challange设计这样一个算法，但现在BIDE对我所做的一切都很好。