$BLZ9=B$(B


# 木構造

共通科目情報処理(講義)、体育専門学群対象、2000年05月18日
電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/ipe/taiiku-kougi-2000/2000-05-18
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/ipe/
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html
http://www.ipe.tsukuba.ac.jp/~yshinjo/

## ■復習

## ファイルとは

永続的なメモリ（ハードディスクなど）を便利にしたもの（抽象化、仮想化）。
情報に名前を付けるためのもの

ディレクトリとは

ファイルに名前をつけるための仕組み
ファイル名の一覧表を含んでいるもの

コンピュータの構成要素

ハードウェア(目に見えるもの、触れるもの)

- CPU
メモリ(速くて揮発的)
ハードディスク、フロッピ・ディスク、CD-ROM(遅くて永続的)
- ソフトウェア(ビットの並びで表現できるもの)
- プログラム
データ
- ソフトウェアは、ファイルに保存されている。

「ソフトウェア」という言葉は、コンピュータ以外でも使われている。
たとえば、「音楽ソフトウェア」と言ったりする。

人間の場合、ハードウェアは、遺伝子、発生時の化学的な環境、生まれたあと
で食べたものなどで決まる。ソフトウェアは、親や友だちとの対話を通じて得
たり、テレビを見たり、勉強したり、練習したりして身に付ける。

## ■今日の重要な話

コンピュータを使って情報を整理する時に、もっとも基本的で重要な方
法として、木構造を使う方法がある。
木構造には、３種類の表現方法がある。
木構造は、ファイルの名前、インターネット上のコンピュータの名前を
管理するために使われている。
木構造だけでは、情報の整理はうまくいかない。木構造を補う仕組みが
必要になる。

## ■木構造

木構造（tree structure）というのは、コンピュータ・サイエン
ス（計算機科学）でよく使われる用語である。分野によっては、同じものを
階層構造（hierarchical structure）という言葉で表現すること
が好まれる。ドイツ語語源の、ヒエラルヒー(Hierarchie)という言葉が使われ
ることもある。

木構造の例を、大学の組織を使って説明する(図1-1)。

木構造は、節と枝からできている。
特別な節として、根(root)が１個ある。
木構造では、ある節から別の節までの道が１通りしかない。
つながっている節と節で、根に近いものを親、そうでない
ものを子という。

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

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

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

たとえば「情報学類」の場合、次のように記述する。

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

筑波大学体育専門学群健康・スポーツ教育専攻

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

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

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

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

筑波大学．体育専門学群．健康・スポーツ教育専攻

筑波大学／体育専門学群／健康・スポーツ教育専攻

健康・スポーツ教育専攻．体育専門学群．筑波大学

区切り文字としては、「．」（点）や「／」（スラッシュ）がよく使われる。
並べる時に、木の根に近いほうから書く流儀と遠い方から書く流儀がある。

住所の表記も、木構造である。

日本国．茨城県．つくば市．天王台

図1-1に示されている木構造は、また図1-2のように、「領域(domain)」を分割
するような見方もできる。木構造の場合には、領域の境界線が交わることがな
い。

図1-2 大学組織に見られる木構造（領域的な見方）

Windows の画面や、Macintosh　の Finder の表示は、この領域の分割に似て
いる。

### ◆木の例

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

ファイルの名前
インターネット上のコンピュータの名前
電子メールのアドレス
World Wide Web のアドレス (URL)
ネットワーク・ニュースのニュース・グループの名前
さまざまなメニュー

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

分類（生物、図書館の本）
住所
会社組織、官僚機構
文章の構造

### ◆文書の木

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

章立て。章、節、項。
箇条書き。箇条書きの中に箇条書き。
字下げ。段付け。
１つの文。

英語では、段落(paragraph)の内部も、きちんと木構造で書くことが求められ
る。そのためのマークとなる単語が大事になる。日本語でも、大学のレポート
も、英語的に木構造になっていると讀みやすい。

１つの文も、木構造で表される。

Time flies like an arrow.

図1-3 「Time flies like an arrow.」の木(その１)

光陰矢のごとし。

同じ単語の並びでも、木構造を作ることもできる。

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

時蝿、矢を好む。

### ◆ディレクトリの木

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

図1-5 ファイルとディレクトリの木

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

### ◆パス名

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

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

/
\
:

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

パス名の例:

/home6/s991001
/usr/local/bin/mnews

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

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

絶対パス名 ( absolute path name )
絶対パス名というのは、ディレクトリの木の根(ルート・ディレクトリ)
から出発する道順
相対パス名 ( relative path name )
現在着目しているディレクトリ（カレント・ワーキング・ディレクトリ）
から出発する道順

例：絶対パス名 /usr/bin/awk

ルート・ディレクトリから出発する
usrという枝へ進む
binという枝に進む
最後に (awk)という枝に進む。

よって、/usr/bin/awk は、こういう手順で見つかるファイルを意味する。

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

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

### ◆ホーム・ディレクトリ

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

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

ルートディレクトリ（/）から出発する。
home1 という名前の節に進む。
yshinjo という名前の節に進む。

### ◆インターネット上のコンピュータの名前付けDNS(Domain Name System)

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

図1-6 名前空間のドメインへの分割

この空間の構造は、ファイル名で使われている木構造とまったく同じものであ
る。

図1-7 名前空間の木構造としての見方

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

host1.is.u-ust.ac.jp

このように、インターネットでのコンピュータの名前は、「.」
で区切られた文字列（文字の並び）である。この文字列で使える文字は、アル
ファベット（大文字も小文字も同じだが普通は小文字だけが使われる）と数字、
ハイフン（マイナス）である。
DNS で名前は、ファイルのパス名
とは逆で、右から左に向かって解釈される。上のコンピュータの名前をこれを
ファイルのパス名のように書くと、

/jp/ac/u-ust/is/host1

となる。

「host1.is.u-ust.ac.jp」を
図1-7で考えると、次のようになる。

まず根の下に、jp という節がある。
その下に、ac という節がある。
その下に u-ust という節がある。
その下に is という節がある
最後に、host1 という節(葉)がある。

「host1.is.u-ust.ac.jp」を
図1-6で考えると、次のようになる。

名前空間全体は、まず、af, al, ・・・, jp, ・・・, uk, zw というド
メインに分割されいる。
その中の jp ドメインは、ac, ad, co, ne, gr, or などのドメインに分
割されている。
その中の ac ドメインは、ass, ・・・,u-ust, ・・・, zokei 等のドメ
インに分割されている。
u-ust ドメインは、さらに cc, ipe, is などのドメインに分割されて
いる。
最後に、is ドメインにhost1 という名前が登録されている。

根の直下は、ISO (国際標準化機構, International Standardization
Organization ) が定めた２文字による国別コード(country code)が使われて
いる。ただし、歴史的な理由により、アメリカを中心として .com, .edu, .
gov, .net, .org, .mil などが現在でも使われている。日本の国別コードは、
jp である。jp の下には、次のようなドメインがある。

ac
学校関係(主に大学)、学術研究機関
ad
ネットワーク管理、JPNICの会員
co
会社
ed
児童、生徒などの教育・育成を行う組織。
go
政府機関、国立の施設
gr
任意団体
ne
インターネット接続サービス・プロバイダ
or
法律に基づく団体
都道府県の名前
地方自治体、個人。

## ■木構造の性質

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

### ◆官僚制度の２つの見方

整理棚。人間を系統的に分類する。事実を系統的に分類する。（保存）
情報が流れる経路。（通信）

木構造の問題点

大きさ、細分化の問題。縦割り行政（木構造行政）。
時間的に古くなる。環境変化についていけない。

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

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

### ◆木構造の制約を緩和する仕組み

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

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

シンボリック・リンク(symbolic link,UNIX)
エイリアス(alias, Macintosh)
ショートカット(shortcut, Windows)

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

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

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

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

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

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

データにラベルを付ける（参照の目標となるマークを付ける）。
データにラベルへの参照を埋め込む。

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

http://www.ntt.co.jp/SQUARE/index-j.html

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

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

木の根が左(ファイル名)
木の根が右(コンピュータの名前)

↑[もどる]
←[5月11日]
・[5月18日]
→[6月1日]

Last updated: 2000/05/17 22:26:27