連續(xù)時間區(qū)間內(nèi)的頻繁詞序列挖掘算法

王 璐，劉曉清，何震瀛

（1.復旦大學 軟件學院，上海 200441；2.復旦大學 計算機科學技術學院，上海 200433）

0 概述

互聯(lián)網(wǎng)和人工智能等信息技術的快速發(fā)展，使得新聞報道、博客推文、用戶評論等大量文本數(shù)據(jù)呈指數(shù)級增長，這些文本數(shù)據(jù)中蘊含著時事政治、熱點話題等具有重要價值和研究意義的信息。但由于網(wǎng)絡中文本數(shù)據(jù)海量、繁雜等特點，人們難以在大量篇幅文本中直接獲取有效信息，因此快速高效地在海量文本數(shù)據(jù)中提取有效信息成為研究人員關注的重點。以詞序列形式挖掘文本中頻繁出現(xiàn)的短語成為用戶獲取關鍵信息及進行文本集探索的有效方式之一。頻繁詞序列挖掘是將頻繁出現(xiàn)的詞序列看作能夠反映文檔主題內(nèi)容的短語，挖掘在文本集合中頻繁出現(xiàn)的詞序列。頻繁詞序列挖掘工作在短語挖掘［1］、文本聚類［2］、話題檢測［3］等任務中發(fā)揮重要作用。EL-KISHKY 等［4］在語料庫中抽取頻繁詞序列作為短語候選集，用于短語挖掘。BEIL 等［5］挖掘文本集合中的頻繁項集，使用頻繁項集作為候選簇進行文本聚類。MA［6］檢測滑動時間窗口中的詞頻統(tǒng)計等信息，并將其應用于新聞流的熱點話題提取模型。在這些工作中，頻繁詞序列挖掘是目標任務中重要且耗時的步驟，因此高效的挖掘方法能夠帶來整體任務效率的提升。

在很多實際應用中，新聞、博客等文本數(shù)據(jù)通常會以時間為單位進行組織并存儲。近年來，文獻［7-9］等諸多研究工作都聚焦在流數(shù)據(jù)、時空數(shù)據(jù)等具有時間屬性的文本數(shù)據(jù)中進行文本挖掘。因此，研究時間維度下的文本挖掘工作同樣具有重要意義。在一段時間區(qū)間內(nèi)持續(xù)頻繁出現(xiàn)的短語，更能體現(xiàn)熱點話題和文章內(nèi)容趨勢。例如，當使用《紐約時報》新聞作為輸入數(shù)據(jù)時，劃定時間區(qū)間為“2020 年3 月”、頻次閾值為20，在這段連續(xù)時間區(qū)間內(nèi)進行頻繁詞序列挖掘，發(fā)現(xiàn)獲得的頻繁詞序列為“冠狀病毒實時更新”、“冠狀病毒的簡報”和“伯尼·桑德斯”等，通過這些頻繁詞序列，可以看出該階段的熱點話題更多與新冠肺炎和美國大選的候選人選問題相關。然而，在面對海量文本數(shù)據(jù)并無法完全掌握文本內(nèi)容的情況下，用戶難以在一次查詢中準確設置閾值和時間區(qū)間，需要多次迭代查詢從而完成挖掘任務。用戶趨向于以探索性方式逐步進行挖掘，例如通過調(diào)整最小頻次閾值的大小獲取合適的關鍵短語集合，或通過調(diào)整時間區(qū)間來探索不同時間段內(nèi)的熱點話題的變化。傳統(tǒng)頻繁項集挖掘方法在修改最小頻次閾值或數(shù)據(jù)集后需要重新進行挖掘，因此在海量文本數(shù)據(jù)庫上進行頻繁詞序列挖掘時存在耗時嚴重的問題，無法達到頻繁迭代的查詢效率要求。

