ツリー構造、もう１つの答

をいをいをいをい、ホットエントリーに載るって、こんなに大変なことだったのか。
正月早々、俺はパソコンに向かって何やってんだ。
もっとまったりと、ダラダラする予定だったのに・・・
でも気になる、気になるんだよー。。。なんかフォローを書かずにはいられない。
以下は前回のエントリー [id:rikunora:20081228] の続編です。

大きな数を表すとき、日本では「一、十、百、千」を１つの塊として、それに「万、億、兆・・・」といった名前を付けています。
一方、英語では「One, Ten, Hundred」を１つの塊として、それに「thousand, Million, Billion・・・」といった名前を付けます。
日本の塊は４つずつ、英語の塊は３つずつです。
そこで、日英対決！
４と３ではどちらがより効率的なのでしょうか。

前回のエントリーで
* 数字という文字を、ギリシア数字で考えるとIVXの３文字で表示？
というコメントをいただきました。
これはまた、おもしろい数字体系に着目しましたね。

※「ギリシャ数字」じゃなくて「ローマ数字」だった！あっちゃー。。。(1/8追記)
ギリシア数字は「３つの記号 -> それを組み合わせて数を表す」という、一段階置いた間接的な仕組みをとっていますよね。
そこで「複数の記号をひとまとめに扱って、操作レベルを１段階増やす」方法もあることに気付きました。
上述の、大きな数を幾つかのブロックにまとめて数える方法。
ギリシア数字のように、いったんIVXの３文字で表記するという段階を踏んで、その上で操作を行う方法。
今回は、こうした多段階の仕組みに着目してみましょう。

実際の日本語や英語では、塊を作る階層が１段階だけなのですが、
以下ではツリー構造を想定して「多段階の数え方」というものを考えることにしましょう。
「多段階の数え方」とは、「一、十、百、千」という４つの数字記号だけしか使わない代わりに、
「５百千千千」のように、記号を何回繰り返してもよい、とする数え方です。
こうした恣意的な仮定を導入して、問題を「ツリー構造の性能評価」という一般的なものに落とし込んでみます。

図の右端が「日本語型４分岐」、中央が「英語型３分岐」、左端が比較のための最も単純な「２分岐」ツリーです。
この３つのツリーの中で、どれが最も優れているのでしょうか？
最適な分岐数というものは存在するのでしょうか？

ところで、ツリー構造って何だろう。
身近な例は、パソコンのフォルダ。
パソコンの中では、たくさんのファイルはフォルダを作って整理しますよね。
あれはツリー構造そのもの。
今、考えているのは「１フォルダに平均何個くらいファイルを置いたら最も効率的か」という問題と同じことです。
ツリー構造はデータの分類整理に威力を発揮する、すごい発明なんです。
いわゆるデータベースでは、高速な検索技術としてツリー構造を用いています。
なのでこの問題は、高速なデータベースを作るにはどうすればよいか、という実用上の問題と深く関係しているんです。

さて、ただ漫然とツリーの絵を眺めていても、答は思い付きません。
ここはひとつ、もっとも単純な仮定、
　　（記号を１つ増やす手間）＝（操作段階を１段増やす手間）　　・・・[仮定１]
を入れてみましょう。
操作段階（＝ツリーの高さ）がＮ段だったとき、表し得る状態数（＝ツリー底辺の長さ）は、
それぞれのツリーで 4^N、3^N、2^N です。
なので、ある一定の状態数Ｍ個を表わすのに要する手間は、
　　Ｍ = Ｎ^Ｎ
となります。
この f(N) = Ｎ^Ｎを最小にするようなＮはいくつになるか。
対数をとって微分してみます。
　　f(N) = N^N
　　log f(N) = N log(N)
　　(log f(N))' = log(N) + N・(1/N) = log(N) + 1
(log f(N))' = 0 となるのは、- log(N) = 1 になるとき、
つまり、N = 1/e となるときが最小値です。
（直接 f(N)' を求めると、N^N { 1 + log(N) } となります。
　なんだか大学入試問題みたい。暇な人はやってみよう。）
f(N) = N^N という関数がおもしろいので、グラフに描いてみました。

1/e = 0.367879 のところに極小点があります。
つまり、[仮定１] を正しいものとすれば、ツリーの分岐は約0.37本が良い。
実際には小さいほど良い、つまり２分岐ツリーが最適ということになります。

