DAWG(4-2): MPHF
四回目の中盤。
最小完全ハッシュ関数(Minimal Perfect Hash Function, MPHF)。
『Simple and Space-Efficient Minimal Perfect Hash Functions』*1の理解が進んだので、前回よりも整理されたコードを載せる。
作成方法概要
論文中の最小完全ハッシュ関数の作成方法概要*2。
三ステップからなる。
※ 前提: ハッシュ値を求める対象となるキーセットは、MPHF作成時に静的に取得可能
- Mapping Step:
- Assigning Step:
- Ranking Step:
MPHFに必要な領域は、ハッシュ関数セットの数を2とした場合は各キーごとに大体3.5〜5ビット、3とした場合は各キーごとに2〜3ビット、となる。※ 実際には、各種パラメータや実装方法を変更することで上下するので、あくまでも目安としての数値
ハッシュ関数の数としては2以上の任意の値が指定可能だが、論文(の3.3節末尾)によれば、サイズが一番小さく収まるのは3個の場合で、それ以上増やしても効果がないそうだ。
ソースコード
;; keyに対して、lowからhigh未満のハッシュ値を計算する関数を生成する関数 (defun genhash (low high) (let ((init (+ (random 1000) 1)) ; 毎回異なる関数が生成されるように、三つのパラメータをランダムで与える (mul (+ (random 1000) 3)) (xor (+ (random 1000) 2)) (limit (- high low))) (lambda (key &aux (hash init)) (loop FOR c ACROSS key DO (setf hash (mod (logxor (+ (* hash mul) (char-code c)) xor) limit))) (+ hash low))))
二番目はMapping Step。
;; Mapping Stepに対応する関数 ;; - n: 使用するハッシュ関数の数 ;; - c: PHFが生成するハッシュ値の上限を決めるためのパラメータ※1: 上限 == (* (length keys) c) ;; - keys: 一意なハッシュ値セットの生成対象となるキーセット (defun mapping (n c keys) (make-n-uniform-acyclic-hypergraph n c keys)) ;; n個のハッシュ関数の生成と、キーを枝にハッシュ値を頂点に見立てたグラフの生成を行う関数 (defun make-n-uniform-hypergraph (n c keys &aux (len (length keys))) (let* ((hash-code-limit (ceiling (* c len))) ; PHFが生成するハッシュ値の上限 (hash-fns (loop WITH range = (ceiling hash-code-limit n) ; ハッシュ関数セット REPEAT n FOR beg FROM 0 BY range ;; 生成するハッシュ値の値域は、各ハッシュ関数ごとに区別されている (beg〜beg+range) COLLECT (genhash beg (min (+ beg range) hash-code-limit))))) (values (loop FOR k IN keys COLLECT (mapcar (lambda (h) (funcall h k)) hash-fns)) ; 各キーの(各ハッシュ関数を用いた)ハッシュ値を計算する hash-fns hash-code-limit))) ;; make-n-uniform-hypergraph関数が返したグラフが循環を含まないかどうかをチェックする ;; - 循環チェックは、グラフの末端の枝の除去を繰り返すことで行う ;; - 循環を含まない場合は、枝の除去順にソートしたグラフを返す ※ Assigning Stepで必要 ;; - 循環を含む場合は、もう一度グラフ(およびハッシュ関数セット)を作成し直して、同様の処理を繰り返す (defun make-n-uniform-acyclic-hypergraph (n c keys &optional (try-limit 10)) (when (zerop try-limit) (error "failed!")) (format *error-output* "~&; try ~D~%" try-limit) ;; グラフ作成 (multiple-value-bind (graph hash-fns hash-code-limit) (make-n-uniform-hypergraph n c keys) (let ((incidents-map (make-array hash-code-limit :initial-element '())) ; 各頂点が接続する枝のリストを保持する配列 (ordered-graph '())) ; 枝の除去の逆順にソートされたgraph ;; 各頂点(ハッシュ値)が接続する枝(キー)のリストを設定する (loop FOR edge IN graph DO (loop FOR vertice IN edge DO (push edge (aref incidents-map vertice)))) ;; 循環性チェック (labels ((reap-leaf (vertex) ;; 末端の枝を刈り取り、ordered-graphに追加を行う関数 (let ((edges (aref incidents-map vertex))) (when (= (length edges) 1) ; 末端の枝(= 頂点に接続する枝が一つしかない)なら (let ((edge (car edges))) (setf (aref incidents-map vertex) '()) ; 刈り取る (push edge ordered-graph) ; 刈り取った枝は、ordered-graphの先頭に追加する (dolist (other (remove vertex edge)) ; 他の頂点から、その枝への接続を除去する (setf #1=(aref incidents-map other) (remove edge #1#))) ;; この枝を取り除いたことで、他の頂点(及びそれに紐付く枝)が新しく末端になった可能性があるので、再帰的に処理を繰り返す (dolist (other (remove vertex edge)) (reap-leaf other))))))) ;; 全ての頂点に対して、reap-leaf関数を適用する (loop FOR vertex FROM 0 BELOW hash-code-limit DO (reap-leaf vertex))) ;; 循環を含むならもう一度、含まない(= グラフが森を構成している)ならordered-graphを返す (if (every #'null incidents-map) ; 全ての枝を刈り取ることが出来た場合は、そのグラフは非循環 (values ordered-graph hash-fns hash-code-limit) (make-n-uniform-acyclic-hypergraph n c keys (1- try-limit)))))) #| ※1: 論文によれば、cの値は、n=2の場合は2.0より大きい値、n=3の場合は1.23以上である必要がある n=2の場合にmake-n-uniform-hypergraph関数が循環を含まないグラフを生成する確率は、以下の式で求められる - 式: (sqrt (- 1 (expt (/ 2 c) 2))) ※ ただし、使用するハッシュ関数が各キーから完全にランダムなハッシュ値を生成可能と仮定した場合 論文中では、cの値として2.09を採用している (非循環のグラフ生成確率は、約29%) n=2の場合は、cの値を大きくすれば、非循環グラフ生成確率もそれに合わせて増加するが、 nが3以上の場合は、そう単純ではないらしい。 その辺りはややこしいので、気になる人は、論文の3.1節を参照のこと。 (n >= 3 の場合のcの下限値の計算式も、そこに掲載されている) |#
三番目はAssiging Step。
;; キーセットの各キーが使用するハッシュ関数の割り当て表を作成する関数 ;; 引数は、make-n-uniform-acyclic-hypergraph関数の戻り値そのまま (defun assigning (ordered-graph hash-fns hash-code-limit) (let* ((hash-id-limit (length hash-fns)) ; ハッシュ関数の数 (visited (make-array hash-code-limit :initial-element nil)) ; 頂点の訪問済みマーク (hash-assign-table (make-array hash-code-limit :initial-element hash-id-limit))) ; ハッシュ関数割り当て表 ※ 初期値は、ハッシュ関数の数 ;; 末端の枝の除去の逆順に、グラフ中の枝を走査する (dolist (edge ordered-graph) (loop FOR vertex IN edge FOR hash-id FROM 0 UNLESS (aref visited vertex) ; 頂点が未訪問(= ハッシュ値が未使用なのが確実)の場合 DO ; 各枝は、最低一つの(それまでに)未訪問の頂点を有する ※2 ;; このハッシュ値が使用されるように、割り当て表を設定する (setf (aref hash-assign-table vertex) (mod (- hash-id (loop FOR v IN edge SUM (aref hash-assign-table v))) ; ※3 hash-id-limit)) (return)) ;; 枝に紐付く全ての頂点に訪問済みマークを付ける (loop FOR vertex IN edge DO (setf (aref visited vertex) t))) hash-assign-table)) #| ※2: グラフを末端の枝の除去の逆順に走査するということは、空の状態から木(森)を末端の枝を追加しながら構築していくことに相当する。 そして、各枝の走査一つは、木に末端の枝を一つ追加することに対応する。 追加された末端の枝は、(末端の定義上)最低でも新規の頂点を一つは含むことになるので、ここでの条件は必ず満たされることになる。 ※3: この式の意味: - 実際にキーのハッシュ関数を求める際には、以下のようなコードを実行することになる ※ 実際のコードは、後述のphf関数を参照 # edge = (mapcar (lambda (hash) (funcall hash key)) hash-fns) ; キーに対して、全てのハッシュ関数を適用する # hash-id = (loop FOR v IN edge SUM (aref hash-assign-table v)) ; 使用するハッシュ関数は、各頂点のhash-assign-tableの値の合計値 # (elt hash-fn (mod hash-id hash-id-limit)) ; ハッシュ関数選択 - つまり、枝に紐付く各頂点の、hash-assign-tableの値を合計して、使用するハッシュ関数を選択している ※ mod云々は捨象。以下同。 - この式では、まず上述の合計値を求めて、hash-id(= 使用したいハッシュ関数の番号)からその合計値を引いた値を、hash-assign-tableにセットしている - hash-assign-tableへの値のセットが終わった後に、再度合計値を求めると、常にhash-idとなる -- 各頂点のhash-assign-tableの合計値 = (+ (- hash-id 以前のhash-assign-tableの合計値) 以前のhash-assign-tableの合計値) = hash-id # old-hash-id = (loop FOR v IN edge SUM (aref hash-assign-table v)) # new-hash-id = (+ (- hash-id old-hash-id) old-hash-id) ; => 常に hash-id - つまりこの式は、ただ単に、キー(edge)が使用するハッシュ関数として、hash-idを設定しているに過ぎない (前回の記事ではこれが分かっていなかった...) - なお、一度訪れた枝の頂点は、訪問済みとしてマークされ、以後それに対応するhash-assign-tableの値は、以後修正されることない -- なので、複数の枝(キー)から接続されている頂点(ハッシュ値)の場合のhash-assign-tableの変更による副作用などは気にする必要はない |#
四番目。
Ranking Stepに入る前に、PHFの作成関数およびハッシュ値計算関数を定義しておく。
;; 完全ハッシュ関数(用のデータ)作成関数 ;; 引数はmappingのそれと同様 (defun make-phf (n c keys) (multiple-value-bind (graph hash-fns hash-code-limit) ; Mapping Step (mapping n c keys) (let ((hash-assign-table (assigning graph hash-fns hash-code-limit))) ; Assiging Step (list hash-fns hash-assign-table)))) ; ハッシュ関数セットと割り当て表を返す ;; phf ;; key(key ∈ keys)から一意なハッシュ値を生成する ※ ハッシュ値(x)の範囲は、0 <= x < (* c (length keys)) (defun phf (key phf) (let* ((hash-assign-table (second phf)) (hash-values (mapcar (lambda (h) (funcall h key)) (first phf))) (hash-id-limit (length hash-values)) (assigned-hash-id (mod (loop FOR hash-value IN hash-values SUM (aref hash-assign-table hash-value)) hash-id-limit))) (nth assigned-hash-id hash-values)))
五番目はRanking Step。
;; phf関数が生成した0以上M未満のハッシュ値を、0以上N未満の値に再度マッピングするためのデータ構造を作成する ;; ※ N = キーセットの数、M = phf関数が生成するハッシュ値の上限 >= N ;; ;; - phf: make-phf関数の戻り値 (defun ranking (phf &aux (block-size 256)) (destructuring-bind (hash-fns hash-assign-table) phf ;; blocks: サイズMのビット配列を、block-sizeビット整数にパックして表現した配列 (let ((blocks (make-array (ceiling (length hash-assign-table) block-size) :element-type `(unsigned-byte ,block-size) :initial-element 0)) (hash-id-limit (length hash-fns))) ;; 使用中のハッシュ値に、フラグ(1bit)をセットする (loop FOR n ACROSS hash-assign-table FOR hash-value FROM 0 WHEN (/= n hash-id-limit) DO (multiple-value-bind (index bitpos) (floor hash-value block-size) (setf (ldb (byte 1 bitpos) (aref blocks index)) 1))) ; hash-valueは使用中 ;; 各ブロックごとに、それ以前のブロックに含まれる1bit(= 使用中ハッシュ値)の数をカウントしておく (let ((bases (loop FOR block ACROSS blocks COLLECT acc-1bit-count SUM (logcount block) INTO acc-1bit-count))) (list hash-fns ; 既存 hash-assign-table ; 既存 blocks ; 追加 (coerce bases 'vector)))))) ; 追加 ;; hash-valueのランクを求める ;; - mphf: ranking関数の戻り値 (defun rank (hash-value mphf &aux (block-size 256)) (let ((blocks (third mphf)) (bases (fourth mphf))) (multiple-value-bind (index bitpos) (floor hash-value block-size) (+ (aref bases index) ; blocks[index]以前のブロックに含まれる使用中ハッシュ値の数 (logcount (ldb (byte bitpos 0) (aref blocks index))))))) ; blocks[index]の位置bitposまでに含まれる使用中ハッシュ値の数
最後は、MPHF作成関数とハッシュ値計算関数の定義。
;; MPHF作成関数 ;; make-phf関数に加えて、ranking関数を呼び出すだけ (defun make-mphf (n c keys) (ranking (make-phf n c keys))) ;; MPHF ;; phf関数に加えて、rank関数を呼び出すだけ (defun mphf (key mphf) (rank (phf key mphf) mphf))
以上で実装は終了。
実行例
実行例を一つ。
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; IPADICからランダムに抽出した99単語 (defvar *keys* '("いいつたえりゃ" "いきおいづけりゃ" "いなそ" "うらはずかしい" "かしずけ" "くいあらためん" "こうよう" "ごまめ" "なまじろぅ" "なりわたら" "ねじれる" "はしりぬこ" "ひょろながけりゃ" "ほど近くっ" "むさくるしかれ" "やり場" "ようせ" "インパルス性" "ゴンタ" "スッぱきゃ" "セリカＧＴ" "ツボケ山" "ヌモトル山" "ラグナ" "一里木" "上大川前通" "上怒和" "中部電力" "佳乃" "八津尾" "勇も" "千軍万馬" "南寺方北通" "南柏" "台ケ峰" "同左" "呉絽" "垂れこめる" "女神川" "富雄川" "寝しな" "屯田十一条" "差し掛けりゃ" "干乾し" "平教経" "庄助" "引きずり出そ" "引き延ばし" "思ひ寄" "愛木" "手鎌" "挟み切る" "捩鉢巻" "撰せよ" "擬勢" "日指" "日方" "書割" "東筑紫短大" "東赤田" "東越谷" "槙代" "浜の市" "浜宿" "消えはて" "満ち足りる" "物見高かっ" "瑞瑞しゅぅ" "異様" "白兵" "白星" "白茶ける" "真白けれ" "矢縄" "福井ロジスティクスセンター" "稲尾岳" "穂別川" "笹暮峠" "糸川" "羨ましき" "羽根町乙" "興国寺" "行える" "西境" "規江" "誣い" "誤断" "読めよ" "諭せりゃ" "貞室" "踏みしめよ" "還啓" "銘柄" "門弟" "間部" "鳶が崎" "黒碆" "ＥＲＩ" "ＴＤＫ")) --> *KEYS* ;;;;;; ;; PHF (defvar *phf* (make-phf 2 2.09 *keys*)) --> *PHF* *phf* --> ((#<CLOSURE # {B3F89BD}> #<CLOSURE # {B3F89E5}>) ; ハッシュ関数セット #(2 0 0 0 0 2 0 1 0 0 0 1 2 2 0 0 0 2 2 0 0 1 2 1 2 0 2 2 1 0 2 2 2 2 2 0 0 2 ; ハッシュ関数割り当て表 2 0 0 2 0 2 2 0 1 0 0 0 0 1 0 0 2 0 1 0 0 0 0 0 0 2 2 0 2 0 0 1 2 0 1 0 2 0 2 0 2 0 2 2 2 0 0 2 2 0 0 2 0 1 0 0 1 1 0 2 2 2 0 2 2 1 1 2 2 2 2 1 2 2 2 1 2 2 0 1 2 1 2 1 0 2 0 2 2 1 2 0 1 2 2 2 1 0 2 0 2 2 2 1 2 2 0 2 2 2 1 1 2 2 1 2 2 2 2 2 2 0 2 1 2 2 0 0 2 2 2 2 2 0 2 2 2 1 2 2 2 1 2 1 1 0 2 2 1 2 2 2 2 2 2 2 2 1 2 2 2 1 2 2 2 2 1 2 2)) ;; 99要素が、(今回は)1〜204の値にマッピングされている (sort (mapcar (lambda (k) (list (phf k *phf*) k)) *keys*) #'< :key #'car) --> ((1 "誤断") (2 "寝しな") (3 "西境") (4 "福井ロジスティクスセンター") (6 "書割") (7 "ひょろながけりゃ") (8 "貞室") (9 "ツボケ山") (10 "勇も") (11 "引き延ばし") (14 "擬勢") (15 "諭せりゃ") (16 "やり場") (19 "くいあらためん") (20 "東赤田") (21 "羽根町乙") (23 "規江") (25 "いなそ") (28 "平教経") (29 "かしずけ") (35 "ほど近くっ") (36 "誣い") (39 "行える") (40 "撰せよ") (42 "同左") (45 "なまじろぅ") (46 "消えはて") (47 "いきおいづけりゃ") (48 "踏みしめよ") (49 "女神川") (50 "黒碆") (51 "物見高かっ") (52 "セリカＧＴ") (53 "ごまめ") (55 "満ち足りる") (56 "愛木") (57 "日方") (58 "興国寺") (59 "白茶ける") (60 "真白けれ") (61 "白兵") (62 "八津尾") (65 "なりわたら") (67 "東越谷") (68 "千軍万馬") (69 "屯田十一条") (71 "差し掛けりゃ") (72 "間部") (73 "ヌモトル山") (75 "浜宿") (77 "ＥＲＩ") (79 "ＴＤＫ") (83 "垂れこめる") (84 "笹暮峠") (87 "ねじれる") (88 "読めよ") (90 "上大川前通") (91 "干乾し") (92 "手鎌") (93 "瑞瑞しゅぅ") (94 "ラグナ") (95 "南柏") (96 "上怒和") (100 "異様") (103 "白星") (104 "こうよう") (109 "台ケ峰") (113 "矢縄") (116 "ようせ") (117 "槙代") (119 "思ひ寄") (121 "引きずり出そ") (122 "羨ましき") (124 "はしりぬこ") (127 "一里木") (129 "ゴンタ") (130 "鳶が崎") (134 "捩鉢巻") (135 "中部電力") (137 "稲尾岳") (141 "富雄川") (144 "東筑紫短大") (148 "日指") (149 "南寺方北通") (152 "糸川") (159 "挟み切る") (161 "庄助") (164 "呉絽") (165 "いいつたえりゃ") (171 "還啓") (175 "門弟") (179 "銘柄") (181 "インパルス性") (182 "穂別川") (183 "浜の市") (186 "むさくるしかれ") (195 "スッぱきゃ") (199 "佳乃") (204 "うらはずかしい")) ;;;;;;; ;; MPHF (defvar *mphf* (make-mphf 3 1.23 *keys*)) --> *MPHF* *mphf* --> ((#<CLOSURE # {B43130D}> #<CLOSURE # {B431335}> #<CLOSURE # {B43135D}>) ; ハッシュ関数セット #(0 0 1 0 2 1 1 2 0 2 0 1 0 2 0 1 1 2 1 2 1 0 2 0 0 2 1 0 2 1 0 2 0 3 1 0 1 0 ; ハッシュ関数割り当て表 0 1 2 2 0 1 1 0 1 3 2 0 0 1 0 2 3 1 1 0 0 2 0 3 1 1 0 1 3 1 2 0 0 1 1 3 0 2 0 1 0 3 3 2 2 1 0 2 1 3 2 1 3 0 3 2 1 0 2 3 3 1 3 1 3 1 2 3 1 3 3 1 2 2 3 0 2 3 3 2 3 2 3 0) #(3525035404327211178697215293677109247) ; rank用: 使用中ハッシュ値フラグ用ビット列 #(0)) ; rank用: ;; 99要素が、0〜98の値にマッピングされている (sort (mapcar (lambda (k) (list (mphf k *mphf*) k)) *keys*) #'< :key #'car) --> ((0 "物見高かっ") (1 "ラグナ") (2 "屯田十一条") (3 "いいつたえりゃ") (4 "西境") (5 "擬勢") (6 "ＴＤＫ") (7 "ツボケ山") (8 "真白けれ") (9 "貞室") (10 "寝しな") (11 "槙代") (12 "はしりぬこ") (13 "日方") (14 "干乾し") (15 "差し掛けりゃ") (16 "羽根町乙") (17 "矢縄") (18 "銘柄") (19 "引きずり出そ") (20 "なまじろぅ") (21 "かしずけ") (22 "踏みしめよ") (23 "むさくるしかれ") (24 "一里木") (25 "ねじれる") (26 "中部電力") (27 "東筑紫短大") (28 "規江") (29 "誤断") (30 "ようせ") (31 "黒碆") (32 "上怒和") (33 "富雄川") (34 "書割") (35 "女神川") (36 "間部") (37 "糸川") (38 "瑞瑞しゅぅ") (39 "八津尾") (40 "諭せりゃ") (41 "ごまめ") (42 "捩鉢巻") (43 "平教経") (44 "台ケ峰") (45 "うらはずかしい") (46 "鳶が崎") (47 "消えはて") (48 "南柏") (49 "手鎌") (50 "引き延ばし") (51 "浜の市") (52 "行える") (53 "門弟") (54 "佳乃") (55 "羨ましき") (56 "読めよ") (57 "同左") (58 "満ち足りる") (59 "還啓") (60 "勇も") (61 "異様") (62 "東赤田") (63 "白茶ける") (64 "日指") (65 "ひょろながけりゃ") (66 "垂れこめる") (67 "くいあらためん") (68 "スッぱきゃ") (69 "上大川前通") (70 "いきおいづけりゃ") (71 "稲尾岳") (72 "庄助") (73 "ＥＲＩ") (74 "白兵") (75 "ほど近くっ") (76 "福井ロジスティクスセンター") (77 "浜宿") (78 "挟み切る") (79 "ゴンタ") (80 "なりわたら") (81 "愛木") (82 "撰せよ") (83 "呉絽") (84 "こうよう") (85 "白星") (86 "思ひ寄") (87 "セリカＧＴ") (88 "誣い") (89 "ヌモトル山") (90 "東越谷") (91 "南寺方北通") (92 "やり場") (93 "いなそ") (94 "興国寺") (95 "穂別川") (96 "千軍万馬") (97 "笹暮峠") (98 "インパルス性"))
*1:Fabiano C. Botelho, Rasmus Pagh and Nivio Ziviani、『Simple and Space-Efficient Minimal Perfect Hash Functions』、Springer LNCS(volume. 4619)、2007、p139-150
*2:以降で載せるソースコードも含めて、あくまでも自分の理解確認用に書いているだけなので、正確に知りたい人はオリジナルの論文を参照のこと
*3:一つの枝に紐付く頂点がN個となるため、正確にはハイパーグラフ(N-uniform hypergraph)となる。N=2の場合は、通常のグラフと同様。