針對文本挖掘中熱點話題檢測、關鍵短語挖掘等實際應用場景，本文提出連續(xù)時間區(qū)間內(nèi)的頻繁詞序列挖掘算法。使用頻率樹（Frequency Tree，F(xiàn)-Tree）作為基本索引結構支持高效的頻繁詞序列挖掘，同時設計頻率樹的序列化構建方式和多棵頻率樹的連續(xù)剪枝挖掘算法，快速尋找在連續(xù)時間區(qū)間內(nèi)的熱點短語信息。

1 相關工作

1.1 熱點話題檢測

熱點話題檢測主要關注在一段時間內(nèi)持續(xù)受到關注和討論的主題內(nèi)容，近年來研究人員對于熱點話題檢測進行大量研究。文獻［10］提出PCTF 方法，并將其用于查詢一組詞匯成為熱詞的最長持續(xù)時間。文獻［11-12］在帶有時空信息的數(shù)據(jù)流中，查找一段時間內(nèi)發(fā)布的k個最相關的詞匯或文檔。文獻［13］通過優(yōu)化TF-IPDF 的計算過程，加快熱點詞匯查詢效率。在上述工作中，熱點話題的挖掘結果均以單個詞匯為單位呈現(xiàn)。短語相比詞匯在語意中更加完整，能夠表達更準確的主題含義，在實際應用場景中，人們更傾向于使用短語作為主題表達方式。

1.2 頻繁項集挖掘

頻繁詞序列挖掘問題類似于數(shù)據(jù)挖掘中的頻繁項集挖掘問題［14］。在頻繁項集挖掘中，以Apriori 算法［15-16］為代表的層次優(yōu)先搜索方法通過遍歷迭代數(shù)據(jù)集發(fā)現(xiàn)項集，以FP-Growth 算法［17］為代表的一系列算法根據(jù)數(shù)據(jù)信息構建FP-Tree，在此基礎上進行頻繁項集發(fā)現(xiàn)。Apriori 算法能夠通過簡單修改應用于頻繁詞序列挖掘問題，但由于算法需要多次掃描整個事務數(shù)據(jù)庫，在大規(guī)模文本挖掘中效率低下。憑借良好的擴展性和易編寫的特點，仍有一些研究人員［18-19］使用Apriori 類算法進行詞序列挖掘。FP-Growth 類算法利用樹形結構對原始數(shù)據(jù)進行索引，在挖掘過程中無需生成候選頻繁項集，提高了算法效率。但在FP-Tree 的構建過程中，需要按照項集頻繁度進行重新排序，打亂了項集之前的前后順序和關聯(lián)關系，對于頻繁詞序列挖掘任務而言，單詞構成的詞序列是有序且連續(xù)的。因此，上述頻繁項集工作對于解決頻繁詞序列挖掘問題具有一定指導意義，但無法完全適用于頻繁詞序列的挖掘。

1.3 后綴樹

與FP-Tree 類似，后綴樹是一種多叉樹型的數(shù)據(jù)結構，能夠索引一個字符串的所有后綴。對于由給定字符串S 構成的后綴樹T，T 中每個內(nèi)部節(jié)點到葉子節(jié)點的路徑均能夠構成S 的一個后綴。如圖1 所示，由字符串S=“I Know You Know I Know”構成的后綴樹T 可以看出，S 包含兩個以I 為起始點的后綴“I Know You Know I Know”和“I Know”。

圖1 后綴樹Fig.1 Suffix tree

后綴樹的概念由WEINER［20］在1973 年提出，為了降低后綴樹的存儲代價，MCCREIGHT 等［21］對后綴樹采取壓縮冗余節(jié)點的方法，如圖2 所示，每條邊不再僅限于包含一個單詞而是一個部分叉的字符串，使用$表示字符串結束。每個內(nèi)部節(jié)點都至少具有兩個子節(jié)點。為提高后綴樹的構造效率，UKKONEN［22］在1995 年提出在 線構造字 符串后綴樹的算法，能夠從左向右對字符串進行處理，當遇到不同后綴時對后綴樹的邊進行分割，該方法具有線性的時間復雜度。

