DEIM Forum 2017 F1-3

CSS における DTD に関して充足不能な規則の検出
岡田

拓也†

鈴木

伸崇††

† 筑波大学 情報学群 知識情報・図書館学類 〒 3058550 茨城県つくば市春日 1-2†† 筑波大学 図書館情報メディア系 〒 3058550 茨城県つくば市春日 1-2
E-mail: †s1311477@u.tsukuba.ac.jp, ††nsuzuki@slis.tsukuba.ac.jp
あらまし

本稿では，DTD（Document Type Denition）を参照して CSS（Cascading Style Sheets）中の充足不能な規則を検出するアルゴリズムを提案する．ここで，充足不能な規則とは，DTD に妥当などの XML/HTML データのどの要素にも適用されない規則のことをいう．提案アルゴリズムは，DTD で記述された要素間の関係と CSS の規則の適用範囲をそれぞれ有限オートマトンで表し，有限オートマトン同士の演算により行われる．評価実験では，DTDと CSS のデータセットを用意し，優先度を考慮しない場合と優先度を考慮する場合の規則の充足可能性判定を行い，それぞれの場合で提案アルゴリズムの実行時間について評価した．その結果，現実的な実行時間で充足不能な規則を概ね検出可能であるという結果が得られた．
キーワード
1.

CSS，DTD，XML

はじめに

Web ページをデザインする際には一般的に CSS（Cascadingする．ここで，本研究では充足不能な規則を，DTD に妥当な
どの XML/HTML データのどの要素にも適用されない規則とする．

Style Sheets）を用いる．CSS はデザイン情報を示す規則集合提案手法では，DTD で定義された要素間の関係を有限オーで構成されるが，その中には Web ページのデザインに影響しトマトンで表す．この有限オートマトンを単に DTD のオートない規則もしばしば見られる．そのような規則は CSS ファイ

マトンと呼ぶ．同様に，CSS の規則の適用範囲を表すセレクタ

ルの可読性の低下，また，レンダリングの速度の低下の原因とを正規表現で表し，これを有限オートマトン化する．この有限なる．

オートマトンを単に規則のオートマトンと呼ぶ．その後，DTD

図 1 に規則集合の記述の例を示す．例えば，図 1 の 1 行目のオートマトンと規則のオートマトンの積オートマトンを求は a 要素の color プロパティの値として red を指定する規則でめる．この積オートマトンの認識する言語が DTD 上での規則ある．

の適用範囲を表し，積オートマトンの認識する言語が空ならばDTD 上で規則が適用されることはなく，規則は充足不能とな

a {color:red;}b {color:red;}c {font-size:80%;}d {font-size:110%;}e {width:210px;}
f {background-color:blue;}る．また，DTD 上では適用される規則でも規則間の適用の優

図 1: 規則集合の記述例

解析したもの [1] がある．しかし，スキーマを考慮していない

先度を考慮したときに充足不能となる規則を検出する場合，優先度のより高い規則を補集合を受理するオートマトンで表し，対象となる規則のオートマトンとの積をとる．
CSS における充足不能な規則の検出の先行研究としてはMarti Bosch らによる CSS の規則間の包含関係や同値関係をため，複数の XML/HTML データに対して充足不能な規則をWeb ページのデザインに影響しない規則を検出できれば，そ検出できないのが問題となる．また，DTD ではなく，単一のの規則を修正，または削除することで，CSS ファイルの可読性

HTML データ上で CSS の規則を解析して，不要なセレクタ

やレンダリングの速度が期待できる．しかし，一般的に Webを発見したものとして，Hsiang-Sheng Liang らの先行研究 [2]

サイトは複数の Web ページで構成されており，複数の Webと，Ali Mesbah らの先行研究 [3] がある．これらの先行研究もページに対して共通の CSS を適用することが多い．このよう同様にスキーマを考慮していないため，複数の XML/HTMLな場合に，個々の Web ページと CSS を比較して Web ページ

データに対して充足不能な規則を検出できないのが問題となる．

のデザインに影響しない規則を検出するのは処理に無駄が多

CSS の仕様策定団体である W3C は，CSS の構文をチェックすい．そこで，複数の XML/HTML データの構造を定義するスるツール [4] を公開しているが，これも DTD は考慮していな

キーマのみを参照して，デザインに影響しない規則を検出でき

い．一方，本研究ではスキーマである DTD を考慮するため，れば有用であると考える．そこで本研究では，スキーマである

DTD に妥当な複数の XML/HTML データに対して充足不能

DTD（Document Type Denition）と，CSS が与えられたとな規則を検出できる．CSS 以外では，XPath 式の充足可能性

きに，CSS 中の充足不能な規則を検出するアルゴリズムを提案を判定する問題が考察されている．この問題は一般には計算困難であり [5]，効率よく判定可能な十分条件が提案されている素の関係は，b 要素が兄要素，c 要素が兄要素 b の弟要素であ（文献 [6] など）．

