木構造

総合科目「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)。

木構造という名前は、本物の木が、一度枝分かれした後は決して交わらないこ とに似ていることによる。ある節から別の節までの道が2通り以上あるは、グ ラフ構造と呼ばれる。

筑波大学、第一から第三学群、情報学類、主専攻の図

図1 大学組織に見られる木構造

図1では、筑波大学と書いてある所が木の根にあたる。根からは、何本かの学 群の枝が出ている。このように、コンピュータ・サイエンスでは、木の根を上 に書く習慣がある。第三学群の節には、情報学類、社会工学類などの子の節が ある。第三学群の親は、筑波大学である。

筑波大学、第一から第三学群、情報学類の図

図2 大学組織に見られる木構造(領域的な見方)

A、B、2つの集合があると、一般には、次の4つに分割される。

  1. Aにしか含まれない部分
  2. AとBの両方に含まれる部分
  3. Bにしか含まれない部分
  4. AにもBにも含まれる部分
領域(木構造)の場合、完全に含まれるか、無関係かのどちらかになる。

集合の関係を説明した図。一般的な場合と領域の場合。

図3 2つの集合の関係

◆字下げによる木の表現

木構造を字下げで表すことがある。

筑波大学

◆区切り文字入り表記

「情報学類」という節を、次のように表記する。

筑波大学第三学群情報学類

コンピュータの中で、文字列(文字の並び)で木構造上の位置を表現する時に は、節が分かりやすくために、はっきりと区切りを入れて表現することがよく 行われる。

筑波大学.第三学群.情報学類
筑波大学/第三学群/情報学類
情報学類.第三学群.筑波大学

区切り文字としては、「.」(点)、「/」(スラッシュ)、「\」(バック スラッシュ)、「¥」(円記号)などがよく使われる。単語を並べる時に、木 の根に近いほうから書く流儀と遠い方から書く流儀がある。

◆木の例

コンピュータでは、次のような場所で木構造が使われている。

コンピュータ以外では、次のような場所で木構造が使われている。

◆文の構造

1つの文も、木構造で表される。同じ単語の並びでも、組み立てられる木構造 が違うと違う意味になる。英文の解釈は、木構造を組み立てることである。

Time flies like an arrow.

図4 「Time flies like an arrow.」の木(その1)

図4 「Time flies like an arrow.」の木(その1)

光陰矢のごとし。

図5 「Time flies like an arrow.」の木(その2)

図5 「Time flies like an arrow.」の木(その2)

時蝿、矢を好む。

◆英語の文法

基本5文型は、木構造を意味する。
  1. S V
  2. S V C
  3. S V O
  4. S V O O
  5. S V O C
これを <clause>とする。英語の文は、次の形式で <clause>をいくつかつなげ、最後に「.」をつけたたものである。
<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つが現れることが多い。

◆文書の木

文章の中にも、木構造が現れる。

◆パラグラフの木

英語国民に対する英語の教育では、パラグラフ(段落)の内部も、きちんと木構 造で書くことが求められる。

topic sentence を根に持つ木構造の図

図6 topic sentence を根とする木構造

(よく書かれた)英語の長い文章を斜めに読むには、パラ グラフの先頭の topic sentence だけを読めばよい。

◆日本語の段落の構造:逆茂木型

逆茂木: よろい、かぶとの時代に、敵の侵入を防ぐために樹を斬り倒して尖っ た枝を外に向けて並べた障害物。

逆茂木型の段落

図7 逆茂木型の段落

日本語の特徴

(日本語ではなくて)「国語」の教師は、木構造(生成文法、文脈自由文法、 キョムスキー(学者の名前))を知らないこともある。

日本語でも、文学作品をのぞいて、英語的に木構造になっていると読みやすい。

◆is-a関係

This is-a pen の意味。

図7 「This is-a pen」の集合的な意味

図7 「This is-a pen」の集合的な意味

is-a関係

図8 is-a関係の例(哺乳類 is-a 動物)

図8 is-a関係の例(哺乳類 is-a 動物)

◆ディレクトリの木

ディレクトリは、全体では 木構造(tree structure) になっている。階層化ディレクトリ(hierarchical directory)と呼ばれるこ ともある。

図9 ファイルとディレクトリの木

図9 ファイルとディレクトリの木

ファイルは、葉(leaf)になる。ディレクトリは、節(node)になる。特殊な節と して、根(root)がある。これを、ルート・ディレクトリ(root directory)と いう。

図10 自然の木

図10 自然の木

◆パス名

ファイルの名前の表現には、「パス名」がよくつかわれる。パス (path)とい うのは、道の意味である。パス名では、どの道を通ればよいかの道順を示すこ とでファイルの名前を表現する。

木構造では、節、または、枝(道)に名前がついている。ファイル名は、区切り 文字で区切られた、節、または、枝の名前の並びになる。ファイルの名前を表 現する時の区切り文字としては、次のものがよく使われる。

