一種高效的文本區(qū)間熱詞查詢算法

趙志洲,路 暢,何震瀛,王曉陽

(復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海 200433)

0 概述

互聯(lián)網(wǎng)高速發(fā)展使人們獲取海量信息變?yōu)榭赡?但隨之帶來一些新問題,如“如何從海量Web文本信息中提取用戶感興趣的熱門話題”。

為有效進(jìn)行話題檢測和跟蹤(Topic Detection and Tracking,TDT),研究者開展了大量研究工作[1-2],其中從文本數(shù)據(jù)中提取熱詞成為當(dāng)前研究的熱點(diǎn)問題之一[3-5]。文獻(xiàn)[6]提出TF-IDF(Term Frequency-Inverse Document Frequency)用于詞權(quán)重計(jì)算,TF-IDF綜合考慮詞頻和反文檔頻率,弱化頻繁出現(xiàn)在多個(gè)文檔中的詞的重要性。文獻(xiàn)[7]提出TF-PDF (TF-Proportional Document Frequency)方法,TF-PDF綜合考慮詞頻和文檔頻率,將更高的權(quán)重賦予出現(xiàn)在多個(gè)文檔中的詞。文獻(xiàn)[8](下文稱Chen算法)在TF-PDF方法的基礎(chǔ)上,考慮詞頻隨時(shí)間的波動(dòng)情況,并重新定義詞權(quán)重的計(jì)算方法。上述方法能夠有效提取與話題相關(guān)的詞,即滿足算法的有效性。文獻(xiàn)[9]基于熱度矩陣對(duì)微博熱點(diǎn)話題進(jìn)行檢測。但是這些算法的一個(gè)特點(diǎn)是:面向挖掘任務(wù),時(shí)間復(fù)雜度較高,因此,難以直接應(yīng)用于熱詞在線查詢問題。

為此,本文對(duì)文本數(shù)據(jù)的區(qū)間熱詞在線查詢問題展開研究。熱詞的在線查詢處理方法需要同時(shí)滿足2個(gè)特性:有效提取與話題相關(guān)的詞,即在線查詢的有效性;快速獲得查詢時(shí)間范圍內(nèi)的熱詞,即在線查詢的時(shí)效性。因此,設(shè)計(jì)同時(shí)滿足有效性和時(shí)效性的熱詞在線查詢方法依然是一個(gè)具有挑戰(zhàn)性的問題。針對(duì)上述方法時(shí)效性不足的缺點(diǎn),本文提出一種文本數(shù)據(jù)區(qū)間熱詞在線查詢處理算法(EHWE),該算法可以在已劃分的數(shù)據(jù)上進(jìn)行快速區(qū)間查詢處理。

1 相關(guān)工作

本文常用到的符號(hào)如表1所示。

表1 符號(hào)說明

1.1 熱詞提取

熱詞提取廣泛應(yīng)用于熱門話題分析。熱門話題是指在一段時(shí)間內(nèi),受到人們廣泛關(guān)注并討論的話題。在新聞報(bào)道中,話題的熱度取決于2個(gè)因素[7]:在一篇報(bào)道中熱詞出現(xiàn)的頻率以及包含這些熱詞的新聞報(bào)道的數(shù)量。一般而言,話題不會(huì)在所有時(shí)間中保持它的熱度,它有一個(gè)從產(chǎn)生、興起、成熟和衰亡的過程[10]。國內(nèi)外學(xué)者在TDT的基礎(chǔ)上提出了很多熱門話題發(fā)現(xiàn)的方法,其中基于熱詞的提取并聚類的方法成為一種主流的研究方法[11-14]。

熱詞是指在一段時(shí)間內(nèi)頻繁出現(xiàn)的詞。它用來描述熱門話題,并且會(huì)隨著熱門話題的生命周期而不斷變化。針對(duì)熱詞的提取,Chen算法綜合考慮詞頻和詞表述話題的能力。實(shí)驗(yàn)結(jié)果表明,與TF-IDF[5]和TF-PDF[6]相比,Chen算法能夠有效地過濾與話題無關(guān)的詞,并賦予與話題相關(guān)的名詞短語或?qū)嶓w名詞更高的權(quán)重,滿足算法的有效性。Chen算法中一個(gè)詞的權(quán)重被定義如下:

(1)

(2)

