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

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

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

参照用 記事

自動リンキングについて考えてみた

DITA(Darwin Information Typing Architecture)という技術がありまして、その一部として、情報記述単位(DITAでは「トピック」と呼んでいます)のあいだのリンクを自動的に設定・維持するメカニズムが含まれています。

DITAより少し一般性がある自動リンキングが欲しいな、とちょっと考えてみました。以下、用語法はDITAとはまったく違います。リンクは有向グラフで表現できるので、グラフに関する言葉を使っています。

ノードとクラスタ

グラフGは、ノードの集合Nと(有向な)辺の集合Eからなりますが、Nの部分集合をクラスタと呼ぶことにします。クラスタはノードの集合です。以下のグラフでは、クラスタAとクラスタBは領域として描かれています。集合としては、N = {1, 2, 3, 4, 5}、A = {1, 2, 3}, B = {4} です。

クラスタを“メタノード”と考えて、ノードの集合を N∪C としたグラフを考えます。Cはクラスタを表現するメタノードの集合です。クラスタAとクラスタBをメタノードとして描くと次のようになります。N = {1, 2, 3, 4, 5}、C = {A, B}、N∪C = {1, 2, 3, 4, 5, A, B} です。

通常ノード(楕円)とクラスタノード(四角)のあいだの点線の辺は所属関係を表します。「ノード : クラスタ = ファイル : ディレクトリ」という類比で考えるといいでしょう。

クラスタのなかに再帰的にクラスタも入れられるとすると、所属関係のグラフはツリーとなります。ノードだけ、またはクラスタだけを含むクラスタ一様(uniform, homogenous)、そうでないクラスタ混合(mixed, heterogenous)と呼ぶことにします。

DITAで考えているクラスタ(に相当する概念*1)は:

  1. トップレベルは、クラスタだけを含む一様なクラスタ
  2. その下のレベルは、ノードだけを含む一様なクラスタ
  3. 三段階目はノード

リンキング属性

以下では、ノードとは通常ノード(親子関係の末端)だけでなくてクラスタノードも含めます。各ノードは、リンキングを制御するための属性を持つとします。それは次のようなものです。

  1. allowsTarget : リンクのターゲットとなることを許すか。値は、yes, no, noautoのどれか。
    1. yes : リンクのターゲットにしても良い。
    2. no : リンクのターゲットにはなれない(リンク禁止)。
    3. noauto : 自動リンクのターゲットにはなれないが、明示的なリンクのターゲットにはなれる。
  2. allowsSource : リンクのソースとなることを許すか。値は、yes, no, noautoのどれか。値の意味はallowsTargetと同様。

クラスタノードには、次のリンキング属性もあります。

  1. targetSet : 自動リンクのターゲットとなるメンバーノードの集合。値は、all, main またはノード名(ID)の配列。
    1. all : そのクラスタに属するすべてのノードが自動リンクのターゲットとなる。
    2. main : そのクラスタのメインノード(それが定まっているとして)だけが自動リンクのターゲットとなる。
    3. ノード名の配列 : 具体的に指定されたノードが自動リンクのターゲットとなる。
  2. sourceSet : 自動リンクのソースとなるメンバーノードの集合。値は、all, main またはノード名(ID)の配列。値の意味はtargetSetと同様。

これらの属性の値に基いて、「クラスタクラスタのあいだのリンク」を、メンバーのあいだのリンク達に変換することができます。変換のアルゴリズムは書きませんが、想像はできるでしょう。

内部リンキング

クラスタに属するメンバーノードのあいだのリンクを自動的に生成するヒントとして、次の属性があります。

  1. autoLinking : 内部リンクをどのように作成するか。値は、discrete, complete, ordered。
    1. discrete : 内部リンクを作らない。リンクのグラフは離散グラフになる。
    2. complete : すべてのノードをリンクする。リンクのグラフは完全グラフになる。
    3. ordered : ノードの集合が全順序集合だとして、その全順序に従ってリンクする。
  2. direction : autoLinkingがorderedのとき、隣接するa, bの順序 a<b に対して a→b とするか a←b とするか。値は forward, backward, both。
    1. forward : a<b に対して a→b とする。
    2. backward : a<b に対して a←b とする。
    3. both : 両方向とする。
  3. cyclic : autoLinkingがorderedのとき、最後から最初に戻るリンクを付けるかどうか。値は true, false。

*1:DITAで関連性テーブル(reltable)と呼ばれている概念です。