【摘要】：提出一種基于改進(jìn)后綴樹與交互聚類思想相結(jié)合的算法ISTC算法,通過改造傳統(tǒng)后綴樹結(jié)構(gòu)實(shí)現(xiàn)了對(duì)文檔標(biāo)題和摘要的層次化聚類,同時(shí)用交互聚類的方式替代了傳統(tǒng)的遞歸算法.ISTC算法具有語(yǔ)言無(wú)關(guān)性,不僅適用于基于單詞的西方文字,而且可以在不引入詞典分詞技術(shù)的情況下有效地處理基于單字的中文字符.在此算法基礎(chǔ)上,設(shè)計(jì)并實(shí)現(xiàn)了基于改進(jìn)后綴樹算法的交互聚類引擎,在不同的網(wǎng)絡(luò)環(huán)境下對(duì)其進(jìn)行了系統(tǒng)測(cè)試,并與其他元搜索引擎進(jìn)行了對(duì)比.實(shí)驗(yàn)結(jié)果表明,使用改進(jìn)后綴樹算法進(jìn)行實(shí)時(shí)交互式聚類是可行的.
【圖文】：

類方法是以遞歸算法為基礎(chǔ)并有固定的聚類閾值,需要大量的時(shí)間和空間[5]. STC算法的優(yōu)點(diǎn)是利用短語(yǔ)不僅可以發(fā)現(xiàn)類,還可以描述類.后綴樹算法作為一種新的、增量式的線性時(shí)間運(yùn)算方法,生成的數(shù)據(jù)結(jié)構(gòu)非常緊湊,節(jié)約了大量的存儲(chǔ)空間.文獻(xiàn)[6]給出了詳細(xì)的建樹過程.圖1為與字符串“ABDCABCD”對(duì)應(yīng)的后綴樹結(jié)構(gòu).圖1　后綴樹結(jié)構(gòu)Fig. 1　Structure of suffix tree由圖1可見,傳統(tǒng)的后綴樹結(jié)構(gòu)采用邊作為存儲(chǔ)單位,而在程序?qū)崿F(xiàn)中樹結(jié)構(gòu)仍是以節(jié)點(diǎn)形式存在,這種結(jié)構(gòu)沒有充分發(fā)揮節(jié)點(diǎn)的靈活性.同時(shí),由于傳統(tǒng)后綴樹采用無(wú)序的插入方法,使建立后綴樹和讀取類標(biāo)識(shí)都必須進(jìn)行完全深度遍歷[7],當(dāng)數(shù)據(jù)量增大時(shí),耗時(shí)會(huì)線性增加.中文以單個(gè)漢字為單位的建樹方法比英文以詞為單位占用時(shí)間和空間要大得多

層次化的后綴樹結(jié)構(gòu)是在傳統(tǒng)后綴樹的基礎(chǔ)上,將字符串Sn從邊上提取出放到葉節(jié)點(diǎn)上,每個(gè)節(jié)點(diǎn)作為一個(gè)存儲(chǔ)單元,同時(shí)引入排序方法插入節(jié)點(diǎn),使建樹和讀樹的過程實(shí)現(xiàn)分層處理.當(dāng)一個(gè)節(jié)點(diǎn)不符合要求時(shí),就不對(duì)它的子節(jié)點(diǎn)進(jìn)行深度遍歷,從而減少不必要的時(shí)間開支.節(jié)點(diǎn)結(jié)構(gòu)如圖2所示.圖2　節(jié)點(diǎn)的結(jié)構(gòu)Fig. 2　Structure of nodes節(jié)點(diǎn)標(biāo)簽用于存儲(chǔ)該節(jié)點(diǎn)存儲(chǔ)的字符串內(nèi)容;兄弟指針指向同一層中的下個(gè)節(jié)點(diǎn);子節(jié)點(diǎn)指針指向該節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn),而第二個(gè)節(jié)點(diǎn)由第一個(gè)節(jié)點(diǎn)的兄弟指針鏈接;文檔索引標(biāo)簽是一個(gè)可變長(zhǎng)的數(shù)組,用于存儲(chǔ)該節(jié)點(diǎn)的字符串短語(yǔ)在哪些結(jié)果文檔中存在.在層次化后綴樹結(jié)構(gòu)中,改進(jìn)了節(jié)點(diǎn)的同層次排序,在建樹過程中,每次從根節(jié)點(diǎn)出發(fā),當(dāng)在第一層找到新節(jié)點(diǎn)的排序位置在兩個(gè)現(xiàn)存節(jié)點(diǎn)間并且沒有相同部分時(shí),將節(jié)點(diǎn)直接插入到兩節(jié)點(diǎn)之間.否則
【作者單位】： 吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;吉林大學(xué)通訊工程學(xué)院;
【基金】：吉林省科技發(fā)展計(jì)劃項(xiàng)目基金(批準(zhǔn)號(hào):20070533)
【分類號(hào)】：TP311.13