其中,t是一個(gè)詞,Ft表示詞t在數(shù)據(jù)集中出現(xiàn)的頻率,nt表示包含詞t的文檔個(gè)數(shù),N表示在給定數(shù)據(jù)集中文檔的總數(shù)。熱詞的時(shí)事性用來刻畫詞的使用頻率隨著時(shí)間的變化情況。一個(gè)詞在不同時(shí)間段上的使用頻率差異越大,那么這個(gè)詞越具有時(shí)事性,計(jì)算公式如下:

(3)

Chen算法在提取熱詞時(shí)分為3個(gè)步驟:

步驟1計(jì)算所有詞的詞頻,并獲得跟蹤列表;

步驟2對(duì)于跟蹤列表中的每個(gè)詞,計(jì)算詞權(quán)重;

步驟3根據(jù)權(quán)重將詞排序,選取權(quán)重最大的k個(gè)詞作為熱詞。

Chen算法能夠有效地提取與話題相關(guān)的詞,但時(shí)間復(fù)雜度較高,在實(shí)際應(yīng)用中,由于數(shù)據(jù)集的龐大以及需要多次查詢的緣故,該算法的效率低下,因此難以直接用來進(jìn)行文本區(qū)間熱詞的在線查詢處理。

1.2 具有詞頻約束的區(qū)間查詢

2 文本區(qū)間熱詞的查詢處理方法

2.1 問題描述

文本區(qū)間熱詞的在線查詢問題描述如下:

對(duì)于數(shù)據(jù)集D上的任意查詢q,q={Rq,k},返回區(qū)間Rq上的k個(gè)熱詞,其中Rq=[m,n],m和n表示查詢時(shí)間范圍的起止時(shí)間;k表示指定提取的熱詞個(gè)數(shù)。例如查詢q={20160101,20160331,1000},返回2016年1月1日—2016年3月31日之間按熱度遞減排序的前1 000個(gè)詞。原始數(shù)據(jù)集中的每篇文檔都有一個(gè)時(shí)間屬性,以原始數(shù)據(jù)集中出現(xiàn)的最小的時(shí)間間隔作為單位時(shí)間間隔,統(tǒng)計(jì)每個(gè)單位時(shí)間間隔內(nèi)不同詞出現(xiàn)的次數(shù),并構(gòu)建數(shù)據(jù)集D。它的形式化描述為D={s,t,c},其中,s表示時(shí)間間隔,t表示詞,c表示相應(yīng)時(shí)間間隔s中詞t出現(xiàn)的次數(shù)。數(shù)據(jù)集D上的數(shù)據(jù)結(jié)構(gòu)如表2所示。

表2 數(shù)據(jù)集D的數(shù)據(jù)結(jié)構(gòu)

若文本數(shù)據(jù)中時(shí)間屬性值的下限和上限分別是l和u,則l≤m≤n≤u。

2.2 EHWE算法

2.2.1 數(shù)據(jù)結(jié)構(gòu)

通過對(duì)Chen算法進(jìn)行分析發(fā)現(xiàn),對(duì)于一個(gè)給定的查詢q,在獲得跟蹤列表時(shí),需要計(jì)算q中所有詞在Rq中的詞頻;在計(jì)算一個(gè)詞在Rq中的詞頻和TFPDF值時(shí),需要遍歷這個(gè)詞在查詢時(shí)間范圍內(nèi)的每個(gè)單位時(shí)間間隔的計(jì)數(shù)。為減少獲得跟蹤列表時(shí)需要計(jì)算的詞數(shù)目以及優(yōu)化詞的計(jì)數(shù)結(jié)構(gòu),本節(jié)分別利用數(shù)據(jù)劃分和范圍查詢的思想,對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理并建立數(shù)據(jù)結(jié)構(gòu),使得獲得跟蹤列表和對(duì)查詢q中詞計(jì)數(shù)的時(shí)間復(fù)雜度分別為O(1)。

1)數(shù)據(jù)劃分

本文利用數(shù)據(jù)劃分的思想,將查詢q與一個(gè)四元組U相關(guān)聯(lián)。在獲得跟蹤列表時(shí),只需要判斷U對(duì)應(yīng)的候選詞列表C中的詞是否滿足在Rq中的詞頻大于α的條件。因?yàn)镃的長度要遠(yuǎn)小于Rq中不同詞的個(gè)數(shù)Tq,所以達(dá)到了優(yōu)化目標(biāo)。

