DoubleArray(3-2): キーのサイズ縮小(or string型の利用)

common lisp algorithm

今までのDoubleArrayの実装では、当然のように(vector (unsigned-byte 8))をキーとして利用してきた。

文字列(キー)を扱う場合は、1byte(=8bit)を単位として扱うのが自然なので、悪くはない(むしろ良い?)とは思うのだが、2byte以上を単位として扱うのも、それはそれで利点があるのではないかと思う。

例えば、文字列を2byte単位で扱う場合、以下のような利点があるのではないかと思う。　※ 思いっきり憶測

  • BASE(及びCHECK)配列のサイズが小さくなる
    • DoubleArrayの場合、その実装が#xFF分木から#xFFFF分木になったとしても、（リストによる実装と同様に)余計な空間を消費することがない。
    • そして、キーの長さは1/2になるために、各キーごとに必要な(BASE・CHECK配列の)ノード数は少なくなり、BASE配列全体も小さくなる。
    • ただし、各キーの共有可能な部分は減るので、全体のサイズが単純に1/2になることはない。(後、TAIL配列との関係とか...)
  • 検索速度が速くなる
    • キーの長さが半分になるので、検索時に必要なループ回数も(だいたい)半分となる。
    • ただし、1byte配列から2byte配列への変換コストがかかる場合は、そのコストのために全体としては遅くなる可能性もある。

で、今回は特に、上に挙げた利点の内の、前者(サイズ縮小)の方を試してみることにする。

実装方法(?)

上では、「キーを1byte配列として扱っていたのを2byte配列としたら...」というように書いたが、これをそのまま実装するのは面倒なので、今回はcommon lispのstring型をキーとして利用することにする。


今までのDoubleArrayの実装では、引数として渡されたstringを、一旦(vector (unsigned-byte 8))に変換して、挿入や検索を行っていた。

その主な理由は、stringの要素(character)のコード表現が1byte以上となる可能性があるためだったのだが、既に書いたようにDoubleArrayが2byte以上も扱えるのならば、わざわざ一度byte列に変換する必要もなく、stringをそのまま利用することができる。


加えて、日本語を含む大抵のstring型は、以下のように(vector (unsigned-byte 16))にマップできるので(※sbclの場合)、2byte配列だとして考えてもそれほど問題はない。

> (type-of (map '(vector (unsigned-byte 16)) #'char-code "日本語"))
--> (SIMPLE-ARRAY (UNSIGNED-BYTE 16) (3))

実装

DoubleArray(2): 挿入速度改善での実装をベースとして使う。

修正を加えた箇所は以下の通り*1。