でも、実際のところ [仮定１] は妥当でしょうか。
パソコンでファイル１個作るのと、フォルダ階層１つ作るのと、どちらの手間が大きいか。
普通の感覚からすれば、（ファイル作成の手間）＜（フォルダ階層の手間）ですよね。
そこで、この手間の比率を R と置いて、改めて次の仮定を布いてみます。
　　（記号を１つ増やす手間）＝ R ・（操作段階を１段増やす手間）　　・・・[仮定２]
つまり、このツリー比較にベストの答なんてものはなくて、
最適な分岐数は、操作段階を１段増やす手間によって変わってくる、ということです。
ある一定の状態数Ｍ個を表わすのに要する手間は、
　　Ｍ = (Ｎ / R) ^ Ｎ
以下、上と同じようにして
　　f(N) = (N/R)^N
　　log(f(N)) = N log(N/R) = N { log(N) - log(R) } = N log(N) - N log(R)
　　(log f(N))' = log(N) + 1 - log(R)
(log f(N))' = 0 となるのは、log(N) = log(R) - 1 になるとき、
つまり、N = R / e となるときが最小値です。
（直接 f(N)' を求めると、(n/r)^n ・{ 1 + log(n/r) } ってなるんだぞ。
　ううっ、難関大学入試問題・・・）
N と R の関係は直線的だったんです。
ここから、
・４分岐ツリー（日本の数え方タイプ）のＲ = 約 10.87
・３分岐ツリー（英語の数え方タイプ）のＲ = 約 8.15
といった数字が出てきます。
英語の方がより操作的、ツリー階層を作るのに躊躇しないんですかね。
そういえば、アルファベット２６文字よりも、漢字まで持っている日本語の方がずっと記号の種類も多いし。
ちなみに、問題の発端となったギリシア数字は、およそ３分岐ツリーの延長上（３分岐ツリーを１段深く掘り下げた形）となっています。
つまり、西洋文化は昔から階層を作りたがる傾向にあるのだと、、、そういった妄想に発展するわけですね。

- - - - -

ところで、上のツリー構造のお話は、前回のエントリーの「ｅ進法」とどのように関係するのか。
なんか、前回と違うこと言ってない？
はい、違うこと言ってます。
じゃあ前回の「ｅ進法」はウソなの？
いや、そんなこともないです。
前回のは前回ので、一理あるんです。
視点が違いますから！
以下に、とっても常識的で、アタリマエで、つまらないお話を付け足します。

最も優れた進数とは、いくつなのか？
前回のエントリーと合わせて、私は３つの視点を提供したつもりです。
　視点１．ｅ進法 -- 回路設計者の視点。
　視点２．めんどうくささ -- 日常的な視点。
　視点３．ツリー構造 -- データベース設計者の視点。
この３つには、それぞれ前提、仮定があって、結論があります。
これはなにも進数の話に限ったことではなくて、何だってそうです。
　　　　　(前提)、(仮定)　->　(結論)
　視点１．機械、２状態のランプ -> ｅ進法が最適。
　視点２．人間、めんどくささ = 桁数Ｋ＋基数Ｎ -> １０進数はちょっと多めかな？
　視点３．機械/人間両方、検索の手間 = (N/R)^N -> 階層を作るコストに依存。
こうして見渡せばわかりやすいかな。
この視点ってやつは、３つで終わりなのか？
そんなことないですよね。
考えれば、まだいくらでも出てくると思います。
実は、今回の視点３．は、わざわざ「別の視点が存在するんだよ」ということを示すために作ってみました。
（なので視点１．よりも、もっと話に無理がありますね。）
その気になれば、私はあと３つくらい、同列のお話を作れます。（もう飽きたから寝るけど）

ｅ進法について、ブックマークのコメントを見たところ、どうやら
「最初から２状態のランプを使って考えれば、２進法に有利なのは当たり前じゃない？」
という疑問が多いみたいですね。
その通り。
仮定ですから、アタリマエです。
その仮定が妥当かどうか、自然に受け容れられるかどうか、という判断だけです。
自然だと思えば受け容れるし、こじつけだと思ったら捨てる、それだけ。
私としては、２状態という仮定を布いたにもかかわらず、
結果が２ではなく2.71828...と、ずれた所に来たのが興味深いな、と思っています。

ちなみに、ｅ進法というのは私がオリジナルに考え出したアイデアではありません。
エントリー中で紹介した以下のページにも、よく見ると書いてありますよ。
* 三進法のコンピューターが、二進法のコンピューターより優れた点は？
>> http://oshiete1.goo.ne.jp/qa2083198.html
「原理的にはｅ=2.718・・・進法のコンピュータが最も効率がいいそうです。」
実は、私も以前「原理的にはｅ進法」という結論のところだけ、小耳に挟んだことがあったんです。
でも、なぜそうなるかという説明まではなかった。
そこで、なぜそうなるかという理由を自分なりに考えて、導き出したのが「ランプ」だったのです。
実際のところ「ｅ進法」に、どれほどの妥当性があるのか、私にも計りかねます。
おそらく「ｅ進法」の言い出しっぺは、回路設計者の視点に立って、このことを言ったのだと思います。

ランプでｅ進法、というお話は、もちろん絶対の真理ではありません。
（もし頭からそう信じていた人がいたら、(前提)、(仮定)を問う習慣を付けよう。）
そもそも「最も優れた進数」というお話に、唯一絶対の答なんて無いんです。
なぜ無いのか。
それは、(前提)、(仮定) によって答が変わってくるからです。
設問の立て方が悪くて、あいまいで、(前提)、(仮定)が１つにビシッと決まっていない。
なので、いくらでも妄想を繰り広げる余地があるんですねー。

で、そこまで認めた上で、期待していたのは、もっとオモロくて斬新な視点だったんだけどなー。
私はしょせんコンピューター技術者なので、コンピューターチックな発想しか出てこないんですよ。
これだとつまらない。
なんかこう、俺は前衛的なジャズが好きだから11拍子だっ！とか。
ゴルゴが好きだから１３なんだっ！とか。
個人的には「えーっ、そんなのあり？！」って叫んじゃうような、ぶっ飛んだ発想が好き。
やりすぎるとホントに飛んでっちゃうんで、そのさじ加減が微妙なんですが。。。
視点４．以降の、オモロい発想を期待してるよっ！