在數(shù)據(jù)集中,一個(gè)時(shí)間間隔內(nèi)可以有任意整數(shù)個(gè)不同詞,每個(gè)詞可以出現(xiàn)任意整數(shù)個(gè)數(shù)。首先為全部單位時(shí)間間隔建立索引,索引范圍為[1:S];隨后在每個(gè)單位時(shí)間間隔內(nèi),為每個(gè)不同詞依次構(gòu)建索引,最大索引下標(biāo)是S×T,故索引范圍為[1:ST],所以建立索引結(jié)構(gòu)后,數(shù)據(jù)集D中包括:單位時(shí)間間隔si及其索引i,si中出現(xiàn)的詞tij,詞tij的索引j,詞出現(xiàn)的次數(shù)nij。假設(shè)詞tij在si上不出現(xiàn)時(shí),它的計(jì)數(shù)為0。

表3是對(duì)數(shù)據(jù)集D建立的索引結(jié)構(gòu)的舉例,和表2對(duì)應(yīng)。

表3 對(duì)數(shù)據(jù)集D建立的索引結(jié)構(gòu)

令Rq=[m:n],在計(jì)算查詢q中滿足詞頻大于α的詞時(shí),需要根據(jù)m和n找到詞索引的范圍[jm,jn],并計(jì)算該范圍內(nèi)不同詞的詞頻。算法1是對(duì)數(shù)據(jù)集劃分算法的形式化描述:

算法1數(shù)據(jù)集的劃分算法

輸入數(shù)據(jù)集D

輸出候選詞列表C

1. 構(gòu)建概念上的二叉樹;

2. FOR 樹中的每層l:

3. 構(gòu)建每層的全部四元組U;

4. FOR 全部層的U:

5. 計(jì)算候選詞列表;

(4)

例如,當(dāng)Rq=[1∶16]、l=3時(shí),一共有8個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)的長度為2;可以劃分為3個(gè)四元組,每個(gè)四元組的長度是8,它的劃分規(guī)則如圖1所示。

圖1 S=16、l=3時(shí)數(shù)據(jù)的劃分規(guī)則

通過對(duì)二叉樹每一層劃分四元組,可以發(fā)現(xiàn)對(duì)于在整個(gè)時(shí)間范圍上的任意范圍的查詢q,能夠找到一個(gè)特定的層l和四元組Up,使得查詢q至少包含這個(gè)四元組中的一個(gè)節(jié)點(diǎn),至多包含2個(gè)非兄弟節(jié)點(diǎn),即查詢q是和Up相關(guān)的。例如圖1中的查詢q1和q2,q1對(duì)應(yīng)于l=3,p=1;q2對(duì)應(yīng)于l=3,p=3。

假設(shè)四元組Up對(duì)應(yīng)的時(shí)間間隔中一共有σ個(gè)不同的詞(σ

2)詞計(jì)數(shù)結(jié)構(gòu)

令Rq=[m:n],Up為與其相關(guān)的四元組,Cp是Up對(duì)應(yīng)的候選詞列表。為獲得跟蹤列表,需要遍歷Cp中每個(gè)詞,并計(jì)算它們?cè)赗q中的詞頻,如果滿足條件,則將其加入到跟蹤列表中。在計(jì)算一個(gè)詞的詞頻時(shí),Chen算法需要遍歷詞在Rq內(nèi)每個(gè)單位時(shí)間間隔內(nèi)的計(jì)數(shù),這個(gè)過程的時(shí)間復(fù)雜度是O(ST)。顯然,算法1雖然減少了獲得跟蹤列表時(shí)需要計(jì)算的詞數(shù)目,但整體的時(shí)間復(fù)雜度并沒有降低,仍為O(ST)。為優(yōu)化計(jì)算Cp中每個(gè)詞在Rq中的詞頻的時(shí)間復(fù)雜度,算法2優(yōu)化了詞計(jì)數(shù)的數(shù)據(jù)結(jié)構(gòu),使得計(jì)算一個(gè)詞t在Rq中的詞頻的時(shí)間復(fù)雜度為O(1)。這一過程的形式化描述如下:

算法2查詢q中詞計(jì)數(shù)優(yōu)化算法

輸入數(shù)據(jù)集D

