DEIM Forum 2019 I2-1

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

拓也†

伸崇††

鈴木

† 筑波大学大学院図書館情報メディア研究科 〒 305–8550 茨城県つくば市春日 1–2†† 筑波大学図書館情報メディア系 〒 305–8550 茨城県つくば市春日 1–2
E-mail: †s1721657@s.tsukuba.ac.jp, ††nsuzuki@slis.tsukuba.ac.jp
あらまし Web ページのスタイルを指定するために，一般的に用いられるスタイルシートとして CSS がある．CSS
は規則集合で構成され，規則を XML/HTML データに適用することで Web ページのスタイルを指定する．CSS 作成の過程で，Web ページのスタイルに影響を与えない無駄な規則が記述されることがある．このような規則によって，

CSS の可読性を低下させ，メンテナンスが困難になるなどの問題が生じる．そこで，本研究では DTD を参照することで，DTD に妥当などの XML/HTML データのどの要素にも適用されることのない CSS 規則（充足不能な規則）を検出するアルゴリズムを提案する．提案アルゴリズムでは，オートマトン理論に基づいて充足不能な規則の検出を行う．DTD と CSS 規則それぞれからオートマトンを構成し，オートマトン間の演算により充足不能な規則を検出する．
手動で充足不能な規則を発見することは一般的に極めて難しい問題である．評価実験では，提案アルゴリズムを用いて充足不能な規則を検出する場合と，手動で充足不能な規則を検出する場合とで処理時間などを比較した．その結果，
提案アルゴリズムの有効性を示唆する結果が得られた．
キーワード

CSS，DTD，XML
そこで，本研究では XML/HTML のデータ構造を定義する

1 はじめにWeb ページのスタイルを指定するために，一般的に用いられるスタイルシートに CSS がある．また，CSS は HTML デー
タだけでなく，XML データのスタイル記述言語としても広く用いられている（例えば，DocBook [1] や MathML [2] など）．

CSS は規則集合で構成され，規則を XML/HTML に適用することで，Web ページのスタイルを指定する．個々の規則はセレクタとプロパティで構成される．セレクタによりプロパティを適用する要素が指定される．また，セレクタでは要素間関係を記述したり，要素の持つ属性などが記述できる．CSS は記述の自由度が高いことがメリットとしてあるが，一方，CSS 作成の過程で，Web ページのスタイルに影響を与えない規則が記述されることがある．このような規則によって，CSS の可読性を低下させ，メンテナンスが困難になるなどの問題が生じる．

XML/HTML データに関して不要な CSS 規則を検出する手法は存在するが，それだけでは不十分である．ある程度の規模を持つ Web サイトでは，複数の XML/HTML データに対して共通の CSS を適用することが多い．このような場合において，ある XML/HTML データのスタイルには影響を与えないが，他の XML/HTML データのスタイルに影響を与えるような規則が，CSS 作成者によって記述されることがある．さらに，

XML/HTML データは時間の経過と共に更新されることが多い．ある特定の XML/HTML データのどの要素にも適用されスキーマの一つである DTD を参照することで，DTD に妥当な
どの XML/HTML のどの要素にも適用されることのない CSS
規則（以降，この規則を充足不能な規則と呼ぶ）を検出するアルゴリズムの提案・考察を行う．提案アルゴリズムでは，以下三つの条件に関して，単一の規則が充足不能か否かを判定できる．

•

規則のセレクタにおいて，要素の持つ属性が正しく記述されているか•

規則のセレクタにおいて，要素間関係が正しく記述され

ているか

•

判定対象規則より優先度の高い規則集合の適用要素の集合に，判定対象規則の適用要素の集合が包含されていないか
これらの条件のうち一つでも満たさない条件があれば，規則を充足不能と判定する．提案アルゴリズムでは，DTD の定義するデータ構造と CSS セレクタの構造をそれぞれオートマトンで表現し，オートマトン同士の演算により充足不能な規則を検出する．また，これら三つの条件を手動で確かめながら，充足不能な規則を発見することは，一般的に極めて難しい問題である．
そこで，評価実験では，提案アルゴリズムを用いて充足不能な規則を検出する場合と，手動で充足不能な規則を検出する場合とで処理時間を比較した．この評価実験において，提案アルゴ
リズムを用いて充足不能な規則を検出する方が，処理効率が良く，提案アルゴリズムの有効性が認められる結果が得られた．
関連研究ない CSS 規則が検出されたとしても，その規則が本当に不要なCSS の静的解析について，Geneves らは CSS 規則を論理式のか否かは自明でない．したがって，どの XML/HTML デーに変換して解析するシステムを提案している [3]．Bosch らはタやにも適用され得ない不要な規則を自動的に検出できれば有CSS 規則のリファクタリングを行う手法を提案しており [4]，ま用であると考えられる．

た，Mazinanian らは重複した CSS 規則を検出する手法を提案している [5] [6]．CSS 規則を HTML データ上で解析するためのである．次に，兄 author の弟は author となる．これは，演算手法は数多く提案されている．例えば，FireBug [7] や Chrome子 ‘+’ は要素が 1 回以上出現することを示しているためである．

Developer Tools [8] では，HTML データのどの要素にも適用

