読者です 読者をやめる 読者になる 読者になる

DAWG(4-1): 完全ハッシュ関数

common lisp algorithm

四回目の前半。
DAWGのキーに一意なIDをマッピングするための最小完全ハッシュ関数を実装。
※ ただし今回実装分は、"最小"のつかないただの完全ハッシュ関数まで

参考元

『Simple and Space-Efficient Minimal Perfect Hash Functions』*1を参考にした。
ただし、まだ実装に必要な箇所に軽く目を通しただけなので、詳細は理解していない。
※ いつものことだけど、ちゃんと知りたい人はもとの論文を参照のこと

概要

とりあえず現状での理解。※ 間違っている可能性あり!

  • 定義:
  • 方法:
    • 前提: 対象となるキーセットはあらかじめ確定している
    • 複数のハッシュ関数を併用することで、(比較的容易に)一意性を達成
    • PHFでは、上記方法で各キーを0からM未満の値にマッピングする。
    • MPHFでは、まずPHFを用いてハッシュ値を算出し、その後に(その値に対して)rank操作を適用することで、0からN未満の値を得る。
      • rank操作:
        • 簡単に云えば、昇順に並んだ整数値列*2があるとして、その値を受け取って列内での位置(先頭からのオフセット, 添字)を返すのがrank操作(かな?) ※ 疎な整数値列を密な整数値列にマッピングする
        • 実装例は次回以降を参照(LOUDSの二回目も一応参照)
  • 処理的には三つのステップからなる
    • Mapping Step:
    • Assigning Step:
      • 各キーが、Mapping Stepで取得したハッシュ関数群の内のどれを用いれば良いかを判定するためのテーブルを作成する
    • Ranking Step:

実装

今回は完全ハッシュ関数までを作成する。
使用するハッシュ関数の数は、実装を簡単にするために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))))))

*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:正確には(?)rank用のデータ構造

*4:同関数内の2007/07/15日付けの追加コメントを参照