総合科目「IT革命を解き明かす」、2005年11月07日 電子・情報工学系 新城 靖 <yas @ cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.softlab.cs.tsukuba.ac.jp/~yas/gen/it-2005-11-07
あるいは、次のページから手繰っていくこともできます。
http://www.softlab.cs.tsukuba.ac.jp/~yas/gen/
http://www.cs.tsukuba.ac.jp/~yas/
印刷配布資料 http://www.softlab.cs.tsukuba.ac.jp/~yas/gen/it-2005-11-07 /it-2005-11-07 .pdf
木構造(tree structure)というのは、コンピュータ・サイエン ス(情報学類で学ぶ学問)でよく使われる用語である。分野によっては、同じ ものを階層構造(hierarchical structure)という言葉で表現す ることが好まれる。ドイツ語語源の、ヒエラルヒー(Hierarchie)という言葉が 使われることもある。
木構造の例を、大学の組織を使って説明する(図1)。
図1では、筑波大学と書いてある所が木の根にあたる。根からは、何本かの学 群の枝が出ている。このように、コンピュータ・サイエンスでは、木の根を上 に書く習慣がある。第三学群の節には、情報学類、社会工学類などの子の節が ある。第三学群の親は、筑波大学である。
A、B、2つの集合があると、一般には、次の4つに分割される。
図3 2つの集合の関係
筑波大学
筑波大学第三学群情報学類
コンピュータの中で、文字列(文字の並び)で木構造上の位置を表現する時に は、節が分かりやすくために、はっきりと区切りを入れて表現することがよく 行われる。
筑波大学.第三学群.情報学類
筑波大学/第三学群/情報学類
情報学類.第三学群.筑波大学
区切り文字としては、「.」(点)、「/」(スラッシュ)、「\」(バック スラッシュ)、「¥」(円記号)などがよく使われる。単語を並べる時に、木 の根に近いほうから書く流儀と遠い方から書く流儀がある。
コンピュータでは、次のような場所で木構造が使われている。
コンピュータ以外では、次のような場所で木構造が使われている。
Time flies like an arrow.
図4 「Time flies like an arrow.」の木(その1)
図5 「Time flies like an arrow.」の木(その2)
<sentence> ::= <simple sentence> '.' または <compound sentence> '.' または <compound-complex sentence> '.' <simple sentence> ::= <clause> <compound sentence> ::= <clause> ',' <FANBOYS> <clause> または <clause> ';' <transition word> <clause> または <clause> ',' <conjunctive> <clause> <complex sentence> ::= <dependent clause> ',' <independent clause> または <independent clause> <dependent clause> <compound-complex sentence> ::= <clause> <dependent clause> <dependent clause> ::= <subordinate> <clause> <subordinate> ::= <subordinate-adj> または <subordinate-adv> または <subordinate-noun> <subordinate-adj> ::= who または whom または that または which <subordinate-adv> ::= after または before または because または although または since <subordinate-adv> ::= that または whether <clause> ::= 基本5文型で表せるもの <FANBOYS> ::= for または and または not または but または or または yet または so <conjunctive> ::= <subordinate conjunction> または <coordinate conjunction> または <conjunctive adverb> <subordinate conjunction> ::= as, if, that など <coordinate conjunction> ::= and, but, or, for など <conjunctive adverb> ::= however, nevertheless, still, then などよい英文は、1つの <sentence> には、2つ の<clause>、つまり、S V が2つが現れることが多い。
図6 topic sentence を根とする木構造
(よく書かれた)英語の長い文章を斜めに読むには、パラ グラフの先頭の topic sentence だけを読めばよい。
日本語の特徴
(日本語ではなくて)「国語」の教師は、木構造(生成文法、文脈自由文法、 キョムスキー(学者の名前))を知らないこともある。
日本語でも、文学作品をのぞいて、英語的に木構造になっていると読みやすい。
図7 「This is-a pen」の集合的な意味
is-a関係
図8 is-a関係の例(哺乳類 is-a 動物)
ディレクトリは、全体では
木構造(tree structure)
になっている。階層化ディレクトリ(hierarchical directory)と呼ばれるこ
ともある。
図9 ファイルとディレクトリの木
図10 自然の木
ファイルの名前の表現には、「パス名」がよくつかわれる。パス (path)とい うのは、道の意味である。パス名では、どの道を通ればよいかの道順を示すこ とでファイルの名前を表現する。
木構造では、節、または、枝(道)に名前がついている。ファイル名は、区切り 文字で区切られた、節、または、枝の名前の並びになる。ファイルの名前を表 現する時の区切り文字としては、次のものがよく使われる。
/
\
:
パス名の例:
/home6/s991001
/usr/local/bin/mnews
パス名には、 次の2種類がある。
例:相対パス名 bin/awk (カレント・ワーキング・ディレクトリが /usrの時)
たとえば、icho という名前のコンピュータで、
新城のホーム・ディレクトリは、
絶対パス名では、/home1/yshinjo/
である。
/
)から出発する。
home1
という名前の節に進む。
yshinjo
という名前の節に進む。
電子メールを送ったりWorld Wide Web のページを閲覧する時には、データの 送り先やデータを持っているコンピュータを指定する必要がある。 インターネットで使われている、コンピュータの名前を管理する仕組みは、 DNS(Domain Name System) と呼ばれている。 DNS では、膨大な数のコンピュータの名前を含む名前空間を階層的にドメイン (領域)に分割して管理している。
たとえば、次のような名前を考える。
adonis1.coins.tsukuba.ac.jpこのように、インターネットでのコンピュータの名前は、「
.
」
で区切られた文字列(文字の並び)である。この文字列で使える文字は、アル
ファベットと数字、ハイフン(マイナス)である。
DNS で名前は、右から左に向かって解釈される。
「adonis1.coins.tsukuba.ac.jp
」を
図8で考えると、次のようになる。
図9 名前空間の木構造としての見方
「adonis1.coins.tsukuba.ac.jp
」を
図9で考えると、次のようになる。
jp
という節を選ぶ。
ac
という節を選ぶ。
tsukuba
という節を選ぶ。
coins
という節を選ぶ。
adonis1
という節(葉)を選ぶ。
問題
1986年、3100の公式名と6500の別名。
1990年、6400の公式名。DNS に以降。この時点で、137,000。
ドメイン名 | 数 |
.com | 3335万 |
.net | 532万 |
.org | 330万 |
.biz | 108万 |
.info | 333万 |
.jp | 64万 |
第二レベルのドメインの数。ホストの数はもっと多い。
http://jpinfo.jp/stats/ JPドメイン名に関する統計 by JPRS http://www.zooknic.com/Domains/counts.html by Zooknic.
jp
。
.com,. edu,.gov,.net,.org,.mil
、
新しい: .aero, .biz, .coop, .info, .museum, .name, .pro。
http://www.icann.org/tlds/
。
jp
の下には、次のような枝(領域、ドメイン)がある。
jp
の下に、上のような属性を持たない第2レベルドメイン名
(SLD:Second Level Domain)も使えるようになった。
インターネットにおけるドメイン名や IPアドレスを調整する ための非営利法人。1998年に設立。
以前は、IANA(Internet Assigned Numbers Authority)。
2000年に始めての理事選挙があった。
インターネットのドメイン名の根は、1つしかない。 13個のサーバにコピーが世界各地にある。
もし、別の根の情報を持つサーバがあれば、どうなるのか。
オルタネート・ルート(alternate roots)。
大量の情報を保存するには、木構造を使うしかない。 しかし、、、
図13 こうもりの分類(1)
図14 こうもりの分類(2)
木構造は、ファイルを整理するのに非常に強力な構造である。しかし、それだ けでは、ファイルを整理するには不都合が起きる。それを解消するために、次 のような名前で呼ばれる仕組みが用意されている。
図15 こうもりの分類(別名つき)
中間管理職の意味==横方向に情報が流れない。
木構造でしか情報が流れないような組織は、潰れる。木構造を補う意味で、会 社組織では、裏チャネルや同期会が重要となる。
木構造を補う方法として、ハイパーテキストと呼ばれる方法を使うことがある。
ハイパーテキスト(hypertext)とは、内部に他のテキストへの「参照 (reference)」が埋め込まれているテキスト(文書、文字だけから構成される データ)である。ハイパーテキストという仕組みを使えば、テキストのある部 分から、関連している情報を含んでいるテキストのある部分を引き出すことが 簡単になる。ハイパーテキストを拡張し、テキスト・データだけでなく、音声や画像などの データを扱えるようにしたものを、ハイパーメディア(hypermedia)という。 World Wide Web は、(木構造ではなく)ハイパーメディアに基づいて 作られている情報提示のための仕組みである。
http://www.tsukuba.ac.jp/education/college.html
http
www.tsukuba.ac.jp
/education/college.html
.html
は、その資源がHTML で書かれている事を表わしている。
エラーが出た時には、木構造で親を探してみる。