圖2 壓縮后綴樹Fig.2 Compressed suffix tree

2 問題定義

本文研究的主要問題為根據(jù)用戶給定的查詢范圍和最小頻次閾值，快速找到查詢范圍內(nèi)在所有最小時間區(qū)間上均滿足頻次閾值的詞序列集合，實現(xiàn)對連續(xù)熱點話題的檢測。

定義1（時間區(qū)間T(x，y)）T(x，y)={tx，tx+1，…，ty}，1≤x≤y≤n表示時間區(qū)間，其中，t為最小區(qū)間間隔單位，ti為數(shù)據(jù)集的第i個區(qū)間間隔。T(1，n)表示包含整個數(shù)據(jù)集的完整區(qū)間，其中n表示包含的全部最小區(qū)間的個數(shù)。

定義2（帶有時間屬性的文本數(shù)據(jù)庫D）數(shù)據(jù)集中的文本根據(jù)時間屬性值分布在對應區(qū)間中，存儲分布于時間區(qū)間T(1，n)內(nèi)的文本數(shù)據(jù)庫D={Di|1≤i≤n}，其中Di為時間屬性值屬于時間區(qū)間ti的文本數(shù)據(jù)。

定義3（詞序列s（x，y））根據(jù)由有限個單詞a組成的詞典Σ，文本可表示為d={a1，a2，…，an}。詞序列s(x，y)={ax，ax+1，…，ay}，s(x，y)∈D是由文本集合D中依次出現(xiàn)的單詞組成的連續(xù)序列。

定義4（詞序列的頻次Freq(s，D)）對于給定的文本數(shù)據(jù)庫D={D1，D2，…，Dn}，詞序列s在D中的頻繁度可表示為Freq(s，D)=|{d∈D：s?d}|，即詞序列s在D中完整出現(xiàn)的次數(shù)。

定義5（連續(xù)時間區(qū)間內(nèi)的頻繁詞序列查詢query(D，θ，T)）對于分布在時間區(qū)間T(1，n)內(nèi)的文本數(shù)據(jù)集D={D1，D2，…，Dn}，給定時間 區(qū)間子集T(x，y)和最小查詢閾值θ，查詢在所有最小時間子區(qū)間tx…ty上的所有 文本子集Dx…Dy均滿足Freq(s，Di)≥θ，且不存在s的子串s'滿足Freq(s'，Di)≥θ的所有詞序列s構成的集合S。

3 算法描述

3.1 頻率樹

原始后綴樹在邊上記錄子串起始位置等信息，同時后綴樹通常作為單個字符串而不是文本集合的索引結構，無法很好地表示多條文本數(shù)據(jù)信息。本文對后綴樹結構進行改進，提出頻率樹，使其可用于詞序列頻次的計算，實現(xiàn)詞序列挖掘算法。F-Tree對于原始后綴樹結構修改如下：

1）給定一個包含n條文本數(shù)據(jù)的文本集合D={s1，s2，…，sn}，F(xiàn)-Tree 是一個包含n條文本數(shù)據(jù)的所有后綴的后綴樹。在構造F-Tree 時，在插入第i條文本數(shù)據(jù)s={a1，a2，…，an}時，在s后填充唯一的終止標記符$i，得到s={a1，a2，…，an，$i}。

例1頻率樹與僅索引單條字符串的后綴樹不同，能夠包含多條文本串的所有后綴。使用不同終止符保證了文本數(shù)據(jù)的所有后綴為唯一存在，每個后綴均由唯一的葉節(jié)點表示，避免了后綴數(shù)據(jù)被隱藏在內(nèi)部節(jié)點中或頻次計算被忽略的問題。例如，根據(jù)UKKONEN算法在圖2 的后綴樹中插入新的句子“I Know”時，原始后綴樹在讀取到與邊“I Know”完全匹配后，判斷完成本次插入而無須進行任何操作，導致對于完全相同的后綴錯誤的頻次計算。如圖3 所示，對于由“I Know You Know I Know”和“I Know”構成的F-Tree，當修改為插入“I Know $2”時，能夠與“I Know You Know I Know$1”中“I Know”后綴在終止符位置進行區(qū)分，從而保證頻率統(tǒng)計的正確性。

