GSP算法是AprioriAll算法的扩展算法，而AprioriAll算法为Apriori类算法，故GSP算法也是一个Apriori类算法。在GSP算法中，引入了时间约束、滑动时间窗和分类层次技术，增加了扫描的约束条件，有效地减少了需要扫描的候选序列的数量，同时还克服了基本序列模型的局限性，更切合实际，减少多余的无用模式的产生。另外，GSP利用哈希树来存储候选序列，减少了需要扫描的序列数量，同时对数据序列的表示方法进行了转换，这样就可以有效地发现一个候选项是否是数据序列的子序列。

GSP算法类似于Apriori算法，采用冗余候选模式的剪除策略和特殊的数据结构-----哈希树来实现候选模式的快速访存。

GSP算法基本步骤如下：

（1）扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集

（2）根据长度为i 的种子集Li ，通过连接操作和修剪操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持度，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集

（3）重复第二步，直到没有新的序列模式或新的候选序列模式产生为止

产生候选序列模式主要分两步：

连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中

修切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除

候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列s,找出集合C中被s所包含的所有候选序列模式，并增加其支持度计数

GSP需要多次扫描序列数据库，在第一次扫描中，对所有的单个项目(1—序列模式)进行计数。利用频繁1—序列模式生成候选频繁2—序列模式，进行第二次扫描并求候选频繁2—序列模式的支持数。使用频繁2—序列模式生成候选频繁3—序列模式，重复以上过程，直到找出所有的频繁序列模式。

哈希树GSP采用哈希树存储候选序列模式。哈希树的节点分为三类： 1、根节点；

2、内部节点；

3、叶子节点。

根节点和内部节点中存放的是一个哈希表，每个哈希表项指向其它的节点。而叶子节点内存放的是一组候选序列模式。

从根节点开始，用哈希函数对序列的第一个项目做映射来决定从哪个分支向下，依次在第n层对序列的第n个项目作映射来决定从哪个分支向下，直到到达一个叶子节点。将序列储存在此叶子节点。

初始时所有节点都是叶子节点，当一个叶子节点所存放的序列数目达到一个阈值，它将转化为一个内部节点。

候选序列模式支持度的计算

给定一个序列s是序列数据库的一个记录：

（1）对于根节点，用哈希函数对序列s的每一个单项做映射来并从相应的表项向下迭代的进行操作 （2）。

（2）对于内部节点，如果s是通过对单项x做哈希映射来到此节点的，则对s中每一个和x在一个元素中的单项以及在x所在元素之后第一个元素的第一个单项做哈希映射，然后从相应的表项向下迭代做操作（2）或（3）。

（3）对一个叶子节点，检查每个候选序列模式c是不是s的子序列.如果是相应的候选序列模式支持度加一。

这种计算候选序列的支持度的方法避免了大量无用的扫描，对于一条序列，仅检验那些最有可能成为它子序列的候选序列模式。扫描的时间复杂度由O(n*m)降为O(n*t),其中n表示序列数量，m表示候选序列模式的数量，t代表哈希树叶子节点的最大容量

GSP算法还有好多缺点和不能解决的问题，如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式

需要对序列数据库进行循环扫描

对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理