輸出每個(gè)單位時(shí)間間隔中詞總數(shù)的數(shù)組total;每個(gè)詞在每個(gè)單位時(shí)間間隔中的數(shù)量的數(shù)組t_c

1. FOR 每個(gè)不同的詞t:

2. t_c[t][1]=t在第一個(gè)單位時(shí)間間隔中的數(shù)量;

3. FOR s FROM 2 TO S:

4. t_c[t][s]=t_c[t][s-1]+s中t的數(shù)量;

5. total[1]=第一個(gè)單位時(shí)間間隔中所有詞的數(shù)量

6. FOR s FROM 2 TO S:

7. total[s]=total[s-1]+s中所有詞的數(shù)量

由算法2可知,當(dāng)Rq=[m:n]時(shí),詞t的詞頻freqt,m,n=countt,m,n/Totalm,n,計(jì)算freqt,m,n的時(shí)間為O(1),其中,countt,m,n=t_c[t][n]-t_c[t][m-1]、Totalm,n=total[n]-total[m-1]。

同理,在計(jì)算一個(gè)詞的TFPDF值時(shí),可以用算法2中的數(shù)據(jù)結(jié)構(gòu)來優(yōu)化詞頻和文檔頻率的計(jì)算過程,使得計(jì)算的時(shí)間復(fù)雜度為O(1)。

2.2.2 EHWE算法描述

基于以上的數(shù)據(jù)結(jié)構(gòu),對(duì)于任意一個(gè)查詢Rq=[m:n],EHWE算法的形式化描述如下:

算法3EHWE算法

輸入C,total,t_c,查詢q

輸出熱詞和權(quán)重

1. 根據(jù)查詢q指定的參數(shù)m、n

2. 獲得候選詞列表Cp

3. 計(jì)算m、n范圍內(nèi)詞總數(shù)Totalm,n

4. FOR Cp中的每個(gè)詞 t

5. 計(jì)算詞t在中出現(xiàn)的次數(shù)Countt,m,n

6. IF Countt,m,n>α×Totalm,nTHEN

7. 將詞t加入到跟蹤列表

8. FOR跟蹤列表的每個(gè)詞t

9. 計(jì)算t的權(quán)重wt(根據(jù)式(1));

10.根據(jù)權(quán)重排序選擇前k個(gè)詞

對(duì)一個(gè)查詢Rq=[m∶n],它的長度是m-n+1,如果對(duì)應(yīng)的層級(jí)是l,四元組是p,那么有:

(5)

(6)

2.3 復(fù)雜度分析

由算法3可知,在EHWE算法中,計(jì)算詞權(quán)重并提取熱詞時(shí)主要分為4個(gè)步驟:

步驟1根據(jù)m、n的值,返回與查詢q相關(guān)的候選詞列表;

步驟2判斷候選列表中的詞是否滿足頻率大于α的條件,若滿足,則將其加入到跟蹤列表;

步驟3對(duì)于跟蹤列表中的每個(gè)詞,計(jì)算詞的權(quán)重;

步驟4根據(jù)權(quán)重,將詞降序排序,并返回前k個(gè)作為熱詞。

通過對(duì)2種算法的空間復(fù)雜度分析可以發(fā)現(xiàn),Chen算法需要存儲(chǔ)整個(gè)數(shù)據(jù)集D,空間復(fù)雜度為O(ST);EHWE算法需要存儲(chǔ)所有四元組對(duì)應(yīng)的候選詞列表C以及C中每個(gè)詞的計(jì)數(shù)數(shù)組,它的空間復(fù)雜度為O(ST)。所以,Chen算法、EHWE算法的空間復(fù)雜度保持不變。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 數(shù)據(jù)源與數(shù)據(jù)分析

3.1.1 數(shù)據(jù)源

本節(jié)對(duì)Chen算法和本文提出的EHWE算法進(jìn)行實(shí)驗(yàn)比較。實(shí)驗(yàn)環(huán)境為:Intel Xeon(R) CPU E5-2650v3 @ 2.30 GHz×40,128 GHz內(nèi)存和256 GB磁盤,操作系統(tǒng)為Ubuntu Kylin16.04,程序設(shè)計(jì)語言為Java,使用JDK1.8。實(shí)驗(yàn)數(shù)據(jù)來源于美國有線電視新聞網(wǎng)(CNN)、英國廣播公司(BBC)和紐約時(shí)報(bào)(NYT),數(shù)據(jù)集統(tǒng)計(jì)信息如表4所示。