ることを表している．要素名の右に括弧があるものについては，

本稿の構成は次の通りである．2 章で DTD や CSS，有限オートマトンの概要の説明や充足不能な規則に関する定義を行い，3 章で提案手法について説明する．4 章では評価実験の結果を示し，最後に 5 章でまとめと今後の課題を述べる．

諸

2.

定

2. 2

CSS の概要

XML/HTML に適用されることで Web ページをデザインするスタイルシートとして CSS [7] [8] がある．CSS は規則集合で構成され，一つの規則はセレクタとプロパティ宣言で構成され

義る．セレクタはプロパティを適用する要素を指定するものであ

本章では，DTD や CSS，有限オートマトンの概要と充足不能な規則の定義について述べる．
2. 1

その要素が括弧内の属性を持つことを表している．

る．また，プロパティ宣言はスタイル情報を表している．例えば a {color:red;} という規則において，セレクタは a，プロパ

DTD の概要

ティ宣言は color:red であり，この規則によって，a 要素内の文DTD とは XML/HTML の構造を定義するためのスキーマ

字列は赤字で表示されることになる．本研究では，DTD の定である．DTD を参照することで要素間の親子関係や兄弟関係，義する文書構造と規則の適用範囲を比較して適用されない規則

属性の定義を確認できる．図 2 に DTD の記述例を示す．Σ をを検出するため，セレクタを研究対象とする．

ラベル集合とする．形式的には，DTD は 3 次組 (d, α, a) と定

2. 2. 1セレクタの種類義される．ここで，d は Σ から Σ 上への正規表現の集合への写セレクタの記述にはいくつか種類があるが，本研究では親子像，α は Σ から属性集合への写像，a ∈ Σ は文書要素である．

関係のセレクタと兄弟関係のセレクタを研究対象のセレクタとまたこの DTD が定義する構造を図 4 に示す．

する．その理由は，要素間の関係を適切にセレクタで記述できていないため，規則が適用されないことが多いからである．

DTD D = (d,α,a)<!ELEMENT a (b, c)><!ATTLIST a id ID #REQUIRED><!ELEMENT b (d)><!ELEMENT c (#PCDATA)><!ELEMENT d (#PCDATA)>

図 2: DTD の記述例

d(a) = b,cd(b) = dd(c) = d(d) = ɛa)

親子関係のセレクタ

子孫セレクタ：複数の要素が空白スペースで区切られたセレクタである．子孫セレクタを持つ規則はある要素より下の階層にある要素に適用される．例えば a b というセレクタを持つ規則はある要素 a より下の階層にある要素 b に適用さα(a) = {id}α(b) = α(c) = α(d) = ∅れる．

図 3: DTD の表記られたセレクタである．親子セレクタを持つ規則はある要素の

親子セレクタ：複数のセレクタが大なり記号  > で区切

一つ下の階層にある要素に適用される．例えば a > b というセレクタを持つ規則はある要素 a の一つ下の階層にある要素
b に適用される．

a(id)

b

c

d
図 4: DTD の定義する構造b)

兄弟関係のセレクタ



間接セレクタ：複数の要素がチルダ  ∼ で区切られたセ

レクタである．間接セレクタを持つ規則はある要素の弟要素に適用される．例えば a ∼ b というセレクタを持つ規則はある
要素 a の弟要素 b に適用される．



隣接兄弟セレクタ：複数の要素がプラス記号  + で区切られたセレクタである．隣接兄弟セレクタを持つ規則はある要図 2 では  <!ELEMENT で始まり， > で終わるものは要素宣言， <!ATTLIST で始まり， > で終わるものは属性リ
スト宣言を表している．また，#PCDATA は要素の中身が文字列となることを表している．#REQUIRED は属性の記述を省略できないことを表している．図 3 では DTD D = (d,α,a)において，d は内容モデル，α は属性，a は文書要素とする．内容モデルである d(a) = b,c は，親要素 a が子要素 b と子要素 cを持つことを表し，また，兄要素 b は弟要素 c を持つことも表す．また，ε は子要素を持たないことを表す．属性である α(a)= {id} は a 要素が id 属性を持つことを表す．また，∅ は属性を持たないことを表す．図 4 では矢印の始点が親要素，矢印の終点が親要素に対する子要素を表している．また b 要素と c 要

素に隣接している弟要素に適用される．例えば a + b というセレクタを持つ規則はある要素 a に隣接している弟要素 bに適用される．
2. 2. 2

優 先

度

規則間で適用範囲が重なる場合，優先度の高い規則を適用することになる．本研究の対象のセレクタにおいては，セレクタに出現する要素数がその規則の優先度となる．例えば， a b c{color:red;} のような規則の優先度は 3 である．また，優先度が同じ場合は，CSS の後ろに記述された規則を優先して適用する．また，プロパティ宣言において優先度に関係なく優先してスタイルを適用する!important ルールがあるが，本研究ではプ
ロパティ宣言は研究対象でないため，!important ルールは研究対象としない．

