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

有效

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

技術領域

本發明涉及信息檢索、自然語言處理和模式識別與匹配領域，尤其是一種適用于任意規模串數據的詞典的有序構造及檢索方法。

背景技術

針對串數據的詞典構造與檢索一直是信息檢索、自然語言處理和模式識別與匹配等領域很多應用中的重要技術環節，詞典的構造與檢索速度很大程度上決定了應用系統的整體性能。例如：搜索引擎中倒排索引項的定位、文本處理中的分詞及同義詞替換、文本編輯器中的拼寫檢查、輸入法中的文本聯想等環節對相應詞典的構造和檢索性能要求都非常高。

由于詞典的構造和檢索在實際應用中的關鍵性地位，受到大量業內人士的關注，因此對于該問題的研究成果也較豐富。現今常用的串數據詞典的結構和表示方式包括線性表、二叉樹、檢索樹和散列表。

線性表是一種將數據的鍵在邏輯上依次存儲的數據結構。當對數據進行無序約束存儲時，每次檢索的最差時間復雜度為O(n)（其中n為已知的不重復數據項數量，下文同），效率很低，無法滿足高速檢索要求；當數據以有序約束存儲時，配合二分查找算法，每次檢索的最差時間復雜度降低為O(log₂n)，在可接受范圍內，但每次對詞典條目增加或刪除操作的最差時間復雜度上升為O(n)，效率低下。

二叉樹是一種將表示數據鍵的節點按層次邏輯存儲的數據結構。其一般約束為任意節點至多有左或右子節點各一個，其鍵大于其左子節點且小于其右子節點。使用該數據結構的詞典在增加、刪除和檢索條目過程中的時間消耗通常與樹的最大高度成正比，因此對樹高的控制尤為重要。現今較為成熟的樹高控制策略包括B樹、B+樹、紅黑樹等，使用得當的情況下可將每次操作的最差時間復雜度近似等于O(log₂n)。雖然相對線性表其速度有一定程度的提升，但仍然無法滿足大規模數據環境下的速度要求，另外當以串數據為鍵時由于需將所有相應串數據完整保存在每個節點中因此造成很大的存儲空間浪費，同時最差時間復雜度增加到O(l×log₂n)（其中l為串數據長度，下文同）。

對于詞典應用而言，檢索為其最重要的功能，尤其在自然語言處理類應用中，需要頻繁的在詞典中進行檢索以獲取條目信息，因此串數據的檢索效率對于詞典方法來說是一個非常重要的評價指標。

檢索樹是一種以對串數據鍵進行優化為目標的數據結構，其中以串數據中每一數據單元為一節點，將各節點按層次邏輯存儲。其經典實現為指針結構的TRIE樹，在合適的環境下使用可以具有很高的效率，其增加、刪除和檢索條目的時間消耗通常只與l成正比。相對線性表與二叉樹結構，速度有大幅提高，最差時間復雜度可以近似等于O(l)。但是由于很多情況下TRIE樹中大多數節點的分支節點很少，因此其空間浪費非常多，在千萬數量級的應用中，幾乎無法在計算機內存中進行高速操作；另外，當分支節點非常多時，在分支節點間進行二分查找又會增加更多的時間開銷。先前有研究者提出將TRIE樹轉換為雙數組結構，令其空間浪費大幅減少，并優化了分支節點檢索過程，使其查詢速度完全等于O(l)，能夠滿足大部分應用環境下的高速檢索需求。然而，在查詢串模糊匹配或聯想輸入等應用環境下需要對字典有序遍歷，而雙數組結構TRIE樹無法實現高效的有序遍歷，最差時間復雜度為O(n²×l)，幾乎無法在真實環境下使用。

基于散列表的詞典機制就是構造一種哈希函數來計算詞語的散列值，采用合理的哈希函數可盡量控制散列值分布的均勻性從而避免沖突，當遇到沖突時將散列值相同的詞放入一個線性表結構存儲。檢索時先使用哈希函數計算查詢串的散列值，進而取值，當遇到沖突時則在相應的線性表內進行二分查找，因此當第一次散列值計算不成功時，散列表的查詢性能會大幅下降，所以散列表詞典的性能關鍵即為哈希函數的設計。在完美哈希函數設計的研究成果中，生成完美哈希函數所用的時間開銷通常很高，即便在Linux系統下最著名的完美哈希函數生成器Gperf，也無法保證在大規模數據下仍然能生成完美哈希函數，當詞典條目超過15000個時其散列性能很差，尤其對類似中文的多字節大字符集語言的處理效果更差。另一方面，由于哈希函數的設計目標為均勻分布，因此通常無法保證詞典條目的有序性，進行有序遍歷時需對所有詞典條目先行排序，從效率方面來看幾乎無法實際應用。

發明內容

本發明的目的是提供一種構造及檢索效率高、能滿足不同應用環境下對詞典有序性和靈活性的要求，且同時仍保持較少空間占用的串數據的有序構造及檢索方法。

本發明解決現有技術問題所采用的技術方案：一種串數據詞典的有序構造及檢索方法，包括以下步驟：