木構造

平成15年度 筑波大学第三学群 情報学類 大学説明会 ミニ講義B、2003年7月30日

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/oc-2003
あるいは、次のページから手繰っていくこともできます。
http://www.is.tsukuba.ac.jp/~yas/
http://www.coins.tsukuba.ac.jp/~yas/

印刷配布資料 http://www.coins.tsukuba.ac.jp/~yas/oc-2003 /tree.pdf

■今日の重要な話

• 情報を整理する時に、もっとも基本的で重要な方法として、木構造を使 う方法がある。
• 木構造には、様々な表現方法がある。
  • 節と枝。根も葉もある。根を上に書く。
  • 領域的(集合のベン図)
  • 段付け（字下げ）
  • (区切り文字を挟んで)単語を並べる
• 木構造は、コンピュータであつかうものの名前を管理するために使われ ている。
• 木構造は、英語の読解や作文に役立てることができる。
• 木構造を使うと要素の数が増えても対応することができる。
• 木構造だけでは、情報の整理はうまくいかない。木構造を補う仕組みが 必要になる。
• World Wide Web では、ハイパーテキスト(グラフ構造)が使われている。
• URL (Uniform ResourceLocator) には２つの木の表現が含まれている。

■参考書

■木構造

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

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

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

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

Ａ、Ｂ、２つの集合があると、一般には、次の４つに分割される。

1. Ａにしか含まれない部分
2. ＡとＢの両方に含まれる部分
3. Ｂにしか含まれない部分
4. ＡにもＢにも含まれる部分

◆字下げによる木の表現

筑波大学

• 第一学群
  • 自然学類
  • 社会学類
• 第二学群
  • 生物学類
• 第三学群
  • 情報学類
    • 情報科学主専攻
    • 計算機システム主専攻
    • 知能情報メディア主専攻
  • 社会工学類

◆区切り文字入り表記

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

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

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

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

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

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

◆木の例

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

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

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

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

◆文の構造

Time flies like an arrow.

◆英語の文法

1. S V
2. S V C
3. S V O
4. S V O O
5. S V O C

<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> ::= 基本５文型で表せるもの

<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 など

◆文書の木

• 章立て。章、節、項。
• 箇条書き。箇条書きの中に箇条書き。
• パラグラフ

◆パラグラフの木

• パラグラフは、１つの topic を語る (０個、２つ以上は不可)。
• １つのパラグラフには、１つの topic sentence (パラグラフの内容を一 言で語った文)を置く。
• topic sentence は、多くの場合、パラグラフの先頭に置かれる。
• パラグラフに含まれる他の文は、次のいずれか（宙に浮いているものは不可）。
  • topic sentence を展開させたもの (topic sentence を木の根として、その子供の節になる)
  • (他のパラグラフとの関係を示すもの)
• 木構造を明確にするために、signal wordsを使う。
  • First, Second, Third, ...
  • 原因・結果
  • 対句、対比

受験生へのヒント：（よく書かれた）英語の長い文章を斜めに読むには、パラ グラフの先頭の topic sentence だけを読めばよい。

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

日本語の特徴

• 漢字仮名混じり文。重要な言葉が漢字で書かれている。
• 文の構造。動詞が最後。

（日本語ではなくて）「国語」の教師は、木構造（生成文法、文脈自由文法、 キョムスキー(学者の名前)）を知らないこともある。木構造を知らない人が試 験問題を作る場合、木構造の知識が応用しくにい。

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

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

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

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

adonis1.coins.tsukuba.ac.jp

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

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

• まず根から出発する。
• 根の下の jp という節を選ぶ。
• その下の ac という節を選ぶ。
• その下の tsukuba という節を選ぶ。
• その下の coins という節を選ぶ。
• 最後に、その下の adonis1 という節(葉)を選ぶ。

◆木構造の利点

• 分類をする時に木構造を使うことは自然である
• 要素数が増えても扱える
• 永遠に循環しないで全ての節を訪れることが簡単にできる

◆木構造の問題点

木構造では、ある節から別の節にたどり着く道は、ただ１つしか許されていない。

◆こうもりの分類問題

類似の問題は、領土問題、外交機密費問題、縦割り行政（木構造行政）問題にもある。

◆部分的にグラフ構造を取り入れる

１つの節に、１つの本名の外に、いくつかの「別名」をつけて、２つの道から たどり着けるようにする。検索する時には、本名と別名を区別する。

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

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

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

図13 インターネットの資源とハイパーメディア

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

1. 差されるデータに印(mark,label)を付ける。
2. 差すデータに、参照を埋め込む。

◆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中の２つの木

• コンピュータの名前。区切り文字「．」。木の根が右(右から左に解釈)。
• コンピュータ内の資源の名前。区切り文字「／」。木の根が左(左から右に解釈)。

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

http://www.aaa.bbb.ccc/ddd/eee/fff.html

次の２種類のエラーが出る可能性がある。

1. Not Found. The requested URL /ddd/eee/fff.html was not found on this server.
2. Unable to locate the server URL www.aaa.bbb.ccc. Please check the server name and try again.

エラーが出た時には、木構造で親になる節を探してみればよい。

• /ddd/eee/fff.html が違うと言われた時
  • http://www.aaa.bbb.ccc/ddd/eee/fff.html
  • http://www.aaa.bbb.ccc/ddd/eee/
  • http://www.aaa.bbb.ccc/ddd/
  • http://www.aaa.bbb.ccc/
• www.aaa.bbb.ccc が違うと言われた時
  • http://www.aaa.bbb.ccc/ddd/eee/fff.html
  • http://www.bbb.ccc/ddd/eee/fff.html
  • http://www.ccc/ddd/eee/fff.html