表4 數(shù)據(jù)統(tǒng)計(jì)信息

數(shù)據(jù)集D中最小的時(shí)間單位是d,所以本文實(shí)驗(yàn)中查詢的單位時(shí)間間隔為d。在實(shí)驗(yàn)之前,本文使用Stanford CoreNLP對(duì)原始的文本集進(jìn)行預(yù)處理,包括去除停止詞、分詞、詞形還原。

3.1.2 數(shù)據(jù)分析

在EHWE算法中,為使任意的查詢都能找到與之相關(guān)的四元組,需要對(duì)整個(gè)數(shù)據(jù)集涉及的時(shí)間間隔構(gòu)建完全二叉樹,并且保證每個(gè)葉子節(jié)點(diǎn)實(shí)際大小(包含的詞總數(shù))近似相等。如果不滿足這個(gè)條件,則會(huì)使得四元組對(duì)應(yīng)的候選詞數(shù)目大于上限(4/α-1)。在極端情況下,若每個(gè)四元組中都有一個(gè)節(jié)點(diǎn)的大小為1,那么候選詞的數(shù)目等于查詢q中詞的總數(shù)。為使候選詞列表中詞的數(shù)目小于q中詞的數(shù)目,需要將包含詞數(shù)目非常少的連續(xù)單位時(shí)間間隔合并,并重新構(gòu)建完全二叉樹。

在本文實(shí)驗(yàn)中,數(shù)據(jù)集的單位時(shí)間間隔是d,所以,統(tǒng)計(jì)了3個(gè)數(shù)據(jù)集中每天的新聞報(bào)道中詞的總數(shù),如圖2所示為BBC數(shù)據(jù)集在2014年每天新聞報(bào)道中的出現(xiàn)的詞總數(shù),可以發(fā)現(xiàn)詞總數(shù)在一條水平基線上波動(dòng),說明在2014年英國廣播公司每天的新聞報(bào)道中用詞數(shù)量是穩(wěn)定的。

圖2 BBC 2014年每天的新聞報(bào)道中詞總數(shù)

表5中統(tǒng)計(jì)了3個(gè)文本集在整個(gè)時(shí)間戳上每天出現(xiàn)詞數(shù)目的最大值、最小值以及對(duì)數(shù)據(jù)0-1標(biāo)準(zhǔn)化后的標(biāo)準(zhǔn)差,3個(gè)數(shù)據(jù)集的標(biāo)準(zhǔn)差均小于0.2,說明這3個(gè)新聞來源每天的新聞報(bào)道數(shù)量整體上是穩(wěn)定的,不需要進(jìn)行合并操作,可以直接在整個(gè)時(shí)間間隔構(gòu)建完全二叉樹。

表5 數(shù)據(jù)集分析

3.2 Chen算法和EHWE算法的運(yùn)行時(shí)間比較

為比較Chen算法和EHWE算法運(yùn)行時(shí)間,本節(jié)在上述3個(gè)數(shù)據(jù)集上分別進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 運(yùn)行時(shí)間隨查詢時(shí)間長度的變化

在實(shí)驗(yàn)中,頻率閾值α為0.000 015。從圖3可以看出,在CNN、BBC和NYT 3個(gè)數(shù)據(jù)集上,Chen算法和EHWE算法的運(yùn)行時(shí)間會(huì)隨著查詢時(shí)間的增長而增長,與Chen算法相比,EHWE算法在3個(gè)數(shù)據(jù)集涉及的整個(gè)時(shí)間范圍上的運(yùn)行時(shí)間分別減少59.7%、65.1%和75.5%。與Chen算法相比,EHWE算法減少的時(shí)間主要來源于獲得跟蹤列表并計(jì)算詞的TFPDF值時(shí)運(yùn)行時(shí)間。本文統(tǒng)計(jì)了NYT數(shù)據(jù)集上2種算法在獲得跟蹤列表并計(jì)算詞的TFPDF值過程的時(shí)間消耗,如圖4所示。

圖4 跟蹤列表及詞TFPDF值的時(shí)間比較

