大规模语料中频繁模式增量发现算法  

Frequent Pattern Increment Discovery Algorithm in Large-scale Corpus

作　　者：廖豪[1,2] 陈洁[1,3] 谭建龙[1] 

机构地区：[1]中国科学院计算技术研究所,北京100190 [2]中国科学院研究生院,北京100049 [3]北京邮电大学计算机学院,北京100876

出　　处：《计算机工程》2011年第23期27-29,32,共4页Computer Engineering

基　　金：国家"973"计划基金资助项目(2007CB311100);国家自然科学基金资助项目(20110250)

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

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

分 类 号：TP306[自动化与计算机技术—计算机系统结构]