DAWG2(1): ソート済みファイルからのトライ構築

common lisp sbcl algorithm

七月にやっていたDAWG(Direct Acyclic Word Graph)シリーズ(?)の続き。
結構長い間中断していて自分でも内容がうろ覚えなので、仕切り直してもう一度。
今回はDAWGの前段階として、ソート済み(かつ各行がユニーク)なファイルからトライを構築する。

DAWG

軽くおさらい。
※ 例によって個人的な理解であり、正しくない可能性あり

  • トライに似ている
    • 機能的にはDAWGとトライは一緒
  • トライの共有可能な接尾部分(サブトライ)をまとめたものがDAWG
    • 二つの等価なノード(サブトライ)がある場合、その内の片方のみを使用するようにする
    • 一般に、同一のキーセットを表現するために必要なノード数がトライに比べて少なく、サイズ効率が良い
  • ただし、接尾部分を共有する関係上、汎用的なマップとして使用するには適さない
    • 各キーに(対応する値として)一意なIDを付与した場合は、DAWGはトライと等しくなってしまう
      • サブトライの共有が全くできなくなるので
    • セットあるいはキーの値が極度に偏っているようなマップ、としての用途に適する

ソート済みファイルからのトライ構築

以下、あらかじめソートされたキーセットが(改行区切りで)格納されているファイルからトライを構築するためのソースコード。
※ 参照: each-file-line-bytes

(defpackage trie
  (:use :common-lisp)
  (:shadow :common-lisp get read-byte)
  (:export build-from-file  ; ソート済みファイルからのトライ構築
           node-count       ; トライのノード数を数える
           get))            ; キー検索
