mots quotidiens.
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp by hns, version 2.10-pl1.

先月 2006年12月 来月
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

2006年12月23日() [n年日記]

#1 Splay Tree

研究上必要があって, 前々からずっと気になっていた, SleatorとTarjanの スプレー木(Splay Tree) [LINK] を実装した。
スプレー木は「自己調整(自己組織化)二分木」ともいわれる通り, 頻度の高いアイテムをアクセスの際に木の上の方に自動的に持ってくることで, 高頻度なアイテムへの高速なアクセスを実現する順序木。 自然言語の文字列や単語列の頻度は偏りや Power law の固まりなので, 非常に適している と思う。 かつ, 最悪の場合でもスプレー木は 全体を通して, O(log n) のアクセスを提供することがわかっている。

トライを表現するデータ構造としては, 松本研的には Double Array や その実装である Darts がすぐ思い浮かぶと思いますが, Double Array は既に固定されたトライには高速にアクセス できるものの, 新しいノードの追加や削除が超遅い (単純な線形サーチより遅い) *1 ので, 動的なデータ構造としては向いていない。
AVL木のようなアルゴリズムの授業でよく出てくる平衡木と違い, ノードに余分な データを持たせる必要がなく, かつデータの挿入/検索に伴って自動的に データ構造が調整されて高速なアクセスができる二分木になっている。
例によって, この手の話は中身をちゃんと理解しないと使えないわけですが, 日本語だと, M.Hiroi さんが今年になって 解説 を書かれているようで, とても参考になります。ただ, これだけではわからない部分が 多いので, 原論文 を読むとすっきりと理解できると思います。 3日くらい, 計算用紙に二分木を書きまくって, ようやく大体わかってきた。

スプレー木の基本は, アクセスしたノードを木の回転操作によってルートに持ってくる "move to root" 操作。ただこの際に, ただ順番に木を回転すると, 木のバランス が悪くなってしまい, O(log n)でなくなってしまう。
極端な例として, 木Δの左下端の ノードを回転で根に持ってくると, 根の左側はNULLになり, 木の高さが1増えてしまう。 これを避けるために, 上のような木の"稜線"に沿ったアクセスの場合には, 先に上の ノードを回転し(雰囲気的に言うと, 木をそこで山折りに折り直して), その後で自分のノードを回転する(splay 操作)。 こうすることで, 木が平衡状態に常に近く保たれる。 アクセスされたノードはこの操作で上に集まるので, 二分順序木の中で, 頻度の高いノードは自然に上の方に, 頻度の低いノードは下の方に集まることになる。
上のページ に, splay 操作のデモがあります。

実装としては, Sleator が提供しているもの があってそれで充分なのですが, このサンプルコードは int の二分木だけなので, void * の一般的なデータを挿入できるように一般化してみました。
最終版ではないですし, 需要があるかどうかわかりませんが, 下に置いておきます。

splay.c splay.h

C++ならテンプレートで何とかする所だと思いますが, シンプルにCでする場合は, qsort と同じように, ノードを比較する関数へのポインタを与えて

splay *tree = NULL;
for (i = 1; i < argc; i++)
    tree = splay_insert(tree, argv[i], (cmpfunc)strcmp);

として使えるようになっています (上は文字列を挿入する例)。

さてそうすると, 実際に言語のデータを与えた時, どんな二分木ができるのかが 気になるところ。 上の splay.c を使って, 下のようなプログラムを書くと,

% gcc -c splay.c
% gcc -o sptest sptest.c splay.o
% ./sptest [text]

で, スペースで区切られたテキストの単語を次々に木に挿入して(この時, 自動的に 木が調整される), 最後にスプレー木が出力される。

/*
    sptest.c

*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "splay.h"

int
read_word (FILE *fp, char *buf)
{
        return fscanf(fp, "%s", buf);
}

int
main (int argc, char *argv[])
{
        splay *tree = NULL;
        char s[BUFSIZ];
        FILE *fp;

        if ((fp = fopen(argv[1], "r")) == NULL)
        {
                perror("fopen");
                exit(1);
        }
        while (read_word(fp, s) != EOF)
        {
                if (splay_find(&tree, s, (cmpfunc)strcmp) == NULL)
                        tree = splay_insert(tree, strdup(s), (cmpfunc)strcmp);
        }

        splay_print(tree, (prfunc)puts);

        fclose(fp);
        return 0;
}
上のプログラムを使って, "Alice in Wonderland" の全文(約3600行)と, 毎日新聞2000年度の全テキスト (約150万行, 高頻度20000語)から構築したスプレー木が以下。
alice-tree.txt mai-tree.txt
splay_print() の定義をよく読むとわかると思いますが (M.Hiroiさんのプログラムからお借りしました), この木は左が上で, 頭を90°左に回転させて読みます。 *2 順序二分木なので, 単語は上から下に順にソートされていますが, 頻度の高い単語が見事に左の方(つまり, 木の上の方)に集まっていることがわかって, 面白い。
*1: 最近は少し改善されているかも知れませんが, 基本的に固定されたトライへの アクセスを提供するという部分は, 多分変わっていないと思う。
*2: "Alice" の方は "end" が根になっていますが, これはスプレー木が 最後にアクセスしたアイテムをルートに持ってくるためで, テキストの最後が end で終わっているからです。

#2 分析

上のデータでは, になっています。

ここで, 構築されたスプレー木を使ってテキストを読み直して, アクセスされた 単語ノードの深さの平均を計算してみたところ,

でした。 log2(26406)=14.7, log2(20000)=14.3なので, つまり, 動的に構築した このスプレー木は最深部が深さ33-36と充分大きいにもかかわらず, 完全二分木より さらに性能が良くなっているということ。 *3
log を取っているのでそれほど違いがないように見えますが, このスプレー木の"パープレキシティ"を計算すると, それぞれ 2^12.13 = 4502, 2^13.39 = 10774 になって, それぞれ実効語彙数が4500, 10000程度の 完全二分木と同等になっている。
データを読みながら, 動的に完全二分木を作ることは非常に難しいことを 考えると, 動的に作っているにも関わらず, 言語の性質を利用して 完全二分木よりもさらに良い性能を出しているというのは素晴らしいと思う。 上の平均の計算はスプレー木を固定して行いましたが, スプレー木はアクセスする毎に splay 操作が起こってノードが根に来るため, 一種の 「キャッシュ」が掛かるので, 実際の性能はさらに高くなっている可能性がある と思う。
*3: 内部節点を使わない二分探索の場合。 内部節点も使う場合は, もう少し数値が違ってくると思う。

・ Acknowledgement

実装に際して, エンジニアのF澤さんにアドバイスをいただきました。 感謝します。


1 days displayed.
タイトル一覧
カテゴリ分類
 なかのひと
Powered by hns-2.10-pl1, HyperNikkiSystem Project