一種基于最小完美散列 多關(guān)鍵詞匹配算法

1、一種基于最小完美散列多關(guān)鍵詞匹配算法譚建龍 計算所軟件室 20027內(nèi)容散列函數(shù)介紹計算保序最小完美散列函數(shù)算法概要預(yù)處理介紹搜索算法介紹總結(jié)和展望散列函數(shù)介紹(1)散列函數(shù)(Hashing Function)aaaabbbbccccdddd散列函數(shù)介紹(2)完美散列函數(shù)(Perfect Hashing Function)aaaabbbbccccdddd散列函數(shù)介紹(3)最小完美散列函數(shù)(Minimal PHF)aaaabbbbccccdddd散列函數(shù)介紹(4)保序最小完美散列函數(shù)(Order preserving MPHF)aaaabbbbccccdddd保序最小完美散列函數(shù)(MPHF)沒有

2、任何沖突的把n個關(guān)鍵詞散列到0.n-1第i個關(guān)鍵詞一定散列為i-1;MPHF搜索算法建立隨機的表三張隨機表計算出一個圖Graph存在回路找到了MPHF保序最小完美散列函數(shù)空間復(fù)雜性 三張隨機表：關(guān)鍵詞長度字符集大小計算的圖： 1。23關(guān)鍵詞個數(shù)時間復(fù)雜性O(shè)( 關(guān)鍵詞個數(shù))MPHF函數(shù)字符串關(guān)鍵詞長度次查詢3張隨機表3個整數(shù)4次求模運算3次查詢圖1張圖散列值實際使用的MPHF函數(shù)字符串關(guān)鍵詞長度次查詢3張隨機表3個整數(shù)4次求模運算3次查詢圖1張圖散列值第一步散列第二步散列MPHF-Match算法概要預(yù)處理建立一個基于關(guān)鍵詞的保序最小完美散列函數(shù)(MPHF)建立任何一個整數(shù)跳躍距離的表建立一個使用

3、hashFirst函數(shù)檢測的表搜索文本使用整數(shù)表跳躍前進使用檢測表快速檢測使用MPHF函數(shù)確認發(fā)現(xiàn)關(guān)鍵詞預(yù)處理建立一個基于關(guān)鍵詞的保序最小完美散列函數(shù)(MPHF)建立任何一個整數(shù)跳躍距離的表建立一個使用hashFirst函數(shù)檢測的表搜索文本使用整數(shù)表跳躍前進使用檢測表快速檢測使用MPHF函數(shù)確認發(fā)現(xiàn)關(guān)鍵詞Text Text Text Text Text Text Text Text Text TextTextTextText x整數(shù)散列整數(shù)跳躍表計算跳躍距離xtTe跳躍TextText Text Text Text Text Text Text Text Text TextTextTextText x整數(shù)散列整數(shù)跳躍表計算跳躍距離Text Text Text Text Te第一步MPHF3張隨機表第二步MPHF檢測表1個圖xtTe確認匹配關(guān)鍵詞算法性能 Table5.1: Runtimes for string searching50 times PatternsLengthfgrepagrepHuff-Match100747.036.134.0500743.531.025.01000747.136.533.01500751.839.835.32000755.343