Emacs Lisp Hash-table for SKK

データ構造 Hash-table の理解を深めるため、 SKK 辞書の検索関数を作ってみることにする。

まず、skk-search-jisyo を調べて、SKK のラージ辞書がどのように検索されるか調べた。
ちょっと長いので、辞書のエントリーの削除機能、バイナリサーチの機能に相当する部分を削除して眺める。
リニアサーチの機能だけみると、割と単純で search-forward で検索している。
この辞書ファイルを Hash-table に読み込んでみた。本当は、見出し部分と変換候補データ（リスト）に分解すべきだが、とりあえず見出しと残りだけにしておく。また、コメント行は読み込まない。

(defun skk-jisyo-hash (file)
  (let ((ht (make-hash-table :test 'equal)))
    (let ((buf (skk-get-jisyo-buffer file t)))
      (with-current-buffer buf
	(goto-char (point-min))
	(while (not (eobp))
	  (beginning-of-line)
	  (if (looking-at "^;")
	      nil
	    (if (looking-at "\\(^[^ ]+\\) \\(.*\\)$")
		(puthash (match-string-no-properties 1)
			 (match-string-no-properties 2) ht)))
	  (forward-line))))
    ht))

これでラージ辞書をハッシュテーブルにできた。数秒は掛かった。

(setq *ht* (skk-jisyo-hash skk-large-jisyo))

skk-large-jisyo ファイルは、１７万行もあるので、ハッシュのコリジョンが気になる。
sxhash がハッシュ値を計算しているので、ハッシュテーブル *ht* のキーに対して sxhash を計算させても同じハッシュ値のはず。
ファイルに出力して、R でヒストグラムでも書いてみよう。予想では平均的な分布のはず、、

おっと。全然均等でもないし、よくみると sxhash にはマイナスの値もある。これでいいんだろうか。しかもこのハッシュ値はたまたまか、コリジョンもしてる。

(sxhash "れんらくいたs") => -222760998
(sxhash "れんきゅうあk") => -222760998

しかし、ハッシュテーブルとしておかしいわけではなく、gethash は正しい値を返した。
また、ファイルに出力したハッシュ値を調べると、同じハッシュ値は５０００件くらいであった。十分少ない(つまり優秀なハッシュ関数である)ような気がするが、まだ何とも言えない。

そういえば、sxhash の値から、ハッシュテーブルの本体の配列の添字に変換していると思う。
ということは、どこかでモジュローの計算などで値の範囲を変えているいるはず。

続く。