DAWG2(2.5): DAWG構築時のハッシュ値用の領域節約

前回にソート済みファイルからDAWGを構築する際には、個々のノードのハッシュ値をO(1)で(簡単に)算出可能にするために、ノードにハッシュ値用のフィールドを持たせていた。

;;;; 再掲
;; DAWGのノード用の構造体
(defstruct node
  (label     0 :type octet)
  (sibling nil :type (or null node))
  (child   nil :type (or null node))
  (hash     -1 :type fixnum))        ; 一度計算したハッシュ値をキャッシュしておく

;; ノードのハッシュ値算出
(defun sxhash-node (node)
  (if (null node)
      (sxhash nil)
    (with-slots (hash) node
      (when (= -1 hash)
        ;; キャッシュされていない場合だけ再帰的に計算を行う
        (setf hash (logxor (sxhash (node-label node))
                           (* (sxhash-node (node-child node)) 7)
                           (* (sxhash-node (node-sibling node)) 13))))
      hash)))

この方法は手軽かつ高速なのだけど、フィールドが一つ余分に必要になるのが難点。
キーセットのサイズが大きくなってくると若干気になりだす...。

そこで、O(1)でハッシュ値を算出可能な別の方法も候補に挙げておく。
こっちは若干遅い(多分)けど、余分なフィールドが不要。

;; 補助関数
;; オブジェクトのアドレス(ポインタの値)を取得する
(defun get-obj-address (obj)
  #+SBCL (sb-kernel:get-lisp-obj-address obj)  ; SBCLのみ対応
  #-SBCL (error "error"))

;; 三回のハッシュ値計算(sxhash呼び出し)でノードのハッシュ値を求める方法
;; - 子供や兄弟の構造が同一なら、既に共有されている(ポインタの値が等しい)はずなので、中身を見る必要はない
(defun sxhash-node (node)
  (if (null node)
      #.(sxhash nil)
    (logxor (sxhash (node-label node))                               ; ラベルのハッシュ値
            (*  7 (sxhash (get-obj-address (node-child node))))      ; 最初の子供へのポインタのハッシュ値
            (* 13 (sxhash (get-obj-address (node-sibling node))))))) ; 最初の兄弟へのポインタのハッシュ値

おそらくこれで大丈夫なはず。
※ logxorとか*7とか*13とかの、ハッシュ値の計算方法自体が適切か(均一にバラつかせることが可能か)どうか、という問題はあるけど

ただし、GCによってオブジェクトのポインタの値が変わってしまうような言語では、危険なので実用上は使えない。
(おそらく大抵のCommon Lisp処理系は無理？)
この方法を使うとしたらC++で、かな。

// 特に意味はないけど、C++版も載せてみる。
int node_hash (node* n) {
  if(n==NULL)
    return hash(0);
  else
    return hash(n->label)^(hash(n->child)*7)^(hash(n->sibling)*13);
}