【共引文獻(xiàn)】

相關(guān)期刊論文 前4條

1 陳次白,林磊;動(dòng)態(tài)專家評(píng)估排序技術(shù)[J];情報(bào)雜志;2005年04期

2 陳晶;元搜索引擎實(shí)現(xiàn)技術(shù)[J];情報(bào)雜志;2005年05期

3 劉麗;元搜索引擎結(jié)果顯示方式研究[J];情報(bào)雜志;2005年06期

4 王敏,楊炳儒;基于主題的個(gè)性化元搜索引擎的設(shè)計(jì)與實(shí)現(xiàn)[J];情報(bào)雜志;2005年07期

相關(guān)博士學(xué)位論文 前1條

1 劉煒;智能元搜索引擎中個(gè)性化模式庫(kù)的研究[D];太原理工大學(xué);2007年

相關(guān)碩士學(xué)位論文 前10條

1 鮑宗泛;廣域網(wǎng)數(shù)據(jù)庫(kù)查詢系統(tǒng)的研究與開發(fā)[D];浙江大學(xué);2004年

2 呂傳宇;答疑系統(tǒng)中專題式智能型元搜索引擎的研究[D];重慶大學(xué);2004年

3 洪穎;面向化工領(lǐng)域的智能元搜索引擎系統(tǒng)的研究與設(shè)計(jì)[D];北京化工大學(xué);2004年

4 杭月芹;基于文檔查詢信息的檢索系統(tǒng)研究與實(shí)現(xiàn)[D];揚(yáng)州大學(xué);2005年

5 楊才峰;基于自動(dòng)分類的元搜索引擎的研究與應(yīng)用[D];華北電力大學(xué)（河北）;2005年

6 樊康新;基于服務(wù)器端的個(gè)性化元搜索引擎的研究與設(shè)計(jì)[D];蘇州大學(xué);2005年

7 魏振達(dá);基于服務(wù)的元搜索引擎研究[D];南華大學(xué);2006年

8 尹西杰;基于智能Agent的Web個(gè)性化信息檢索系統(tǒng)[D];山東大學(xué);2006年

9 李信利;基于信息類別的元搜索引擎研究[D];山東大學(xué);2006年

10 霍長(zhǎng)青;個(gè)性化元搜索引擎研究與設(shè)計(jì)[D];山東科技大學(xué);2006年

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 曾本勝，，廉玉忠，李世取;后綴樹的平均高度[J];運(yùn)籌與管理;1996年04期

2 王繼成,潘金貴,張福炎;Web文本挖掘技術(shù)研究[J];計(jì)算機(jī)研究與發(fā)展;2000年05期

3 周水庚,關(guān)佶紅,胡運(yùn)發(fā);基于文檔實(shí)例的中文信息檢索[J];計(jì)算機(jī)工程與應(yīng)用;2000年10期

4 鄧英,李明;Web數(shù)據(jù)挖掘技術(shù)及工具研究[J];計(jì)算機(jī)工程與應(yīng)用;2001年20期

5 李睿,李明;Web數(shù)據(jù)挖掘技術(shù)探討[J];甘肅科技;2001年03期

6 姜寧,史忠植;文本聚類中的貝葉斯后驗(yàn)?zāi)Ｐ瓦x擇方法[J];計(jì)算機(jī)研究與發(fā)展;2002年05期

7 林鴻飛,楊元生;用戶興趣模型的表示和更新機(jī)制[J];計(jì)算機(jī)研究與發(fā)展;2002年07期

8 姜寧,宮秀軍,史忠植;高維特征空間中文本聚類研究[J];計(jì)算機(jī)工程與應(yīng)用;2002年10期

9 鄭毅,吳斌,史忠植;基于概念空間的文本檢索系統(tǒng)[J];計(jì)算機(jī)工程與應(yīng)用;2002年12期

10 李家福,陸建江,張亞非;模糊聚類算法在漢語(yǔ)文本聚類中的應(yīng)用[J];計(jì)算機(jī)工程;2002年04期

相關(guān)會(huì)議論文 前9條

1 張寶艷;王慶輝;;中文文本聚類的研究與實(shí)現(xiàn)[A];第一屆學(xué)生計(jì)算語(yǔ)言學(xué)研討會(huì)論文集[C];2002年

