木構造

総合科目「ネットワーク社会を支える情報技術入門 II」、2018年11月19日

                                       筑波大学システム情報系
                                       新城 靖
                                       <yas @ cs.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.softlab.cs.tsukuba.ac.jp/~yas/gen/it-2018-11-19
あるいは、次のページから手繰っていくこともできます。
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-2018-11-19 /it-2018-11-19 .pdf

■今日の重要な話

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

■木構造

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

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

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

• 筑波大学が木の根にあたる。根からは、何本かの学群の枝が出ている。 コンピュータ・サイエンスでは、木の根を上に書く習慣がある。
• 情報学群の節には、情報科学類、情報メディア創成学類、知識情報・図書館学類の子の節がある。 情報学群の親は、筑波大学である。
• 学群は中間節、学類は葉(端節)である。

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

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

◆字下げによる木の表現

筑波大学

• ・・・
• 社会・国際学群
  • 社会学類
  • 国際総合学類
• 理工学群
  • 数学類
  • ・・・
  • 工学システム学類
• 情報学群
  • 情報科学類
  • 情報メディア創成学類
  • 知識情報・図書館学類
• ・・・
• ・・・

◆区切り文字入り表記

筑波大学情報学群情報科学類

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

筑波大学．情報学群．情報科学類

筑波大学／情報学群／情報科学類

筑波大学＼情報学群＼情報科学類

筑波大学￥情報学群￥情報科学類

情報科学類．情報学群．筑波大学

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

◆木の例

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

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

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

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

◆文の構造

Time flies like an arrow.

◆文書の木

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

◆パラグラフの木

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

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

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

日本語の特徴

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

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

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

◆is-a関係

◆has-a関係

例: パソコン。

• ソフトウェア
  • システム・ソフトウェア
    • オペレーティング・システム
    • コンパイラ
  • アプリケーション・ソフトウェア
    • ワードプロセッサ
    • Web ブラウザ
    • メール・リーダ
• ハードウェア
  • 本体
    • マザーボード
    • CPU
    • メモリ
    • ハードディスク
    • 電源
  • キーボード
  • ディスプレイ
  • マウス

◆ディレクトリの木

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

◆パス名

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

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

• ／
• ＼、￥
• ：

パス名の例:

• /home/s123456
• /usr/bin/emacs

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

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

絶対パス名 ( absolute path name )

絶対パス名というのは、ディレクトリの木の根(ルート・ディレクトリ) から出発する道順

相対パス名 ( relative path name )

現在着目しているディレクトリ（カレント・ワーキング・ディレクトリ） から出発する道順

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

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

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

◆ホーム・ディレクトリ

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

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

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

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

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

azalea1.coins.tsukuba.ac.jp

「azalea1.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 ドメインに azalea1 という名前が登録されている。

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

◆DNSができるまで

問題

• 名前の衝突。同じ名前を取り合いになった。
• 中央の管理組織の負荷が増えた。
• 最新のホスト名の一覧表の維持が困難になった。 コピーがネットワークを重たくした。

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

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

2018年11月ごろの名の統計

トップレベルドメイン名	ドメイン名の数
.com	1億3938万
(.tk)	(2136万)
.de	1295万
.net	1505万
.uk	1115万
.org	1056万
.cn	1013万
.ru	645万
.info	548万
.top	505万
.nl	371万
.eu	329万
.loan	298万
.xyz	248万
.fr	270万
.us	255万
.br	236万
.ca	232万
.au	225万
.it	211万
.co	171万
.se	171万
.in	157万
.jp	153万
.pl	152万
.cf	131万
.ga	131万
.ml	117万
.be	117万

.jpは、属性型、地域型含む。

◆ICANN

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

2016年10月1日、アメリカ政府の監督から完全に独立。 JPNIC News & Views vol.1439【臨時号】2016.10.3

◆Top Level Domain(TLD)

◆TLDの種類

ccTLD (country code Top Level Domain)

ISO (国際標準化機構, International Standardization Organization ) が定めた２文字による国別コード(country code)) (ISO 3166) を使う。日本の国別コードは、jp。

gTLD (generic Top Level Domain)

ccTLD 以外。伝統的: .arpa .com,.edu,.gov,.int,.mil,.net,.org。 新しい: .aero,.biz,.coop,.info,.museum,.name,.pro (2000年)、 .jobs,.travel,.cat カタロニア語,.mobi,.asia, .tel, .travel (2005年)

◆TLDの自由化