2. 3

充足不能な規則の定義

DTD で定義された要素に適用されない規則は，DTD に妥当などの XML のどの要素にも適用されることはない．このような規則を充足不能な規則とする．形式的には，D を DTD，S
を CSS の規則集合，r ∈ S を CSS の規則とする．D に妥当な
どの XML データ d に対しても，r を適用できる要素が d に存在しないならば，D の下で r は充足不能であるという．本研究ではこのような充足不能な規則を検出するアルゴリズムを提案
する．
2. 4

図 6: 積オートマトン A

有限オートマトンの概要提案手法では有限オートマトンを用いるため，有限オートマ
トンの概要を述べる．有限オートマトンとは，ある特定の性質を満たす文字列を認識する抽象機械である．有限オートマトンの認識する文字列の集合を言語という．図 5 に二進数を受理する有限オートマトンを示す．q0 ，q1 ，q2 が状態を表し，初期状
態は太矢印で示された q0 となる．受理状態は q1 ，q2 となる．
遷移関数は矢印で表し，例えば，q0 において 1 が入力された
場合，q2 に遷移する．この有限オートマトンを M としたとき，この有限オートマトンの認識する言語は L(M ) = {0, 1, 10, 11,…} となる．

2. 4. 2

補集合を受理する有限オートマトン

ある決定性有限オートマトン A = (Q, Σ, δ , q0 , F ) に対し，決定性有限オートマトン B = (Q, Σ, δ , q0 , Q − F ) を A の補集合を受理する有限オートマトンという．すなわち，A の非受理状態を受理状態に，受理状態を非受理状態にすると B になる．アルファベット Σ 上において，L を A の認識する言語，

L を B の認識する言語とするとき，L = Σ∗ - L が成り立つ．
また，決定性有限オートマトンとはどの状態と入力記号の組に対しても，遷移先が高々1 つになるような有限オートマトンで
ある．
3.

提案手法

充足不能な規則を検出するには，DTD で定義される要素間の関係と，CSS のセレクタに記述される要素間の先祖子孫関係
や兄弟関係を比較する必要がある．そのために，DTD で定義される要素間の関係を表す有限オートマトンと，CSS のセレ
図 5: 二進数を受理する有限オートマトン

クタに記述される要素間の先祖子孫関係や兄弟関係を表す有限オートマトンの積をとる．このような処理を行うために，CSS

形式的には，有限オートマトンは 5 次組 M = (Q, Σ, δ , q0 ,のセレクタを正規表現で表す．また，規則間優先度を考慮してF ) と定義される．ここで，Q は状態集合，Σ は入力記号の集充足不能な規則を検出するため，優先度によるセレクタのソー合，δ は遷移関数，q0 は初期状態，F は受理状態の集合を表す．

トを行う．

以下に二進数を受理するオートマトンの形式的定義を示す．



状態集合：Q = {q0 , q1 , q2 }

入力記号の集合：Σ = {0, 1}



遷移関数：δ (q0 , 0) = q1 , δ (q0 , 1) = q2 , δ (q2 , 0) = q2 ,δ (q2 , 1) = q2



初期状態：初期状態は q0



受理状態の集合：F = {q1 , q2 }2. 4. 1積オートマトン有限オートマトン AL = (QL , Σ, δL , qL , FL ) と有限オート
マトン AM = (QM , Σ, δM , qM , FM ) があるとき，AL の認識する言語と AM が認識する言語の共通集合を受理する積オート
マトン A は，A = (QL × QM , Σ, δ , (qL , qM ), FL × FM ) と表せる．ただし，p を AM の状態，r を AL の状態，(p, r ) を

3. 1

前

処

理

前処理として，DTD の内容モデルについて以下の処理を行う．



接続演算子|：要素 a と要素 b があるとき，a | b は a

または b が出現することを意味する．3.4 節の DTD のオートマトンは，要素の親子関係に基づいて作成される．そこで，本手法では接続演算子|を，記述された順序で要素が出現することを意味する接続演算子 , に置き換える．



接続演算子&：要素 a と要素 b があるとき，a & b は aと b が任意の順序で出現することを意味する．接続演算子&についても接続演算子|と同様の理由で接続演算子 , に置き換
える．



実体参照：実体参照を行っている箇所は実体宣言で定義

A の状態としたとき，δ ((p, r), 1) = (δL (p, 1), δM (r, 1)) であされた要素に置き換える．実体宣言で実体が定義されている場

る．図 6 に有限オートマトン AL と有限オートマトン AM の積合は，要素を参照するまでさらに実体参照する．

オートマトン A を示す．

図 7 に表記処理前の DTD を，図 8 に表記処理後の DTD を示す．また図 7 と図 8 に出現する EMPTY は要素が内容を持たないことを意味する．