(in-package :trie)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; スペシャル変数 ＆ 型定義 ＆ 宣言
;; 速度重視の最適化宣言用変数
(defvar *fastest* '(optimize (speed 3) (safety 0) (debug 0)))

;; 型定義
(deftype octet () '(unsigned-byte 8))
(deftype octets () '(simple-array octet))
(deftype array-index () `(mod ,array-dimension-limit))

;; インライン宣言
(declaim (inline make-byte-stream peek-byte read-byte eat-byte make-node))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; キー(バイト列)をストリームとして扱うための構造体と関数
(defstruct byte-stream 
  (bytes #() :type octets)
  (cur     0 :type array-index)
  (end     0 :type array-index))

;; 位置を一つ分進めたストリームを返す
(defun eat-byte (in)
  (incf (byte-stream-cur in))
  in)

;; 現在位置のバイトを取得する。終端に達している場合は0を返す
(defun peek-byte (in)
  (with-slots (bytes cur end) (the byte-stream in)
    (if (>= cur end)
        0
      (aref bytes cur))))

;; 現在位置のバイトを取得し、位置を一つ分進める。終端に達している場合は0を返す
(defun read-byte (in)
  (prog1 (peek-byte in)
    (eat-byte in)))

;;;;;;;;;;;;;;;;;;;
;;;; トライのノード
(defstruct node
  (label     0  :type octet)
  (children '() :type list))  ; 子ノード(サブトライ)群はリンクリストとして保持する

;;;;;;;;;
;;;; 挿入
;; 新しい子ノードを、parentノードの最初の子として追加する
;; ストリームinの全てのバイトを消費するまで、再帰的に処理を続ける
(defun push-child (in parent)
  (declare #.*fastest*) 
  (let ((new-node (make-node :label (peek-byte in))))  ; ノード作成
    (push new-node (node-children parent))             ; 先頭に追加
    (when (plusp (read-byte in))
      (push-child in new-node))))

;; キーを挿入する
(defun insert (in parent)
  (declare #.*fastest*)
  (let ((node (first (node-children parent))))
    (if (or (null node)                             ; 1) parentに子ノードがいない場合
            (/= (peek-byte in) (node-label node)))  ; 2) 先頭の子ノードとラベル(バイト)が異なる場合 ※1
        (push-child in parent)       ; キーの残りのバイト列を、子ノードとして追加する
      (insert (eat-byte in) node)))) ; このバイトに対応するノードは既に存在するので、次のバイト(と子ノード)を処理する
#|
※1: キーはソート順で挿入されるため、先頭の子ノードとラベル(バイト)が異なる場合は、
　　 (peek-byte in)の値は、(node-label node)よりも大きいものとなる。

　　 そして、(peek-byte in)の値をラベルとして作成されたノードが、
　　 先頭の子ノードとして新らたに追加されるので、ここで構築するトライの各ノードの
　　 子ノードは、ラベル(バイト)の降順に整列することになる。
|#

;; ソート済み(かつユニーク)のファイルからトライを構築する
;; - 各キーはバイト列として扱う
;; - 各キー(バイト列)の末尾には、終端文字としてヌル文字を付与する (peek-byte関数参照)
(defun build-from-file (filepath)
  (declare #.*fastest*)
  (let ((trie (make-node)))
    (each-file-line-bytes (bytes beg end filepath)
      (let ((in (make-byte-stream :bytes bytes :cur beg :end end)))
        (declare (dynamic-extent in))
        (insert in trie)))
    trie))

;;;;;;;;;
;;;; 検索
(defun get-impl (in parent)
  (loop FOR node IN (node-children parent)
    DO
    (cond ((> (peek-byte in) (node-label node))
           (return nil))
          ((= (peek-byte in) (node-label node))
           (return (or (zerop (peek-byte in))
                       (get-impl (eat-byte in) node)))))))

;; key(文字列)がトライに含まれているかどうかを判定する
;; ※ 今回は動作しさえすれば良いので、最適化宣言等は行っていない
(defun get (key trie)
  (let* ((bytes (sb-ext:string-to-octets key)) ; XXX: この部分はSBCL依存
         (in (make-byte-stream :bytes bytes :cur 0 :end (length bytes))))
    (get-impl in trie)))
     
;;;;;;;;;;;;;;;;;;;;;
;;;; ノード数カウント
(defun node-count (trie)
  (loop FOR child IN (node-children trie)
        SUM (1+ (node-count child))))

構築時間とノード数

後々の作成物との比較のために、上記トライを構築するための時間とそのノード数を計測しておく。
まずはそのためのデータ(キーセット)を用意。

## データ用意
# Wikipediaの記事タイトル: 約500万行
$ ./wikipedia-title.sh > wiki.title.500
$ wc -l wiki.title.500
5340379

# Wikipediaの記事タイトル: 約250万行
$ ruby line-filter.rb 2 wiki.title.500 > wiki.title.250

# Wikipediaの記事タイトル: 約50万行
$ ruby line-filter.rb 10 wiki.title.500 > wiki.title.50

#! /bin/sh
#
# データ用意用スクリプト１
# 各国語のwikipediaの記事タイトルを取得し、ソート&ユニークした結果を出力する

TMP=`mktemp -d`
cd $TMP

wget http://download.wikimedia.org/jawiki/20100607/jawiki-20100607-all-titles-in-ns0.gz
wget http://download.wikimedia.org/euwiki/20100612/euwiki-20100612-all-titles-in-ns0.gz
wget http://download.wikimedia.org/zhwiki/20100612/zhwiki-20100612-all-titles-in-ns0.gz
wget http://download.wikimedia.org/fiwiki/20100620/fiwiki-20100620-all-titles-in-ns0.gz
wget http://download.wikimedia.org/frwiki/20100614/frwiki-20100614-all-titles-in-ns0.gz
wget http://download.wikimedia.org/svwiki/20100620/svwiki-20100620-all-titles-in-ns0.gz
wget http://download.wikimedia.org/trwiki/20100620/trwiki-20100620-all-titles-in-ns0.gz
wget http://download.wikimedia.org/hewiki/20100620/hewiki-20100620-all-titles-in-ns0.gz
wget http://download.wikimedia.org/nowiki/20100619/nowiki-20100619-all-titles-in-ns0.gz
wget http://download.wikimedia.org/cawiki/20100619/cawiki-20100619-all-titles-in-ns0.gz

gzip -d *-ns0.gz
cat *-ns0 | LC_ALL=C sort | LC_ALL=C uniq

cd ..
rm -rf $TMP

echo DONE

# データ用意用スクリプト２
# Usage: ruby line-filter.rb <数値:何行に一つを出力するか> <入力ファイル>

N = ARGV[0].to_i
open(ARGV[1]).each_with_index do |line,i|
  if i%N == 0
    puts line
  end                              
end

構築時間とノード数。

;;; sbcl-1.0.40

;;; Wikipediaタイトル: 50万行
;; 構築
(time
 (defparameter *trie50* (trie:build-from-file "wiki.title.50")))
Evaluation took:
  3.747 seconds of real time
  3.740000 seconds of total run time (3.200000 user, 0.540000 system)
  [ Run times consist of 3.450 seconds GC time, and 0.290 seconds non-GC time. ]
  99.81% CPU
  8,617,362,375 processor cycles
  331,201,008 bytes consed
--> *TRIE50*

;; ノード数
(trie:node-count *trie50*)
--> 6897632  ; 690万

;;; Wikipediaタイトル: 250万行
;; 構築
(time
 (defparameter *trie250* (trie:build-from-file "wiki.title.250")))
Evaluation took:
  23.904 seconds of real time
  23.900000 seconds of total run time (20.020000 user, 3.880000 system)
  [ Run times consist of 22.490 seconds GC time, and 1.410 seconds non-GC time. ]
  99.98% CPU
  54,975,170,067 processor cycles
  1,397,494,464 bytes consed
--> *TRIE250*
  
;; ノード数
(trie:node-count *trie250*)
--> 29112012  ; 2911万

;;; Wikipediaタイトル: 500万行
;;; ※ メモリ(2GB)が足りなくなったのでパス

GCの処理時間がやたら長いのが気になる。