大規(guī)模語(yǔ)料的頻繁模式快速發(fā)現(xiàn)算法

《大規(guī)模語(yǔ)料的頻繁模式快速發(fā)現(xiàn)算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第12期龔才春等：大規(guī)模語(yǔ)料的頻繁模式快速發(fā)現(xiàn)算法·167·大規(guī)模語(yǔ)料的頻繁模式快速發(fā)現(xiàn)算法龔才春1,2，賀敏1,2，陳海強(qiáng)1，許洪波1，程學(xué)旗1(1.中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京100080；2.中國(guó)科學(xué)院研究生院，北京100039)摘要：提出了一種大規(guī)模語(yǔ)料頻繁模式快速發(fā)現(xiàn)算法，通過(guò)采用合適的策略將語(yǔ)料劃分為若干子語(yǔ)料，對(duì)每個(gè)子語(yǔ)料單獨(dú)進(jìn)行處理，即可獲得原始語(yǔ)料的頻繁模式；同時(shí)該算法能夠避免處理頻次在設(shè)定閾值以下的模式，進(jìn)一步減少了內(nèi)存占用，提高了處理速度。實(shí)驗(yàn)表明，對(duì)3.6G互聯(lián)網(wǎng)新聞?wù)Z料發(fā)現(xiàn)頻次大于100的所有頻繁模式中最高消耗內(nèi)存為1.6GB，單機(jī)平均每秒處

2、理文本語(yǔ)料3.28M。關(guān)鍵詞：頻繁模式；語(yǔ)料劃分；重復(fù)串中圖分類(lèi)號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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期龔才春等：大規(guī)模語(yǔ)料的頻繁模式快速發(fā)現(xiàn)算法·167·1引言收稿日期：2007-09-22；修回日期：2007-12-02基金項(xiàng)目：國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（“973”計(jì)劃）基金資助項(xiàng)目（2004CB318109，2007CB311100）FoundationItem:TheNationalBasicResearchProgramofChina(973Program)(2004CB318109,2007CB

6、311100)在互聯(lián)網(wǎng)高度發(fā)達(dá)的今天，網(wǎng)絡(luò)用語(yǔ)日新月異，產(chǎn)生了大量新的詞語(yǔ)和短語(yǔ)，如“芙蓉姐姐”、“天仙妹妹”、“紅衣教主”、“靈湖MM”、“草根文化”等；在日常生活中也會(huì)產(chǎn)生很多新的用語(yǔ)，如“非典”、“神六”；在網(wǎng)絡(luò)在線聊天室、即時(shí)通信等也會(huì)產(chǎn)生很多非正式表達(dá)方式，如“：）”、“^_^”、“brb”、“886”、“3ks”…發(fā)現(xiàn)這些使用頻繁的新的詞語(yǔ)、短語(yǔ)、非正式表達(dá)方式對(duì)搜索引擎的索引詞優(yōu)化、中文處理的新詞發(fā)現(xiàn)、社會(huì)計(jì)算的熱點(diǎn)發(fā)現(xiàn)等都有非常重要的意義[1~3]。在生物信息處理領(lǐng)域有大量的基因數(shù)據(jù)，如DNA序列、蛋白質(zhì)序列等，從海量基因數(shù)據(jù)中發(fā)現(xiàn)頻繁出現(xiàn)的基因片段對(duì)研

7、究生物進(jìn)化、物種相關(guān)性等有重要意義[4,5]。這種在語(yǔ)料中頻繁出現(xiàn)的模式（字符串或基因片段等）稱(chēng)為頻繁模式。隨著互聯(lián)網(wǎng)的發(fā)展，互聯(lián)網(wǎng)語(yǔ)料的規(guī)模也以指數(shù)規(guī)律增大，其規(guī)模已經(jīng)遠(yuǎn)遠(yuǎn)超出一般服務(wù)器內(nèi)存大小；基因數(shù)據(jù)的堿基對(duì)數(shù)量每12個(gè)月到16個(gè)月就翻一番，其規(guī)模也超出服務(wù)器內(nèi)存的規(guī)模[5]。第12期龔才春等：大規(guī)模語(yǔ)料的頻繁模式快速發(fā)現(xiàn)算法·167·本文提出一種大規(guī)模語(yǔ)料的頻繁模式發(fā)現(xiàn)算法，通過(guò)對(duì)原始語(yǔ)料進(jìn)行適當(dāng)?shù)膭澐郑瑢澐纸Y(jié)果保存到磁盤(pán)，依次將各劃分調(diào)入內(nèi)存即可發(fā)現(xiàn)整個(gè)語(yǔ)料的所有頻繁模式。本文的主要貢獻(xiàn)有：1)提出了一種大規(guī)模語(yǔ)料的劃分方法，