圖3 頻率樹Fig.3 Frequency tree

2）F-Tree 的每個節(jié)點由節(jié)點標號i與頻次屬性值freq 組成node(i：freq)，用freq 來表示由根節(jié)點0到當前節(jié)點i的路徑拼接得到的詞序列s[0，1，…，i]的頻次，即對于由數(shù)據(jù)集D構成的具有n個節(jié)點的F-Tree，樹中的任意節(jié)點i∈(1，n)，freqi=Freq(s[0，1，…，i]，D)。

例2以圖3 中節(jié)點2 為例，節(jié)點9 存儲的freq=1，即由根節(jié)點0 到節(jié)點9 的路徑與路徑拼接成的詞序列“Know I Know $1”在數(shù)據(jù)集中的出現(xiàn)頻次為1。同理，節(jié)點1 的freq=3 表示“I Know”詞序列出現(xiàn)頻次為3。

引理1在F-Tree 中，葉子節(jié)點的freq 為1。

證明如圖3 所示，F(xiàn)-Tree 中由根節(jié)點到葉子節(jié)點的路徑表示文本數(shù)據(jù)后綴，由于每條插入數(shù)據(jù)采用不同終止符進行標記，因此數(shù)據(jù)集中所有后綴均是唯一的，即葉子節(jié)點的freq 為1。

引理2每個內(nèi)部節(jié)點的freq 等于其直接連接子節(jié)點的freq 之和。

證明數(shù)據(jù)集中詞序列s出現(xiàn)頻次Freq(s，D)等于數(shù)據(jù)集中以s為前綴的所有后綴個數(shù)，由于每個后綴能夠由葉節(jié)點唯一表示，根據(jù)引理1，對于根節(jié)點到i的路徑構成的詞序列s[root，i]，F(xiàn)req(s，D)等于i的所有孩子節(jié)點中葉節(jié)點freq 之和，即等于與節(jié)點i直接連接的孩子節(jié)點的freq 之和。

引理3如果由根節(jié)點到節(jié)點i的路徑組成的詞序列s[0，i]的頻次為n，那么對于i的所有孩子節(jié)點，根節(jié)點到孩子節(jié)點的路徑組成的詞序列頻次一定小于等于n，即?j∈child(i)，F(xiàn)req(s[0，j]，D)＜Freq(s[0，i]，D)。

證明由于每個節(jié)點的freq 等于其直接孩子節(jié)點的freq 之和，如果該節(jié)點的頻次小于設定閾值，那么它的孩子節(jié)點freq 一定小于設定閾值，即如果一個詞序列s的出現(xiàn)頻次為n，那么所有以s為前綴的更長詞序列出現(xiàn)頻次一定小于等于n。

3.2 基于頻率樹的頻繁詞序列挖掘算法

由F-Tree 節(jié)點的freq 特點可知，通過對比節(jié)點freq 值與頻次閾值的大小，可以判斷詞序列是否符合查詢要求。當使用F-Tree 進行最小頻次為θ的頻繁詞序列挖掘時，可以通過對F-Tree 進行深度遍歷實現(xiàn)。根據(jù)引理3，F(xiàn)-Tree 能夠通過節(jié)點freq 值與閾值θ的對比對F-Tree 進行剪枝，從而減少遍歷范圍，提高查詢效率。遍歷F-Tree 到達某個節(jié)點時，如果它的freq 大于最小閾值，記錄邊中的詞序列并繼續(xù)向下遍歷；直到節(jié)點freq 不再滿足閾值要求，那么對應后綴不再滿足頻繁詞序列要求，向上回溯到父節(jié)點；如果節(jié)點滿足閾值且它的所有孩子節(jié)點均不滿足閾值要求，那么由根節(jié)點到該節(jié)點的記錄的路徑邊詞序列即為滿足要求的一個最長頻繁詞序列?；陬l率樹的頻繁詞序列挖掘算法（TS_Mining）描述如算法1 所示。