從圖4可以看出,EHWE算法的這部分運(yùn)行時(shí)間接近為常數(shù),而Chen算法在這部分的運(yùn)行時(shí)間隨著查詢時(shí)間的增長而增長。這是因?yàn)镋HWE算法這部分的時(shí)間復(fù)雜度為O(1),而Chen算法的這部分時(shí)間復(fù)雜度是O(ST),并且T和S相關(guān)。

如圖5所示,通過統(tǒng)計(jì)紐約時(shí)報(bào)在2014年隨著時(shí)間按照月份依次遞增時(shí),在數(shù)據(jù)集中出現(xiàn)不同詞的個(gè)數(shù),可以發(fā)現(xiàn)T和S是線性相關(guān)的,所以在獲得跟蹤列表并計(jì)算詞的TFPDF值時(shí),Chen算法的時(shí)間消耗會(huì)呈現(xiàn)如圖4所示的指數(shù)增長。

圖5 紐約時(shí)報(bào)2014年前n月份中出現(xiàn)的詞總數(shù)

3.3 參數(shù)α的分析

α是用戶事先設(shè)定的頻率閾值,表示一個(gè)詞能成為熱詞的最低頻率。α值越大,表示滿足條件的詞個(gè)數(shù)理論上就會(huì)越少。本文實(shí)驗(yàn)比較α值不同時(shí)對(duì)Chen算法和EHWE算法的影響,如圖6所示。

圖6 2種算法運(yùn)行時(shí)間隨α變化的影響

圖6(a)和圖6(b)分別表示在給定不同的α值時(shí),Chen算法和EHWE算法關(guān)于獲得跟蹤列表并計(jì)算詞TFPDF值(以下稱A過程)以及整個(gè)提取熱詞(以下稱B過程)過程中時(shí)間的消耗。實(shí)驗(yàn)的數(shù)據(jù)集是NYT,查詢的時(shí)間范圍是2010年1月—2015年12月。從圖6(a)可以發(fā)現(xiàn),當(dāng)α值增大時(shí),2種算法在A過程的時(shí)間消耗并沒有顯著變化,說明A過程的運(yùn)行時(shí)間消耗與α的大小無關(guān),這是因?yàn)樗鼈兊臅r(shí)間復(fù)雜度分別是O(ST)和O(1),并且S和T與查詢的時(shí)間范圍有關(guān)。由圖6(b)可以發(fā)現(xiàn),隨著α的增加,2種算法在B過程的運(yùn)行時(shí)間消耗會(huì)降低,并且趨于穩(wěn)定。這是因?yàn)殡S著α的增加,跟蹤列表中詞數(shù)目會(huì)減小,所以計(jì)算詞權(quán)重的時(shí)間消耗會(huì)減少。在極端情況下,當(dāng)跟蹤列表中的詞數(shù)目為0時(shí),2種算法在B過程的時(shí)間消耗會(huì)近似等于A過程的時(shí)間消耗,并且Chen算法的時(shí)間消耗大于EHWE算法。綜上所述,當(dāng)α值不斷增大時(shí),EHWE算法在數(shù)據(jù)集上的運(yùn)行時(shí)間仍小于Chen算法的運(yùn)行時(shí)間。

本文主要貢獻(xiàn)包括:

1)提出文本區(qū)間熱詞的在線查詢處理問題,與面向挖掘的熱詞提取問題相比,更加關(guān)注在線查詢的2個(gè)特性:有效性和時(shí)效性;

2)設(shè)計(jì)了EHWE算法,該算法能夠在保證計(jì)算結(jié)果準(zhǔn)確率的前提下,降低了提取熱詞的時(shí)間復(fù)雜度;

3)理論分析和實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果都表明EHWE算法優(yōu)于Chen算法。

4 結(jié)束語

本文對(duì)文本區(qū)間熱詞在線查詢問題進(jìn)行研究。在Chen算法基礎(chǔ)上,通過數(shù)據(jù)劃分和范圍查詢,對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理,并提出EHWE算法,在保證準(zhǔn)確率和空間復(fù)雜度不變的條件下,降低了提取熱詞的時(shí)間復(fù)雜度。實(shí)驗(yàn)結(jié)果表明,EHWE算法在CNN、BBC、NYT3個(gè)文本集上的時(shí)間代價(jià)要小于Chen算法。本文EHWE算法中尚未考慮對(duì)計(jì)算詞Var值的優(yōu)化,這將是下一步的主要工作。另外,基于熱詞的文本聚類算法以及對(duì)聚類的優(yōu)化也需要進(jìn)一步研究。

