このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

パス名とグラフ構造とパンくずリスト

インターネットのURLでも、ローカルファイル名でも、「パス」という概念を使っていますよね。例えば、/home/hiyama/junk/memo.txt というファイルは、"home", "hiyama", "junk", "memo.txt" という名前を区切り記号(この場合はスラッシュ)を挟んで並べたものです。区切り記号や構文の詳細は違っても、階層的な名前空間ではなんらかの「パス」が使われます。

ファイルシステムの例で考えるとして、/home/hiyama/junk/memo.txt というパスを図示すると次のようになるでしょう。

[] --> [home] --> [hiyama] --> [junk] --> (memo.txt)

ディレクトリー(フォルダー)は角括弧(ブラケット)で囲み、ファイルは丸括弧で囲みました。この図で、[] はルートディレクトリーです。つまり、ルートディレクトリーは無名です。

上の図では、ディレクトリーとファイルが名前を持っています。ルートも "" という名前を持つといえなくもないでしょう。そして、親子関係を示す矢印(-->)は名前を持ちません。さて、発想を変えて次のように図示してみます。

[] -home-> [] -hiyama-> [] -junk-> [] -memo.txt-> ()

今度は、ディレクトリーとファイルは無名で、矢印に名前が付いているのです。こう考えても特に変わりはないのですが、シンボリックリンク(ファイルの別名)などを考えやすくなります。/home/hiyama/junk/memo.txt が /tmp/junk-memo.txt をシンボリックリンクとして指しているとします。この状況は次のように描けます。

---tmp-> [1] --- junk-memo.txt ------> (2)
/ /
[0] /memo.txt
\-home-> [3] -hiyama-> [4] -junk-> [5]

ノード(ディレクトリーとファイル)は無名ですが、識別に番号を付けておきました。2番ノードを指す名前は、「0, 1, 2 という道筋をたどったとき」と、「0, 3, 4, 5, 2 という道筋をたどったとき」では違います。パスというのはもともと「道」の意味でした。ノードそれ自体に名前が付着していると考えるより、そのノードに至る道順をパスという記号形式で表現していると考えた方が自然だと思います。

一般的なグラフ構造の観点から考えると、ノードに値が付着する場合と、辺(エッジ、アーク)に値が付着する場合があります。ノードや辺にくっつく値は、「色」とか「重さ」とか呼ばれることが多いのですが、名前(文字列)でもかまいません。もちろん、ノードにも辺にも値が対応している構造を考えることもあります。上の図は、ノードには番号、辺には名前が対応しています。

Webサイトで、パンくずリストがよく使われます。例えば:

  • ショップ > 洋品 > その他 > ベルト
  • ショップ > 小物・アクセサリー > ベルト

これは、Webページをノード、ハイパーリンク遷移を辺と考えたとき、異なる遷移経路(まさにパス)を表現していると考えてもいいでしょう。実際には、リアルな遷移経路というよりはコンテンツの階層的な分類に対応しそうですが、その場合でもパンくずリストは、グラフ構造のパスを扱っているように思われます。