算法1基于頻率樹的頻繁詞序列挖掘算法

使用F-Tree 的頻繁詞序列挖掘算法能夠獲得每個單位時間區(qū)間內(nèi)的頻繁詞序列結果。為了進行連續(xù)時間區(qū)間范圍內(nèi)的頻繁詞序列挖掘，需要對每個單位時間區(qū)間內(nèi)的挖掘結果進行合并，得到在所有單位時間區(qū)間內(nèi)均滿足查詢條件的詞序列。在對單個F-Tree 挖掘結果進行合并時，一個基礎的取交集方法是對所有的結果集合逐個合并取交集，從而獲取滿足要求的最終結果集合。對第i個時間區(qū)間的詞序列集合Si中的詞序列s逐個進行遍歷，獲取s與前i-1 個區(qū)間合并的結果集合S′i-1的最長交集，將不為空的詞序列加入S′i，從而得到前i個區(qū)間的詞序列結果集合S′i。連續(xù)區(qū)間查詢的取交集算法（Intersection）描述如算法2 所示。

算法2連續(xù)區(qū)間查詢的取交集算法

3.3 改進的剪枝挖掘算法

算法1 與算法2 在對每個F-Tree 都進行閾值為θ的挖掘的同時，需要對每個單位時間區(qū)間內(nèi)的結果集合進行重復取交集操作，從而找到在所有F-Tree中均滿足查詢條件的詞序列。從結果來看，此類算法需要掃描經(jīng)過更多的路徑并進行額外的取交集計算，造成了效率損失。因此，本文在此基礎上進行改進，充分利用F-Tree 的數(shù)據(jù)結構，在F-Tree 掃描過程中完成取交集操作，將頻率樹的頻繁詞序列挖掘算法改進為剪枝挖掘算法（TS_Pruning），具體描述如算法3 所示。

算法3改進的剪枝挖掘算法

使用前i-1 個單位時間區(qū)間內(nèi)的結果作為輸入，對第i棵F-Tree 進行掃描剪枝，獲得在前i個單位區(qū)間內(nèi)均滿足查詢條件的結果集合。在剪枝查詢算法中，對于輸入集合的每個詞序列s，在區(qū)間i中的F-Tree 中以根節(jié)點為起點，自上而下在F-Tree 中查找詞序列s所經(jīng)節(jié)點是否滿足查詢閾值，從而找到滿足查詢條件的最長前綴。該算法充分利用了第i-1 個區(qū)間的挖掘結果，能夠減少F-Tree 需要掃描的范圍，同時無須對結果集合進行合并，減少了多次遍歷的時間代價。后綴樹的詞序列匹配算法（find_prefix）描述如算法4 所示。

算法4基于頻率樹的詞序列匹配算法

3.4 外存頻率樹加載

當使用大規(guī)模文本數(shù)據(jù)集進行查詢時，常規(guī)主機的內(nèi)存往往無法容納全部頻率樹索引結構。根據(jù)F-Tree 結構可以看出，樹中邊信息與節(jié)點信息僅與文本數(shù)據(jù)集相關，而與每次查詢的設定閾值無關。因此，當面臨內(nèi)存中無法容納所有F-Tree 索引結構的情況下，通過序列化方法構建每個最小區(qū)間內(nèi)的后綴樹并存儲在本地文件中，當進行查詢時，只需通過反序列化將時間區(qū)間范圍內(nèi)的后綴樹進行結構恢復，而無須對時間區(qū)間內(nèi)的全部文檔重新遍歷來構建后綴樹。當進行連續(xù)時間區(qū)間內(nèi)挖掘時，不再需要多次根據(jù)不同時間區(qū)間內(nèi)的文本集合構造F-Tree。相對于讀取原數(shù)據(jù)并重新構建F-Tree 的方法，序列化方法能快速還原F-Tree 結構，從而提升整體挖掘效率。