<!ENTITY % entity “b | c”><!ELEMENT a (%entity;)><!ATTLIST a id ID #REQUIRED><!ELEMENT b (d)><!ELEMENT c (EMPTY)><!ELEMENT d (#PCDATA)>
図 7: 表記処理前の DTD<!ENTITY % entity “b | c”><!ELEMENT a (b, c)><!ATTLIST a id ID #REQUIRED><!ELEMENT b (d)><!ELEMENT c (EMPTY)><!ELEMENT d (#PCDATA)>
図 8: 表記処理後の DTD

親子セレクタ：親子セレクタに記述された最初の要素の前では，アルファベット Σ 上の要素が 0 回以上出現するため，
この部分の正規表現を Σ∗ で表す．例えば，a > b というセレクタを正規表現で表すと， Σ∗ ab となる．
b)

兄弟関係のセレクタ



間接セレクタ：間接セレクタに記述された要素間，また，

間接セレクタに記述された最初の要素の前では，アルファベッ
ト Σ 上の要素が 0 回以上出現するため，この部分の正規表現を

3. 2

提案手法の概要Σ∗ で表す．例えば，a ∼ b というセレクタを正規表現で表す

本手法の処理の流れは以下のようになる．
（ 1 ） 規則集合に対して以下の処理を行う．

と， Σ∗ aΣ∗ b となる．

隣接兄弟セレクタ：隣接兄弟セレクタに記述された最初（ a ） 規則のセレクタを優先度の高い順にソートする．

の要素の前では，アルファベット Σ 上の要素が 0 回以上出現す（ b ） セレクタを正規表現で表す．

るため，この部分の正規表現を Σ∗ で表す．例えば，a + b と（ 2 ） DTD のオートマトンを作成する．

いうセレクタを正規表現で表すと， Σ∗ ab となる．

（ 3 ） 各規則 r に対して，規則 r のオートマトンを作成する．
（ 4 ） 各規則 r に対して，DTD のオートマトンと規則 r の

3. 4

DTD のオートマトンの作成

DTD から要素間の関係を表す DTD のオートマトンを作成

オートマトンの積をとり，積オートマトンを求める．

する．要素間の親子関係を表す DTD のオートマトンと要素間（ a ） 積オートマトンの認識する言語が空ならば，r は充足の兄弟関係を表す DTD のオートマトンの作成手法を以下に不能と判定する．

記す．

（ 5 ） 充足不能と判定されなかった各規則 r に対して，r よ
り優先度の高い規則の補集合を受理する有限オートマトンと rの有限オートマトンの積をとり，積オートマトンを求め，さらに，この積オートマトンと DTD のオートマトンの積をとり，a)

親子関係を表す DTD のオートマトン

DTD

D = (d, α,a) の 親 子 関 係 を 表 す オ ー ト マ ト ン は

M =(Q, Σ, δ, q0 , F ) と定義される．

状 態 集 合 Q：初 期 状 態 は q0 と し ，状 態 集 合 を積オートマトンを求める．

Q={q0 }∪{qa | a ∈ Σ}とする．q0 からは文書要素を表す状（ a ） 積オートマトンの認識する言語が空ならば，r は充足態にのみ遷移する．また，遷移のための入力記号は文書要素を不能と判定する．一方，積オートマトンの認識する言語が空で表す入力記号とする．例えば，文書要素が a 要素の場合，q0 かなければ，r は充足可能と判定する．

ら入力記号 a により，状態 qa に遷移する．

以下，それぞれの処理について詳細を説明する．
3. 3

規則集合の表記の処理



遷移関数 δ ：ある要素を表す状態からその要素の子要素を表す状態への遷移により，要素の親子関係を表す．例えば，

規則間優先度を考慮した充足不能な規則の検出を効率的に行

内容モデルに  d(a) = b という記述がある場合，状態 qa からうために，優先度によるセレクタのソートを行う．本手法では入力記号 b により，状態 qb に遷移する．つまり，δ (qa , b) = qb

優先度の高い順にセレクタをソートすることにする．図 9 にが成り立つ．

ソート前の規則集合，図 10 にソート後の規則集合を示す．



受理状態集合 F：DTD のオートマトンと積をとる親子関係を表す規則のセレクタにおいて，最後の要素が DTD のオーa b c {color:red;}b c {color:blue;}a d c {color:green;}d b d a {color:yellow;}b b a {color:gray;}b a {color:navy;}

d b d a {color:yellow;}b b a {color:gray;}a d c {color:green;}a b c {color:red;}b a {color:navy;}b c {color:blue;}

図 9: ソート前の規則集合

図 10: ソート後の規則集合

トマトンの受理状態となる．例えば，規則 a b {color:red;}のオートマトンと積をとる場合，セレクタの最後の要素が b なので，F ={qb }となる．
図 11 に DTD の形式的定義，図 12 に図 11 の親子関係を表す DTD のオートマトンを示す．また，図 11 の ∗ は要素が 0回以上出現することを表す．
b)

