摘要： 提出一种适用于大规模语料的频繁模式增量发现算法。统计局部区域提取的字符串频度，对局部相对低频字符串进行剪枝。利用多模式串匹配算法，统计剪枝后局部相对高频字符串在整个语料中的频度，得到频度大于阈值的频繁模式。实验结果表明，该算法具有较低的空间复杂度和时间复杂度，内存消耗为基于后缀数组的频繁模式发现算法的20%左右。

关键词: 频繁模式, 增量式, 多模式串匹配算法, 后缀树, 后缀数组

Abstract: This paper presents a memory-based frequent pattern incremental discovering algorithm for large-scale corpus. It extracts strings and counts frequencies of them from local area, prunes the local relative low frequency strings, and uses multi-mode string matching algorithm to count the local relative high frequency strings in the whole corpus, eventually gets the frequent patterns that the frequency is greater than the threshold. Experimental result shows that the algorithm has a better space complexity and the highest consumption of the memory size in the process of frequent-pattern discovery is about 20% to the size of the algorithm based on suffix array.

Key words: frequent pattern, incremental, multi-pattern string matching algorithm, suffix tree, suffix array

中图分类号: 

• TP306