DAWG(4-1): 完全ハッシュ関数
四回目の前半。
DAWGのキーに一意なIDをマッピングするための最小完全ハッシュ関数を実装。
※ ただし今回実装分は、"最小"のつかないただの完全ハッシュ関数まで
参考元
『Simple and Space-Efficient Minimal Perfect Hash Functions』*1を参考にした。
ただし、まだ実装に必要な箇所に軽く目を通しただけなので、詳細は理解していない。
※ いつものことだけど、ちゃんと知りたい人はもとの論文を参照のこと
概要
とりあえず現状での理解。※ 間違っている可能性あり!
実装
今回は完全ハッシュ関数までを作成する。
使用するハッシュ関数の数は、実装を簡単にするために2個に固定とする。
;; ハッシュ関数生成関数 ;; - キーに対してlowからhigh未満の値を算出するハッシュ関数を生成する ;; - 生成されるハッシュ関数は、生成時にランダムに決定される三つのパラメータ(init,x,y)によって、毎回異なるものとなる ;; ※ ハッシュ値の計算方法自体はテキトウ (defun genhash (low high) (let ((init (+ (random 1000) 1)) (x (+ (random 1000) 3)) (y (+ (random 1000) 2)) (limit (- high low))) (lambda (key) (let ((hash init)) (loop FOR c ACROSS key DO (setf hash (mod (logxor (+ (* hash x) (char-code c)) y) limit))) (+ hash low))))) ;; 例 (funcall (genhash 0 10000) "abc") --> 3301 (funcall (genhash 1000 1500) "abc") --> 1330
;; 各キーに対して、二つの異なるハッシュ関数を用いて、ハッシュ値を計算する ;; cは生成されるハッシュ値の上限を決定するための定数 ※ 論文中では2.09 ;; ;; 論文中では、グラフ用語が良く出てくるので、関数名もそれに習っている ;; - 枝 = キー ;; - 頂点 = キーに紐付くハッシュ値 ;; ※ ハッシュ関数がn個の場合は、一つの枝にn個の頂点が紐付くことになる ;; 普通のグラフとは違いn=2とは限らないのでハイパーグラフ (今回の実装では、実質上ただのグラフだけど...) (defun make-2-uniform-hypergraph (c keys) (let* ((len (length keys)) (hash-code-limit (ceiling (* c len))) ; ハッシュ値の最大値: 概要のところで述べたMはこれに当たる (hash-fns (list (genhash 0 (round hash-code-limit 2)) ; 0 〜 hash-code-limit/2 (genhash (round hash-code-limit 2) hash-code-limit)))) ; hash-code-limit/2 〜 hash-code-limit (values (loop FOR k IN keys ; 各キーに対応するハッシュ値リスト COLLECT (mapcar (lambda (h) (funcall h k)) hash-fns)) hash-fns))) ; 使用したハッシュ関数 ;; 例 (make-2-uniform-hypergraph 2.09 '("abc" "123" "あいう" "カキク")) --> ((3 8) (3 6) (1 5) (0 6)) (#<CLOSURE (LAMBDA #) {C7D0F6D}> #<CLOSURE (LAMBDA #) {C7D0F8D}>)
;; キーセットを引数として、適切なハッシュ関数群と、それを適用した結果のハッシュ値リストを得る ;; ※ 論文中の Mapping Step に対応 ;; ;; 主に次の三つの処理を行う ;; - make-2-uniform-hypergraph関数を呼び出して、ハッシュ関数とハッシュ値リストを得る ;; - それらが適切なものかどうかをチェックする ;; -- 不適切ならtry-limit回だけ再試行 ;; - 後続の処理に備えて、ハッシュ値リスト(グラフ)を並び替える (defun make-acyclic-2uh-graph (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) (make-2-uniform-hypergraph c keys) (let ((edges (make-array (ceiling (* c (length keys))) :initial-element '())) (ordered-graph '())) ;; チェックをしやすくするために、一方の頂点(ハッシュ値)と接続している頂点のリストを作成しておく (loop FOR (vertex1 vertex2) IN graph DO (push vertex1 (aref edges vertex2)) (push vertex2 (aref edges vertex1))) ;; graphが適切かどうかをチェックする ;; graphが循環を含んでいなければ合格 (loop FOR from-vertex FROM 0 BELOW (length edges) DO (loop WITH from = from-vertex ; 枝の片一方の頂点 FOR (to . rest-vertices) = (aref edges from) ; 枝のもう片方の頂点 WHILE (and to (null rest-vertices)) DO ; 頂点fromが頂点toにしか繋がっていない場合 (つまり末端の頂点の場合) (push (sort `(,from ,to) #'<) ordered-graph) (setf (aref edges from) '() ; 頂点fromを取り除く (aref edges to) (remove from (aref edges to)) ; 頂点toに接続する頂点リストから、fromを取り除く from to))) ; ↑の処理で頂点toが末端の頂点になった可能性があるので、同様の処理を繰り返す ;; 末端の頂点を取り除くことを繰り返した結果、全ての頂点が除去されたなら、そのグラフは循環を含まない ;; ;; [メモ] ;; 末端の頂点: 頂点(ハッシュ値)に接続する枝(キー)が一つしかない ;; => 他と重複がなく、キーに一意に紐付くハッシュ値 ;; 頂点の除去: 末端の頂点の除去は、それに接続する枝を除去することに等しい ;; => 一回の除去は、キーとそのハッシュ値のペアを一つ選択することに対応 ;; 全ての頂点が除去されたということは、全てのキーのハッシュ値が重複なく選択されたということ (if (every #'null edges) (values ordered-graph hash-fns) (make-acyclic-2uh-graph c keys (1- try-limit)))))) ; もう一度 ;; 例 (make-acyclic-2uh-graph 2.09 '("abc" "123" "あいう" "カキク")) ; try 10 ; try 9 ; try 8(defvar *phf* (make-phf '("abc" "123" "あいう" "カキク"))) ; try 7 ; try 6 ; try 5 --> ((1 5) (1 6) (3 6) (0 4)) (#<CLOSURE (LAMBDA #) {C7D390D}> #<CLOSURE (LAMBDA #) {C7D392D}>)
;; 各キーが使用するハッシュ関数を判定するためのテーブルを準備する ;; ※ 論文中の Assigning Step に対応 ;; ;; graphは、make-acyclic-2uh-graph関数内の返り値(= ordered-graph) (defun assigning (c graph) (let* ((size (ceiling (* (length graph) c))) (visited (make-array size :initial-element nil)) ; 頂点(ハッシュ値)が、処理済みかどうか (assign-table (make-array size :initial-element 2))) ; 使用ハッシュ関数判定用テーブル (dolist (edge graph) (loop FOR v IN edge FOR i FROM 0 ;; 未訪問なら、後続の処理を行う ;; ※ 各edgeは最低一つの未訪問頂点を含んでいる必要があるらしい ;; make-acyclic-2uh-graph関数内で、末端頂点の削除のタイミングでordered-graphに枝を追加していたのはそのため WHEN (not (aref visited v)) DO (setf (aref assign-table v) (mod (- i (loop FOR v2 IN edge WHEN (aref visited v2) SUM (aref assign-table v2))) 2)) ; (setf (aref visited v) t)) ; 修正(2010/07/15) (return)) ; 追加(2010/07/15): 未訪問の頂点を見つけたら、その時点でこの枝に対する処理は終了 ;; 追加(2010/07/15): 枝の全ての頂点に訪問済みのマークをつける (loop FOR v IN edge DO (setf (aref visited v) t))) assign-table)) ;; 例 (assigning 2.09 (make-acyclic-2uh-graph 2.09 '("abc" "123" "あいう" "カキク"))) ; try 10 --> #(2 0 1 0 1 2 1 1 2)
;; 完全ハッシュ関数(に必要なデータ)作成関数 (defun make-phf (c keys) (multiple-value-bind (graph hash-fns) (make-acyclic-2uh-graph c keys) (list (assigning c graph) hash-fns))) ;; 完全ハッシュ関数 (defun phf (key phf) (destructuring-bind (assign-table (hash-fn1 hash-fn2)) phf (let ((h1 (funcall hash-fn1 key)) (h2 (funcall hash-fn2 key))) (if (= 0 (mod (+ (aref assign-table h1) (aref assign-table h2)) 2)) h1 ; 一番目のハッシュ関数を返す h2)))) ; 二番目のハッシュ関数を返す ;; 例 (defvar *phf* (make-phf 2.09 '("abc" "123" "あいう" "カキク"))) ; try 10 ; try 9 --> *PHF* (mapcar (lambda (k) (list k (phf k *phf*))) '("abc" "123" "あいう" "カキク")) --> (("abc" 7) ("123" 6) ("あいう" 0) ("カキク" 5))
この例だとキー数が少ないので面白みがないが、一応各キーに一意な値を割り付けることができている。
追記(2010/07/14): 最小完全ハッシュ関数
別記事に分けようかと思っていたが、rank処理を追加して最小完全ハッシュ関数にするのは簡単なので、追記で載せてしまう。
;; make-phfが作成した完全ハッシュ関数にrank用のデータを追加し、最小完全ハッシュ関数を返す (defun ranking (keys phf) (destructuring-bind (assign-table hash-fns) phf ;; blocks: 特定のハッシュ値が使用されているかどうかを判定するためのbool列を32バイト整数にパックした配列 ;; 256ビット(32バイト)は、論文中に出てきたような気がするから使っているだけで、特に意味はない (let ((blocks (make-array #1=(ceiling (length assign-table) 256) :element-type '(unsigned-byte 256) :initial-element 0))) (loop FOR k IN keys FOR hash = (phf k phf) DO (multiple-value-bind (index bitpos) (floor hash 256) ;; 使用しているハッシュ値にはフラグを立てる (setf (ldb (byte 1 bitpos) (aref blocks index)) 1))) ;; 各ブロックより前方にあるブロック群に含まれる1ビット(= 使用中ハッシュ値)の数をカウント/保持する (let ((bases (loop FOR block ACROSS blocks COLLECT acc-1bit-count SUM (logcount block) INTO acc-1bit-count))) (list assign-table hash-fns blocks ; 追加 (coerce bases 'vector)))))) ; 追加 ;; rank関数: phf関数が返したhash-valueから、最小完全ハッシュ値を計算する (defun rank (hash-value mphf) (let ((rank-blocks (third mphf)) (rank-bases (fourth mphf))) (multiple-value-bind (index bitpos) (floor hash-value 256) ;; mph = 位置hash-valueよりも前方にある使用中ハッシュ値の数 (+ (aref rank-bases index) (logcount (ldb (byte bitpos 0) (aref rank-blocks index))))))) ;; 最小完全ハッシュ値を求める (defun mphf (key mphf) (let ((phf (subseq mphf 0 2))) (rank (phf key phf) mphf))) ;;; 例 ;; key set (defparameter *keys* '("abc" "123" "あいう" "カキク")) --> *KEYS* ;; phf (defparameter *phf* (make-phf 2.09 *keys*)) ; try 10 ; try 9 ; try 8 --> *PHF* (mapcar (lambda (k) (list k (phf k *phf*))) *keys*) --> (("abc" 6) ("123" 5) ("あいう" 4) ("カキク" 0)) ; 0 〜 (* (length *keys*) 2.09) ;; mphf (defparameter *mphf* (ranking *keys* *phf*)) --> *MPHF* (mapcar (lambda (k) (list k (mphf k *mphf*))) *keys*) --> (("abc" 3) ("123" 2) ("あいう" 1) ("カキク" 0)) ; 0 〜 (length *keys*)
以上。
追記2(2010/07/15): ranking関数修正
上のranking関数の実装では、キーセットを引数に取り、全部のキーに対してハッシュ値を計算している。
この処理(ハッシュ値計算)は実は本来不要で、assign_tableだけがあればrank用のデータは作成できる。
ただ、上記関数作成時点で、assigning関数にバグ*4があったため、それが出来なかった。
バグは修正したので、ranking関数も修正版を載せておく。
;; キーセットを引数に取る必要はない (defun ranking (phf) (destructuring-bind (assign-table hash-fns) phf (let ((blocks (make-array #1=(ceiling (length assign-table) 256) :element-type '(unsigned-byte 256) :initial-element 0))) (loop FOR n ACROSS assign-table FOR hash FROM 0 WHEN (/= n 2) ; n != 2 => ハッシュ値は使用されている ※ 2はハッシュ関数(= 枝の頂点)の数。初期化はassigning関数内で行われている DO (multiple-value-bind (index bitpos) (floor hash 256) ;; 使用しているハッシュ値にはフラグを立てる (setf (ldb (byte 1 bitpos) (aref blocks index)) 1))) ;; ここから下には修正なし (let ((bases (loop FOR block ACROSS blocks COLLECT acc-1bit-count SUM (logcount block) INTO acc-1bit-count))) (list assign-table hash-fns blocks (coerce bases 'vector))))))
