[發明專利]一種串數據詞典的有序構造及檢索方法

有效

• 申請號: 201410006131.0
• 申請日: 2014-01-06
• 公開（公告）號: CN103761270B
• 公開（公告）日: 2017-02-01
• 發明（設計）人: 馬云龍;林鴻飛
• 申請（專利權）人: 大連理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 大連星海專利事務所21208
• 代理人: 徐雪蓮

1.一種串數據詞典的有序構造及檢索方法，其特征在于，包括以下步驟：

S1、將串數據逐一輸入到臨時迸發樹中：通過數據采集系統采集到的文檔集合進行處理并讀取其中的串數據，根據串數據中的字節序列創建臨時迸發樹并將其初始化，將串數據逐一輸入到初始化狀態的臨時迸發樹中并將其更新；

S2、將臨時迸發樹合并入最終迸發樹：預先創建空的最終迸發樹，當臨時迸發樹中的串數據量達到閾值條件時，將臨時迸發樹中的串數據合并入最終迸發樹中；此時，若文檔集合中尚有未處理的串數據，則將臨時迸發樹中的內容清空，將未處理的串數據按照S1步驟輸入到臨時迸發樹中；若文檔集合中的所有串數據均處理完畢，則將臨時迸發樹及其內部數據全部釋放；

S3、將最終迸發樹轉換為六元組結構有限狀態轉換器：按詞典順序遍歷最終迸發樹的各個節點，對于最終迸發樹的每個分支所表示的詞典條目首先將其分支最末端節點所存儲的統計數據保存至外存并記錄其外存地址，將各分支對應的字節序列作為鍵而將所述外存地址作為值，并以鍵值對的形式添加入有限狀態轉換器中，最后判斷有限狀態轉換器中的鍵值對數據是否滿足保存條件，若滿足保存條件則以六元組的形式保存并繼續遍歷；所述六元組由字節內容、同父狀態序號、子狀態數量、首個子狀態序號、狀態輸出值、是否為終止狀態組成；?

S4、將六元組結構有限狀態轉換器構造成為三數組結構有限狀態轉換器：遍歷六元組有限狀態轉換器中的鍵值對數據，將六元組有限狀態轉換器編譯為以三數組為主配合輔助表的數據結構存儲，所述三數組由基地址數組、狀態輸入數組和同源狀態數組組成；所述輔助表為不同字節輸入對應的內碼表、子狀態表核狀態輸出表，其中，內碼表由對所述六元組中字節內容進行順序編碼而獲得，所述子狀態表由所述六元組中的首個子狀態號獲得，狀態輸出表由所述六元組中的狀態輸出值和是否為終止狀態內容獲得；?

S5、根據應用需求，利用編譯后的三數組結構有限狀態轉換器對數據詞典做檢索或順序遍歷：在對串數據進行檢索時，將查詢串的字節序列依次作為輸入變量，參照內碼表及狀態輸出表中當前輸入變量的內碼以及當前狀態序號在基地址數組中尋找后續狀態，循環操作直至可判斷該狀態是否存在，并讀取狀態輸出表將循環中所有狀態輸出值的和輸出；在遍歷需求應用中，利用路徑狀態棧，通過同源狀態數組和各輔助表中數據在基地址數組中進行詞典順序尋址，并配合狀態輸出表，完成詞典遍歷。

2.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特征在于，當串數據在輸入臨時迸發樹前，按串數據中字節序列依次生成對應的新分支節點以及迸發節點，并將該分支末端存儲的統計數據初始化；當串數據輸入臨時迸發樹時，按串數據中字節序列依次檢索，得到相應分支末端存儲的統計數據并將其更新。

3.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特征在于，步驟S4中所述基地址數組、狀態輸入數組和同源狀態數組中的每個元素均對應有限狀態轉換器中的一個狀態，且各數組中相同地址的元素對應同一狀態，基地址數組中元素存儲對應狀態所有子狀態的地址基礎值，同源狀態數組中元素存儲對應狀態緊鄰的下一同源狀態輸入變量的內碼，狀態輸入數組中元素存儲對應狀態輸入變量的內碼，內碼表記錄所有已出現輸入變量到其內碼的映射，子狀態表記錄各內部狀態的首個子狀態輸入變量的內碼，狀態輸出表記錄相應詞典條目對應的值或數據地址。

4.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特征在于，步驟S3中在有限狀態轉換器中插入鍵和值方法為：對鍵的字節序列依次遍歷，若當前字節對應的狀態已存在則進而判斷若當前值小于該狀態的輸出值，則將該狀態的輸出值減去當前值，并將該狀態所有子狀態的輸出值加上差值，最后將當前值設為0，否則將當前值減去該狀態的輸出值；若當前字節對應的狀態不存在，則創建該狀態，并將該狀態的輸出值設為當前值，最后將當前值設為0；當需要向有限狀態轉換器中插入新狀態時，先按步驟S4中狀態編譯過程檢測是否有沖突，若無沖突則可在三數組和六元組結構中同時插入該狀態的相應數據；否則將該狀態的相應數據插入六元組結構有限狀態轉換器中，當所有插入操作完成后，按步驟S4重新編譯為三數組結構；當需要將有限狀態轉換器中已有狀態刪除時，直接將三數組結構和六元組結構中相應的狀態數據設置為0即可。

5.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特征在于，所述保存條件為：當某個已存在狀態的同源狀態被創建時，該狀態及其所有在內存中的子分支均可以六元組的形式保存并釋放相應的內存空間。