また，α(book) = {price, id} では，book が属性 price と id をされない規則を検出できる．Hague らは，HTML5 アプリケー

持つことを表す．

ション上で冗長な CSS 規則を検出するための手法を提案している [9]．Mesbah らは，HTML データ上で冗長な CSS 規則を検出するための手法を提案している [10]．しかし，これらの手法は DTD を考慮していない．筆者の知る限り，DTD の下での規則の充足不能性について考察した研究は存在しない．

2. 2 CSS の概要
XML/HTML に適用されることで Web ページのスタイルを指定するスタイルシートとして CSS がある．CSS は規則集合で構成され，一つの規則はセレクタとプロパティで構成される．
セレクタによりプロパティを適用する要素を指定する．例えば

ul li {font-color:red} という規則において，セレクタは ul li，

2 諸 定 義プロパティは color:red であり，この規則によって，ul の子孫
本章では，DTD や CSS，充足不能な CSS 規則に関する定義を行う．

要素 li 内の文字列は赤字で表示されることになる．
次に CSS 規則について定義を述べる．Σ をラベル集合とする．Σ に属するラベルおよび記号 ‘∗’ を単純セレクタという．単2. 1 DTD の概要
DTD とは XML/HTML の構造を定義するためのスキーマである．DTD を参照することで要素間の親子関係や兄弟関係，属性の定義を確認できる．DTD を 3 次組 D = (d, α, s) と表す．ここで，d は Σ から Σ 上の正規表現集合への写像，α はΣ から属性集合への写像，s ∈ Σ は開始ラベルである．ラベルa ∈ Σ に対して，d(a) を a の内容モデルという．例えば，図 1の book を文書要素とする DTD を考える．

純セレクタ s に対して，もし s =‘∗’，または，s がラベルでありかつ s = l(v) ならば，s は v にマッチするという．

2. 2. 1 要素間関係セレクタ
セレクタとは，単純セレクタを結合子で繋げたものである．
ここで，結合子とは空白を表す ‘ ’（子孫），‘＞’（子），‘＋’（隣接兄弟），および，‘∼’（一般兄弟）である．セレクタ sel の長さを len(sel) と表し，sel に含まれる単純セレクタの数と定義
する．例えば，sel = a ∗ ＞ c のとき，len(sel) = 3 である．

s, s′ を単純セレクタ，(v, v ′ ) を木 t の頂点の組とする．
<!ELEMENT book(title, author+)><!ATTLIST bookprice CDATA #IMPLIED
id
ID#IMPLIED><!ELEMENT author (name, age)><!ELEMENT title(#PCDATA)><!ELEMENT name (#PCDATA)><!ELEMENT age(#PCDATA)>•

もし s が v にマッチし，s′ が v ′ にマッチし，かつ，v ′が v の子孫であるならば，子孫セレクタ s s′ は (v, v ′ ) にマッ
チするという．

•

もし s が v にマッチし，s′ が v ′ にマッチし，かつ，v ′が v の子であるならば，子セレクタ s ＞ s′ は (v, v ′ ) にマッチするという．

•

もし s が v にマッチし，s′ が v ′ にマッチし，かつ，v ′が v の（必ずしも隣接しない）弟であるならば，一般兄弟セレ

図 1 DTDクタ s ∼ s′ は (v, v ′ ) にマッチするという．

このとき，上記 DTD は 3 次組 (d, α,book) で表され，ここで d(book) = title author+ ，d(author) = name age，d(title)= d(name) = d(age) = ϵ である．木 t の頂点 v に対して，v の•もし s が v にマッチし，s′ が v ′ にマッチし，かつ，v ′が v に隣接する弟であるならば，隣接兄弟セレクタ s ＋ s′ は(v, v ′ ) にマッチするという．

ラベルを l(v) と表す．このとき，木 t と DTD D = (d, s) に対

sel = s1 c1 s2 c2 s3 …sn−1 cn−1 sn をセレクタ，(v, v ′ ) を木 t の頂して，もし t のルートのラベルが s であり，かつ，t の任意の頂点の組とする．ここで，si は単純セレクタ，ci は結合子である．

点 n に対して d(l(n)) が l(n1 )l(n2 )…l(nm ) にマッチするならば，t は D に対して妥当であるという．ここで，n1 , n2 , …, nm
は n の子である．また，α(book) = {price, id}，α(author)= α(title) = α(name) = α(age) = ϵ である．
次に上記 DTD で定義される親子関係や兄弟関係，属性について述べる．例えば，d(book) = title author+

について考える．ここで，親子関係については，親 book の子は book の内容
モデルに出現する title と author である．また，兄弟関係については，book の内容モデルに出現する各要素を兄としたときもし n 個の頂点の系列 v = v1 , v2 , …, vn = v ′ で，任意の 2 <=i<= n に対して si−1 ci−1 si が (vi−1 , vi ) にマッチするものが存在するならば，sel は (v, v ′ ) にマッチするという．

