キマイラ・サイトは http://www.chimaira.org/です。
トラックバック／コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
ところで、アーカイブってけっこう便利ですよ。タクソノミーも作成中。
2010-03-18 (木)
パス名とグラフ構造とパンくずリスト
雑記／備忘 | | 
インターネットの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ページをノード、ハイパーリンク遷移を辺と考えたとき、異なる遷移経路（まさにパス）を表現していると考えてもいいでしょう。実際には、リアルな遷移経路というよりはコンテンツの階層的な分類に対応しそうですが、その場合でもパンくずリストは、グラフ構造のパスを扱っているように思われます。
- 37 http://pipes.yahoo.com/pipes/pipe.info?_id=faa858a20082ef6d25ad27557e37e011
- 37 http://reader.livedoor.com/reader/
- 20 http://www.google.co.jp/search?sourceid=navclient&hl=ja&ie=UTF-8&rlz=1T4GZEZ_jaJP332JP332&q=千疋屋 高い
- 18 http://ezsch.ezweb.ne.jp/search/?sr=0101&query=バルト９
- 18 http://wikiwiki.jp/firefox/
- 16 http://www.google.co.jp/reader/view/
- 16 http://www.google.co.jp/reader/view/?hl=ja&tab=wy
- 15 http://www.google.co.jp/search?sourceid=chrome&ie=UTF-8&q=chrome+View-Source
- 12 http://d.hatena.ne.jp/
- 9 http://www.google.co.jp/search?q=パンくずリスト+javascript+動的&hl=ja&sa=2
https://addons.mozilla.org/ja/firefox/addon/5908
> お探しの物はこれですか？
これです、これです。これが欲しかった！
どうもありがとうございます。
これ、昔は使えました。昔良く使ってたので、覚えてます。
で調べたら、どうもXP SP2以降はサポートされなくなったようですね。何故かは不明…
http://support.microsoft.com/kb/904678/ja
> XP SP2以降はサポートされなくなったようですね。何故かは不明…
なんでだろう？ 他と合わせたくないのか。
が、いくつか疑問が湧いてきました。
・エッジに名前を付ける場合、ファイルの削除や追加は、どのように扱われるのか。
・ファイル・システムのメンタル・モデルとはどう折り合うのか。
・グラフ理論では、ノードやエッジの構造の動的変化を扱うことはできるのか。
等々です。
何かヒントを頂ければ幸いです。
> ・エッジに名前を付ける場合、ファイルの削除や追加は、どのように扱われるのか。
ファイルの時は、ノードに実体があるので、やはりノードの削除・追加として扱うしかないでしょう。
メモリ内のオブジェクト構造なら、辺、つまり名前による参照を取り除くとそのうちノードはガーベッジコレクションされると考えていいと思います。
> ・ファイル・システムのメンタル・モデルとはどう折り合うのか。
たぶん、ファイル自体に名前が付いていると想定している人が多いと思います。それはどうにもならないでしょうし、あえて変える必要もないと思います。メカニズムとしては、ディレクトリは、名前とID（iノード番号とか）の対応表なので、「辺に名前」方式に近いかと。
> ・グラフ理論では、ノードやエッジの構造の動的変化を扱うことはできるのか。
扱ってますよ。物理と関係も深いみたいですが、僕はよく知りません。
コンピュータプログラムが扱うデータ構造では、動的に変化するグラフの例はいくらでもあるでしょ。
メカニズムとメンタル・モデルの違いを
改めて意識させられました。
削除についても、本体(i-node)は参照カウント方式なので、メモリに限らず一律にガベージコレクトされると言っちゃっていいんじゃないでしょうか。
FATファイルシステムは「ノードに名前」ですが、NTFSはどうなっているんでしょう。ハードリンクがあるからエッジに名前になっているのかな?
> メンタルモデルとしても、Unixシステムプログラマならそう理解しているはず
僕もi-nodeで解釈する方ですが、名前がエッジ側に付いてると想定している人は少数派のような気がします。統計的根拠はありませんけど。
> メモリに限らず一律にガベージコレクトされると言っちゃっていいんじゃないでしょうか。
言われてみればそうですね。指されなくったデータ領域は放置されるだけですから。
ご指摘ありがとうございます。
ＯＳが想定しているモデルと、ユーザが描くモデルの両面があるかと思います。
私が面白いと思ったのは、後者の方で、
システムを完全に正しく説明できるモデルが
人間が認知しやすいモデルとは限らないのではないか、ということです。
新しい見方には、なじみがないってこともあります。
ファイルシステムですが、「ファイル名」という言葉を使っている人は、
「ノードに名前」のモデルを思い描いているのではないでしょうか。
link, unlink については、「メカニズムを知らないと使いこなせない」とも
言えるのではないでしょうか。