;; 最大値を変更
;; (sbclの場合は)characterの最大値は#x110000だが、それだと挿入速度が遅くなりすぎるので、
;; とりあえず#xFFFFとした(ほとんどの日本語はこの範囲で扱えたはず...)。
(defconstant MAX-CODE #xFFFF)

;;; struct
(defstruct (double-array (:conc-name da-))
  (base (make-array 32 :element-type 'fixnum :initial-element NULL))
  (chck (make-array 32 :element-type 'fixnum :initial-element NULL))
  ;; tailの要素はcharacter型に変更
  (tail (make-array 32 :element-type 'character :adjustable t :fill-pointer 1)))


;; 文字列->byte列への変換は必要なくなったので、この名前は適切ではないが、
;; 変更箇所を減らすために、関数名はそのままにする。
;; (code-char EOS)を末尾に付けたstringを返す
(defun eos-terminated-octets (octs &aux (len (length octs)))
  (adjust-array octs (1+ len) :initial-element #.(code-char EOS)))

;; 以下の二つの関数は、
;; /=を使っていたところを、char/=を使うように変更
(defun common-prefixes (o1 start1 o2 start2)
  (do ((i start1 (1+ i)) (j start2 (1+ j)))
      ((char/= @o1#i @o2#j) (coerce (subseq o1 start1 i) 'list))))

(defun tail=(octs start tail-start &aux (len (length octs)))
  (do ((i start (1+ i)) (j tail-start (1+ j)))
      ((= i len) t)
    (if (char/= @octs#i @*tail*#j) (return nil))))

;; これ以降の関数は、
;; 1byteのコード値を使っていたところを、
;; 適宜(char-code 文字)を使うように変更
(defun get-next (code node)
  (+ @*base*#node (char-code code))) ;;;

(defun set-node (code prev x &aux (next (+ (char-code x) (char-code code)))) ;;;
  (allocator:alloc next)
  (setf @*base*?prev (char-code x) ;;;
        @*chck*?next prev)
  next)

(defun make-char-code (#1=char-or-code)      ;;;
  (if (characterp #1#) (char-code #1#) #1#)) ;;;

(defun x-check (set)
  (setf set (mapcar #'make-char-code set)) ;;;

  (let ((x (allocator:x-check set)))
    @*chck*?(+ x (apply #'max set))
    (code-char x))) ;;;

(defun modify-nodes (current node codes &optional c &aux (old-base @*base*#node))
  (let ((new-base (char-code (x-check (if c (cons c codes) codes))))) ;;;
    (setf @*base*#node new-base)

    (setf codes (mapcar #'make-char-code set)) ;;;

    (dolist (code codes)
      (let ((old (+ old-base (char-code code)))  ;;;
            (new (+ new-base (char-code code)))) ;;;
        (shiftf @*base*?new @*base*#old NULL)
        (shiftf @*chck*?new @*chck*#old NULL)
        (allocator:free  old) 
        (allocator:alloc new)
        
        (when (plusp @*base*#new)
          (setf *chck*
                (nsubstitute new old *chck*
                             :start (1+ @*base*#new)
                             :end (min (length *chck*) (+ @*base*#new MAX-CODE)))))

        (when (and (/= current node) (= current old))
          (setf current new)))))
  current)

以上。
この実装では、挿入速度が極端に遅くなるが、それ以外は特に1byte配列からstringに変換したことでの問題はなさそうだ。

比較

キーとしてstringを使った場合と、utf-8エンコードの(vector (unsigned-byte 8))を使った場合、euc-jpエンコードの(vector (unsigned-byte 8))を使った場合の、BASE配列サイズを比較する。


結果

キーの型挿入数(キーの)平均サイズBASE配列サイズ*2
string5万9.68104,924
utf-8エンコードの(vector (unsigned-byte 8))5万22.34168,438
euc-jpエンコードの(vector (unsigned-byte 8))5万16.02136,123

やはり、BASE配列のサイズはstringを使ったものが一番小さくなっている。
common lispの場合は、一度byte配列にエンコードせずに、stringをそのまま使えるというのも利点*3だと思うので(本当に?)、この方法は(改良の必要はあるが)使えるかもしれない。

追記(2009/10/06)

この記事を書いた後に、実際に上述のアイディアを(C++で)試してみたが、結局使えないことが分かった。
理由は下記の通り。
・速度向上? => 確かにキーの長さは短くなるので、その点では速くなっているようだが、キーを多バイトずつ扱うためのコストのせいで、結局総処理時間は長くなってしまった(試した限りでは、1.2倍くらい)。
・サイズ縮小? => 確かにサイズは縮小できるのだが、これを使うよりはこっちで試した方法の方が、縮小率が良かった。かつ、この二つの方法は両立しないので、それなら後者を使った方が良い。

*1:tail配列のelement-typeを(unsigned-byte 16)にして、make-octets関数内でstringの各要素をchar-codeでmapするようにすれば、こんなにいろいろ修正しなくても良かったのでは、と修正が終わってから気がついた。

*2:末尾の未使用領域は除いている

*3:追記(2010/03/23): 実際上は、このメリットが一番大きいように思う。最近作成したJavaの形態素解析器では、単語の辞書引きに使用しているDoubleArrayを、この考えを反映して(Javaにとって自然な)2byte(UTF-16)単位でキーを扱うよう実装した。そのおかげでキーの検索部分はかなり素直なコードとなった。