また，規則のオートマトンの作成を効率的に行うために，前処理としてセレクタを正規表現で表す．以下にその前処理について記す．

兄弟関係を表す DTD のオートマトン

DTD

D = (d, α,a) の 兄 弟 関 係 を 表 す オ ー ト マ ト ン は

M =(Q, Σ, δ, q0 , F ) と定義される．

状 態 集 合 Q：初 期 状 態 は q0 と し ，状 態 集 合 をa)

親子関係のセレクタ

Q={q0 }∪{qa | a ∈ Σ}とする．q0 からはそれぞれの兄弟関

子孫セレクタ：子孫セレクタに記述された要素間，また，係の中で最初の要素を表す状態に遷移する．また，遷移のため

子孫セレクタに記述された最初の要素の前では，アルファベッの入力記号はそれぞれの兄弟関係の中で最初の要素を表す入力

ト Σ 上の要素が 0 回以上出現するため，この部分の正規表現記号とする．例えば，内容モデルに  d(a) = b, c と  d(b) =∗を Σ で表す．例えば，a b というセレクタを正規表現で表すd, e という記述がある場合，q0 から，入力記号 b により状態と， Σ∗ aΣ∗ b となる．

qb に遷移し，入力記号 d により状態 qd に遷移する．

q0

DTD D = (d,α,a)ad(a) = b, cd(b) = d, ed(d) = a*d(c) = d(e) = εaα(a) = {id}α(b) = α(c) = α(d) = α(e) = ∅

qd

qa

d

図 11: DTD の形式的定義



qb

Σ

Σ

c

b

qc

e

a

q’0

Σ
b

q’a1

Σ
b

q’b1

c

q’b2

q’c1

qe

図 12: 親子関係を表す DTD のオートマトン

図 14: 規則 a b b c {color:red;}の非決定性有限オートマトン

遷移関数 δ：ある要素を表す状態からその要素に隣接する

現する場合に，それぞれの要素を表す状態を区別するためであ

弟要素を表す状態への遷移により，要素の兄弟関係を表す．例

る．規則 a b b c {color:red;}のセレクタでは b 要素が複数回えば，内容モデルに  d(a) = b, c という記述がある場合，状態′出現するが，出現順序により，最初の b 要素を表す状態が qb1，

qb から入力記号 c により，状態 qc に遷移する．つまり，δ (qb ,′次の b 要素を表す状態が qb2となる．

c) = qc が成り立つ．



また，非決定性有限オートマトンは決定性有限オートマトン

受理状態集合 F：DTD のオートマトンと積をとる兄弟関に変換可能である．本手法では，非決定性有限オートマトンを係を表す規則のセレクタにおいて，最後の要素が DTD のオープログラムで処理しやすい決定性有限オートマトンに変換する．

トマトンの受理状態となる．例えば，規則 a ∼ b {color:red;}

図 3.9 に規則 a b b c {color:red;}の決定性有限オートマトンをのオートマトンと積をとる場合，セレクタの最後の要素が b な′示す．図 15 において，状態 r1 は状態集合{q0′ , qa1}を，状態 r2ので，F ={qb }となる．

′
′
′
′
′
は状態集合{q0′ , qa1, qb1 }を，状態 r3 は状態集合{q0 , qa1 , qb1 ,図 13 に図 11 の兄弟関係を表す DTD のオートマトンを示す．

qb

c

′
′
′
′
′
′
qb2
}を，状態 r4 は状態集合{q0 , qa1 , qb1 , qb2 , qc1 }を表す．

qc

b
d

q0

qd

e

b,c,d,e

qe

r0

a
qa

a,c,d,ear1

a,b,d,e a,b,d,ea,c,d,e
b

r2

b

r3

c

r4

c

a

図 13: 兄弟関係を表す DTD のオートマトン

また，本手法では有限オートマトンの遷移関数を二次元ハッシュで実装する．二次元ハッシュは二つのキーと値で構成される

図 15: 規則 a b b c {color:red;}の決定性有限オートマトン
3. 6

積オートマトンの作成

本手法では DTD のオートマトンと規則のオートマトンの積が，一つ目のキーには遷移前の状態を，二つ目のキーには入力記をとり，積オートマトンを求める．形式的には，DTD のオート号を，値には遷移後の状態をそれぞれ格納する．例えば，δ (qa ,マトン (Q, Σ, δ, q0 , F ) と規則のオートマトン (Q′ , Σ, δ ′ , q0′ , F ′ )b) = qb を二次元ハッシュで表すと，{ qa =>{b=> qb  }}との積オートマトンは (Q × Q′ , Σ, δ ′′ , (q0 , q0′ ), F ′′ ) である．ここなる．

で，δ ′′ と F ′′ は次のように定義される．

3. 5

規則のオートマトンの作成

