algorithm - 为什么 BIDE 使用半最大周期进行 serach 空间修剪？

Answer 1

我想我得到了答案。这是一个示例，它在最大周期内有新事件，但在半最大周期内没有：

[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我们可以通过前向扩展将初始值增长为AB{*A*B}，但我们不能在半最大周期中添加任何字符A{*}B，因为我们无法通过前向扩展来达到它，AB并且 PrefixSpan 仅通过前向扩展来增长模式。因此，例如，如果我们x在第二个半最大周期中找到AB在相同的支持下，那么我们必须停止增长AB并等待 PrefixSpan 增长AxB，A -> Ax -> AxB并继续增长AxB模式而不是AB模式。办公室。我们在这里寻找封闭的频繁模式，而不是频繁模式，因此我们可以安全地修剪搜索空间。我不确定是否可以设计一个频繁模式挖掘算法，它既可以向前扩展，也可以向后扩展。也许稍后我会尝试为挑战设计这样的算法，但现在 BIDE 适合我正在做的事情。