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

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

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

参照用 記事

マイクロデータ(microdata)を理解するために -- プロパティリストとマルチバリューのオブジェクト

「マイクロフォーマット(microformats) vs. マイクロデータ(microdata)」より引用:

マイクロフォーマット/マイクロデータ共通のデータモデルとAPIの詳細に関しては、また次の機会に述べるつもりです。

なんて書いたので、マイクロデータの仕様を注意して読んでみました。すると、データモデルに関してなんか微妙なことが書かれています。思ったよりシチ面倒くさいことになります。そこで、基礎を固めるためにプロパティリストとマルチバリューのオブジェクトというデータ構造について説明することにします。

内容:

  1. 不思議なプロパティリスト
  2. マルチバリューのオブジェクト
  3. 入れ子構造の平坦化

不思議なプロパティリスト

マイクロデータにおいて、プロパティが名前-値ペアである点は間違いありません。マイクロデータのアイテムはプロパティの“集まり”です。この集まりが集合(セット)かバッグ(マルチセット)かリストかというのが問題です。僕は集合と解釈していいだろうと思っていたのですがそうではありませんでした。

まず、まったく同じプロパティが2回出現した場合、これを1回の出現だとはみなせないようです。次の例を見てください。


{
("fn" : "檜山 正幸"),
("email" : "hiyama{AT}chimaira{DOT}org"),
("url" : "http://www.chimaira.org/"),
("url" : "http://www.chimaira.org/"),
}

これは次の集まりとは同一視できないのです。


{
("fn" : "檜山 正幸"),
("email" : "hiyama{AT}chimaira{DOT}org"),
("url" : "http://www.chimaira.org/"),
}

では、バッグと考えればいいのでしょうか。バッグ(マルチセットとも言う)とは、「出現回数が意味を持つが出現順序は意味を持たない集まり」です。マイクロデータの仕様を読むと、「出現順序は意味を持たない」とは言い切れないのです。

プロパティ名が違うプロパティのあいだでは順序は無関係、これはOKです。以下の2つの集まりは同値です。


{
("fn" : "檜山 正幸"),
("email" : "hiyama{AT}chimaira{DOT}org"),
("url" : "http://www.chimaira.org/"),
("url" : "http://d.hatena.ne.jp/m-hiyama/")
}


{
("url" : "http://www.chimaira.org/"),
("email" : "hiyama{AT}chimaira{DOT}org"),
("fn" : "檜山 正幸"),
("url" : "http://d.hatena.ne.jp/m-hiyama/")
}

しかし、同じ名前のプロパティどおしでは順序を変えると同値ではなくなる、というのです。次の2つは同値ではありません。


{
("fn" : "檜山 正幸"),
("email" : "hiyama{AT}chimaira{DOT}org"),
("url" : "http://www.chimaira.org/"),
("url" : "http://d.hatena.ne.jp/m-hiyama/"),
}

{
("fn" : "檜山 正幸"),
("email" : "hiyama{AT}chimaira{DOT}org"),
("url" : "http://d.hatena.ne.jp/m-hiyama/"),
("url" : "http://www.chimaira.org/")
}

正確に述べると、プロパティのリストに次のような同値関係を入れることになります。

  1. 同じ名前のプロパティの出現順序が入れ替わらない限り、プロパティの出現順序を変えても同値である。
  2. 同じ名前のプロパティの出現順序が入れ替わると同値とはみなさない。

マルチバリューのオブジェクト

マイクロデータのデータモデルは、プロパティリストに上で述べたような同値関係を入れればいいのですが、ちょっとややこしいですね。もっと分かりやすいデータ表現があります。

JSONオブジェクトで、値がリストであるものを考えます。次はその例です。


{
"fn" : ["檜山 正幸"],
"email" : ["hiyama{AT}chimaira{DOT}org"],
"url" : ["http://www.chimaira.org/", "http://d.hatena.ne.jp/m-hiyama/"],
}

プロパティ値は必ずリストです。リストは出現順序を入れ替えると違う値とみなされます。しかし、オブジェクトのプロパティの出現順序は意味を持ちません。これは、マイクロデータのデータモデルと同じセマンティクスを持ちます。