CSS 規則を sel p : v と表す．ここで，sel はセレクタ，p はプロパティ，v はプロパティ値である（ただし，実際には，1 つの CSS 規則にプロパティとその値の組を複数記述することができる．そのような CSS 規則は，sel p : v のように 1 つのプロ
パティとその値をもつ CSS 規則を複数記述することで表せる．
例えば，sel {p1 : v1 , p2 : v2 } は 2 つの CSS 規則 sel p1 : v1 との，その兄の（必ずしも隣接しない）弟を考える．まず，title

sel p2 : v2 として表せる．
）．CSS 規則 r に対して，r のセレクを兄としたとき，その弟は兄の後ろに出現し得る要素すべてとタを sel(r)，r のプロパティを prop(r) と表す．セレクタ sel になり，ここでは author しかないので，兄 title の弟は author

対して，sel の終端の単純セレクタを tail(sel) と表す．例えば，

r = a b ＋ c p : v とすると，sel(r) = a b ＋ c，prop(r) = p，

（ 1 ） sel(r) において，D の下で単純セレクタの持つ属性がtail(sel(r)) = c である．以下では簡単のため，任意の CSS 規

正しく記述されていないならば r は充足不能である．

則 r に対して，tail(sel(r)) はラベルであると仮定する．

（ 2 ） sel(r) = s1 c1 s2 c2 s3 …sn−1 cn−1 sn を r のセレクタ，

2. 2. 2 属性セレクタ

D = (d, s) を DTD とする．D に妥当などの木 t に対しても，

本研究では一部の属性セレクタを扱う．以下に示す属性セレ

sel(r) がマッチするような頂点の組 (v, v ′ ) が t に存在しないな

クタが対象である．

•

id セレクタ：記号 ‘#’ で表されるセレクタである．単純らば，r は充足不能である．簡単に言うと，sel(r) において，Dの下で要素間関係が正しく記述されていないならば r は充足不セレクタの後に記述することでその単純セレクタが id 属性を能である．

持つことになる．

（ 3 ） CSS 規則の衝突が発生している場合，pri(sel(r)) より•

class セレクタ：記号 ‘.’ で表されるセレクタである．単優先度の高い規則（もし 2 つの CSS 規則が同じ優先度をもつ純セレクタの後に記述することでその単純セレクタが class 属

場合，後に出現する CSS 規則）集合の適用要素の集合に，r の性を持つことになる．

適用要素の集合が包含されているならば r は充足不能である．

•

一般属性セレクタ：att を属性とするとき，[att] と表されるセレクタである．単純セレクタの後に記述することでその単純セレクタが att を持つことになる．

3 つのパターンすべてで充足不能とならない場合は，r は充足可能である．
以下に充足不能な CSS 規則の例を示す．

2. 2. 3 優 先 度
CSS スクリプトにおいて，CSS 規則の衝突，すなわち，同じ
プロパティをもつ複数の CSS 規則が XML/HTML データの同じ要素にマッチする，ということがしばしば発生する．このような衝突を解決するために，CSS では優先度と呼ばれる仕組みが用意されている．最も優先度が高い CSS 規則のみが適用される．
セレクタ sel に出現するラベルの数，id セレクタの数，class<!ELEMENT book(title, author+)><!ATTLIST bookprice CDATA #IMPLIED
id
ID#IMPLIED><!ELEMENT author (name, age)><!ELEMENT title(#PCDATA)><!ELEMENT name (#PCDATA)><!ELEMENT age(#PCDATA)>

セレクタの数，一般属性セレクタの数をそれぞれ ltot(sel)，

idtot(sel)，cltot(sel)，atttot(sel) と表す．pri(sel) は sel の優

図 2 DTD

先度を表す．このとき，pri(sel) = ltot(sel)+idtot(sel)×100+

cltot(sel) × 10 + atttot(sel) × 10 である．例えば，sel = a#1 ∗＋ c のとき，ltot(sel) = 2，idtot(sel) = 1，cltot(sel) = 0，

atttot(sel) = 0 であり，pri(sel) = 102 となる．CSS スクリプ
トは CSS 規則のリスト R として定義される．CSS 規則 r の R
における位置を indexR (r) と表す．例えば，R = [r, r ′ , r ′′ ] としたとき，indexR (r) = 1 かつ indexR (r ′′ ) = 3 である．r がR に出現するとき，r ∈ R と書く．木 t と t の頂点 v に対して，もし CSS 規則 r ∈ R が次の条件を満たすならば，r は v に適用されるという．

•

t のある頂点 v ′ に対して，sel(r) は (v ′ , v) にマッチし，

かつ，•

任意の CSS 規則 r′ ∈ R に対して，もし sel(r′ ) がある頂点 v ′′ に対して (v ′′ , v) にマッチし，かつ，prop(r) = prop(r′ )であるならば，(a) pri(sel(r)) > pri(sel(r′ ))，または，(b)pri(sel(r)) = pri(sel(r′ )) かつ indexR (r) > indexR (r′ )，が成り立つ．

2. 3 充足不能な CSS 規則の定義

book.a{font-family:serif}
author title {font-family:serif}book age{font-family:serif}
author age {font-family:sans-serif}
name + age {font-family:fantasy}

図 3 充足不能な CSS 規則の例