3.5 時間復雜度分析

假設文本數(shù)據(jù)集中文本長度為m，查詢時間區(qū)間長度為T，在單位時間區(qū)間下挖掘的頻繁詞序列的總長度平均為L1，最終頻繁詞序列結果集合總長度為L2。

F-Tree 構造具有與壓縮后綴樹相同的時間復雜度，根據(jù)文獻［9］可知，F(xiàn)-Tree 構造的時間復雜度為O（m）。對于樸素F-Tree 的頻繁詞序列挖掘算法，需要對F-Tree 進行深度遍歷找到滿足查詢要求的所有路徑，查找長度為L1，對于所有區(qū)間下的F-Tree 挖掘的時間復雜度為O(T×L1)。同時，取交集的結果集合的合并方式共需要進行t次合并操作，每次合并操作對兩個集合進行遍歷，時間復雜度為因此，總的時間復雜度為改進的剪枝挖掘算法將第i-1 個區(qū)間挖掘結果集合作為新的時間區(qū)間挖掘的輸入，避免結果合并帶來的時間代價。同時，在F-Tree 的挖掘過程中，只需對上一個區(qū)間的結果集合路徑進行遍歷剪枝，利用剪枝算法避免無效路徑的搜索，從而降低時間復雜度。在每次挖掘過程中，遍歷路徑長度L'滿足L1＜L'＜L2，因此時間復雜度將趨近于O(T×L2)，進一步降低了挖掘時間復雜度。

4 實驗結果與分析

4.1 實驗設置

4.1.1 實驗數(shù)據(jù)集

實驗使用2 個開放數(shù)據(jù)集進行測試：twitter 數(shù)據(jù)集采用2009 年4月至2009年6月的16萬條twitter 文本；blogs 數(shù)據(jù)集采用來自blogger.com 的2004 年1 月至2004 年12 月的博客文章［23］，該語料庫共包 含681 288 篇文章。在實驗中設置單位時間區(qū)間長度為1 周。為了更加符合現(xiàn)實應用場景，使用NLTK 自然語言處理庫對文本集合進行預處理，包括按照標點和停用詞對文章進行斷句、詞形還原等。表1 給出了數(shù)據(jù)集的詳細信息。

表1 數(shù)據(jù)集詳細信息Table 1 Dataset details

4.1.2 實驗環(huán)境和對比算法

實驗算法均由C++11 語言編寫，gcc 編譯，運行環(huán)境為2 GHz Intel Core i5 四核處理器，16 GB 內(nèi)存，macOS Catalina 10.15.7 操作系統(tǒng)。

實驗將Apriori 頻繁項集挖掘算法作為對比算法，并分別修改頻繁詞序列查詢的各項參數(shù)，以驗證本文提出的基于頻率樹的頻繁詞序列挖掘算法TS_Mining 和改進的剪枝挖掘算法TS_Pruning 的有效性。

4.2 性能分析

對于twitter 數(shù)據(jù)集，設置查詢的起始時間為2009 年4 月1 日，查詢時間區(qū)間T為1、3、6、9、12 周；對于blogs 數(shù)據(jù)集，設置查詢的起始時間為2004 年1 月1 日，查詢時間區(qū)間T為5、10、20、50 周。

圖4 給出了在內(nèi)存存儲數(shù)據(jù)情況下改變查詢時間區(qū)間后的查詢耗時對比。由圖4 可以看出，當數(shù)據(jù)全部存在于內(nèi)存時，TS_Pruning 算法運行時間開銷最低，這是由于在查詢條件相同的情況下TS_Pruning 算法掃描路徑更少，TS_Mining 算法不需要多次迭代掃描數(shù)據(jù)集，因此相比Apriori 算法查詢耗時約減少了2 個數(shù)量級，具有明顯的效率提升。

圖4 改變查詢時間區(qū)間后的查詢耗時對比Fig.4 Comparison of query time consumption after changing the query time interval

