[發(fā)明專利]一種高效的文本區(qū)間熱詞查詢方法

有效

• 申請?zhí)枺?/td>: 201710059191.2
• 申請日: 2017-01-23
• 公開（公告）號: CN106874430B
• 公開（公告）日: 2021-06-04
• 發(fā)明（設(shè)計）人: 趙志洲;路暢;何震瀛;王曉陽;韓偉力
• 申請（專利權(quán)）人: 復(fù)旦大學(xué)
• 主分類號: G06F16/31
• 分類號: G06F16/31;G06F16/33
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;陸尤

1.一種高效的文本區(qū)間熱詞查詢方法，其特征在于，包括兩個階段：

一、利用時間序列劃分和范圍查詢的思想，對原始文本數(shù)據(jù)D進行預(yù)處理；

二、數(shù)據(jù)預(yù)處理的基礎(chǔ)上，對給定查詢q的時間范圍R_q＝[m：n]以及需要提取的熱詞個數(shù)k，計算確定所需熱詞；

其中，利用時間序列劃分和范圍查詢的思想，對原始文本數(shù)據(jù)D進行預(yù)處理的具體步驟為：

(1)為原始文本數(shù)據(jù)構(gòu)建數(shù)據(jù)結(jié)構(gòu)

首先，統(tǒng)計每個單位時間間隔內(nèi)不同單詞的出現(xiàn)次數(shù)，并為全部單位時間間隔建立索引，索引范圍為[1:S]，其中S表示文本數(shù)據(jù)D中單位時間間隔的數(shù)目；隨后在每個單位時間間隔s內(nèi)，為不同單詞依次構(gòu)建索引，索引范圍為[1:ST]，其中T表示文本數(shù)據(jù)D中不同單詞的數(shù)目；最后為上述數(shù)據(jù)建立數(shù)據(jù)結(jié)構(gòu)，它包括：單位時間間間隔s_i及其索引i，s_i中出現(xiàn)的單詞t_ij，單詞t_ij的索引j，單詞出現(xiàn)的次數(shù)n_ij；假設(shè)單詞t_ij在s_i上不出現(xiàn)時，它的計數(shù)為0；

(2)為上述的數(shù)據(jù)結(jié)構(gòu)構(gòu)建完全二叉樹，并對數(shù)據(jù)進行劃分

基于以上數(shù)據(jù)結(jié)構(gòu)，對數(shù)據(jù)集構(gòu)建概念上的完全二叉樹，其中根節(jié)點是整數(shù)數(shù)組[1:S]，每個子節(jié)點都是父節(jié)點的子數(shù)組，而葉子節(jié)點的長度為1，對一個節(jié)點[a:b]，它的左子節(jié)點是[a:b]的左半部分，即右子節(jié)點是[a:b]的右半部份，即假設(shè)S是2的冪，則這棵樹一共有l(wèi)gS+1層，每層l有2^l個節(jié)點，每個節(jié)點的長度是這顆二叉樹是用來概念上劃分查詢范圍對應(yīng)的四元組，不需要實際存儲；隨后，對于上述二叉樹的每一層l，令2≤l≤lgS，每隔兩個子節(jié)點將連續(xù)四個子節(jié)點劃分為一個四元組U，則第l層有2^l-1-1個四元組；設(shè)U_p是第l層劃分的第p個四元組，范圍是[a:b]，長度是有1≤p≤2^l-1-1，那么：

(3)獲取所有四元組的候選單詞列表

假設(shè)四元組U_p對應(yīng)的時間間隔中一共有σ個不同的單詞，σ＜T，通過遍歷這些單詞，計算每個單詞的詞頻；其中U_p對應(yīng)的四個子節(jié)點中包含的單詞數(shù)目依次為c1，c2，c3和c4；令c＝min(c1,c2,c3,c4)，則若單詞t在U_p中的出現(xiàn)次數(shù)大于α×c，那么將t加入到U_p對應(yīng)的候選單詞列表C_p中，通過遍歷這個四元組內(nèi)的所有單詞，獲得這個四元組對應(yīng)的候選單詞列表；

(4)優(yōu)化單詞計數(shù)的數(shù)據(jù)結(jié)構(gòu)

令R_q＝[m:n]，U_p為與其相關(guān)的四元組，C_p是U_p對應(yīng)的候選單詞列表；優(yōu)化單詞計數(shù)的數(shù)據(jù)結(jié)構(gòu)的形式化描述如下：

對于每個不同的單詞t:，將單詞在每個單位時間間隔中的數(shù)量累加，即t_c[t][s]＝t_c[t][s-1]+s中t的數(shù)量，其中t_c表示單詞在每個單位時間間隔中的數(shù)量的累加；

將每個單位時間間隔內(nèi)所有單詞的數(shù)量累加，即total[s]＝total[s-1]+s中所有單詞的數(shù)量；

當(dāng)R_q＝[m:n]時，單詞t的詞頻freq_t,m,n＝count_t,m,n/Total_m,n，計算freq_t,m,n的時間為O(1)，其中count_t,m,n＝t_c[t][n]-t_c[t][m-1]，Total_m,n＝total[n]-total[m-1]。

2.根據(jù)權(quán)利要求1所述的高效的文本區(qū)間熱詞查詢方法，其特征在于，所述在數(shù)據(jù)預(yù)處理的基礎(chǔ)上，對給定查詢q的時間范圍R_q＝[m：n]以及需要提取的熱詞個數(shù)k，計算確定所需熱詞的計算步驟為：

(1)根據(jù)m，n的值獲得候選單詞列表C_p，C_p對應(yīng)的層級l和四元素p的計算公式如下：

其中，l和q是整數(shù)；令若0或(n-1)2^zmod S_q＝0，且那么l＝z，否則l＝z+1；

對上述C_p中的每一個單詞，計算其在m,n時間范圍中的詞頻，如果滿足頻率大于α的條件，則將其將入到跟蹤列表中；

(2)對于跟蹤列表中的每一個單詞，計算單詞權(quán)重，計算公式如下：

其中，TFPDF_t表示單詞t的廣泛性，表示單詞t的時事性，F(xiàn)O_t和VO_t分別表示單詞t的TFPDF_t值和Var_t值在所有單詞中的排名，用來調(diào)節(jié)單詞對時事性的偏差；

(3)根據(jù)單詞的權(quán)重將單詞排序，并返回前k個作為熱詞。