• 英語の37文字(a-z,0-9,-)以外の文字(日本語も含む)でも利用可能にする。
• 審査費用 US$185,000。年間 US$25,000。
• 2012年1月募集開始。 2012年6月現在、1930件の申し込み。 2013年12月現在、1930件の申し込み。 2013年12月現在、1930件の申し込み。
• 2014年2月-10月、.nagoya, .tokyo, .yokohama, .okinawa, .ryukyu 等の登録開始。
• 複数の申請が競合すると、TLDのオークションが行われることもある。 .web 1億3500万ドル、.shop 4150万ドル、.app 2500万ドル、.tech 676万ドル等。

■木構造の制約と問題点

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

◆こうもりの分類問題

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

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

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

◆図書の分類

• 木構造の各節は、(最大)10個の子供の節への枝を作る。 枝には、0から9の名前をつける。
• 根から枝をn個たどった場合、n個の数で表す。 例: 007.64 は、根から 0→0→7→6→4 とたどった枝を意味する。

• 木のバランスがとれていない。時代の変化について行けない。 兄弟の節で、自分より下の節の本の数が違う。 （例：コンピュータ系は、数が多いが、007.6 のように深い階層にある。）
• いくつかの種類がある。日本十進分類法、 デューイ十進分類法。
• １つの視点からの分類しかできない。コウモリの分類問題問題。

◆木構造を使わない図書の分類

◆ファセット(カテゴリ)をつかう分類

例: アパートの分類。次のような項目から任意の順で絞り込める。

• 住所
• 家賃
• 間取り
• 通勤時間
• 築年数

◆Folksonomy(フォークソノミー)

情報(Webページ、ブログなど)に、各人がタグを付けていく。 そのようなタグ付けされた情報を多数持ち寄ると、 大衆(folks)に指示されたタグが浮かび上がる。

Social Bookmark などでよく使われている。

◆二分木(binary tree)

◆系統樹(phylogenetic tree)

• 普通は、二分木で書く。(分岐した時期が近くなるとどちらが先かよくわから ないものもあるが、必ずどちらかが先と考える。)
• 種Ａと種Ｂの共通の祖先となるものが存在する。 (今は絶滅したかもしれないが。)

参考: http://www.biol.tsukuba.ac.jp/tjb/Vol5No9/TJB200609TM.html

牧岡　俊樹（元　筑波大学　生物科学系）: "動物系統分類学―私の昔のテキストから―", つくば生物ジャーナル　Tsukuba Journal of Biology (2006) 5: TJB200609TM.

◆細胞内共生説

• ミトコンドリア
• 葉緑体

◆ねずみ講(無限連鎖講)

• メンバが節となり木構造を作る。
• 先に参加したメンバが、２人以上新しいメンバを入れる。
• 各メンバは、親に参加費を払う。
• 各メンバは、子供から参加費を受け取り、一部を自分でもらい、残りを自分の親に送る。

◆マルチ商法

マルチ商法も、ねずみ講と同様に木構造を作る。 マルチ商法は、ねずみ講と異なり、 商品販売やサービスの提供の提供が伴う。 日本では、直ちに違法にはならないが、法律で厳しく規制されている。 （日本では、法律を守ると利益が出ないので、違法な形で勧誘が行われることがある。）

◆官僚制度の２つの見方

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

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

• 政府の予算のトップレベルは、国会の審議で省庁に分割して割り当てる。
• 一度省庁に分割した予算を、下流で合算して使うことはできない。 （これを許せば、国会審議の意味がなくなる。）

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

• 大きさ、細分化の問題。縦割り行政（木構造行政）。
• 時間的に古くなる。状況の変化についていけない。日本の財務省／国会は、 省庁予算に「シーリング」を設定して、省庁に配分を任せると、予算配分が固 定化される。
• 省庁内部の組織の木構造で、レベルを上がる（昇進する）ためには、国民 の利益ではなく、省益を考えるようになる。昇進できない人は、必ずやめる （天下り）。

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

国会議員が、木構造の問題を打ち破る必要がある。

◆領土問題

領土問題の「木構造」の考え方に基づいた解決方法

• 互いに木構造で考えることをやめる。

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

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

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

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

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

言語の分類

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

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

マークアップ言語でマークを付ける時の方法としては、テキストに タグ(tag,たぐ)(名札の意味) を埋め込む。

たとえば日本語の普通の文書では、括弧「」で括れば誰かの発言を意味する。 これは括弧"「" と "」" の間のテキストに誰かの発言という意味のマークが 付けられていることを意味する。

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

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

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

◆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が変更された時

• Not Found. The requested URL XXX was not found on this server.
• Unable to locate the server URL XXX. Please check the server name and try again.

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