一種構造用於處理大規模詞典的完美哈希函數的方法
2023-07-04 05:04:06 4
專利名稱:一種構造用於處理大規模詞典的完美哈希函數的方法
技術領域：
本發明涉及信息檢索和自然語言處理技術領域：
，尤其涉及一種構造用於處理大規模詞典的完美哈希函數的方法。
背景技術：
在信息檢索和自然語言處理等領域的很多應用中都涉及到詞典查找，詞典查找的速度很大程度上決定了系統的整體性能。例如，集成開發環境(IDE)的保留詞識別、編輯器的拼寫檢查、光學字符識別(OCR)的結果校驗、文本處理的中文分詞、倒排索引的Post list定位等速度要求都非常高，都需要快速詞典查找。完美哈希函數能夠將詞典的單詞快速映射到唯一的整數，不存在衝突，因此是一種理想的詞典查找方法。
已經有不少人提出了完美哈希函數的構造策略，但是都不能很好地處理大規模的詞典，而且已有的大部分哈希函數都不能處理像漢語這樣的大字符集的詞典。
如Cichille提出了給單詞首尾兩字符關聯整數，取單詞首尾兩字符所關聯整數和單詞長度之和作為單詞的哈希值。Cichelli的方法只能處理不超過45個單詞的詞典。
Cercone提出了詞典劃分的方法，將詞典按照單詞長度劃分為不同子詞典，對單詞所有字符均關聯整數，再將各子哈希函數合併得到整個詞典的完美哈希函數。Cercone的方法可以對1000個以內單詞的詞典成功構造完美哈希函數。
Gperf是Linux系統下著名的哈希函數構造方法，但是其官方網站提供的最新版本Gperf也不能處理超過15000個單詞的詞典，尤其是對類似中文的大字符集詞典時效果更差。另外，Gperf不能保證每次運行都能找到詞典的完美哈希函數，哈希函數的填充因子非常小，導致哈希函數表佔用內存非常多。
已有實驗表明，對含有15000個詞語的中文詞典，使用Gperf構造哈希函數構造過程需要大概8個小時，填充因子不到4％。
Sager提出minicycle算法來構造完美哈希函數，他通過對單詞所有字符關聯整數，從而為每個單詞對應一個三元組(h0，h1，h2)，並試圖找到映射g(0…r)→(0…|K|-1)，使得h(key)＝h0+g(h1)+g(h2)是一個完美哈希函數。Sager提出的minicycle算法最多也只能處理包含512個單詞的詞典。
在Sager的工作基礎上，Fox改善了單詞三元組的生成方式，並提出使用相關圖來加速映射過程。Fox對每個字符在每個位置出現關聯三個隨機數s0、s1和s2，單詞對應的三元組的h0、h1和h2分別由單詞各字母在相應位置對應的s0、s1和s2之和。得到每個單詞的h0、h1和h2之後，Fox以所有單詞的h1和h2為頂點，將每個單詞對應的h1和h2頂點之間連一條邊，構成詞典的相關圖，在相關圖的基礎上Fox對每個頂點hi關聯一個整數g(hi)，使得h(key)＝h0+g(h1)+g(h2)是一個完美哈希函數。
Fox的方法最大的缺點在於需要大量的空間保存隨機數集合，同時該方法的相關圖頂點數為詞典單詞數量的0.6倍，這些都導致了Fox方法的工作空間(保存哈希函數需要的內存)較大。另外隨機數策略不能保證對任何詞典均能構造其完美哈希函數。
發明內容(一)要解決的技術問題有鑑於此，本發明的主要目的在於提供一種構造用於處理大規模詞典的完美哈希函數的方法，以成功對包含上百萬單詞的詞典構造完美哈希函數，處理中文等大字符集詞典，並提高填充因子，縮短構造時間，減少哈希函數的工作空間。
(二)技術方案為達到上述目的，本發明的技術方案是這樣實現的一種構造用於處理大規模詞典的完美哈希函數的方法，該方法包括A、將待構造哈希函數的詞典中的單詞平滑；B、將平滑後詞典按照單詞長度分為n個子詞典，對每個子詞典構造相關圖，n為自然數；C、對構造的每個子詞典的相關圖中的頂點進行排序，對排序後各頂點依次關聯整數，將各單詞映射到不同的哈希地址，得到詞典的完美哈希函數。
所述步驟A包括採用兩個不同的平滑函數，分別將每個單詞除首字符外的每個字符平滑為兩個字符。
對於單詞k＝c1c2…cn，平滑後形如k`＝c1f1(c2)f2(c2)…f1(cn)f2(cn)，f1和f2為兩個平滑函數，f1(ci)和f2(ci)表示由字符ci及其附近字符計算得到的平滑值。
所述平滑函數為自定義的函數，或為根據詞典大小和期望填充因子調整相關參數得到的函數。
對於英文詞典，所述平滑函數為f(ci)＝a(ci-1)2+bci；對於中文詞典，所述平滑函數為f(ci)＝aci-1+bci；其中a、b為參數。
步驟B中所述每個子詞典內所有單詞長度相同；步驟B中所述對每個子詞典構造相關圖包括對單詞長度大於1的子詞典，以其所有單詞最後兩個字符為頂點，兩個字符出現在同一個單詞的最後兩個位置，則在這兩個字符對應的頂點間連一條邊，形成該子詞典的相關圖。
所述形成該子詞典的相關圖後進一步包括將各子詞典相關圖的集合在一起，形成原詞典的多級相關圖。
步驟B中所述多級相關圖，其頂點集合為相應子詞典平滑後單詞最後兩個字符的集合，其邊集為相應子詞典所有單詞的集合。
步驟C中所述對構造的每個子詞典的相關圖中的頂點進行排序按照類似Prim算法的方式進行，具體包括對各級相關圖頂點按照類似Prim算法排序，將度最高的頂點v1排第一，與v1相鄰的度最高的頂點v2排第二，與v1或v2相鄰的度最高的頂點v3排第三，……，直到該級相關圖所有頂點都已經排序。
步驟C中所述對排序後各頂點依次關聯整數，將各單詞映射到不同的哈希地址，得到詞典的完美哈希函數包括對各級相關圖的每個頂點依次關聯一個合適的整數，將與當前頂點相鄰的所有單詞映射到哈希表空閒地址，即對於單詞k＝c1c2…cn，平滑後單詞形如k`＝c1f1(c2)f2(c2)…f1(cn)f2(cn)，對k`各字符關聯整數，使得h(k`)＝g(c1)+g(f1(c2))+g(f2(c2))+…+g(f1(cn))+g(f2(cn))為完美哈希函數，其中g(f1(ci))和g(f2(ci))分別表示對頂點f1(ci)和f2(ci)關聯的整數。
(三)有益效果從上述技術方案可以看出，本發明具有以下有益效果1、利用本發明，通過將待構造哈希函數的詞典中的單詞平滑，將平滑後詞典按照單詞長度分為n個子詞典(n為自然數)，對每個子詞典構造相關圖，然後對構造的每個子詞典的相關圖中的頂點進行排序，對排序後各頂點依次關聯整數，將各單詞映射到不同的哈希地址，進而能夠對包含上百萬單詞的詞典成功構造完美哈希函數，並且能夠處理中文等大字符集詞典，填充因子接近1，提高了填充因子，縮短了構造時間，減少了哈希函數的工作空間。
2、本發明提供的這種構造用於處理大規模詞典的完美哈希函數的方法，可以對任意大小的詞典成功構造完美哈希函數，尤其是對如漢語這樣的大字符集上的詞典，效果更好。
3、本發明提供的這種構造用於處理大規模詞典的完美哈希函數的方法，可以通過調整工作空間大小來調節填充因子，當需要更高的填充因子時只需要更改平滑函數，增加相關圖頂點數量即可。
4、本發明提供的這種構造用於處理大規模詞典的完美哈希函數的方法，將原始詞典劃分為若干個子詞典，對每個子詞典獨立構造相關圖，因此本發明提供的哈希函數構造方法比Fox等已有方法速度更快。對從北大人民日報語料庫上抽取的12萬中文詞語構成的詞典，用本發明提供的完美哈希函數構造方法構造過程僅需4.14秒，工作空間僅為60867個整數，將12萬詞語映射到13萬1千個哈希地址空間。
圖1為本發明提供的構造用於處理大規模詞典的完美哈希函數的方法流程圖；圖2為依照本發明實施例對子詞典構造的相關圖；其中，圖2(a)是對子詞典K1構造的相關圖；圖2(b)是對子詞典K2構造的相關圖；圖3為依照本發明實施例各級相關圖的頂點排序與關聯整數過程示意圖。
具體實施方式為使本發明的目的、技術方案和優點更加清楚明白，以下結合具體實施例，並參照附圖，對本發明進一步詳細說明。
本發明的實現原理如下本發明提供的構造用於處理大規模詞典的完美哈希函數的方法，將哈希函數的構造過程分為字符平滑階段、多級相關圖構造階段、頂點賦值階段。
在字符平滑階段，將單詞除首字符外的其它每個字符都用兩個不同的平滑函數將其平滑為兩個字符，對於單詞k＝c1c2…cn，平滑後形如k`＝c1f1(c2)f2(c2)…f1(cn)f2(cn)，f1和f2為兩個平滑函數。
在多級相關圖構造階段，對平滑後的詞典，按照單詞長度分為若干子詞典，各子詞典內所有單詞長度相同。對每個子詞典，以其所有單詞最後兩個字符為頂點，兩個字符出現在同一個單詞的最後兩個位置，則在這兩個字符對應的頂點間連一條邊，形成該子詞典的相關圖。各子詞典相關圖的集合形成原詞典的多級相關圖。
在頂點賦值階段，對各級相關圖的每個頂點依次關聯一個合適的整數，將與當前頂點相鄰的所有單詞映射到哈希表空閒地址，即對於單詞k＝c1c2…cn，平滑後單詞形如k`＝c1f1(c2)f2(c2)…f1(cn)f2(cn)，對k`各字符關聯的整數使得h(k`)＝g(c1)+g(f1(c2))+g(f2(c2))+…+g(f1(cn))+g(f2(cn))，其中g(f1(ci))和g(f2(ci))分別表示對頂點f1(ci)和f2(ci)關聯的整數。
如圖1所示，圖1為本發明提供的構造用於處理大規模詞典的完美哈希函數的方法流程圖，該方法包括以下步驟步驟101將待構造哈希函數的詞典中的單詞平滑；步驟102將平滑後詞典按照單詞長度分為n個子詞典，對每個子詞典構造相關圖，n為自然數；步驟103對構造的每個子詞典的相關圖中的頂點進行排序，對排序後各頂點依次關聯整數，將各單詞映射到不同的哈希地址，得到詞典的完美哈希函數。
上述步驟101包括採用兩個不同的平滑函數，分別將每個單詞除首字符外的每個字符平滑為兩個字符。
對於單詞k＝c1c2…cn，平滑後形如k`＝c1f1(c2)f2(c2)…f1(cn)f2(cn)，f1和f2為兩個平滑函數，f1(ci)和f2(ci)表示由字符ci及其附近字符計算得到的平滑值。
上述平滑函數為自定義的函數，或為根據詞典大小和期望填充因子調整相關參數得到的函數。
對於英文詞典，所述平滑函數為f(ci)＝a(ci-1)2+bci；對於中文詞典，所述平滑函數為f(ci)＝aci-1+bci；其中a、b為參數。
上述步驟102中所述每個子詞典內所有單詞長度相同。上述步驟102中所述對每個子詞典構造相關圖包括對單詞長度大於1的子詞典，以其所有單詞最後兩個字符為頂點，兩個字符出現在同一個單詞的最後兩個位置，則在這兩個字符對應的頂點間連一條邊，形成該子詞典的相關圖。
所述形成該子詞典的相關圖後進一步包括將各子詞典相關圖的集合在一起，形成原詞典的多級相關圖。
上述步驟102中所述多級相關圖，其每級相關圖頂點集合為相應子詞典平滑後單詞最後兩個字符的集合，其邊集為相應子詞典所有單詞的集合。
上述步驟103中所述對構造的每個子詞典的相關圖中的頂點進行排序按照類似Prim算法的方式進行，具體包括對各級相關圖頂點按照類似Prim算法排序，將度最高的頂點v1排第一，與v1相鄰的度最高的頂點v2排第二，與v1或v2相鄰的度最高的頂點v3排第三，……，直到該級相關圖所有頂點都已經排序。
上述步驟103中所述對排序後各頂點依次關聯整數，將各單詞映射到不同的哈希地址，得到詞典的完美哈希函數包括對各級相關圖的每個頂點依次關聯一個合適的整數，將與當前頂點相鄰的所有單詞映射到哈希表空閒地址，即對於單詞k＝c1c2…cn，平滑後形如k`＝c1f1(c2)f2(c2)…f1(cn)f2(cn)，對k′各字符對應頂點關聯的整數使得h(k`)＝g(c1)+g(f1(c2))+g(f2(c2))+…+g(f1(cn))+g(f2(cn))為完美哈希函數，其中g(f1(ci))和g(f2(ci))分別表示對頂點f1(ci)和f2(ci)關聯的整數。
基於圖1所述的構造用於處理大規模詞典的完美哈希函數的方法流程圖，以下結合具體的實施例對本發明構造用於處理大規模詞典的完美哈希函數的方法進一步詳細說明。
實施例在本實施例中，構造用於處理大規模詞典的完美哈希函數的方法也分為三個階段字符平滑階段、多級相關圖構造階段和頂點賦值階段，下面分別詳細介紹如下1.字符平滑階段在相關圖中，頂點的度越高，為該頂點關聯一個整數越困難，哈希函數的填充因子可能越小。因此，本發明在構造多級相關圖之前先對詞典所有單詞做平滑處理，使得構造的每一級相關圖頂點度都較小，並且分布均勻。本發明將單詞除首字符外的所有字符都用兩個不同的平滑函數將其平滑為兩個字符，例如對單詞k＝c1c2…cn，平滑後形如k`＝c1f1(c2)f2(c2)…f1(cn)f2(cn)，f1和f2為平滑函數。f1(ci)和f2(ci)表示由字符ci及其附近字符計算得到的平滑值。平滑函數是用戶自定義的函數，對於英文詞典，f(ci)＝a(ci-1)2+bci是常用的平滑函數；對於中文詞典，f(ci)＝aci-1+bci是常用的平滑函數，其中a、b是參數。表1顯示了詞典K＝{aa，ac，ba，bb，bc，aca，baa，cab，cbc，cca}的平滑結果，令a、b、c的整數id分別為1、2、3，平滑函數分別為f1(ci)＝2c1+ci，f2(ci)＝ci-1+ci(i≥2)。例如對單詞「cab」，f1(『a』)＝2『c』+『a』＝2×3+1＝7；f2(『a』)＝『c』+『a』＝3+1＝4；f1(『b』)＝2『c』+『b』＝2×3+2＝8；f2(『b』)＝『a』+『b』＝1+2＝3；因此，「cab」平滑後為(3，7，4，8，3)。
表12.多級相關圖構造階段對平滑後的詞典，本發明將構造多級相關圖。多級相關圖的構造首先需要將平滑後詞典按照單詞長度分為若干子詞典，每個子詞典內所有單詞長度相同，對每個子詞典構造一級相關圖，形成原始詞典的多級相關圖。對於表1所示的詞典，將劃分為兩個子詞典K1＝{aa，ac，ba，bb，bc}和K2＝{aca，baa，cab，cbc，cca}，每個子詞典分別構造一級相關圖，每個子詞典對應的相關圖頂點為平滑後單詞最後兩個字符的集合，邊為子詞典所有單詞的集合。圖2(a)和圖2(b)分別是對子詞典K1和K2的相關圖，其中圖中各頂點表示平滑後各字符，下標表示字符在單詞中的位置。
3.頂點賦值階段本發明在頂點賦值階段首先將所有哈希表地址全部置為「空閒」，然後按照單詞長度依次對各子詞典處理。對所有字符在第一個位置出現關聯隨機整數，如表1所示的詞典，第一個位置a、b、c字符分別關聯1、3和8。對於每一個子詞典所構造相關圖的頂點進行排序，對排序後的頂點vi依次關聯整數g(vi)，使得與vi相鄰的所有單詞映射到哈希表空閒地址，標誌這些地址為佔用，直到各相關圖所有頂點均已經關聯合適整數。
對每一級相關圖，本發明按照類似於Prim算法的排序方式對相關圖頂點排序，度最高的頂點v1排第一，與v1相鄰的度最高的頂點v2排第二，與v1或v2相鄰的度最高的頂點v3排第三......。圖3是圖2(a)所示相關圖的排序示意圖，本發明將按照52、43、33、62、32、23、72、53的順序對這些頂點關聯整數，使得K1＝{aa，ac，ba，bb，bc}各單詞映射到哈希表的不同地址。首先對52頂點關聯整數0，43頂點關聯整數必須保證將與之相鄰的單詞「ac」映射到第一個空閒地址(地址1)，因此43頂點所關聯整數g(43)＝1可滿足hash(″ac″)＝g(11)+g(52)+g(43)＝1+0+1＝1，標誌哈希表地址1為「佔用」。同理33頂點應該關聯整數g(33)＝1才能使單詞「ba」映射到第一個空閒地址2......。表2顯示了單詞平滑後各字符在各位置關聯的整數。
表2以上所述的具體實施例，對本發明的目的、技術方案和有益效果進行了進一步詳細說明，所應理解的是，以上所述僅為本發明的具體實施例而已，並不用於限制本發明，凡在本發明的精神和原則之內，所做的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。
權利要求
1.一種構造用於處理大規模詞典的完美哈希函數的方法，其特徵在於，該方法包括A、將待構造哈希函數的詞典中的單詞平滑；B、將平滑後詞典按照單詞長度分為n個子詞典，對每個子詞典構造相關圖，n為自然數；C、對構造的每個子詞典的相關圖中的頂點進行排序，對排序後各頂點依次關聯整數，將各單詞映射到不同的哈希地址，得到詞典的完美哈希函數。
2.根據權利要求
1所述的構造用於處理大規模詞典的完美哈希函數的方法，其特徵在於，所述步驟A包括採用兩個不同的平滑函數，分別將每個單詞除首字符外的每個字符平滑為兩個字符。
3.根據權利要求
2所述的構造用於處理大規模詞典的完美哈希函數的方法，其特徵在於，對於單詞k＝c1c2…cn，平滑後形如k`＝c1f1(c2)f2(c2)…f1(cn)f2(cn)，f1和f2為兩個平滑函數，f1(ci)和f2(ci)表示由字符ci及其附近字符計算得到的平滑值。
4.根據權利要求
1所述的構造用於處理大規模詞典的完美哈希函數的方法，其特徵在於，所述平滑函數為自定義的函數，或為根據詞典大小和期望填充因子調整相關參數得到的函數。
5.根據權利要求
2、3或4所述的構造用於處理大規模詞典的完美哈希函數的方法，其特徵在於，對於英文詞典，所述平滑函數為f(ci)＝a(ci-1)2+bci；對於中文詞典，所述平滑函數為f(ci)＝aci-1+bci；其中a、b為參數。
6.根據權利要求
1所述的構造用於處理大規模詞典的完美哈希函數的方法，其特徵在於，步驟B中所述每個子詞典內所有單詞長度相同；步驟B中所述對每個子詞典構造相關圖包括對單詞長度大於1的子詞典，以其所有單詞最後兩個字符為頂點，兩個字符出現在同一個單詞的最後兩個位置，則在這兩個字符對應的頂點間連一條邊，形成該子詞典的相關圖。
7.根據權利要求
6所述的構造用於處理大規模詞典的完美哈希函數的方法，其特徵在於，所述形成該子詞典的相關圖後進一步包括將各子詞典相關圖的集合在一起，形成原詞典的多級相關圖。
8.根據權利要求
6所述的構造用於處理大規模詞典的完美哈希函數的方法，其特徵在於，步驟B中所述多級相關圖，其頂點集合為相應子詞典平滑後單詞最後兩個字符的集合，其邊集為相應子詞典所有單詞的集合。
9.根據權利要求
1所述的構造用於處理大規模詞典的完美哈希函數的方法，其特徵在於，步驟C中所述對構造的每個子詞典的相關圖中的頂點進行排序按照類似Prim算法的方式進行，具體包括對各級相關圖頂點按照類似Prim算法排序，將度最高的頂點v1排第一，與v1相鄰的度最高的頂點v2排第二，與v1或v2相鄰的度最高的頂點v3排第三，……，直到該級相關圖所有頂點都已經排序。
10.根據權利要求
1所述的構造用於處理大規模詞典的完美哈希函數的方法，其特徵在於，步驟C中所述對排序後各頂點依次關聯整數，將各單詞映射到不同的哈希地址，得到詞典的完美哈希函數包括對各級相關圖的每個頂點依次關聯一個合適的整數，將與當前頂點相鄰的所有單詞映射到哈希表空閒地址，即對於單詞k＝c1c2…cn，平滑後單詞形如k`＝c1f1(c2)f2(c2)…f1(cn)f2(cn)，對k`各字符關聯整數，使得h(k`)＝g(c1)+g(f1(c2))+g(f2(c2))+…+g(f1(cn))+g(f2(cn))為完美哈希函數，其中g(f1(ci))和g(f2(ci))分別表示對頂點f1(ci)和f2(ci)關聯的整數。
專利摘要
本發明涉及信息檢索和自然語言處理技術領域：
，公開了一種構造用於處理大規模詞典的完美哈希函數的方法，該方法包括A、將待構造哈希函數的詞典中的單詞平滑；B、將平滑後詞典按照單詞長度分為n個子詞典，對每個子詞典構造相關圖，n為自然數；C、對構造的每個子詞典的相關圖中的頂點進行排序，對排序後各頂點依次關聯整數，將各單詞映射到不同的哈希地址，得到詞典的完美哈希函數。利用本發明，能夠對包含上百萬單詞的詞典成功構造完美哈希函數，並且能夠處理中文等大字符集詞典，填充因子接近1，提高了填充因子，縮短了構造時間，減少了哈希函數的工作空間。
文檔編號G06F17/30GK1996306SQ200610171640
公開日2007年7月11日 申請日期2006年12月31日
發明者龔才春 申請人:中國科學院計算技術研究所導出引文BiBTeX, EndNote, RefMan