一種串數據詞典的有序構造及檢索方法
2023-06-03 13:18:36 3
一種串數據詞典的有序構造及檢索方法
【專利摘要】一種串數據詞典的有序構造及檢索方法，本發明包括：S1、將串數據逐一輸入到一個臨時迸發樹中；S2、當臨時迸發樹中數據量達到閾值條件時，將其合併入最終迸發樹中；S3、將最終迸發樹轉換為六元組結構有限狀態轉換器；S4、將六元組結構有限狀態轉換器編譯為三數組結構形式；S5、根據應用需求，利用編譯後的三數組結構有限狀態轉換器實現對數據詞典的檢索或順序遍歷。利用本發明，能夠對上千萬數據項進行高效的詞典構造，同時滿足不同環境和應用中的檢索需求。
【專利說明】一種串數據詞典的有序構造及檢索方法
【技術領域】
[0001]本發明涉及信息檢索、自然語言處理和模式識別與匹配領域，尤其是一種適用於任意規模串數據的詞典的有序構造及檢索方法。
【背景技術】
[0002]針對串數據的詞典構造與檢索一直是信息檢索、自然語言處理和模式識別與匹配等領域很多應用中的重要技術環節，詞典的構造與檢索速度很大程度上決定了應用系統的整體性能。例如:搜尋引擎中倒排索引項的定位、文本處理中的分詞及同義詞替換、文本編輯器中的拼寫檢查、輸入法中的文本聯想等環節對相應詞典的構造和檢索性能要求都非常聞。
[0003]由於詞典的構造和檢索在實際應用中的關鍵性地位，受到大量業內人士的關注，因此對於該問題的研究成果也較豐富。現今常用的串數據詞典的結構和表示方式包括線性表、二叉樹、檢索樹和散列表。
[0004]線性表是一種將數據的鍵在邏輯上依次存儲的數據結構。當對數據進行無序約束存儲時，每次檢索的最差時間複雜度為0(n)(其中η為已知的不重複數據項數量，下文同)，效率很低，無法滿足高速檢索要求；當數據以有序約束存儲時，配合二分查找算法，每次檢索的最差時間複雜度降低為0(lOg2n)，在可接受範圍內，但每次對詞典條目增加或刪除操作的最差時間複雜度上升為0(η)，效率低下。
[0005]二叉樹是一種將表示數據鍵的節點按層次邏輯存儲的數據結構。其一般約束為任意節點至多有左或右子節點各一個，其鍵大於其左子節點且小於其右子節點。使用該數據結構的詞典在增加、刪除和檢索條目過程中的時間消耗通常與樹的最大高度成正比，因此對樹高的控制尤為重要。現今較為成熟的樹高控制策略包括B樹、B+樹、紅黑樹等，使用得當的情況下可將每次操作的最差時間複雜度近似等於0(lOg2n)。雖然相對線性表其速度有一定程度的提升，但仍然無法滿足大規模數據環境下的速度要求，另外當以串數據為鍵時由於需將所有相應串數據完整保存在每個節點中因此造成很大的存儲空間浪費，同時最差時間複雜度增加到0(lXlog2n)(其中I為串數據長度，下文同)。
[0006]對於詞典應用而言，檢索為其最重要的功能，尤其在自然語言處理類應用中，需要頻繁的在詞典中進行檢索以獲取條目信息，因此串數據的檢索效率對於詞典方法來說是一個非常重要的評價指標。
[0007]檢索樹是一種以對串數據鍵進行優化為目標的數據結構，其中以串數據中每一數據單元為一節點，將各節點按層次邏輯存儲。其經典實現為指針結構的TRIE樹，在合適的環境下使用可以具有很高的效率，其增加、刪除和檢索條目的時間消耗通常只與I成正比。相對線性表與二叉樹結構，速度有大幅提高，最差時間複雜度可以近似等於0(1)。但是由於很多情況下TRIE樹中大多數節點的分支節點很少，因此其空間浪費非常多，在千萬數量級的應用中，幾乎無法在計算機內存中進行高速操作；另外，當分支節點非常多時，在分支節點間進行二分查找又會增加更多的時間開銷。先前有研究者提出將TRIE樹轉換為雙數組結構，令其空間浪費大幅減少，並優化了分支節點檢索過程，使其查詢速度完全等於0(1)，能夠滿足大部分應用環境下的高速檢索需求。然而，在查詢串模糊匹配或聯想輸入等應用環境下需要對字典有序遍歷，而雙數組結構TRIE樹無法實現高效的有序遍歷，最差時間複雜度為O (η2 X I)，幾乎無法在真實環境下使用。
[0008]基於散列表的詞典機制就是構造一種哈希函數來計算詞語的散列值，採用合理的哈希函數可儘量控制散列值分布的均勻性從而避免衝突，當遇到衝突時將散列值相同的詞放入一個線性表結構存儲。檢索時先使用哈希函數計算查詢串的散列值，進而取值，當遇到衝突時則在相應的線性表內進行二分查找，因此當第一次散列值計算不成功時，散列表的查詢性能會大幅下降，所以散列表詞典的性能關鍵即為哈希函數的設計。在完美哈希函數設計的研究成果中，生成完美哈希函數所用的時間開銷通常很高，即便在Linux系統下最著名的完美哈希函數生成器Gperf，也無法保證在大規模數據下仍然能生成完美哈希函數，當詞典條目超過15000個時其散列性能很差，尤其對類似中文的多字節大字符集語言的處理效果更差。另一方面，由於哈希函數的設計目標為均勻分布，因此通常無法保證詞典條目的有序性，進行有序遍歷時需對所有詞典條目先行排序，從效率方面來看幾乎無法實際應用。
【發明內容】
[0009]本發明的目的是提供一種構造及檢索效率高、能滿足不同應用環境下對詞典有序性和靈活性的要求，且同時仍保持較少空間佔用的串數據的有序構造及檢索方法。
[0010]本發明解決現有技術問題所採用的技術方案:一種串數據詞典的有序構造及檢索方法，包括以下步驟:
[0011]S1、將串數據逐一輸入到臨時迸發樹中:通過數據採集系統採集到的文檔集合進行處理並讀取其中的串數據，根據串數據中的字節序列創建臨時迸發樹並將其初始化，將串數據逐一輸入到初始化狀態的臨時迸發樹中並將其更新；
[0012]S2、將臨時迸發樹合併入最終迸發樹:預先創建空的最終迸發樹，當臨時迸發樹中的串數據量達到閾值條件時，將臨時迸發樹中的串數據合併入最終迸發樹中；此時，若文檔集合中尚有未處理的串數據，則將臨時迸發樹中的內容清空，將未處理的串數據按照Si步驟輸入到臨時迸發樹中；若文檔集合中的所有串數據均處理完畢，則將臨時迸發樹及其內部數據全部釋放；
[0013]S3、將最終迸發樹轉換為六元組結構有限狀態轉換器:按詞典順序遍歷最終迸發樹的各個節點，對於最終迸發樹的每個分支所表示的詞典條目首先將其分支最末端節點所存儲的統計數據保存至外存並記錄其外存地址，將各分支對應的字節序列作為鍵而將所述外存地址作為值，並以鍵值對的形式添加入有限狀態轉換器中，最後判斷有限狀態轉換器中的鍵值對數據是否滿足保存條件，若滿足保存條件則以六元組的形式保存並繼續遍歷；所述六元組由字節內容、同父狀態序號、子狀態數量、首個子狀態序號、狀態輸出值、是否為終止狀態組成；
[0014]S4、將六元組結構有限狀態轉換器構造成為三數組結構有限狀態轉換器:遍歷六元組有限狀態轉換器中的鍵值對數據，將六元組有限狀態轉換器編譯為以三數組為主配合輔助表的數據結構存儲，所述三數組由基地址數組、狀態輸入數組和同源狀態數組組成；所述輔助表為不同字節輸入對應的內碼錶、子狀態表核狀態輸出表，其中，內碼錶由對所述六元組中字節內容進行順序編碼而獲得，所述子狀態表由所述六元組中的首個子狀態號獲得，狀態輸出表由所述六元組中的狀態輸出值和是否為終止狀態內容獲得；
[0015]S5、根據應用需求，利用編譯後的三數組結構有限狀態轉換器對數據詞典做檢索或順序遍歷:在對串數據進行檢索時，將查詢串的字節序列依次作為輸入變量，參照內碼錶及狀態輸出表中當前輸入變量的內碼以及當前狀態序號在基地址數組中尋找後續狀態，循環操作直至可判斷該狀態是否存在，並讀取狀態輸出表將循環中所有狀態輸出值的和輸出；在遍歷需求應用中，利用路徑狀態棧，通過同源狀態數組和各輔助表中數據在基地址數組中進行詞典順序尋址，並配合狀態輸出表，完成詞典遍歷。
[0016]當串數據在輸入臨時迸發樹前，按串數據中字節序列依次生成對應的新分支節點以及迸發節點，並將該分支末端存儲的統計數據初始化；當串數據輸入臨時迸發樹時，按串數據中字節序列依次檢索，得到相應分支末端存儲的統計數據並將其更新。
[0017]步驟S4中所述基地址數組、狀態輸入數組和同源狀態數組中的每個元素均對應有限狀態轉換器中的一個狀態，且各數組中相同地址的元素對應同一狀態，基地址數組中元素存儲對應狀態所有子狀態的地址基礎值，同源狀態數組中元素存儲對應狀態緊鄰的下一同源狀態輸入變量的內碼，狀態輸入數組中元素存儲對應狀態輸入變量的內碼，內碼錶記錄所有已出現輸入變量到其內碼的映射，子狀態表記錄各內部狀態的首個子狀態輸入變量的內碼，狀態輸出表記錄相應詞典條目對應的值或數據地址。
[0018]步驟S3中在有限狀態轉換器中插入鍵和值方法為:對鍵的字節序列依次遍歷，若當前字節對應的狀態已存在則進而判斷若當前值小於該狀態的輸出值，則將該狀態的輸出值減去當前值，並將該狀態所有子狀態的輸出值加上差值，最後將當前值設為0，否則將當前值減去該狀態的輸出值；若當前字節對應的狀態不存在，則創建該狀態，並將該狀態的輸出值設為當前值，最後將當前值設為O ;當需要向有限狀態轉換器中插入新狀態時，先按步驟S4中狀態編譯過程檢測是否有衝突，若無衝突則可在三數組和六元組結構中同時插入該狀態的相應數據；否則將該狀態的相應數據插入六元組結構有限狀態轉換器中，當所有插入操作完成後，按步驟S4重新編譯為三數組結構；當需要將有限狀態轉換器中已有狀態刪除時，直接將三數組結構和六元組結構中相應的狀態數據設置為O即可。
[0019]所述保存條件為:當某個已存在狀態的同源狀態被創建時，該狀態及其所有在內存中的子分支均可以六元組的形式保存並釋放相應的內存空間。
[0020]三數組數據結構有限狀態轉換器的構造方法如下:
[0021]在對六元組結構形式有限狀態轉換器中各狀態進行編譯的過程中，假設有狀態W…、Ym，相應的輸出值分別為y1、y2、…、ym，其父狀態均為X ;如果存在一正整數k使得對於任意正整數i (1屬於[1，111])均滿足:
[0022]aisne [k] =0，base [k+code [Yi] ] =0
[0023]則令:
[0024]label [k+code [Yi] ] =code [Yi], sib [k+code [Yi] ] =Yi+!, output [k+code [Yi] ] =Yi
[0025]且當X狀態為可結束狀態時，令:
[0026]base [X] =_k
[0027]否則，令:[0028]base [X] =k
[0029]通常情況下應令k為能滿足衝突檢測條件的最小正整數。
[0030]步驟S5中利用基地址數組和狀態輸入數組進行查詢串檢索，或利用基地址數組和同源狀態數組以及各輔助表進行詞典序遍歷，並配合狀態輸出表，輸出對應詞典條目及其統計數據的外存地址。
[0031]在步驟S4中將所述六元組結構有限狀態轉換器構造成為三數組結構的過程中，按照廣度優先策略並利用貪心策略每次選擇子狀態數量最多的狀態進行編譯，具體方法為:
[0032](A)創建候選狀態優先隊列，優先順序為狀態直接子狀態數降序；
[0033](B)將有限狀態轉換器的起始狀態加入優先隊列；
[0034](C)從優先隊列中彈出隊首狀態進行編譯，並將其所有直接子狀態加入優先隊列；
[0035](D)如果優先隊列不為空，則重複步驟(C);否則構造結束。
[0036]當需要在詞典中檢索指定詞時，僅使用三數組結構即可完成，步驟如下:
[0037](al)將檢索詞轉換為字節序列word且序列長度為I,令i=0、x=0、v=0 ；
[0038](bl)若滿足 label [ | base [x] | +code [word[i] ] ] =code [word[i]]，則令
[0039]X= I base [x] |+code [word[i] ]、v=v+output [x];否則，指定詞不存在，檢索失敗；
[0040](cl)令i=i+l,若i小於I,則轉至步驟(bl);否則若base[x] < O,檢索成功,返回V值用於對詞統計信息的尋址；否則，指定詞不存在，檢索失敗。
[0041]當需要對詞典進行有序遍歷時，步驟如下:
[0042](a2)創建路徑狀態棧,令x=0、v=output [O],將x入棧；
[0043](b2)若base[x] ( 0，則輸出當前狀態棧中路徑及V值；
[0044](c2)若 base[x]古 O,則令 x= | base [x] |+asine [base [x]],將 x 入棧，令
[0045]v=v+output[x],轉至步驟(b2);否貝U,將x從路徑狀態棧中彈出，令v=v-output [X];若 sib [X] Φ label [x],則令 x=x_label [x] +sib [x]、v=v+output [x],將 x入棧，轉至步驟(b2);否則，若當前路徑狀態棧不為空，則令X為其首狀態，轉至步驟(c2)；否則，遍歷結束。
[0046]本發明的有益效果在於:1.本發明使用迸發樹代替常用的TRIE樹，並利用臨時迸發樹和最終迸發樹進行兩階段的詞典構造，有效降低了詞典條目添加和更新過程中的時間消耗，同時保證了詞典的有序形式，另外較傳統TRIE樹大幅降低了詞典在構造過程中的內存佔用。在單機環境中(CPU為雙核3.0GHz,內存為3G，下文同)，對於Lucene工具的說明文檔共80.1MB數據建立詞典，共佔用內存13794KB，為TRIE樹結構內存佔用的43% ;共消耗時間4.95秒，為TRIE樹結構時間消耗的89% ；
[0047]2.本發明提出的將詞典先使用迸發樹結構存儲後經過轉換和編譯最終表示為三數組結構有限狀態轉換器的方法，可以對任意規模的串數據成功構造詞典，尤其是該構造過程可以完全適應各種字符集或編碼的文本，甚至是實值向量，保證了詞典構造和使用的靈活性。
[0048]3.本發明構造的三數組結構有限狀態轉換器，較傳統的雙數組結構TRIE，在保證有等效的檢索速度的同時，彌補了其丟棄詞典順序信息而造成無法對詞典進行順序遍歷的缺陷。對於Lucene工具的說明文檔共80.1MB數據建立的詞典，共包含16698個詞典條目，在單機環境中，遍歷一次僅需26.2毫秒，為TRIE樹結構時間消耗的19%。更進一步的，使用本發明構造的三數組結構有限狀態轉換器，不但能在線性時間內進行詞典順序遍歷，而且能夠直接檢索到任意狀態其所有子狀態數據在外存中的地址區間，滿足了大量模糊模式匹配應用的需求。
[0049]4.本發明構造的三數組結構有限狀態轉換器能夠提供高效的詞典檢索操作，檢索一個詞只需要計算I次簡單的整數相加和邏輯判斷即可，而與詞典中所存條目數量無關。對於Lucene工具的說明文檔共80.1MB數據建立的詞典，共包含16698個詞典條目，在單機環境中，平均每秒可檢索隨機詞189.7萬次，同時數據空間利用率為90.3%。。
【專利附圖】
【附圖說明】
[0050]圖1為本發明提出的一種任意規模串數據詞典的有序構造與檢索方法的流程圖。
[0051]圖2為臨時迸發樹結構示意圖。
[0052]圖3為最終迸發樹結構示意圖。
[0053]圖4為由最終迸發樹到六元組結構有限狀態轉換器的轉換過程示意圖。
[0054]圖5為本發明提出的三數組結構有限狀態轉換器的數據結構示意圖。
【具體實施方式】
[0055]以下結合附圖及【具體實施方式】對本發明進行說明:
[0056]一種串數據詞典的有序構造及檢索方法，包括如下步驟:
[0057]步驟1、將串數據逐一輸入到臨時迸發樹中:迸發樹的形式如圖2所示:將通過數據採集系統採集到的文檔集合進行處理並讀取其中的串數據，在串數據輸入臨時迸發樹前，按串數據中字節序列以空的臨時迸發節點為根依次生成對應的新分支節點以及迸發節點，並將該分支末端存儲的統計數據初始化；然後將該串數據輸入臨時迸發樹中，此時按串數據中字節序列依次檢索，得到相應分支末端存儲的統計數據並將其更新；
[0058]步驟2、將臨時迸發樹合併入最終迸發樹:預先創建空的最終迸發樹，當臨時迸發樹中數據量達到閾值條件時，將其合併入最終迸發樹中，其形式如圖3所示；此時，若文檔集合中尚有未處理的串數據，則將臨時迸發樹內容清空，用於繼續添加後續數據，並轉至步驟I ;否則，將臨時迸發樹及其內部數據全部釋放，迸發樹構造過程結束；此時，最終迸發樹已為一有序詞典，但其檢索效率並不高，因此需將其轉換為效率更高的有限狀態轉換器。轉至步驟3:
[0059]步驟3、將最終迸發樹轉換為六元組結構有限狀態轉換器:具體過程包括:按詞典順序遍歷最終迸發樹的各個節點，對於最終迸發樹的每個分支所表示的詞典條目首先將其分支最末端節點所存儲的統計數據保存至外存並記錄其外存地址，將各分支對應的字節序列作為鍵而將所述外存地址作為值，並以鍵值對的形式添加入有限狀態轉換器中，最後判斷有限狀態轉換器中的鍵值對數據是否滿足保存條件，若滿足保存條件則以六元組的形式保存並繼續遍歷；六元組由字節內容、同父狀態序號、子狀態數量、首個子狀態序號、狀態輸出值、是否為終止狀態六項參數據組成；
[0060]在有限狀態轉換器中插入鍵和值方法為:對鍵的字節序列依次遍歷，若當前字節對應的有限狀態轉換器中的同父狀態序號、子狀態數量、首個子狀態序號、是否為終止狀態已存在，而當前值小於該狀態的輸出值，則將該狀態的對應的輸出值減去當前值，並將該狀態所有子狀態的輸出值(子狀態數量、首個子狀態序號)加上差值，最後將當前值設為O，否則將當前值減去該狀態的輸出值；若當前字節對應的狀態不存在，即六元組中的同父狀態序號、子狀態數量、首個子狀態序號、是否為終止狀態不存在，則創建該狀態，並將該狀態的輸出值設為當前值，最後將當前值設為O ;
[0061]其中，保存六元組的條件為:當某已存在狀態的同源狀態被創建時，該狀態及其所有在內存中的子分支均可以六元組的形式輸出並釋放相應的內存空間，因此，同一時刻只有一條分支實際存在於內存中，大大降低了有限狀態轉換器構造時的內存消耗； [0062]步驟4、將六元組結構有限狀態轉換器構造成為三數組結構有限狀態轉換器:遍歷六元組有限狀態轉換器中的鍵值對數據，將六元組有限狀態轉換器編譯為以三數組為主配合輔助表的數據結構存儲，其中，三數組由基地址數組、狀態輸入數組和同源狀態數組組成；輔助表為不同字節輸入對應的內碼錶、子狀態表核狀態輸出表，其中，內碼錶由對六兀組中字節內容進行順序編碼而獲得，子狀態表由所述六元組中的首個子狀態號獲得，狀態輸出表由所述六元組中的狀態輸出值和是否為終止狀態內容獲得；
[0063]具體地，使用base、label和sib分別代表基地址數組、狀態輸入數組和同源狀態數組，另外使用code、aisne和output分別代表內碼錶、子狀態表和狀態輸出表；
[0064]三個數組中的每個元素均對應有限狀態轉換器中的一個狀態，且各數組中相同地址的元素對應同一狀態，base數組中元素存儲對應狀態所有子狀態的地址基礎值，label數組中元素存儲對應狀態輸入字節的內碼，sib數組中元素存儲對應狀態緊鄰的下一同源狀態輸入字節的內碼，code中記錄所有已出現輸入變量到其內碼的映射，aisne中記錄各內部狀態的首個子狀態輸入變量的內碼，output中記錄相應詞典條目對應的值或數據地址；由此可知，當base [i]和label [i]的值均為O時，表示該位置沒有對應的狀態，否則為對應的狀態已存在；三數組數據結構的構造方法如下:
[0065]在狀態編譯過程中，假設有狀態YpY2、…、Ym，相應的輸出值分別為y1、y2、…、ym，其父狀態均為X ;如果存在一正整數k使得對於任意正整數i (i屬於[1，!11])均滿足:
[0066]aisne [k] =0，base [k+code [Yi] ] =0
[0067]則令:
[0068]label [k+code [Yi] ] =code [Yi], sib [k+code [Yi] ] =Yi+!, output [k+code [Yi] ] =Yi
[0069]且當X狀態為可結束狀態時，令:
[0070]base [X] =-k
[0071]否則，令:
[0072]base [X] =k
[0073]通常情況下應令k為能滿足衝突檢測條件的最小正整數；
[0074]在編譯狀態的選擇過程中，可以使用廣度優先或深度優先策略進行，但兩者都會使得構造後的數組存在較大的數據稀疏性。為進一步減少數組空間浪費，本發明提出了一種選擇編譯狀態的優化策略:三數組構造過程的時間消耗以及最終結構的數據稀疏性都與狀態編譯過程中衝突次數成正比，而一個狀態的直接子狀態越多則其編譯時遇到衝突的可能性也就越大，因此本發明在步驟4中在廣度優先策略的基礎上使用貪心策略進行優化，即每次均選擇所有候選狀態中直接子狀態數最多的狀態編譯；優化的具體方法如下:
[0075](A)創建候選狀態優先隊列，優先順序為狀態直接子狀態數降序；
[0076](B)將有限狀態轉換器的起始狀態加入優先隊列；
[0077](C)從優先隊列中彈出隊首狀態進行編譯，並將其所有直接子狀態加入優先隊列；
[0078](D)如果優先隊列不為空，則重複步驟C ;否則構造結束。
[0079]根據應用需求，可利用六元組有限狀態轉換器和三數組有限狀態轉換器配合實現對數據詞典條目的添加和刪除，同時可利用編譯後的三數組結構有限狀態轉換器實現對數據詞典的快速檢索和遍歷。當需要向有限狀態轉換器中插入新狀態時，應先按步驟4中狀態編譯過程檢測是否衝突，若無衝突則可在三數組結構和六元組結構同時插入該狀態的相應數據；否則將該狀態的相應數據插入六元組結構有限狀態轉換器中，當所有插入操作完成後，按步驟4重新編譯為三數組結構。
[0080]當需要將有限狀態轉換器中已有狀態刪除時，直接將三數組結構和六元組結構相應的狀態數據設置為O即可。
[0081]步驟5、根據應用需求，利用編譯後的三數組結構有限狀態轉換器對數據詞典做檢索或順序遍歷:在對串數據進行檢索時，將查詢串的字節序列依次作為輸入變量，參照內碼錶及狀態輸出表中當前輸入變量的內碼以及當前狀態序號在基地址數組中尋找後續狀態，循環操作直至可判斷該狀態是否存在，並讀取狀態輸出表將循環中所有狀態輸出值的和輸出；在遍歷需求應用中，利用路徑狀態棧，通過同源狀態數組和各輔助表中數據在基地址數組中進行詞典順序尋址，並配合狀態輸出表，完成詞典遍歷。
[0082]當需要在詞典中檢索指定詞時，僅使用三數組結構即可完成，步驟如下:
[0083](al)將檢索詞轉換為字節序列word且序列長度為I,令i=0、x=0、v=0 ；
[0084](bl)若滿足 label [ | base [x] | +code [word[i] ] ] =code [word[i]]，則令
[0085]X= I base [x] |+code [word[i] ]、v=v+output [x];否則，指定詞不存在，檢索失敗；
[0086](cl)令i=i+l,若i小於I,則轉至步驟(bl);否則若base[x] < O,檢索成功,返回V值用於對詞統計信息的尋址；否則，指定詞不存在，檢索失敗。
[0087]當需要對詞典進行有序遍歷時，步驟如下:
[0088](a2)創建路徑狀態棧,令x=0、v=output [O],將x入棧；
[0089](b2)若base[x] ( 0，則輸出當前狀態棧中路徑及V值；
[0090](c2)若 base[x]古 O,則令 x= | base [x] |+asine [base [x]],將 x 入棧，令
[0091]v=v+output [x],轉至步驟(b2)；否貝丨』，將x從路徑狀態棧中彈出，令v=v-output [X];若 sib [X] Φ label [x],則令 x=x_label [x] +sib [x]、v=v+output [x],將 x入棧，轉至步驟(b2);否則，若當前路徑狀態棧不為空，則令X為其首狀態，轉至步驟(c2)；否則，遍歷結束。
[0092]實施例:
[0093]為使本發明的目的、技術方案和有益效果更加清晰和更易於實施，以下結合具體實施例，並參照附圖，對本發明做進一步詳細說明。
[0094]假設現有2個待處理文檔，內容如表1所示:
[0095]表1待處理文檔內容[0096]
【權利要求】
1.一種串數據詞典的有序構造及檢索方法，其特徵在於，包括以下步驟: 51、將串數據逐一輸入到臨時迸發樹中:通過數據採集系統採集到的文檔集合進行處理並讀取其中的串數據，根據串數據中的字節序列創建臨時迸發樹並將其初始化，將串數據逐一輸入到初始化狀態的臨時迸發樹中並將其更新； 52、將臨時迸發樹合併入最終迸發樹:預先創建空的最終迸發樹，當臨時迸發樹中的串數據量達到閾值條件時，將臨時迸發樹中的串數據合併入最終迸發樹中；此時，若文檔集合中尚有未處理的串數據，則將臨時迸發樹中的內容清空，將未處理的串數據按照SI步驟輸入到臨時迸發樹中；若文檔集合中的所有串數據均處理完畢，則將臨時迸發樹及其內部數據全部釋放； 53、將最終迸發樹轉換為六元組結構有限狀態轉換器:按詞典順序遍歷最終迸發樹的各個節點，對於最終迸發樹的每個分支所表示的詞典條目首先將其分支最末端節點所存儲的統計數據保存至外存並記錄其外存地址，將各分支對應的字節序列作為鍵而將所述外存地址作為值，並以鍵值對的形式添加入有限狀態轉換器中，最後判斷有限狀態轉換器中的鍵值對數據是否滿足保存條件，若滿足保存條件則以六元組的形式保存並繼續遍歷；所述六元組由字節內容、同父狀態序號、子狀態數量、首個子狀態序號、狀態輸出值、是否為終止狀態組成； 54、將六元組結構有限狀態轉換器構造成為三數組結構有限狀態轉換器:遍歷六元組有限狀態轉換器中的鍵值對數據，將六元組有限狀態轉換器編譯為以三數組為主配合輔助表的數據結構存儲，所述三數組由基地址數組、狀態輸入數組和同源狀態數組組成；所述輔助表為不同字節輸入對應的內碼錶、子狀態表核狀態輸出表，其中，內碼錶由對所述六兀組中字節內容進行順序編碼 而獲得，所述子狀態表由所述六元組中的首個子狀態號獲得，狀態輸出表由所述六元組中的狀態輸出值和是否為終止狀態內容獲得； 55、根據應用需求，利用編譯後的三數組結構有限狀態轉換器對數據詞典做檢索或順序遍歷:在對串數據進行檢索時，將查詢串的字節序列依次作為輸入變量，參照內碼錶及狀態輸出表中當前輸入變量的內碼以及當前狀態序號在基地址數組中尋找後續狀態，循環操作直至可判斷該狀態是否存在，並讀取狀態輸出表將循環中所有狀態輸出值的和輸出；在遍歷需求應用中，利用路徑狀態棧，通過同源狀態數組和各輔助表中數據在基地址數組中進行詞典順序尋址，並配合狀態輸出表，完成詞典遍歷。
2.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特徵在於，當串數據在輸入臨時迸發樹前，按串數據中字節序列依次生成對應的新分支節點以及迸發節點，並將該分支末端存儲的統計數據初始化；當串數據輸入臨時迸發樹時，按串數據中字節序列依次檢索，得到相應分支末端存儲的統計數據並將其更新。
3.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特徵在於，步驟S4中所述基地址數組、狀態輸入數組和同源狀態數組中的每個元素均對應有限狀態轉換器中的一個狀態，且各數組中相同地址的元素對應同一狀態，基地址數組中元素存儲對應狀態所有子狀態的地址基礎值，同源狀態數組中元素存儲對應狀態緊鄰的下一同源狀態輸入變量的內碼，狀態輸入數組中元素存儲對應狀態輸入變量的內碼，內碼錶記錄所有已出現輸入變量到其內碼的映射，子狀態表記錄各內部狀態的首個子狀態輸入變量的內碼，狀態輸出表記錄相應詞典條目對應的值或數據地址。
4.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特徵在於，步驟S3中在有限狀態轉換器中插入鍵和值方法為:對鍵的字節序列依次遍歷，若當前字節對應的狀態已存在則進而判斷若當前值小於該狀態的輸出值，則將該狀態的輸出值減去當前值，並將該狀態所有子狀態的輸出值加上差值，最後將當前值設為O，否則將當前值減去該狀態的輸出值；若當前字節對應的狀態不存在，則創建該狀態，並將該狀態的輸出值設為當前值，最後將當前值設為O ;當需要向有限狀態轉換器中插入新狀態時，先按步驟S4中狀態編譯過程檢測是否有衝突，若無衝突則可在三數組和六元組結構中同時插入該狀態的相應數據；否則將該狀態的相應數據插入六元組結構有限狀態轉換器中，當所有插入操作完成後，按步驟S4重新編譯為三數組結構；當需要將有限狀態轉換器中已有狀態刪除時，直接將三數組結構和六元組結構中相應的狀態數據設置為O即可。
5.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特徵在於，所述保存條件為:當某個已存在狀態的同源狀態被創建時，該狀態及其所有在內存中的子分支均可以六元組的形式保存並釋放相應的內存空間。
6.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特徵在於，三數組數據結構有限狀態轉換器的構造方法如下: 在對六元組結構形式有限狀態轉換器中各狀態進行編譯的過程中，假設有狀態YpY2>…、Ym，相應的輸出值分別為y1、y2、…、ym，其父狀態均為X ;如果存在一正整數k使得對於任意正整數i (1屬於[1，111])均滿足:aisne[k]=0，base[k+code[Yi] ] =0則令:
label [k+ code [Yi] ] = code [Yi], sib [k+ code [Yi] ] = Yi+1, output [k+ code [Yi] ] =Yi 且當X狀態為可結束狀態時，令:
base[X]=_k 否則，令:
base[X]=k 通常情況下應令k為能滿足衝突檢測條件的最小正整數。
7.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特徵在於，步驟S5中利用基地址數組和狀態輸入數組進行查詢串檢索，或利用基地址數組和同源狀態數組以及各輔助表進行詞典序遍歷，並配合狀態輸出表，輸出對應詞典條目及其統計數據的外存地址。
8.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特徵在於，在步驟S4中將所述六元組結構有限狀態轉換器構造成為三數組結構的過程中，按照廣度優先策略並利用貪心策略每次選擇子狀態數量最多的狀態進行編譯，具體方法為: (A)創建候選狀態優先隊列，優先順序為狀態直接子狀態數降序； (B)將有限狀態轉換器的起始狀態加入優先隊列； (C)從優先隊列中 彈出隊首狀態進行編譯，並將其所有直接子狀態加入優先隊列； (D)如果優先隊列不為空，則重複步驟(C);否則構造結束。
9.根據權利要求1所述的一種串數據詞典的有序構造及檢索方法，其特徵在於，當需要在詞典中檢索指定詞時，僅使用三數組結構即可完成，步驟如下:(al)將檢索詞轉換為字節序列word且序列長度為I,令i=0、x=0、v=0 ； (bl)若滿足 label[I base[x] I+code[word[i]]]=code[word[i]],則令X= I base [x] |+code [word[i] ]、v=v+output [x];否則，指定詞不存在,檢索失敗； (cl)令i=i+l,若i小於I,則轉至步驟(bl);否則若base[x] ( O,檢索成功,返回V值用於對詞統計信息的尋址；否則，指定詞不存在，檢索失敗； 當需要對詞典進行有序遍歷時，步驟如下: (a2)創建路徑狀態棧,令x=0、v=output [O],將x入棧； (b2)若base[x] ( 0，則輸出當前狀態棧中路徑及V值； (c2)若 base[x]幸 O,則令 x= |base [x] |+asine[base[x]],將 x 入棧，令v=v+output [x],轉至步驟(b2);否則，將X從路徑狀態棧中彈出，令V=V-Output [X];若sib [X] Φ.label [x]，則令 x=x_label [x] +sib [x]、v=v+output [x]，將 x 入棧，轉至步驟(b2);否則，若當前路徑狀態棧不為 空，則令X為其首狀態，轉至步驟(c2);否則，遍歷結束。
【文檔編號】G06F17/30GK103761270SQ201410006131
【公開日】2014年4月30日 申請日期:2014年1月6日 優先權日:2014年1月6日
【發明者】馬雲龍, 林鴻飛 申請人:大連理工大學