やってみる

アウトプットすべく己を導くためのブログ。その試行錯誤すらたれ流す。

📌 ？
トップ > WindowsXP > リストとツリーのデータ構造について考えてみた

リストとツリーのデータ構造について考えてみた

WindowsXP

HTMLで表現するために。

問題

HTMLでパンくずリストやツリーを表現したい。しかし専用のHTMLタグはない。CSSフレームワークやJSライブラリで実装することになる。しかしCSSフレームワークのひとつsemantic.uiでは<div>タグ乱用によりセマンティックWEBでないHTMLになってしまった。

解法

HTMLタグだけでツリーを表現する場合、リスト<ol>(<ul>), <li>が相応しいと思う。HTMLは階層の表現ができる。タグ内に含めるという形で。HTMLタグの仕様自体が木構造で表現するようになっているから相性はいいはず。

データ構造

難しくてよくわからない。私は算数や数学が非常に苦手なので厳しい。Wikipediaの表現がむずかしくて読み解けない。後回し。

HTML

HTML構造

HTMLの構文は木構造で表すものである。以下のHTMLコードなら<section>要素の中に<h1>, <p>要素を含むことを意味する。

<section>
    <h1>見出し</h>
    <p>パラグラフ1</p>
    <p>パラグラフ2</p>
</section>

<ul>タグ

HTMLでは<ul>タグでリストを表現する。しかしHTMLコード自体は木構造になっている。

<ul>
    <li>リスト項目A</li>
    <li>リスト項目B</li>
    <li>リスト項目C</li>
</ul>

<ul>タグのネスト

https://developer.mozilla.org/ja/docs/Web/HTML/Element/ul#Nesting_list

<ul>
    <li><span>根</span>
    <ul>
        <li><span>親</span>
        <ul>
            <li><span>子</span>
        </ul>
    </ul>
    </li>
    <li><span>根2</span></li>
</ul>

CSSでビュレットとテキストの間のmarginを指定するために<span>要素を加えた。

HTMLは木構造で表現するため要素を包含させることで木構造にできる。しかしデータ構造の表現としては冗長。もしプレーンテキストなら以下のように表現しそう。

パターン1

根
    親
        子
根2

パターン2

根.親.子
根2

表現の限界

HTMLはその構文自体が木構造で表現されるため表現の幅も木構造に制限される。グラフ理論からみれば、枝の意味付けが2種類しかできない。

データ構造 枝の意味
リスト 前後関係
ツリー 前後関係, 包含帰属関係

たとえば過去ログで継承関係と生成/被生成関係の2関係をダイアグラムにしたかったときがある。

blockdiagは1ブロックから２方向の矢印を出せない

クラス図でいうところの汎化/特化、コンポジションにあたる。

このときの関係を表現できない。木構造の包含関係は継承のかわりにはならない。包含関係なら部分集合になるが、継承と部分集合は意味が異なる。

それを表現するにはグラフ理論を表現できる構文が必要である。

型→<生成>→物
△
｜
Type→<生成>→Object
△
｜
Class→<生成>→Instance

RDF

https://ja.wikipedia.org/wiki/Resource_Description_Framework

トリプルという形式でデータを記述することで要素とその関係を記述できる。簡易記法のうちN-Triplesというのがある。主語 述語 目的語(S V O)の順にスペース区切りで書く。

型 生成 物
Type 継承 型
Type 生成 Object
Class　継承 Type
Class 生成 Instance
  • 型は物を生成する
  • Typeは型を継承する
  • TypeはObjectを生成する
  • ClassはTypeを継承　
  • ClassはInstanceを生成する
型→<生成>→物
△
｜
Type→<生成>→Object
△
｜
Class→<生成>→Instance

生成や継承など要素間の関係を自分で作れるところがリストやツリーと異なる。

課題

データ構造としての表現はできる。しかし、どのように描画するかまでは指定できない。たとえば配置。継承元が上で派生先が下。矢印の方なども。矢印の意味(トリプルのV)によってX軸かY軸かを指定したい。

トリプル記法と表現定義を書いてUMLやフローチャートなど一定の法則がある表現形式を作れないものか。HTML5で出力すればクリッカブルマップによる任意形状のクリックやリンクやツールチップなど表現の幅が広がるのに。

HTMLで表現できるもの

HTMLで表現できないもの

  • 集合
  • グラフ

集合は木構造で表現できそうだが、wikipediaによると以下の条件が必要。それを満たせないと思う。

「その集まりの元であるかどうかが不確定要素なしに一意に決定できる」ように定義されていなければならない。

所感

何をするときに何の理論が必要か。それを表現する手段には何があるのか。わかっていないと使いこなせない。