図 2 の DTD の 下 で 図 3 の CSS 規 則 book.a {font-family:serif} は，パターン 1 において DTD で要素 book がclass 属性を持たないことから，充足不能である．CSS 規則
author title {font-family:serif} は，パターン 2 において DTD
で要素 author の子孫要素に要素 title が出現しないことから，充足不能である．また，book age {font-family:serif} は充足不能である．その理由は次のとおりである．パターン 3 において
まず 4 番目または 5 番目の規則集合とプロパティの衝突が発生している．次にどの要素 age も要素 book を親としてもつま

本稿では，DTD の下で充足不能な CSS 規則を検出する問題

たは要素 name を隣接する兄としてもち，よってどの要素 ageについて考える．ここで，CSS 規則 r と DTD D に対して，もに対しても 4 番目または 5 番目の CSS 規則が適用されるためし D に妥当などの XML/HTML データのどの要素にも r が適（もし 2 つの CSS 規則が同じ優先度をもつ場合，後に出現す用されない場合，r は D の下で充足不能であるという．本論文

る CSS 規則が適用される），book age {font-family:serif} はでは r が充足不能となるパターンを 3 つに限定し，順に検証充足不能である．言い換えると，book age {font-family:serif}する．

の優先度より優先度の高い規則集合の適用要素の集合に，bookage {font-family:serif} の適用要素の集合が包含されているため，book age {font-family:serif} は充足不能である．

（ 7 ） 1. 4. 6. すべて（パターン 1, 2, 3 すべて）で充足不能とならない場合は，r は充足可能と判定する．
以降各ステップについて具体的に述べる．

3 充足不能な規則の検出手法
本章では，次の DTD の下で充足不能な CSS 規則を検出す

3. 2 属 性 判 定
sel(r) に属性を持つ単純セレクタが存在する場合，r の属性

る問題について考える．

判定を行う．ここで，sel(r) 中の属性を持つ単純セレクタの集

入力： DTD D ，CSS スクリプト R，CSS 規則 r ∈ R

合を As とし，as ∈ As は属性を持つ単純セレクタである．as

問題： r が D の下で充足不能であるか否かを決定せよ

は要素 ele(as ) とその要素の持つ属性 att(as ) で構成される．ま本稿では r が充足不能となるパターンを 3 つに限定し，順にた，DTD D の要素 Σ から属性集合への写像を α とする．こ

検証する．

こで，任意の as ∈ As に対して att(as ) ̸∈ α(ele(as )) が成り立

（ 1 ） sel(r) において，D の下で単純セレクタの持つ属性がつ as が存在するならば，r は充足不能と判定する．

正しく記述されていないならば r は充足不能である．

例えば，sel = a#1 b.1 ＋ c である r の属性判定について考（ 2 ） sel(r) において，D の下で要素間関係が正しく記述さえる．ここで，D について，α(a) = {id, class}，α(b) = {id}，れていないならば r は充足不能である．