[1] FISCUS J G,DODDINGTON G R.Topic Detection and Tracking Evaluation Overview[M].New York:USA:Kluwer Academic Publishers,2002.

[2] 洪 宇,張 宇,劉 挺,等.話題檢測與跟蹤的評(píng)測及研究綜述[J].中文信息學(xué)報(bào),2007,21(6):71-87.

[3] ALLAN J,PAPKA R,LAVRENKO V.On-line New Event Detection and Tracking[C]//Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York,USA:ACM Press,1998:37-45.

[4] 周亞東,孫欽東,管曉宏,等.流量內(nèi)容詞語相關(guān)度的網(wǎng)絡(luò)熱點(diǎn)話題提取[J].西安交通大學(xué)學(xué)報(bào),2007,41(10):1142-1145.

[5] HISAMITSU T,NIWA Y.A Measure of Term Represent-ativeness Based on the Number of Co-occurring Salient Words[C]//Proceedings of the 19th International Con-ference on Computational Linguistics-Volume 1.Stroudsburg,USA:Association for Computational Linguistics,2002:1-7.

[6] SALTON G,YANG C S.On the Specification of Term Values in Automatic Indexing[J].Journal of Documen-tation,1973,29(4):351-372.

[7] BUN K K,ISHIZUKA M.Topic Extraction from News Archive Using TF*PDF Algorithm[C]//Proceedings of International Conference on Web Information Systems Engineering.Washington D.C.,USA:IEEE Computer Society,2002:73-82.

[8] CHEN K Y,LUESUKPRASERT L,CHOU S T.Hot Topic Extraction Based on Timeline Analysis and Multi-dimensional Sentence Modeling[J].IEEE Transactions on Knowledge & Data Engineering,2007,19(8):1016-1025.

[9] 聶文匯,曾 承,賈大文.基于熱度矩陣的微博熱點(diǎn)話題發(fā)現(xiàn)[J].計(jì)算機(jī)工程,2017,43(2):57-62.

[10] CHEN C C,CHEN Y T,SUN Y,et al.Life Cycle Modeling of News Events Using Aging Theory[C]//Proceedings of European Conference on Machine Learning.Berlin,German:Springer,2003:47-59.

[11] 王 林,藏冠中.基于復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的論壇熱點(diǎn)主題發(fā)現(xiàn)[J].計(jì)算機(jī)工程,2008,34(11):214-216.

[12] 高 妮,周明全,耿國華,等.基于文本挖掘的話題發(fā)現(xiàn)技術(shù)[J].計(jì)算機(jī)工程,2009,35(19):36-38.

[13] KUMARAN G,ALLAN J.Text Classification and Named Entities for New Event Detection[C]//Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York,USA:ACM Press,2004:297-304.

[14] 黃承慧,印 鑒,侯 昉.一種結(jié)合詞項(xiàng)語義信息和TF-IDF方法的文本相似度量方法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(5):856-864.

[15] YAO A C.Space-time Tradeoff for Answering Range Queries[C]//Proceedings of the 14th Annual ACM Symposium on Theory of Computing.New York,USA:ACM Press,1982:128-136.

[16] DUROCHER S,SHAR R,SKALA M,et al.Linear-space Data Structures for Range Frequency Queries on Arrays and Trees[J].Algorithmica,2016,74(1):344-366.

[17] CHAN T M,DUROCHER S,SKALA M,et al.Linear-space Data Structures for Range Minority Query in Arrays[J].Algorithmica,2015,72(4):901-913.

[18] GREVE M,JORGENSEN A G,LARSEN K D,et al.Cell Probe Lower Bounds and Approximations for Range Mode[M].Berlin,Germany:Springer,2010.

[19] KARPINSKI M,NEKRICH Y.Searching for Frequent Colors in Rectangles[C]//Proceedings of the 20th Annual Canadian Conference on Computational Geometry.Vancouver,Canada:[s.n.],2008:11-19.

[20] DUROCHER S,HE M,MUNRO J I,et al.Range Majority in Constant Time and Linear Space[C]//Proceedings of International Colloquim Conference on Automata,Languages and Programming.Berlin,Germany:Springer,2011:244-255.

編輯 索書志