正規表現は非決定性有限オートマトンに変換可能である．図3.8 に規則 a b b c {color:red;}（セレクタを正規表現で表すと
∗

∗

∗

∗

Σ aΣ bΣ bΣ c）の非決定性有限オートマトンを示す．



任意の q ∈ Q, q ′ ∈ Q′ , a ∈ Σ に対して，δ ′′ ((q, q ′ ), a) =δ(q, a) × δ(q ′ , a)F ′′ = F × F ′積オートマトンの初期状態は DTD のオートマトンの初期

図 14 の有限オートマトンにおいて，初期状態は q0′ とする．

状態 q0 と規則のオートマトンの初期状態 q0′ の組 (q0 ,q0′ ) とす

受理状態は規則のセレクタに出現する最後の要素とし，規則 aる．また，規則のセレクタの最後の要素が b のとき，積オーb b c {color:red;}では，最後の要素が c 要素なので，受理状態′
トマトンの受理状態は (qb ,qb1
) となる．親子関係を表すセレク′
は c 要素を表す状態 qc1とする．また，状態の添え字の末尾にタを持つ規則のオートマトンと DTD のオートマトンで積をと数字が付与されているが，これはセレクタに同じ要素が複数出るとき，DTD のオートマトンは親子関係を表すオートマトン

を用い，兄弟関係を表すセレクタを持つ規則のオートマトンと可能性判定の結果が記述されている．まず，2，4，5 行目の規

DTD のオートマトンで積をとるとき，DTD のオートマトンは則は充足可能な規則であり，かつ，セレクタの最後の要素が判兄弟関係を表すオートマトンを用いる．積オートマトンの例と定対象規則のセレクタの最後の要素と同じなので，2，4，5 行

して，図 3.6 の DTD のオートマトンと規則 a b {color:red;}の目の規則同士の和を表す有限オートマトンを作成する．次に，オートマトンの積をとってできる積オートマトンを図 16（状態

この有限オートマトンの補集合を受理する有限オートマトンを遷移により受理状態に到達し得ない状態は省略）に示す．

作成する．そして，この有限オートマトンと 6 行目の規則の有限オートマトンの積オートマトンを求める．最後に，DTD のa(q0,q’0)a

オートマトンと求めた積オートマトン同士の積オートマトンを(qd,q’a1)(qa,q’a1)

求める．この積オートマトンの認識する言語が空ならば 6 行目の規則は充足不能と判定できる．一方，積オートマトンの認識b(qb,q’b1)dする言語が空でないならば 6 行目の規則は充足可能と判定できる．

図 16: 積オートマトン

3. 7

1.
2.
3.
4.
5.
6.

規則の充足可能性判定

規則の充足可能性判定を行うために，積オートマトンの認識する言語に着目する．作成した積オートマトンにおいて，認識する言語が空ならば DTD と積をとった規則は充足不能と判定

a a b {…} （充足可能）
a b c {…} （充足可能）
b b c {…} （充足不能）
b c {…} （充足可能）
d c {…} （充足可能）
c c {…}

でき，一方，認識する言語が空でないならば DTD と積をとった規則は充足可能と判定できる．認識する言語が空か否かを調図 17: 規則集合（プロパティ宣言は省略）

べるためには，積オートマトンの初期状態を起点として遷移可能な状態集合に受理状態が含まれているか確認すればよい．受理状態が含まれていなければ，積オートマトンの認識する言語
は空であり，規則は充足不能と判定できる．一方，受理状態が含まれていれば，積オートマトンの認識する言語は空でなく，規則は充足可能と判定できる．しかし，この判定には，判定対象の規則より優先度が高いものは考慮されていないため，充足可能と判定された規則については，規則間優先度を考慮して充足可能か否かを判定する必要がある．ただし，優先度の高い順にソートされた規則集合の中で一番前に記述された規則（最も優先度の高い規則）の充足可能性判定を行う際には規則間優先度を考慮する必要はない．
3. 7. 1

規則間優先度の考慮

規則間優先度を考慮した規則の充足可能性判定の流れは以下のようになる．
（ 1 ） 「判定対象の規則 r より優先度の高い規則のすべての和」を表す有限オートマトンを作成する．これを M とする．
（ 2 ） M の補集合を受理する有限オートマトンを作成する．
（ 3 ） M の補集合を受理する有限オートマトンと r のオー
トマトンの積をとり，積オートマトンを求める．これを M ′ とする．
（ 4 ） DTD のオートマトンと M ′ の積をとり，積オートマ
トンを求める．
（ a ） 積オートマトンの認識する言語が空ならば，r は充足不能と判定する．一方，積オートマトンの認識する言語が空でなければ，r は充足可能と判定する．
規則間優先度を考慮した規則の充足可能性判定の例として，
図 17 の規則集合において 6 行目の規則が充足不能か否かを判定する場合を考える．また，図 17 の丸括弧内には規則の充足