ファイル名で「.」は、木構造の区切りとしては使われない。

パス名の例:

◆絶対パス名と相対パス名

パス名には、 次の2種類がある。

絶対パス名 ( absolute path name )
絶対パス名というのは、ディレクトリの木の根(ルート・ディレクトリ) から出発する道順
相対パス名 ( relative path name ) 現在着目しているディレクトリ(カレント・ワーキング・ディレクトリ) から出発する道順
例:絶対パス名 /usr/bin/awk
  1. ルート・ディレクトリから出発する
  2. usrという枝へ進む
  3. binという枝に進む
  4. 最後に (awk)という枝に進む。
よって、/usr/bin/awk は、こういう手順で見つかるファイルを意味する。

例:相対パス名 bin/awk (カレント・ワーキング・ディレクトリが /usrの時)

  1. カレント・ワーキング・ディレクトリから出発する
  2. binという枝に進む
  3. 最後に (awk)という枝に進む。

◆ホーム・ディレクトリ

複数の人が使うコンピュータで、個人のファイルを保存する 時の出発点となるディレクトリを、ホーム・ディレクトリと呼ぶ。

たとえば、icho という名前のコンピュータで、 新城のホーム・ディレクトリは、 絶対パス名では、/home1/yshinjo/ である。

◆世界最大の木構造:DNS(Domain Name System)

電子メールを送ったりWorld Wide Web のページを閲覧する時には、データの 送り先やデータを持っているコンピュータを指定する必要がある。 インターネットで使われている、コンピュータの名前を管理する仕組みは、 DNS(Domain Name System) と呼ばれている。 DNS では、膨大な数のコンピュータの名前を含む名前空間を階層的にドメイン (領域)に分割して管理している。

たとえば、次のような名前を考える。

adonis1.coins.tsukuba.ac.jp
このように、インターネットでのコンピュータの名前は、「.」 で区切られた文字列(文字の並び)である。この文字列で使える文字は、アル ファベットと数字、ハイフン(マイナス)である。 DNS で名前は、右から左に向かって解釈される。

全体がドメインに分割された図

図8 名前空間のドメインへの分割

adonis1.coins.tsukuba.ac.jp」を 図8で考えると、次のようになる。

ドメインを木構造としてとらえた図

図9 名前空間の木構造としての見方

adonis1.coins.tsukuba.ac.jp」を 図9で考えると、次のようになる。

◆DNSができるまで

初期のインターネットは、コンピュータの名前(ホスト名)は、 フラットな名前空間が使われていた。

問題

1986年、3100の公式名と6500の別名。

1990年、6400の公式名。DNS に以降。この時点で、137,000。

2005年1月ごろの名の統計
ドメイン名
.com3335万
.net532万
.org330万
.biz108万
.info333万
.jp64万
.jp は地域型含む。

第二レベルのドメインの数。ホストの数はもっと多い。

http://jpinfo.jp/stats/ JPドメイン名に関する統計 by JPRS http://www.zooknic.com/Domains/counts.html by Zooknic.

◆ドメイン名の種類

ccTLD (country code Top Level Domain)
ISO (国際標準化機構, International Standardization Organization ) が定めた2文字による国別コード(country code)) (ISO 3166) を使う。日本の国別コードは、jp
gTLD (generic Top Level Domain)
ccTLD 以外。伝統的: .com,. edu,.gov,.net,.org,.mil、 新しい: .aero, .biz, .coop, .info, .museum, .name, .pro。 http://www.icann.org/tlds/
jp の下には、次のような枝(領域、ドメイン)がある。
ac
学校関係(主に大学)、学術研究機関
ad
ネットワーク管理、JPNICの会員
co
会社
ed
児童、生徒などの教育・育成を行う組織。
go
政府機関、国立の施設
gr
任意団体
ne
インターネット接続サービス・プロバイダ
or
法律に基づく団体
都道府県の名前
地方自治体、個人。

◆汎用JPドメイン名

jp の下に、上のような属性を持たない第2レベルドメイン名 (SLD:Second Level Domain)も使えるようになった。

汎用JPドメイン名(JPNIC)

◆ICANN

ICANN(Internet Corporation for Assigned Names and Numbers)

インターネットにおけるドメイン名や IPアドレスを調整する ための非営利法人。1998年に設立。

以前は、IANA(Internet Assigned Numbers Authority)。

2000年に始めての理事選挙があった。

◆オルタネート・ルート問題

インターネットのドメイン名の根は、1つしかない。 13個のサーバにコピーが世界各地にある。

もし、別の根の情報を持つサーバがあれば、どうなるのか。

オルタネート・ルート(alternate roots)。

■木構造の制約と問題点

大量の情報を保存するには、木構造を使うしかない。 しかし、、、

◆こうもりの分類問題

図13 こうもりの分類(1)

図13 こうもりの分類(1)

図14 こうもりの分類(2)

