大规模语料的频繁模式快速发现算法.pdfVIP

第28卷第12期 通 信 学 报 、白1．28 No．12 2007年 l2月 Joumal on Communicafions December2007 大规模语料的频繁模式快速发现算法 龚才春 ，一，贺敏 ，一，陈海强 ，许洪波 ，程学旗 (1．中国科学院 计算技术研究所，北京 100080；2．中国科学院 研究生院，北京 100039) 摘 要：提出了一种大规模语料频繁模式快速发现算法，通过采用合适的策略将语料划分为若干子语料，对每个 子语料单独进行处理，即可获得原始语料的频繁模式；同时该算法能够避免处理频次在设定阈值以下的模式，进 一 步减少了内存占用，提高了处理速度。实验表明，对3．6G互联网新闻语料发现频次大于 100的所有频繁模式 中最高消耗内存为1．6GB，单机平均每秒处理文本语料3．28M。 关键词：频繁模式；语料划分；重复串 中图分类号：TP391 文献标识码：A 文章编号：1000．436X(2007)12．0161．06 1n ’ 一 ‘ ‘ ’ ‘ ’ 一 ’ ’ requent-oattern discovering algorithm for large-scale corpus GONG Cai—chun ’-，HE Min ’-，CHEN Hai—qiang ，XU Hong_bo ，CHENG Xue—qi (1．InstituteofComputingTechnology,ChineseAc~emyofSciences，Beijing100080，China； 2．Graduate School of Chinese Academy of Sciences，Beijing 100039，China) Abstract：A memory·based frequent-pattern discovering Mgofithm for large·scale corpus was presented．First，the origi- nal corpus was partitioned into several parts using appropriate dividing policy．Then each partition was processed inde· pendently to produce a temporary result，and the union of all temporary results is the fmal frequent·pattem set．Th e algo· rithm prunes a subtree once it is sure that none of the corresponding pattern will be frequent．Experiment shows that it takes no more than 1．6 gigabytes of memory to discover all patterns appearing more than 100 times for a 3．6 gigabytes news corpus，the average speed is 3．28 magabytes per second． Key words：frequent pa~em；corpus partition；repeat 中文处理的新词发现、社会计算的热点发现等都有 1 引言