すべてのプロパティ値がリストであるオブジェクトをマルチバリューのオブジェクトと呼ぶことにします。マルチバリュー(多値)は意味が曖昧な言葉ですが、ここでの意味は値が必ずリストで与えられることです。そう約束すると、マイクロデータのアイテム(=特殊な同値関係が入ったプロパティリスト)は、マルチバリューのオブジェクトとみなしてもいいことが分かります。Catyのスキーマ構文で書けば次のようです


type Value = (string|Item);
type Item = {
* : [Value*]?
};

ただし、値が空リストの時は、そのプロパティがないのと同じです。値が空リストであるプロパティを削除した形を正規形とするなら、正規形のスキーマは次のとおり。


type Value = (string|Item);
type Item = {
* : [Value, Value*]? // 項目は1つ以上
};

入れ子構造の平坦化

マルチバリューのオブジェクトよりプロパティリストのほうが扱いやすい処理もあります。その例として、入れ子になったプロパティリストから入れ子を取り除いて平坦にする例を挙げます。単に平坦にするだけではなくて、もとの入れ子情報を完全に残します。どうやって入れ子情報を残すかというと、プロパティ名をパス形式にするのです。

以下は、JavaScriptで書いたアルゴリズムです。次の点は手抜きしているのでご注意。

  1. 名前-値ペア(プロパティ)を、長さ2の配列で表現しています。最初が名前、次が値です。
  2. 末端の値は文字列と仮定しています。その他の型の値ではうまくいきません。
  3. パスとして、文字列のリストを使っています。
// -*- coding: utf-8 

/** ユーティリティ関数 */
function concat(a, b) {
    return Array.prototype.concat.apply(a, [b]);
}

/** アイテムの平坦化 */
function flattenItem(item) {
    var result = [];
    for (var i = 0; i < item.length; i++) {
	var name = item[i][0];
	var value = item[i][1];
	var flatten = flattenPair(name, value); // [pair, ...]
	result = concat(result, flatten);
    }
    return result;
}

/** 名前-値ペアの平坦化 */
function flattenPair(name/*string*/, value) {
    if (typeof value === 'string') {
	return [ [[name], value] ]; // singletonItem: [pair]
    }
    var flatten = flattenItem(value); // item: [pair, ...]
    for (var i = 0; i < flatten.length; i++) {
	var path = flatten[i][0];
	path.unshift(name);
	flatten[i][0] = path;
    }
    return flatten;
}

firebugで実行してみると、次のようになります。


>>> var i = [["a", "1"], ["b", [["x", "2"], ["y", [["z", "3"]]]]], ["c", "4"]]
>>> var x = flattenItem(i)
>>> x
[[["a"], "1"], [["b", "x"], "2"], [["b", "y", "z"], "3"], [["c"], "4"]]

平坦化したリストから、次の関数でマルチバリューのオブジェクトを作ると分かりやすいでしょう。

function flatListToObject(list) {
    var result = {};
    for (var i = 0; i < list.length; i++) {
	var propName = list[i][0].join(".");
	if (!result[propName]) {
	    result[propName] = [];
	}
	result[propName].push(list[i][1]);
    }
    return result;
}

この関数を使ってみます。


>>> var y = flatListToObject(x)
>>> y
Object { a=, more...}

最後のyの値を詳しく見ると:

プロパティ名 プロパティ値
a ["1"]
b.x ["2"]
b.y.z ["3"]
c ["4"]

もとの入れ子構造(階層)が、ドット区切りのプロパティ名のほうに反映されているのです。(もとの名前にドットが含まれると破綻します。)

念のため、次のようなデータも考えてみましょう。

  • [ ["a", "1"], ["a", "1"], ["a", "2"], ["b", [["c", "3"], ["d", "4"]]] ]

ブラケットだらけで分かりにくいですね。次のように書けばだいぶマシです。

  • {("a", "1"), ("a", "1"), ("a", "2"), ("b", {("c", "3"), ("d", "4")})}

マルチバリューの平坦なオブジェクトに変換すると次のようになります。

プロパティ名 プロパティ値
a ["1", "1", "2"]
b.c ["3"]
b.d ["4"]

入れ子になったプロパティリストやオブジェクトを、もとの階層の情報を保存しながら平坦化するには、プロパティ名の側に階層的パス構造を入れればいいわけです。このテクニックはけっこう色んな場面で使えます。そして、この方法のなかにはモナドが隠れているのですが分かりますか?