図14 こうもりの分類(2)

◆シンボリック・リンク/エイリアス/ショートカット

木構造は、ファイルを整理するのに非常に強力な構造である。しかし、それだ けでは、ファイルを整理するには不都合が起きる。それを解消するために、次 のような名前で呼ばれる仕組みが用意されている。

2つの節に、「別名」をつけて、2つの道からたどり着けるようにする。 (木構造では、1つの節にたどり着く道は、ただ1つしかない。)

図15 こうもりの分類(別名つき)

図15 こうもりの分類(別名つき)

◆官僚制度の2つの見方

情報の流れには予算の流れも関連している。

◆官僚制度に見られる木構造の問題点

中間管理職の意味==横方向に情報が流れない。

木構造でしか情報が流れないような組織は、潰れる。木構造を補う意味で、会 社組織では、裏チャネルや同期会が重要となる。

◆外務省機密費問題

会計法違反。外務省に分かれた予算を首相官邸に流した。 国会の審議の意味がなくなった。

◆領土問題

木構造のどちらに付くか。

■ハイパーテキストとハイパーメディア

木構造を補う方法として、ハイパーテキストと呼ばれる方法を使うことがある。

ハイパーテキスト(hypertext)とは、内部に他のテキストへの「参照 (reference)」が埋め込まれているテキスト(文書、文字だけから構成される データ)である。ハイパーテキストという仕組みを使えば、テキストのある部 分から、関連している情報を含んでいるテキストのある部分を引き出すことが 簡単になる。

ハイパーテキストを拡張し、テキスト・データだけでなく、音声や画像などの データを扱えるようにしたものを、ハイパーメディア(hypermedia)という。 World Wide Web は、(木構造ではなく)ハイパーメディアに基づいて 作られている情報提示のための仕組みである。

図16 インターネットの資源とハイパーメディア></P>
<P><STRONG>図16 インターネットの資源とハイパーメディア</STRONG></P>
</A>



</P><P>

ハイパーメディアやハイパーテキストのデータを作成するためには、次の2つ
の事が必要になる。

<OL>
<LI>差されるデータに印(mark,label)を付ける。
<LI>差すデータに、参照を埋め込む。
</OL>

文書(テキスト)に、「ここは表題」、「ここは箇条書」といった、文書の構
造を示す目印(マーク)を付けることをを付けることを、マークアップすると
いう。

ハイパーメディアを記述するためには、上の2つのことを支援した、人工の言
語を使う。このような言語を、マークアップ言語(markup language)という。

</P><P>

言語の分類
<UL>
<LI> 自然言語
<UL>
<LI> 日本語
<LI> 英語
<LI> 中国語
</UL>
<LI> 人工言語
<UL>
<LI> 数学で使う表現
<LI> 化学式
<LI> コンピュータ言語
<UL>
<LI> プログラミング言語(コンピュータのプログラムを作る時に使う言語)
<LI> スクリプト言語
<LI> マークアップ言語
<UL>
<LI> HTML
<LI> SGML
<LI> XML
<LI> TeX, LaTeX
<LI> roff
</UL>
</UL>
</UL>
</UL>

</P><P>

WWW では、マークアップ言語として HTML (HyperText Markup Language)と呼
ばれている言語が使われている。

</P><P>

マークアップ言語でマークを付ける時の方法としては、テキストに

タグ(tag),たぐ)(名札の意味)

を埋め込む。

</P><P>

たとえば日本語の普通の文書では、括弧「」で括れば誰かの発言を意味する。
これは括弧

HTML や SGML では、「<」 と 「>」で括られた範囲がタ グになる。タグには、「<name>」という形式と 「</name>」という形式の2つの種類があり、前者を 開始タグ 後者を 終了タグ といいます。開始タグと終了タグに囲まれた部分が、マークが付けされたテキ ストになる。

ハイパーリンクを実現するためのマークアップ言語には、次の2つの機能が必 要になる。

◆URL

HTML では、他のデータへの参照を実現するためにURL (Uniform Resource Locator) という形式を使う。次に、URL の例を示す。

http://www.tsukuba.ac.jp/education/college.html

http
HyperText Transfer Protocol。WWWのデータを保持しているプログラム と、WWWを表示するプログラムの間でデータをやり取りするときの形式を定め た約束。
www.tsukuba.ac.jp
そのデータを持っているコンピュータの名前。
/education/college.html
そのコンピュータの中での資源の名前(ファイルの名前)。最後の .html は、その資源がHTML で書かれている事を表わしている。

◆URL中の2つの木

URL には、2つの木構造の表記方法が混じっている。

◆URLを間違えた時/URLが変更された時

2種類のエラー 長い URL のどの部分が怪しいかを区別できるようにする。

エラーが出た時には、木構造で親を探してみる。


Last updated: 2005/11/12 19:59:57
Yasushi Shinjo / <yas @ cs.tsukuba.ac.jp>