[發明專利]一種挖掘最大重復序列的方法及裝置

有效

• 申請號: 201410200896.8
• 申請日: 2014-05-13
• 公開（公告）號: CN105095276B
• 公開（公告）日: 2020-04-21
• 發明（設計）人: 梁辰;范偉
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 北京中博世達專利商標代理有限公司 11274
• 代理人: 張娜

本發明實施例提供一種挖掘最大重復序列的方法及裝置，基于流水線和后綴樹確定最大重復序列，實現增量式挖掘，提高了計算效率。本發明實施例提供的挖掘最大重復序列的方法包括：獲取字符；將字符追加到流水線集合中的每個流水線中，分別判斷追加字符后的每個流水線中的序列與后綴樹上對應的序列是否相同；在流水線集合中，若存在第一流水線，在追加字符后的序列與后綴樹上對應的序列不同，則根據第一預設策略以及所述第一流水線中的序列確定最大重復序列；若存在第二流水線，在追加所述字符后的序列與后綴樹上對應的序列相同，則根據所述第二流水線的位置指針以及第二預設策略確定最大非串聯重復序列。

技術領域

本發明涉及數據挖掘領域，尤其涉及一種挖掘最大重復序列的方法及裝置。

背景技術

模式挖掘指在一組序列數據中，尋找一些特定的便于人們理解與解釋的基本序列模式，實現將所處理的長序列數據進行分解，便于后期各種建模和再分析，降低在大數據流量中人為干預的程度，提高序列處理的效率和準確度，因此，模式挖掘在以軟件控制的設備中起到了非常重要的作用，例如，模式挖掘在智能手機的用戶行為建模、傳感器數據流分析、金融系統欺詐交易識別、生物基因序列檢測等多種領域中被廣泛使用。在模式挖掘的實際應用中，人們通常將序列數據中包含最多信息且做成結構最小的序列模式-最大重復序列作為基本序列模式，但是，在模式挖掘中，有一類數據隨著時間的變化而不斷有新的數據產生，例如，手機設備所攜帶的傳感器可以記錄每時每刻用戶的位置、通話、上網瀏覽記錄等，這類數據根據時間先后順序排列，并且以序列化的方式呈現，尤其是，隨著大數據與移動互聯網的蓬勃發展，這些序列數據產生的數量和速度都成倍增長，如何從這些序列數據中實時動態地挖掘出基本序列模式(即最大重復序列)成為亟待解決的問題。

目前，挖掘序列數據中最大重復序列的方法為：根據一段時間內的序列數據建立相應的后綴樹，再在后綴上查找最大重復序列；其中，后綴樹是一種數據結構，能快速解決很多關于字符串的問題，用來支持有效的字符匹配和查詢；例如，將序列數據“abcabxa$”用圖1所示的后綴樹來表示，即后綴樹的根節點到每一個葉子節點的路徑表示序列“abcabxa$”中的每一個后綴子序列；然后，尋找存在不同左邊元素的兩個葉子節點，并標記出來；從葉子節點開始自下而上遍歷后綴樹上的每一個節點，如果一個節點下的子樹中存在已標記的節點，則此節點也被標記；如果一個節點下的子樹中沒有被標記的節點，則檢查此節點下孩子節點的左元素；如果此節點下孩子節點的左元素不同，則標記當前節點；用這個方法掃描所有節點直至根節點，并將所有非標記節點剔出，所剩下的樹就是最大重復序列；由此可知，在現有技術中，需要通過對整個后綴樹進行遍歷和標記來確定最大重復序列，且當下一時刻有新數據加入到原來的序列數據中時，除了根據后綴樹的建立規則在原有的后綴樹上增加相應的節點結構之外，之前遍歷標記的結果也需要進行重新統計和標識，即需要重新對增加節點后的后綴樹進行遍歷和標記，增大計算量。

發明內容

本發明實施例提供一種挖掘最大重復序列的方法及裝置，基于流水線和后綴樹確定最大重復序列，實現增量式挖掘，提高了計算效率。

為達到上述目的，本發明采用的技術方案是，

第一方面，本發明實施例提供一種挖掘最大重復序列的方法，包括：

獲取字符；

將所述字符追加到流水線集合中的每個流水線中，分別判斷追加所述字符后的每個流水線中的序列與后綴樹上對應的序列是否相同，其中，所述流水線集合包含至少一個流水線，所述流水線包含序列以及位置指針，所述序列包含與所述字符所在的字符串中所述字符之前的字符相同的字符，所述位置指針指向所述流水線包含的序列的尾字符在所述后綴樹上的位置；

在所述流水線集合中，若存在第一流水線，在追加所述字符后的序列與后綴樹上對應的序列不同，則根據第一預設策略以及所述第一流水線中的序列確定最大重復序列。