圖5給出了在磁盤加載數(shù)據(jù)情況下改變查詢時間區(qū)間后的加載與查詢總耗時對比。由圖5可以看出，查詢所需數(shù)據(jù)需要從磁盤中加載到內(nèi)存，基于F-Tree的算法相對于Apriori算法具有大幅的效率提升，但由于查詢?nèi)蝿盏暮臅r主要在數(shù)據(jù)加載到內(nèi)存的過程中，因此TS_Mining與TS_Pruning算法的總耗時差別并不明顯。對于twitter 數(shù)據(jù)集和blogs 數(shù)據(jù)集，設置查詢閾值θ為10、20、50、100、200。圖6給出了在twitter數(shù)據(jù)集和blogs數(shù)據(jù)集下的查詢耗時對比，由兩個數(shù)據(jù)集中的運行結果顯示，TS_Pruning算法的查詢效率高于Apriori算法。

圖5 改變查詢時間區(qū)間后的加載與查詢總耗時對比Fig.5 Comparison of loading and total query time consumption after changing the query time interval

圖6 改變查詢閾值后的查詢耗時對比Fig.6 Comparison of query time consumption after changing the query threshold

通過以上實驗結果可以看出，本文提出的TS_Mining 算法和TS_Pruning 算法能夠較好地適應不同需求的查詢問題，在不同查詢閾值和查詢時間區(qū)間的應用場景下均能保持更好的查詢效率。

為驗證本文算法在實際應用場景中的可用性，除了算法查詢時間外，還統(tǒng)計了基于Apriori 和F-Tree 算法的內(nèi)存和磁盤存儲開銷。在所有數(shù)據(jù)及索引全部存儲于內(nèi)存的應用場景下，基于F-Tree 的算法的內(nèi)存存儲開銷約為Apriori 算法的3 倍，如表2 所示。

表2 Apriori 與F-Tree 的內(nèi)存存儲開銷Table 2 Memory storage overhead of Apriori and F-Tree

如表3 所示，當數(shù)據(jù)量較大需要在磁盤中進行存儲時，F(xiàn)-Tree 索引的存儲方式在磁盤存儲開銷上相對原始文本大小約有5 至6 倍的增長，但隨著磁盤存儲價格的不斷降低，在外存存儲的方式還是能夠被接受的。對兩類算法實時加載的最大內(nèi)存消耗進行統(tǒng)計，如圖7 所示，在實時加載數(shù)據(jù)的應用場景下，基于F-Tree 的算法內(nèi)存消耗約為Apriori 算法的4 倍。然而，由于對于連續(xù)時間區(qū)間查詢而言，只需逐次加載一個單位時間區(qū)間內(nèi)的數(shù)據(jù)并進行挖掘，內(nèi)存消耗僅與單位時間區(qū)間內(nèi)數(shù)據(jù)量有關，與總數(shù)據(jù)集大小和查詢條件的設置無關。

表3 F-Tree 磁盤存儲開銷Table 3 Disk storage overhead of F-Tree

圖7 實時加載的最大內(nèi)存消耗Fig.7 Maximum memory consumption for real-time loading

5 結束語

本文研究連續(xù)時間區(qū)間內(nèi)的頻繁詞序列挖掘問題，通過改進后綴樹結構提出基于頻率樹的快速頻繁詞序列挖掘算法。針對連續(xù)時間區(qū)間內(nèi)的頻繁詞序列查詢問題，設計改進的剪枝挖掘算法進一步提升頻繁詞序列挖掘效率。實驗結果表明，本文提出的基于頻率樹的快速頻繁詞序列挖掘算法和改進的剪枝挖掘算法在不同的應用場景下的查詢效率均明顯優(yōu)于傳統(tǒng)Apriori 挖掘算法。后續(xù)將針對頻率樹的外存存儲代價問題進行優(yōu)化，通過壓縮頻率樹索引和改進后綴樹加載效率，進一步提高整體查詢和加載效率。