α(c) = {id, class} であるとする．このとき，As = {a#1, b.1}

（ 3 ） CSS 規則の衝突が発生している場合，pri(sel(r)) よりとなる．また，as = a#1 に対して，ele(as ) = a，att(as ) = id

優先度の高い規則（もし 2 つの CSS 規則が同じ優先度をもつであり，as = b.1 に対して，ele(as ) = b，att(as ) = class で場合，後に出現する CSS 規則）集合の適用要素の集合に，r のある．このとき，b.1 ∈ As に対して att(b.1) ̸∈ α(ele(b.1)) が適用要素の集合が包含されているならば r は充足不能である．

成り立つため，r の属性判定の結果は充足不能となる．

3 つのパターンすべてで充足不能とならない場合は，r は充足
3. 3 DTD オートマトンの構成可能である．

DTD の要素間関係を表す DTD オートマトンを構成する．

3. 1 提案手法の概要

例えば，図 4 は DTD D = (d, s)（ここでは，α は考慮しな

次に r ∈ R が DTD D の下で充足不能か否かを決定する本い）の DTD オートマトンを示しており，ここで d(s) = ab∗ ，

手法の流れを示す．

d(a) = ϵ，d(b) = sc，d(c) = ϵ である（演算子 ‘∗’ は要素が 0（ 1 ） sel(r) に出現する属性を持つ単純セレクタそれぞれに回以上出現することを表す）．この図において，横方向の状態

ついて，DTD の α を参照し，単純セレクタに属性セレクタが遷移は D の内容モデルにおける状態遷移つまり兄弟関係を表

正しく指定されていないものがあれば，上記パターン 1 にて r

し，縦方向の状態遷移は親子関係を表す．

は充足不能と判定する（以降簡単のためこの判定を属性判定と呼ぶ）．
（ 2 ） D の DTD オートマトン MD を構成する．
（ 3 ） sel(r) を正規表現 re(sel(r)) に変換する（r の CSS 規
則オートマトン Mr を構成する）．
（ 4 ） 以下が成り立つか否かを判定する

L(MD ) ∩ L(Mr ) = ∅
上記の式が成立するならば，パターン 2 にて r は充足不能と判定する（以降簡単のためこの判定を優先度無し要素間関係判定と呼ぶ）．
（ 5 ） r1 , r2 , …, rk ∈ R を，r と衝突し得る CSS 規則とする．すなわち，任意の 1 <= k に対して，tail(sel(ri )) == i <tail(sel(r))，prop(ri ) = prop(r)，かつ，(a) pri(sel(ri )) >pri(sel(r)) ま た は (b) pri(sel(ri ))= pri(sel(r)) か つ
indexR (ri ) > indexR (r) が成り立つ．1 <= k に対して，= i <sel(ri ) を正規表現 re(sel(ri )) に変換する（ri の CSS 規則オー
トマトン Mri を構成する）．
（ 6 ） 以下が成り立つか否かを判定する

L(MD ) ∩ L(Mr ) ⊆ L(MD ) ∩∪L(Mri )1<=i<=k

図 4 DTD オートマトンの例

DTD オートマトンを形式的に定義する．D = (d, s) を Σ 上の DTD とする．Σv = {av | a ∈ Σ} かつ Σh = {ah | a ∈ Σ}と定義する．ここで，Σv と Σh は，それぞれ縦ラベルと横ラベ
ルと呼ばれる．正規表現 d(a) に対して，d(a) に出現する各ラ
ベル b を対応する横ラベル bh に置き換えたものを dh (a) と表

上記の式が成立するならば，パターン 3 にて r は充足不能と判す．Mh (a) = (Qa , Σh , δa , q0a , Fa ) を，dh (a) のオートマトン，

定する（以降簡単のためこの判定を優先度あり要素間関係判定

r を CSS 規則とする．このとき，r に関する D の DTD オーと呼ぶ）．

トマトンを次に示す M として定義する．

M = (Q, Σh ∪ Σv , δ, q0 , F )
ここで，

•
Q=

3. 4 CSS 規則オートマトンの構成

Q，δ ，F は次のように定義される．

まず，Q は次のように定義される．

∪

Qa ∪ {q0 , qs }sel = s1 c1 s2 …cn−1 sn をセレクタとする．sel を表す正規表
現 re(sel) を，re(sel) = c′0 s′1 c′1 s′2 …c′n−1 s′n と定義する．ここ
で，0 <
=i<
= n に対してa∈Σ

ここで，Qa は Mh (a) の状態集合，q0 は初期状態，qs は開始
ラベル s を表す状態である．

•

δ は，各ラベル a の δa（Mh (a) の遷移関数）と δv をマー

c′i =ジすることにより得られる．δa は横方向の状態遷移つまり兄弟関係を表し，δv は縦方向の状態遷移つまり親子関係を表す．ここで，δv は次のように定義される．a ∈ Σ をラベル，b を d(a)s′i =

直観的には，q ∈ Qa (bh ) は dh (a) における「b の状態」を表す．次に，δv (q, cv ) は，c が d(b) に出現する場合に，任意のq ∈ Qa (bh ) が cv により Qb (ch ) に属する状態に遷移するように定義される（図 5）．すなわち，Qs (ch ) Qb (ch )δv (q, cv ) =









•

ci−1 ∈ { ＞, ＋ } のとき(si )v|a∈Σ av(si )h|a∈Σ ahsi ∈ Σ，かつ，
i = 1 または ci−1 ∈ { , ＞ } のとき
si = ‘ ∗ ’ かつ ci−1 ∈ { , ＞ } のときsi ∈ Σかつ ci−1 ∈ { ＋, ∼} のとき
si = ‘ ∗ ’ かつ ci−1 ∈ { ＋, ∼} のとき

例えば，sel = a ∼ b ＞ c のとき，re(sel) = (Σv )∗ av (Σh )∗ bh cv
である．

ある a ∈ Σ，d(a) に出現する b，および d(b) に出現する c に対して，

q ∈ Qa (bh ) のとき
∅


{qs }





δa (q, c)δv (q, c)








∅

ci−1 = ‘ ∼ ’ のとき

q = qs かつ c が d(s) に出現するとき

それ以外のときδ は，δa と δv を用いて次のように定義される．

δ(q, c) =(a) i = 0，または，(b) i >
= 1 かつ ci−1 = ‘ ’ のとき

かつ，1 <=i<= n に対して属する状態のうち，bh で到達するものの集合を Qa (bh ) と表す．

Qa (bh ) = {q ∈ Qa | q ∈ δa (q ′ , bh ), q ′ ∈ Qa }(Σh )∗
ϵに出現するラベル，c を d(b) に出現するラベルとする．Qa にすなわち，(Σv )∗

q = q0 かつ c = sv のときある a ∈ Σとある c ∈ Σh に対して，

q ∈ Qa のときある a ∈ Σとある c ∈ Σv に対して，

q ∈ Qa のとき
それ以外のときF は，r に出現する末尾の結合子と末尾の単純セレクタ

図 6 re(sel) = (Σv )∗ av (Σh )∗ bh cv のオートマトン Mr （CSS 規則
オートマトン）

また，正規表現 re(sel) はオートマトン Mr に変換可能である（本稿では変換アルゴリズムについては省略する）．図 6 にre(sel) = (Σv )∗ av (Σh )∗ bh cv のオートマトン Mr （CSS 規則
オートマトン）を示す．

3. 5 優先度無し要素間関係判定

により定義される．r = s1 c1 s2 …cn−1 sn p : v とする．F はD の DTD オートマトン MD と CSS 規則オートマトン Mrsel(r) の末尾の結合子 cn−1 と末尾の単純セレクタ sn で到達可との積オートマトンを求め，その空性判定を行うことで，sel(r)能な状態の集合である．すなわち，で記述される要素間関係が DTD の要素間関係に適合してい

{ ∪
F =

q ′ ∈Q∪q ′ ∈Qδ(q ′ , (sn )v )cn−1 ∈ { , ＞ } のとき

δ(q ′ , (sn )h )cn−1 ∈ { ＋, ∼} のとき

図 4 において，もし r = a c p : v ならば，F = {q2b } である．

るかを調べること（優先度無し要素間関係判定）ができる．

L(MD ) ∩ L(Mr ) = ∅ が成り立つならば，r は D の下で充足不能となる．
また，次の 3.6 節の優先度あり要素間関係判定は計算困難であるのに対し，一方優先度無し要素間関係判定は多項式時間で計算可能である [11]．本稿では，優先度あり要素間関係判定の前に優先度無し要素間関係判定を行い充足不能な規則を検出する．ここで規則が充足不能と判定されれば，以降の優先度あり
要素間関係判定を行う必要がなく，これにより優先度あり要素
間関係判定の回数を減らすことができる．

図 5 Qa (bh ) に属する状態から Qb (ch ) に属する状態への遷移

3. 6 優先度あり要素間関係判定
r1 , r2 , …, rk ∈ R を，r と衝突し得る CSS 規則とする．すな
わち，任意の 1 <=i<= k に対して，tail(sel(ri )) = tail(sel(r))，

prop(ri ) = prop(r)，かつ，(a) pri(sel(ri )) > pri(sel(r)) または (b) pri(sel(ri )) = pri(sel(r)) かつ indexR (ri ) > indexR (r)が成り立つ．1 <=i<= k に対して，sel(ri ) を正規表現 re(sel(ri ))に変換する（ri の CSS 規則オートマトン Mri を構成する）．
以下が成り立つか否かを判定する

L(MD ) ∩ L(Mr ) ⊆ L(MD ) ∩∪L(Mri )

1<=i<=k

上記の式が成立するならば，r は充足不能と判定する．また，L(MD ) ∩ L(Mr ) ⊆ L(MD ) ∩か 否 か は ，MR =∪∪L(Mri ) が成り立つ

1<
=k
=i<

Mri を 任 意 の 1 <= i <= k に対し

1<
= i<
=k

ての Mri の和オートマトンとし，MR を MR の補集合オー
トマトンとするとき L(MD ) ∩ L(Mr ) ∩ L(MR ) = ∅ が成り

図8

r が充足不能と判定されない場合の集合関係

立つか否かと同じである．この式が成立するならば，r は充足不能である．この判定を直観的に表した集合関係図を示す．図 7 は L(MD ) ∩ L(Mr ) ∩ L(MR ) = ∅ が成り立ち rが充足不能と判定される場合の集合関係図であり，図 8 はL(MD ) ∩ L(Mr ) ∩ L(MR ) = ∅ が成り立たず r が充足不能と工学類 | 筑波大学 理工学群の Web サイト 2 の CSS と食べロ
グの Web サイト 3 の CSS を用いる．
まず，社会工学類 | 筑波大学 理工学群の Web サイトの CSS
での提案アルゴリズムの評価について述べる．以降，D を DTD

判定されない場合の集合関係図である．また，ここまで述べた（XHTML-1.0-Transitional），C1 を社会工学類 | 筑波大学 理

属性判定，優先度無し要素間関係判定，優先度あり要素間関係

工学群の Web サイトの CSS（実験では CSS の一部を利用）と判定すべてで充足不能とならない場合は，r は充足可能と判定する．C1 に属性判定で充足不能と判定される CSS 規則や結合する．

子 ‘＋’，および，‘∼’ を含むセレクタを持つ CSS 規則が存在しなかったため，筆者がそれらの CSS 規則を C1 に追加した．また，図 9 は C1 についてプロパティごとに CSS 規則を収集した表記である．これを C1p とする．C1p では ‘∗’ の連続でプロパ
ティごとに CSS 規則が区分されている．また，先頭にプロパ
ティ，後ろにそのプロパティを持つ CSS 規則集合が記述されている．表 1 は C1p で各充足不能性判定パターン（属性判定，優先度無し要素間関係判定，優先度あり要素間関係判定）で検出された充足不能な CSS 規則の数と充足可能判定された CSS 規
則の数の結果である（簡単のため以降，属性判定をパターン 1，
優先度無し要素間関係判定をパターン 2，優先度あり要素間判
定をパターン 3 とする）．
表1
図 7 r が充足不能と判定される場合の集合関係

4 評価実験

実験 1 の充足不能性判定の結果

パターン 1 パターン 2 パターン 3

2

1

9

充足可能

計

32

44

また，実験では DTD と CSS に詳しい筑波大学大学院博士前期課程の院生 2 人の実験協力者に充足不能性判定を行っても本章では，提案アルゴリズムに関する評価実験の結果について述べる．評価実験の環境は以下の通りである．

らった．実験は以下のように行われた．
（ 1 ） 事前に DTD，CSS，パターン 1，パターン 2，パター•

CPU: Intel Xeon E5-2623 v3 3.0Ghz CPU

ン 3 の定義や関連する例を実験協力者に説明した．

•

メモリ: 16GB RAM（ 2 ） DTD とプロパティごとに CSS 規則を収集した表記の•OS: Linux CentOs 7 64bit

CSS スクリプトを実験協力者に提示し，手動で各充足不能性判•

使用言語: Ruby 2.4.1

定パターンを順に検証してもらった．

また，評価実験では W3C が公開している DTD（XHTML-1.0-

表 2 はその結果である．提案アルゴリズムの実行時間は 20.38

Transitional） 1 を用いる．CSS にはこの DTD を用いている分であった．表の各セルは実験協力者によって正しく判定されWeb サイトで使用されている CSS を用いる．本稿では，社会
2：https://www.sk.tsukuba.ac.jp/College
1：https://www.w3.org/TR/xhtml1/

3：http://m.tabelog.com/

要素を持たないため，この CSS 規則は提案アルゴリズムにより充足不能と判定された．またパターン 3 にて，提案アルゴリズ
ムで検出した 9 つの充足不能な CSS 規則について，実験協力
者 1 は 9 つの充足不能な CSS 規則のうち 7 つを検出した．一方，実験協力者 2 は 9 つの充足不能な CSS 規則のうち 5 つを検出した．提案アルゴリズムによりパターン 3 で検出された充足不能な CSS 規則には，例えばプロパティtext-decoration を持つ dl.footer navi dd ul li a がある．まず dl#news dd a または ul.footer link li a の規則集合とプロパティtext-decorationの衝突が発生している．次にどの要素 a も要素 dl を親としてもち，よってどの要素 a に対しても dl#news dd a または

ul.footer link li a の CSS 規則が適用されるため，dl.footer navi
dd ul li a は提案アルゴリズムにより充足不能と判定された．言い換えると，dl.footer navi dd ul li a の優先度より優先度の高い規則集合の適用要素の集合に，dl.footer navi dd ul li a の適用要素の集合が包含されているため，dl.footer navi dd ul li a
は提案アルゴリズムにより充足不能と判定された．なお実験協力者による充足不能性判定には少々誤りがあったが，これらの誤りは実験協力者のケアレスミスによるものである．
次に，食べログの Web サイトの CSS での同様の提案アルゴ
リズムの評価について述べる．以降，C2 を食べログの Web サ
イトの CSS（実験では CSS の一部を利用）とする．C2 に属性判定で充足不能と判定される CSS 規則や結合子 ‘＋’，および，‘∼’ を含むセレクタを持つ CSS 規則が存在しなかったため，筆者がそれらの CSS 規則を C2 に追加した．また，C2p は図9 と同様に表記される．なお，C2p には “#headline a:hover”
や “#breadcrumb-wrap #location a:hover” などの擬似クラス “hover” を持つ CSS 規則が含まれるが，本稿では擬似クラスは考慮しない（ただし実験では優先度の計算に疑似クラスも含めた．なお擬似クラス 1 つにつき優先度は 10 である．
）．表

3 は C2p で各充足不能性判定パターン（属性判定，優先度無し
要素間関係判定，優先度あり要素間関係判定）で検出された充足不能な CSS 規則の数と充足可能判定された CSS 規則の数の
図 9 プロパティごとに CSS 規則を収集した表記 C1p

結果である．
また，実験では DTD と CSS に詳しい筑波大学大学院博士

た CSS 規則の割合である．充足不能性判定に各実験協力者平

前期課程の院生 2 人の実験協力者に充足不能性判定を行っても均約 46.79 分かかった．

らった．実験は前の実験と同様に行われた．

パターン 1 にて，提案アルゴリズムで検出した 2 つの充足

表 4 はその結果である．前の実験と同様の実験環境下で提案不能な CSS 規則について，実験協力者 1 は 2 つの充足不能なアルゴリズムの実行時間は 35.89 分であった．この実験では，

CSS 規則すべてを検出した．一方，実験協力者 2 は 2 つの充

前の実験より実行時間が長かった．その理由として，この実験

足不能な CSS 規則のうち 1 つを検出した．提案アルゴリズム

では前の実験よりパターン 3 の実行回数が多かったことが考によりパターン 1 で検出された充足不能な CSS 規則には，例えられる．表の各セルは実験協力者によって正しく判定された

えばプロパティfont-size を持つ p[type=“submit”] input があCSS 規則の割合である．充足不能性判定に各実験協力者平均約る．DTD では p 要素は type 属性を持たないため，この CSS

60.76 分かかった．

規則は提案アルゴリズムにより充足不能と判定された．またパパターン 1 にて，提案アルゴリズムで検出した 2 つの充足不ターン 2 にて，提案アルゴリズムで検出した 1 つの充足不能な能な CSS 規則について，両実験協力者は 2 つの充足不能な CSS

CSS 規則について，両実験協力者はこの充足不能な CSS 規則

規則のうち 1 つを検出した．提案アルゴリズムによりパターンを検出した．提案アルゴリズムによりパターン 2 で検出された

1 で検出された充足不能な CSS 規則には，例えばプロパティ

充足不能な CSS 規則には，例えばプロパティfont-size を持つ

padding を持つ script.search-box がある．DTD では script 要∗ html p#search box input がある．DTD では html 要素は親素は class 属性を持たないため，この CSS 規則は提案アルゴリ

表2
実験協力者

充足可能

計

1

2/2

1/1

7/9

32/32

42/44（95%）

2

1/2

1/1

5/9

31/32

38/44（86%）

表3
実験協力者

表4
パターン 1

2

実験 1 の結果

パターン 1 パターン 2 パターン 3

実験 2 の結果

パターン 1 パターン 2 パターン 3

充足可能

計

1

1/2

1/1

16/16

19/20

37/39（95%）

2

1/2

1/1

15/16

16/20

33/39（85%）

文

実験 2 の充足不能性判定の結果
パターン 2 パターン 3

1

16

充足可能

計

20

39

ズムにより充足不能と判定された．またパターン 2 にて，提案
アルゴリズムで検出した 1 つの充足不能な CSS 規則について，両実験協力者はこの充足不能な CSS 規則を検出した．提案ア
ルゴリズムによりパターン 2 で検出された充足不能な CSS 規
則には，例えばプロパティmargin を持つ li ＋ p がある．DTD
では p 要素は li 要素を隣接する兄として持たないため，このCSS 規則は提案アルゴリズムにより充足不能と判定された．またパターン 3 にて，提案アルゴリズムで検出した 16 つの充足不能な CSS 規則について，実験協力者 1 はこれらすべての充足不能な CSS 規則を検出した．一方，実験協力者 2 は 16 つの充足不能な CSS 規則のうち 15 つを検出した（提案アルゴリズ
ムによりパターン 3 で検出された充足不能な CSS 規則の例は省略する）．なお実験協力者による充足不能性判定には少々誤りがあったが，これらの誤りは実験協力者のケアレスミスによるものである．
これらの実験において，実験協力者は特に優先度無し要素間
関係判定・優先度あり要素間関係判定に時間がかかり大変だったと感じていた．このことから，手動での充足不能性判定はCSS を整備する上で大きな負担となることが分かる．また，これらの実験において手動での充足不能性判定より提案アルゴ
リズムを用いた充足不能性判定の方が実行時間を抑えられた．
よって，これらの結果から提案アルゴリズムは CSS 規則の充足不能性判定を行うのに役立つと考えられる．

5 む す び
本稿では，まず，オートマトン理論に基づいて，充足不能なCSS 規則を検出するアルゴリズムを考案した．次に，提案アルゴリズムに関する評価実験を行った．評価実験では，提案アルゴリズムと人手による充足不能な CSS 規則の検出結果を比較
し，CSS の整備に関して提案アルゴリズムの有用性を示唆する結果を得た．今後の課題として，まず，本稿で扱っていない

CSS 規則，例えば，“first-child” や “last-child” などの擬似クラスを用いたセレクタについて考察することを考えている．次に，より多くの DTD や CSS を使用した評価実験を行いたいと考えている．さらに，プロパティの継承への対応や DTD 以
外のスキーマ言語への対応なども今後の課題となる．

献[1] N. Walsh, “DocBookCssStylesheets.” https://github.com/
docbook/wiki/wiki/DocBookCssStylesheets/.
[2] B. Bos, D. Carlisle, P.D.F. Ion, B.R. Miller, and eds., “AMathML for CSS profile,.” https://www.w3.org/TR/mathmlfor-css/.
[3] P. Geneves, N. Layaida, and V. Quint, “On the analysis
of cascading style sheets,” Proceedings of the 21st International Conference on World Wide Web, pp.809-818, 2012.
[4] M. Bosch, P. Geneves, and N. Layaida, “Automated refactoring for size reduction of CSS style sheets,” Proceedingsof the 2014 ACN Symposium on Document Engineering,pp.13-16, 2014.
[5] D. Mazinanian, N. Tsantalis, and A. Mesbah, “Discovering
refactoring opportunities in cascading style sheets,” Proceedings of the 22Nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp.496-506,
2014.
[6] D. Mazinanian, N. Tsantalis, “Migrating cascading style
sheets to preprocessors by introducing mixins,” Proceedings of the 31st IEEE/ACM International Conference on
Automated Software Engineering, pp.672-683, 2016.
[7] Firebug Working Group, “FireBug.”
https://www.getfirebug.com/.
[8] Google Inc., “Chrome developer tools,”
https://developers.google.com/web/tools/chrome-devtools/.
[9] M. Hague, A.W. Lin, and C.H.L. Ong, “Detecting redundant CSS rules in HTML5 applications: A tree rewriting approach,” SIGPLAN Not., vol.50, no.10, pp.1-19, Oct. 2015.
[10] A.Mesbah, and S.Mirshokraie, “Automated analysis of CSS
rules to support style maintenance,” Proceedings of the 34th
International Conference on Software Engineering, pp.408418, 2012.
[11] 鈴木 伸崇，岡田 拓也，權 娟大．“CSS 規則充足不能性問題の計算複雑さ”．データ工学と情報マネジメントにおけるフォーラ
ム，2018．