资源描述：
《大规模语料的频繁模式快速发现算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第12期龚才春等：大规模语料的频繁模式快速发现算法·167·大规模语料的频繁模式快速发现算法龚才春1,2，贺敏1,2，陈海强1，许洪波1，程学旗1(1.中国科学院计算技术研究所，北京100080；2.中国科学院研究生院，北京100039)摘要：提出了一种大规模语料频繁模式快速发现算法，通过采用合适的策略将语料划分为若干子语料，对每个子语料单独进行处理，即可获得原始语料的频繁模式；同时该算法能够避免处理频次在设定阈值以下的模式，进一步减少了内存占用，提高了处理速度。实验表明，对3.6G互联网新闻语料发现频次大于100的所有频繁模式中最高消耗内存为1.6GB，单机平均每秒处
2、理文本语料3.28M。关键词：频繁模式；语料划分；重复串中图分类号：TP391文献标识码：A文章编号：1000-436X(2007)12-0161-06Frequent-patterndiscoveringalgorithmforlarge-scalecorpusGONGCai-chun1,2,HEMin1,2,CHENHai-qiang1,XUHong-bo1,CHENGXue-qi1(1.InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100080,China;2.GraduateScho
3、olofChineseAcademyofSciences,Beijing100039,China)Abstract:Amemory-basedfrequent-patterndiscoveringalgorithmforlarge-scalecorpuswaspresented.First,theoriginalcorpuswaspartitionedintoseveralpartsusingappropriatedividingpolicy.Theneachpartitionwasprocessedindependentlytoproduceatemporaryres
4、ult,andtheunionofalltemporaryresultsisthefinalfrequent-patternset.Thealgorithmprunesasubtreeonceitissurethatnoneofthecorrespondingpatternwillbefrequent.Experimentshowsthatittakesnomorethan1.6gigabytesofmemorytodiscoverallpatternsappearingmorethan100timesfora3.6gigabytesnewscorpus,theaver
5、agespeedis3.28magabytespersecond.Keywords:frequentpattern;corpuspartition;repeat第12期龚才春等：大规模语料的频繁模式快速发现算法·167·1引言收稿日期：2007-09-22；修回日期：2007-12-02基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2004CB318109，2007CB311100）FoundationItem:TheNationalBasicResearchProgramofChina(973Program)(2004CB318109,2007CB
6、311100)在互联网高度发达的今天，网络用语日新月异，产生了大量新的词语和短语，如“芙蓉姐姐”、“天仙妹妹”、“红衣教主”、“灵湖MM”、“草根文化”等；在日常生活中也会产生很多新的用语，如“非典”、“神六”；在网络在线聊天室、即时通信等也会产生很多非正式表达方式，如“：）”、“^_^”、“brb”、“886”、“3ks”…发现这些使用频繁的新的词语、短语、非正式表达方式对搜索引擎的索引词优化、中文处理的新词发现、社会计算的热点发现等都有非常重要的意义[1~3]。在生物信息处理领域有大量的基因数据，如DNA序列、蛋白质序列等，从海量基因数据中发现频繁出现的基因片段对研
7、究生物进化、物种相关性等有重要意义[4,5]。这种在语料中频繁出现的模式（字符串或基因片段等）称为频繁模式。随着互联网的发展，互联网语料的规模也以指数规律增大，其规模已经远远超出一般服务器内存大小；基因数据的碱基对数量每12个月到16个月就翻一番，其规模也超出服务器内存的规模[5]。第12期龚才春等：大规模语料的频繁模式快速发现算法·167·本文提出一种大规模语料的频繁模式发现算法，通过对原始语料进行适当的划分，将划分结果保存到磁盘，依次将各划分调入内存即可发现整个语料的所有频繁模式。本文的主要贡献有：1)提出了一种大规模语料的划分方法，