2 張剛;周昭濤;王斌;;基于主題的分布式信息檢索研究[A];NCIRCS2004第一屆全國(guó)信息檢索與內(nèi)容安全學(xué)術(shù)會(huì)議論文集[C];2004年

3 邱立坤;程葳;龍志yN;孫嬌華;;面向BBS的話題挖掘初探[A];全國(guó)第八屆計(jì)算語(yǔ)言學(xué)聯(lián)合學(xué)術(shù)會(huì)議（JSCL-2005）論文集[C];2005年

4 黎琳;;Web內(nèi)容挖掘在數(shù)字圖書館中的應(yīng)用[A];中國(guó)工程物理研究院第七屆電子技術(shù)青年學(xué)術(shù)交流會(huì)論文集[C];2005年

5 彭怡;;從數(shù)據(jù)挖掘文章聚類分析看其發(fā)展趨勢(shì)[A];現(xiàn)代工業(yè)工程與管理研討會(huì)會(huì)議論文集[C];2006年

6 朱強(qiáng)生;田英;周延泉;何華燦;;基于非負(fù)因子分析的模糊文本挖掘[A];2006通信理論與技術(shù)新進(jìn)展——第十一屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集[C];2006年

7 羅娜;左萬(wàn)利;袁福宇;張靖波;張慧杰;;使用本體語(yǔ)義提高文本聚類(英文)[A];全國(guó)語(yǔ)域web與本體能研討會(huì)論文集[C];2006年

8 顏端武;李曉鵬;王磊;成曉;;文本聚類中基于本體的相似性測(cè)度(英文)[A];全國(guó)語(yǔ)域web與本體能研討會(huì)論文集[C];2006年

9 丁X;許侃;;基于文本聚類方法的我國(guó)科技管理研究領(lǐng)域的計(jì)量研究[A];第三屆科技政策與管理學(xué)術(shù)研討會(huì)暨第二屆科教發(fā)展戰(zhàn)略論壇論文匯編[C];2007年

相關(guān)重要報(bào)紙文章 前2條

1 王培森;從Web挖到競(jìng)爭(zhēng)情報(bào)[N];中國(guó)計(jì)算機(jī)報(bào);2003年

2 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 王 斌;內(nèi)容為王[N];計(jì)算機(jī)世界;2004年

相關(guān)博士學(xué)位論文 前6條

1 戈鵬;敏捷化CAPP系統(tǒng)原理、關(guān)鍵技術(shù)與應(yīng)用實(shí)踐[D];四川大學(xué);2003年

2 何清;機(jī)器學(xué)習(xí)與文本挖掘若干算法研究[D];中國(guó)科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2002年

3 梁作鵬;面向Web的XML檢索關(guān)鍵技術(shù)研究[D];東南大學(xué);2005年

4 熊云波;文本信息處理的若干關(guān)鍵技術(shù)研究[D];復(fù)旦大學(xué);2006年

5 劉向威;NLP技術(shù)在中文信息檢索中的應(yīng)用研究[D];天津大學(xué);2005年

6 何麗;基于Web挖掘的決策支持系統(tǒng)模型研究[D];天津大學(xué);2005年

相關(guān)碩士學(xué)位論文 前10條

1 易靖;基于信息粒度原理的文本分類方法的研究[D];北京工業(yè)大學(xué);2001年

2 蘇偉峰;基于概念的文本自動(dòng)分類研究[D];廈門大學(xué);2002年

3 劉恒;程序中重復(fù)代碼的自動(dòng)檢測(cè)[D];大連理工大學(xué);2003年

4 劉立平;一種中文文本聚類方法的研究[D];湘潭大學(xué);2003年

5 張俊艷;基于SVM有聚類指導(dǎo)的Web中文文本分類器的研究及其實(shí)現(xiàn)[D];福州大學(xué);2004年

6 馬國(guó)俊;潛在語(yǔ)義索引在中文文本聚類中的應(yīng)用研究[D];西安建筑科技大學(xué);2004年

7 谷波;基于粗集模型的聚類方法及其在文獻(xiàn)過濾系統(tǒng)中的應(yīng)用[D];山西大學(xué);2004年

8 李建祥;智能網(wǎng)頁(yè)推薦系統(tǒng)的相關(guān)技術(shù)研究[D];西南交通大學(xué);2004年

9 繆嘉嘉;數(shù)據(jù)倉(cāng)庫(kù)的數(shù)據(jù)獲取關(guān)鍵技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2003年

10 袁磊;基于概率模型的文本聚類[D];吉林大學(xué);2005年

本文編號(hào)：2525626