4.

評価実験

本章では，提案手法に関する評価実験について述べる．
4. 1

概

要

ここでは評価実験の概要と手順について記す．本手法は大きく分けて規則間優先度を考慮しない場合の規則の充足可能性判
定と，規則間優先度を考慮した規則の充足可能性判定の 2 つに分けられる．そこで，評価実験では主にこの 2 点について評価する．具体的には，評価実験（1）において，規則間優先度を考慮する場合と規則間優先度を考慮しない場合，それぞれについて適切に充足不能な規則を検出しているかを評価する．また，評価実験（2）では，規則間優先度を考慮する場合と規則間優先度を考慮しない場合，それぞれについて提案手法の処理時間について評価する．評価実験に用いる DTD は W3C が公開している DTD（XHTML-1.0-Transitional） [9] を用いる．評価
実験に用いる CSS は以下の手順で収集した．
（ 1 ） 以下の 4 つの Web サイトで使われている CSS を用
いる．



食べログ



日本漢字能力検定

社会工学類 | 筑波大学 理工学群

NHK オンライン（ 2 ） 子孫セレクタに ID セレクタ等が付加されているもの
は，それらを削除して子孫セレクタのみを残す．また，カンマ, でセレクタが区切られているような規則は評価対象外とする．

（ 3 ） 本評価実験では，実データに親子セレクタや間接セレ
クタ，隣接兄弟セレクタが出現することが少ないので，子孫セレクタを単独で持つ規則のみを評価対象とする．

が含まれていたためである．この規則は要素 marquee が DTD

表 1 に CSS のデータセットを示す．なお，表 1 の規則数は子孫セレクタを単独で持つ規則の数を表す．

で定義されていないため充足不能と判定された．以上の結果か
ら提案手法のアルゴリズムにより，規則間優先度の考慮なしで充足不能な規則を適切に検出可能であると言える．

表 1: CSS のデータセットb)

Web サイト名

規則数

食べログ （http://m.tabelog.com/）17

日本漢字能力検定 （http://www.kanken.or.jp/kanken/）23

社会工学類 | 筑波大学 理工学群

27

（https://www.sk.tsukuba.ac.jp/College/）
NHK オンライン （http://www.nhk.or.jp/）469

規則間優先度の考慮あり（ 1 ） 提案手法のアルゴリズムを用いて充足不能な規則を検出する．
（ 2 ） もともと CSS 中に含まれる充足不能な規則を 1 で充足不能と判定できているか確認する．
表 3 に結果を示す．なお，NHK オンラインは規則数が多く，充足不能な規則数を手作業で把握するのは困難であったため不明と記した．

評価実験の環境は以下の通りである．

プ ロ セッサ:Intel(R) Core(TM) i5-5200U CPU @表 3: 充足不能な規則の検出結果（優先度の考慮あり）

2.19GHzWeb サイト名



OS: Windows 10 64-bit

メモリ: 8.00GB



使用言語: Ruby 2.1.4

4. 2

規則数

充足不能な

検出した

規則数

充足不能な
規則数

評価実験 (1)

提案手法のアルゴリズムを用いて，規則間優先度の考慮がない場合と規則間優先度の考慮がある場合それぞれにおいて，充

食べログ

17

7

7

日本漢字能力検定

23

16

16

社会工学類 | 筑波大学 理工学群

27

14

14

NHK オンライン

469

不明

412

足不能な規則を適切に検出できるかを確認するために以下のよ
食べログと日本漢字能力検定と社会工学類 | 筑波大学 理工

うな手順で実験を行った．
a)

学群の 3 つの CSS について，もともと含まれていた充足不能

規則間優先度の考慮なし（ 1 ） 以下に示す 5 つのセレクタを持つ規則間優先度を考慮な規則をすべて検出することができた．以上の結果から提案手せずに充足不能となる規則を CSS に挿入する．

法のアルゴリズムにより，規則間優先度の考慮ありの場合でも

body head title

h3 head

option base

充足不能な規則を適切に検出可能であると言える．
4. 3

評価実験 (2)提案手法のアルゴリズムを用いて現実的な時間で充足不能なa small body

規則の検出が可能かを評価するために，規則間優先度の考慮な

dir li html

しの場合と規則間優先度の考慮ありの場合それぞれにおいて，（ 2 ） 提案手法のアルゴリズムを用いて充足不能な規則を検処理時間を計測した．
図 18 に規則間優先度の考慮なしの場合の結果を示す．規則

出する．
（ 3 ） 1 に挙げた充足不能な規則を 2 で充足不能と判定でき数が多い NHK オンラインの CSS ではすべての規則についてているか確認する．

充足不能か否かを判定するのに少々時間がかかったが，規則数が少ない食べログや日本漢字能力検定，社会工学類 | 筑波大学

表 2 に結果を示す．

理工学群の CSS では現実的な処理時間で充足不能な規則を検表 2: 充足不能な規則の検出結果（優先度の考慮なし）
Web サイト名

規則数出できた．したがって，今回の実験の範囲では，ある程度規則

充足不能な

検出した

数を限定することで，規則間優先度の考慮なしで充足不能な規

規則数

充足不能な

則の検出を現実的な時間で行えたと言える．

規則数
食べログ

22

5

5

80

日本漢字能力検定

28

5

5

70

社会工学類 | 筑波大学 理工学群

32

5

5

NHK オンライン

474

6

6

処理時間(s)

60

50
40
30

20

4 つすべての CSS について，挿入した 5 つの充足不能な規則をすべて検出することができた．また，NHK オンラインにおいて充足不能な規則を 6 つ検出したのは，もともと充足不能な規
則 div marquee{font-size:14px;line-height:16px;color:#f00;}

10
0
食べログ

日本漢字能力検定

社会工学類

NHKオンライン

図 18: 処理時間（規則間優先度の考慮なし）

図 19 に規則間優先度の考慮ありの場合の結果を示す．規則
数が多い NHK オンラインの CSS ではすべての規則について
充足不能か否かを判定するのに少々時間がかかったが，規則数

in the presence of DTDs, Journal of the ACM (JACM),
vol.55, no.2, May 2008. DOI:10.1145/1346330.1346333[6]出できた．したがって，今回の実験の範囲では，規則数が著しand K. Ikeda,

Satisability

Proc. IEICE TRANSACTIONS on Information and Systems, vol.E96-D, no.5, pp.1029-1042, May 2013.
[7]

World Wide Web Consortium (W3C), Cascading Style
Sheets Level 2 Revision 1 (CSS 2.1) Specication, World

く多くならない限り，規則間優先度の考慮ありで充足不能な規則の検出を現実的な時間で行えたと言える．

Y. Fukushima,of Simple XPath Fragments under Duplicate-Free DTDs,

が少ない食べログや日本漢字能力検定，社会工学類 | 筑波大学
理工学群の CSS では現実的な処理時間で充足不能な規則を検N. Suzuki,

Wide Web Consortium (W3C),
http://www.w3.org/TR/CSS2/, 参照 May. 27,2016.
[8]

World Wide Web Consortium (W3C), CSS Syntax Module
Level 3, World Wide Web Consortium (W3C),
http://www.w3.org/TR/css-syntax-3/, 参照 May. 27,2016.

3000

[9]

2500

World Wide Web Consortium (W3C), -//W3C//DTD

処理時間(s)XHTML 1.0 Transitional//EN, World Wide Web Consor2000

tium (W3C),
http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd,

1500

参照 November. 08,2016.

1000

500
0
食べログ

日本漢字能力検定

社会工学類

NHKオンライン

図 19: 処理時間（規則間優先度の考慮あり）

5.

む

す

び

本稿では，DTD と CSS が与えられたとき，有限オートマト
ンを用いて CSS 中の充足不能な規則を検出する手法を提案した．更に，提案手法を実装し，評価実験を行うことで，提案手法
で充足不能な規則の検出が可能であることを確認した．今後の課題としては属性を考慮することで，和をとる有限オートマト
ンの数や，積オートマトンの作成回数を少なくすることが挙げられる．属性を考慮しない現在の手法では，不必要な有限オー
トマトン同士の和や，不必要な積オートマトンの作成がなされ得る．このことは，充足不能な規則の検出の効率を下げる．例
えば，規則 a#foo b c {color:red;}と規則 a c {color:yellow;}において，規則 a c {color:yellow;}は値 foo 以外の id 属性を持
つ a 要素の子孫要素である c 要素にも適用され得るので，規則
a c {color:yellow;}の適用範囲は規則 a#foo b c {color:red;}の適用範囲に包含されることはない．そのため，和や積をとる必要がなくなる．このような工夫をすることでより効率的に充足不能な規則を検出できると考えられる．

文
[1]

献

M. Bosch, P. Geneves, and N. Layaida, Automated refactoring for size reduction of CSS style sheets, Proc. DocEng,
September 2014. DOI:10.1145/2644866.2644885[2]

H.S. Liang, K.H. Kuo, P.W. Lee, Y.C. Chan, Y.C. Lin,and M.Y. Chen, Seess: seeing what I broke â visualizing change impact of cascading style sheets (CSS), Proc.
UIST, October 2013. DOI:10.1145/2501988.2502006[3]

A.Mesbah, and S.Mirshokraie, Automated analysis of CSS
rules to support style maintenance, Proc. ICSE, pp.408
418, June 2012.

[4]

World Wide Web Consortium (W3C), W3C CSS 検証サー

ビス, World Wide Web Consortium (W3C),
https://jigsaw.w3.org/css-validator/validator.html, 参照 November. 19,2016.
[5]

M. Benedikt, W. Fan, and F. Geerts, XPath satisability