DEIM Forum 2013 A1-4

正規木文法を用いた XPath 式修正候補発見アルゴリズム
池田光雪†

鈴木 伸祟 ††

† 筑波大学大学院 図書館情報メディア研究科 〒 305–8550 茨城県つくば市春日 1–2†† 筑波大学 図書館情報メディア系 〒 305–8550 茨城県つくば市春日 1–2
E-mail: †{lumely,nsuzuki}@slis.tsukuba.ac.jp
あらまし

スキーマが存在する状況において，XPath 式を用いて問合せを行う場合を考える．近年，XML はますま

す巨大・複雑化しており，ユーザがその構造を把握すること，さらには XPath 式を記述・修正することは必ずしも容易でない．これまで筆者らは DTD が存在する状況において XPath 式間の編集距離を定義し，K 最短経路問題に帰着させるという手法で入力 XPath 式に構文的に類似し，かつ DTD に対して妥当な K 個の XPath 式を出力する手法を提案してきた．本稿では，スキーマとして正木木文法を用いた XPath 式修正候補発見アルゴリズムを提案する．
キーワード

XML, XPath, 正木木文法

1. は じ め にう XPath 式を記述した場合を考える．本アルゴリズムを用いれば，以下のようにこの XPath 式に類似した妥当な式の列挙

スキーマの規則を満たす（妥当な）XML 文書に対し XPathが得られる (K = 3 の場合の例). 右端の数値は，要素名を置換式を記述する場合を考える．このとき，ユーザが対象となるする際の重みを文字列間の正規化編集距離の値 [15] とし，それXML の構造をよく理解していない場合，スキーマに関して妥
当な，すなわち何らかの解が得られるであろう XPath 式を記述

以外の編集操作の重みを 1 とした場合の編集距離を表している．
1. //person[@id = "2013"]/name(0.75)

することは必ずしも容易でない．とりわけ，近年において XML

2. //people/person[@id = "2013"]/name(1.75)

やスキーマはますます巨大化・複雑化してきており，その構造

3. /site/people/person[@id = "2013"]/name(2.25)

を理解することはより困難になってきている．さらに，スキー

このように naem というタイプミスが修正された上で，その要

マ進化によって XML やスキーマの構造が変化し，元々スキー

素を検索する妥当な XPath 式が入力式に近いものから得られマに対し妥当であった XPath 式が妥当でなくなる場合がある．

る．なお，各編集操作に付加するコストは自由に変更すること

また，XML のキーワード検索ではユーザはそれらの構造を意ができる．例えば，「/より//の使用を優先してより簡潔な式を識すること無く問合せを行うことが可能であるが，XPath に比優先的に列挙する」，「//より/の使用を優先し，途中の経路をべ詳細な検索を行うことは難しい．そこで，スキーマに関して

詳細に指定した式を優先的に列挙する」等の調整が可能である．

妥当でない XPath 式 p に対し，スキーマに関して妥当かつ p

本稿では，DTD のみに対応していた既存アルゴリズムを正との類似性が高い XPath 式をユーザに提示できれば XPath 式

木木文法まで対応可能なように拡張したアルゴリズムを提案す

記述の支援に有用であると考えられる．

る．XML と併用される代表的なスキーマ言語である RELAX

これまで著者らはこの問題に対し，ユーザが真に欲しい

NG, W3C XML Schema, DTD は正規木文法で表現可能なこ

XPath 式はユーザが記述した式 p に構造や要素名などが似てとが知られている [13] ため，本拡張により上記三つのスキーマいるという仮定のもと，スキーマが DTD D の場合に XPath

言語全てにアルゴリズムが対応可能となる．具体的には，まず式間の編集距離を定義し D と p を合成した XD グラフを作成

入力スキーマを正規木文法 G = (N, T, S, P ) と考え，G からして，その上で K 最短経路問題を解くという手法で p に構文要素間の構造を表すグラフ G(P ) を構築する．さらに，XPath

的に類似し，かつ D に対して妥当な K 個の XPath 式を出力

式 p と G(P ) から XG グラフ G(p, G(P )) を作成し，その上でする手法を提案してきた [11]．

K 最短経路問題を解くことで K 個の p に類似した XPath 式

このアルゴリズムの特徴は DTD の全体構造を把握していな
くとも，目的の要素名さえある程度特定できれば妥当な XPath

を得る．

XML に対する問合せに関しては様々な研究が行われてい式が得られることである．例として次の DTD を考える．
<!ELEMENT site
(people)>る [9] が，本稿と最も関連が強いのは文献 [7] である．同文献で<!ELEMENT people (person)*>て妥当かつ p との類似度が高いものを列挙するアルゴリズムを<!ELEMENT person (name)>

提案している．本稿との主な違いは，同文献のスキーマは有向<!ELEMENT name

非循環グラフ (DAG) であり再帰を扱うのが事実上困難なこと，(#PCDATA)>

は，与えられた問合せ式 p とスキーマ D に対して，D に関し<!ATTLIST person id ID #REQUIRED>

ノード間の順序を考慮しないデータモデルとなっており，問合

ここで，ID が 2013 である person の name 要素を取得したい

せ式も無順序木として表されていること，編集距離でなく独と考えたが，誤って q = /person[@id = "2013"]/naem とい自に定義した類似度を用いている (編集操作に対するコストの変更が困難) ことである．一方本稿では，再帰を許しかつノード間の順序を前提としたデータモデルを扱い，編集操作に対するコストは任意の値に設定可能である．また DTD における再帰について，実際に使用されている DTD を対象とした調査

表 1 XP の構文定義
XP ::= “/” RelativePath
RelativePath ::= LocationStep | LocationStep “/” RelativePath
LocationStep ::= Axis “::” Label | Axis “::” Label Predicate
Axis ::= “↓” | “↓∗ ” | “→+ ” | “←+ ”が行われており，60 個の DTD のうち 35 個が再帰を含んでいLabel ::= (any label in T )Predicate ::= “[” Exp “]”た [6]．文献 [2], [16] では，ユーザへの質問を通して対話的に所

Exp ::= PredPath | PredPath Op Value

望の XQuery 式を学習し，提示するシステムを提案している．

PredPath ::= RelativePath

一方，本稿では 1 つの XPath 式から，類似した複数の正解候補

Op ::= “=” | “<” | “>” | “=<”| “=>”を出力する．また，スキーマの存在を陽に仮定しない場合におValue ::= ‘”’ (any string other than ‘”’) ‘”’

いて，XML への問合せに対する近似的な問合せ結果を列挙する手法が提案されている (文献 [4], [5] など)．これらはインスタ•

e が t の根であるとき，I(e) は初期状態である．

ンスに対する問合せを扱っており，本稿のような問合せ式の修•各ノード e とそれらの子ノード e0 , e1 , ..., em について，正候補の発見とは異なる．XHTML など，問合せの対象においG 中の遷移規則 X → ar が存在し，以下を満たす．

て使用されている要素が非常に少なく，かつ複雑に組み合わせ– I(e) = X ，られている場合，一般には本研究のようなスキーマを用いた修– e の終端記号は a，

正候補の発見手法に比べ，インスタンスを用いたこれらの手法– I(e0 )I(e1 )...I(em ) が r にマッチする．

では有用な修正候補を得ることができる．しかし，XMark [18]正木木文法 G によって受理される集合を L(G) と表す．正木が生成するインスタンスのようにスキーマで文書構造を詳しく

木文法 G が木 t を受理するとは，G に対する t の解釈が存在す

定義している場合は，本稿のような問合せ式の修正候補発見手るということである．

法でも高速かつ有用な修正候補の提示が可能である．

例えば，前章の DTD は正規木文法 G = (N, T, S, P ) と表す

さらに，XMLSpy [3] や文献 [1] で提案されているエディタな
どには，XPath 式を記述する際に要素名などを補完する機能があるが，本稿のように修正候補の列挙は行わない．XML のことができ，ここでN = {Site, P eople, P erson, N ame, P cdata}

キーワード検索に関しても多くの研究がなされている (例えばT = {site, people, person, name, pcdata}

文献 [20], [12], [17])．これらは，XML の問合せ言語に詳しくな

S = {Site}

いユーザにとって特に有用である．

P = {Site → site(P eople), P eople → people(P erson∗ ),提案アルゴリズムでは軸として child, descendant-or-self,

P erson → person(N ame), N ame → P cdata(P cdata),

following-sibling, preceding-sibling のみを許し，ノードテスト

P cdata → pcdata(ϵ)}

は要素名のみという制約を設けた XPath 式を対象としている．
これらの制約のうち，軸については parent 軸など上方向の軸である．

も対象とした方が望ましいが，実際に使用されている XPath

本稿で用いる XPath 式の集合を XP と表記する．XP は child

式のほとんどは下方向の軸のみを使用している [10] ため，有用

軸 (↓)，descendant-or-self 軸 (↓∗ )，following-sibling 軸 (→+ )，性は損なわれないと考えられる．

preceding-sibling 軸 (←+ ) のいずれかを用いた，ノードテスト
としてラベルのみを許すロケーションパスの集合であり，形式

2. 諸 定 義

的には表 1 で定義される．定義から，XP における XPath 式

正規木文法を 4 次組 G = (N, T, S, P ) と表す．ここで，N は非終端記号の有限集合，T は終端記号の有限集合，S を開始記
号，P を X → ar の形をした遷移規則の集合とする．ただし，は次のように表せる．

p = /ax[1] :: l[1][exp[1]]/ · · · /ax[m] :: l[m][exp[m]]X ∈ N, a ∈ T であり，r は N 上の正規表現である．X を規則

こ こ で ，1 <= i <= m に 対 し て ax[i] ∈ Axis，l[i] ∈ T ，の左辺，ar は右辺，a，r をそれぞれこの規則のラベル，内容

exp[i] ∈ Exp である．

モデルという．

G=(N, T, S, P ) を 正 規 木 文 法 ，p=/ax[1]::

正規木文法 G = (N, T, S, P ) とラベル a, b に対して，もし次l[1][exp[1]]/ · · · /ax[m] :: l[m][exp[m]] を XPath 式とする．pの条件のいずれか一方が成立するならば，G において a から bのロケーションステップ数を |p| と表す．もし以下の条件が成に到達可能であるという．

立するならば，p は G に関して妥当であるという．

•

′

′

a = b，または P 内に遷移規則 X → ar と X → br が′•′あるラベル a に対して，a から a に到達可能，かつ遷′′′

ax[1] = ↓ かつ S → l[1]r となるような遷移規則が P に存在，または，ax[1] = ↓∗ かつ l[1] は T 中に出現する

存在し，X が r に出現する．
′•′

移規則 X → a r と X → br が存在し，X が r に出現する．
正木木文法 G に対する木 t の解釈 I は，t 中の各ノード e から状態 I(e) への以下を満たす写像である．

•

2<
=i<
= m に対して以下が成り立つ– ax[i] = ↓ かつ遷移規則 X → l[i − 1]r と X ′ → l[i]r′ が存在し，X ′ が r に出現する– ax[i] = ↓∗ かつ G において l[i − 1] から l[i] へ到達可能

編集操作 op のコストを γ(op) と表し，このとき γ がコスト関である•

exp[i] =| ϵ の場合，右辺が l[i]r である遷移規則が P に存数である．以下，γ(op) >= 0 と仮定する．コスト関数として，定在し，XPath 式 /↓:: l[i]/exp[i] が正規木文法 (G = (N, T, r, P ))

数だけでなく関数も使用できる．例えば，op = l → l′ のとき，に関して妥当である (1 <
=i<
= m)

γ(op) を l と l′ の (文字列間の) 編集距離等に設定することが可XPath 式 p ∈ XP に対して, もし p が述語を含まない場合，
p は単純であるという.

能である．また，軸名に関しても同様の設定が可能である．編集∑
操作列 sc = op1 op2 · · · opn のコストを γ(sc) = 1<i<n γ(opi )= =と定義する．正木木文法 G，XPath 式 p，正整数 K に対して，

3. XPath 式に対する編集操作

G の下での p に対する K 最適編集操作列とは，以下のすべて

本章では，XPath 式に対する編集操作を定義する．XPathの条件を満たす編集操作列の系列 sc1 , · · · , scK である．

•

sc1 (p), · · · , scK (p) はすべて G に関して妥当である

軸の置換：軸 ax を ax′ に置換する．ax → ax′ と表す．

•

γ(sc1 ) <= ··· <= γ(scK )例えば，/ ↓:: a に更新操作 ↓ → ↓∗ を適用すると / ↓∗ :: a を得る．

•

sc1 , · · · , scK は最適，すなわち，p に対する任意の編集式に対する編集操作は以下の 4 種類である．

•
•

′

′

ラベルの置換：ラベル l を l に置換する．l → l と表す．

例えば，/ ↓:: a に更新操作 a → b を適用すると / ↓:: b を得る．

•

ロケーションステップの追加：ロケーションステップ

操作列 sc に対して以下が成り立つ– も し sc(p) が G に 関 し て 妥 当 な ら ば ，sc(p) ∈{sc1 (p), · · · , scK (p)} または γ(sc) >= γ(scK )ax :: l を追加する．ϵ → ax :: l と表す．例えば，/ ↓:: a の末尾

sc1 (p), · · · , scK (p) を G の下での p に対する K 最適修正候補に更新操作 ϵ →↓:: b を適用すると / ↓:: a/ ↓:: b を得る．

という．

•

ロケーションステップの削除：ロケーションステップ

ax :: l を削除する．ax → ϵ と表す．例えば，/ ↓:: a/ ↓:: b の最初のロケーションステップに更新操作 / ↓:: a → ϵ を適用すると/ ↓:: b を得る．
•

4. XPath 式修正候補発見問題の NP 困難性
XPath 式 の 修 正 候 補 発 見 問 題 を ，正 規 木 文 法 G =(N, T, S, P )，XPath 式 p，および正整数 K が与えられた時

ロケーションステップの交換：隣接する 2 つのロケーショに，p がコスト K 以下の修正候補をもつか否かを決定する問題

ンステップを入れ替える．ax :: l/ax′ :: l′ → ax′ :: l′ /ax :: l とと定義する．この問題が NP 困難であることを示す．

表す．例えば，/ ↓:: a/ ↓:: b に対し更新操作 ↓:: a/ ↓:: b →↓::

［定理 1］ ロケーションパスの交換を許した場合，XPath 式のb/ ↓:: a を適用すると / ↓:: b/ ↓:: a を得る．

修正候補発見問題は NP 困難である．

ロ ケ ー ション ス テップ ls の 位 置 を pos(ls) と 表 し ，次 の証明： XPath 式の修正候補発見問題が NP 困難であることを，よ う に 定 義 す る ．q = /ax[1] :: l[1][exp[1]]/ · · · /ax[m] ::有向ハミルトン経路問題から XPath 式の修正候補発見問題へ

l[m][exp[m]] ∈ XP を XPath 式とする．まず，pos(ax[i] ::l[i]) = i (1 <= i <= m) と 定 義 す る ．述 語 に お け る ロの帰着により示す．有向ハミルトン経路問題とは以下のようなケ ー ション ス テップ の 位 置 に つ い て ，exp[j] = ax′ [1] ::入力:

有向グラフ H = (V, E) および頂点 u, v ∈ V ．

′

問題:

H が u から v に至る有向ハミルトン経路 (V のすべて

′

′

′

′

l [1][exp [1]]/ · · · /ax [n] :: l [n][exp [n]] と す る ．こ の と き ，′pos(ax′ [k] :: l′ [k]) = j.k (1 <= k <= n) と定義する．exp [h]問題である．

の点をちょうど 1 つづつ通る経路) を含むか否か決定せよ．

における位置も同様に定義できる．例えば，q = / ↓:: a/ ↓::有 向 ハ ミ ル ト ン 経 路 問 題 の イ ン ス タ ン ス ，有 向 グ ラ フb[↓:: f [↓:: g]]/ → :: c を考える．このとき，pos(↓:: b) = 2，

H = (V, E) および頂点 u, v ∈ V に対して，XPath 式修正+

pos(↓:: f ) = 2.1，pos(↓:: g) = 2.1.1 である．位置 pos のロケー

候補発見問題のインスタンス，正規木文法 G = (N, T, S, P )，ションステップに適用する編集操作 op を [op]pos と表す．もしXPath 式 p，および正整数 K を次のようにして構成する．まop がロケーションステップ ls の追加である場合，[op]pos は ls

ず，G = (N, T, S, P ) は次のように定義される．

を pos に位置するロケーションステップの直後に追加する．

XPath 式 p に対し，位置をもつ編集操作の系列を編集操作

N = {V1 , V2 , · · · , Vk } ∪ {D}列と呼ぶ．編集操作列 sc を p に適用して得られる XPath 式を

T = {v1 , v2 , · · · , vk } ∪ {d}sc(p) と表す．例えば，sc = [ϵ → ↓:: b]1 [c → f ]3 ，p = / ↓∗ ::S = {Vj | u = vj }∗a/ ↓:: d/ ↓:: c の場合，sc(p) = / ↓ :: a/ ↓:: b/ ↓:: d/ ↓:: f である．
本稿では以下の仮定を置く．A1 = {↓, ↓∗ }，A2 = {→+ , ←+ }とする．

•

同種の軸への置換のみ許す．ax ∈ A1 は A1 に属する軸へのみ置換可能とする．A2 に関しても同様である．

•

軸が A1 に属するロケーションステップのみ追加可能とする．
編集操作に対してコストを付与する関数をコスト関数という．

P = {Vi → vi (Vj ) | vi → vj ∈ E} ∪{Vh → vh (D) | vh ∈ V } ∪ {D → d(ϵ)}
次に，XPath 式 p を次のように定義する．

p = /v1 /v2 / · · · /vk /d
また，編集操作のコストについて，ロケーションステップの交換操作のコストを 1，それ以外のコストを ∞ とする．また，

K = k(k + 1)/2 とする．

以下， H が u から v への有向ハミルトン経路をもつことと，(S, s)

p がコスト K 以下の修正候補をもつことが同値であることを示す．

(A, a)(B, b)から p′ へ k(k + 1)/2 回以下のロケーションステップの交換で(C, c)(D, d)

修正可能である．したがって，p はコスト k(k + 1)/2 以下の修

図1

遷移規則グラフ(⇒) H が u から v への有向ハミルトン経路 u = vi1 →vi2 → · · · → vik = v をもつとする．G の定義から，XPath 式
p′ = /vi1 /vi2 / · · · /vik /d は G に関して妥当である．更に，p

正候補 p′ をもつ．

(⇐) H が u から v への有向ハミルトン経路をもたないとす

P = {S → s(A, B), A → a(C, D), B → b(D)る．このとき，H における u から v への長さ k の任意の経路

C → c(P cdata), D → d(B|P cdata),

は，ある頂点を 2 個以上含む．このことと G の定義から，p をP cdata → pcdata(ϵ)}

妥当な XPath 式に修正する場合，必ずロケーションステップの削除および追加が必要となり，その修正コストは ∞ となる．
したがって，p がコスト k 以下の修正候補をもつことはない．

であるとき，G の遷移規則グラフは図 1 になる．

5. 2 XG グラフ

以上の結果から，ロケーションステップの交換を許した場合，XPath 式 p と遷移規則グラフ G(P ) から XG グラフを構成

K = 1 の場合でも修正候補発見問題を効率よく解くのは困難

する．直観的には，XG グラフにおける各辺は 3. で定義した編である．以下，ロケーションステップの交換を用いない場合に，集操作に対応している．そのため，扱う軸ごとに異なる辺が存在する．以下，まず 5. 2. 1 で下記 (1) の場合の XG グラフに

修正候補発見問題を効率よく解くアルゴリズムを考える．

ついて説明を行う（紙面の都合上 (2) と (3) は省略する）．次5. XG グラフに，5. 2. 2 で XG グラフの形式的定義を示し，辺に対するコス

提案アルゴリズムの中心をなす XG グラフの構成法について

トの付与の仕方について述べる．

述べる．本章では，XPath 式は単純であると仮定する．一般の(1) ↓ 軸のみを用いる場合

場合については 6. 2 にて考察する．

(2) ↓ 軸と ↓∗ 軸を用いる場合

本稿では，G = (N, T, S, P ) の下での p に対する K 最適編(3) →+ 軸と ←+ 軸を用いる場合
5. 2. 1 ↓ 軸のみを用いた XG グラフ

集操作列を次のようにして求める．
（ 1 ） G の生成規則 P から遷移規則グラフ G(P ) を構成する．

まず，XPath 式 p = / ↓:: a/ ↓:: d と図 1 の生成規則グラフ（ 2 ） p と G(P ) から，XG グラフ G(p, G(P )) を構成する．

G(P ) に対して，どのような XG グラフが構成されるのかを述これは S に関して妥当な，p に編集操作列を適用して得られる

べる．軸は ↓ のみを用いるので，編集操作としてロケーション

XPath 式を表すすべての経路から構成される．

ステップの削除・追加, ラベルの置換のみを考えればよい．p と（ 3 ） G(p, G(P )) 上で K 最短経路問題を解く．その結果がG(P ) の合成グラフ G(p, G(P )) を図 2 に示す．この図に示す

G の下での p に対する K 最適編集操作列を表す．この詳細はように，XG グラフは G(P ) を |p| + 1 個並べてそれらのノード

6. で述べる．

を辺で接続したものである．ただし，(N, n)0 , (N, n)1 , (N, n)2

5. 1 遷移規則グラフは新たに追加したノードであり，XPath のデータモデルにおXG グラフを構成するには，正木木文法の生成規則をグラフ

けるルートノードに対応する．遷移規則グラフのノードに添字として表す必要がある．そこで，まず遷移規則グラフを定義すを付加してノードを区別する．例えば，G(P ) におけるノード

る．G = (N, T, S, P ) を正木木文法とする．このとき，遷移規(S, s) は，G(p, G(P )) の一番上の遷移規則グラフでは (S, s)0 ，則グラフ G(P ) = (V, E) は次のように定義される有向グラフでその下の遷移規則グラフでは (S, s)1 と表記される．

ある．

図 2 に示すように，遷移規則グラフのノード間に追加される辺は以下の 3 種である．

V = {(X, a) | X → ar ∈ P }•

E = {(X, a) → (X ′ , a′ ) | X → ar ∈ P ,
′

′

•
′

X が r に出現，X =| Pcdata，ある a ∈ T とN 上の正規表現 r′ に対して X ′ → a′ r′ ∈ P }•→ : ロケーションステップの追加 (ϵ →↓:: l) に対応≻: ロケーションステップの削除 (↓:: l → ϵ) に対応

99K: ラベルの置換 (l → l′ ) に対応

直感的には，右方向の辺はロケーションステップの追加，下方向の辺はロケーションステップの削除，斜め方向の辺はラベル

例えば，正木木文法 G = (N, T, S, P ) において，

N = {S, A, B, C, D, P cdata}
T = {s, a, b, c, d, pcdata}
S = {S}の置換をそれぞれ表している．これら 3 種の辺についてより具体的に説明する．まず，図 2 の辺 (N, n)0 → (S, s)0 について考える．この辺は「ルートノードから子ノード s へ，p のロケー
ションステップを用いずに移動する」ことを表している．この
移動は子ノード s への移動であり，(p には元々存在しない) ロ

(N, n)0(A, a)0(C, c)0(B, b)0(D, d)0

次のように定義される有向グラフである ((N, n)0 , · · · , (N, n)mのnはn∈/ V なるラベルとする)．

(S, s)0

遷移規則グラフ↓::a(A, a)1(N, n)1(C, c)1

V ′ = {(N, n)0 , · · · , (N, n)m } ∪ V0 ∪ · · · ∪ Vm
E ′ = Einsc ∪ (F1 ∪ · · · ∪ Fm )(1)

式 (1) の Einsc は ↓:: l の追加を表す辺 (図 2 の “ϵ →↓:: l” の(S, s)1(B, b)1(D, d)1(A, a)2(C, c)2(B, b)2(D, d)2↓::d辺に該当) であり，次のように定義される．下記のうち，Ei はGi (P ) の辺である．
(N, n)2(S, s)2

図 2 XG グラフ G(p, G(P ))Einsc = {(N, n)0 → (S, s)0 , · · · , (N, n)m → (S, s)m } ∪(E0 ∪ · · · ∪ Em )また，式 (1) の Fi (1 <=i<= m) は，Gi−1 (P ) と Gi (P ) の間に張られる辺であり，p の i 番目の軸 ax[i] の種類に応じて定義

ケーションステップ ↓:: s によって行われるとみなす．したがって，辺 (N, n)0 → (S, s)0 は新たなロケーションステップ ↓:: sの追加，すなわち編集操作 [ϵ → ↓:: s]0 を表す．
次に，図 2 の辺 (S, s)0 99K (B, b)1 について考える．この辺が異なる．本稿では簡単のため ax[i] ∈ {↓} とし，Fi = Di ∪ Ciとする．ここで，Di ，Ci は次のように定義される．また，Diは図 2 の “↓:: l → ϵ” の辺，Ci は図 2 の “l → l′ ” の辺にそれぞれ対応する．

は「p のロケーションステップ ↓:: a を用いてノード s から子Di = {(N, n)i−1 → (N, n)i } ∪ {li−1 → li | l ∈ V }ノード b へ移動する」ことを表しているが，移動先ノードが b

Ci = {(N, n)i−1 → (S, s)i } ∪ {li−1 → li′ | l → l′ ∈ E}(3)であるため ↓:: a のラベルを b へ置換する必要がある．すなわ
ち，辺 (S, s)0 99K (B, b)1 は編集操作 [a → b]1 を表している．
最後に，図 2 の辺 (B, b)1≻(B, b)2 を考える．これはノード

b からノード b への移動，すなわち「p のロケーションステップ↓:: d を無視 (削除) して同じノード b に留まる」ことを表している．すなわち，辺 (B, b)1 99K (B, b)2 は編集操作 [↓:: d → ϵ]2を表す．
図 2 において，(N, n)0 を開始ノード，(D, d)2 を受理ノードという．開始ノード及び受理ノードの決定方法は 6. にて述べる．開始ノードから受理ノードへの経路は，p を修正して得られる G に関して妥当な XPath 式を表す．例えば，図 2 における p′ = (N, n)0 → (S, s)0 99K (A, a)1 99K (D, d)2 という経路を考える．上記の経路のうち，最初の辺 (N, n)0 → (S, s)0 はロケーションステップ ↓:: s の追加 [ϵ →↓:: s]0 を表す．次の辺(S, s)0 99K (A, a)1 は，↓:: a におけるラベルの置換 [a → a]1 を表すが，同一ラベルへの置換でありロケーションステップは変化しない．同様に，最後の辺 (A, a)1 99K (D, d)2 においても pのロケーションステップ ↓:: d はそのままである．したがって，

p′ は XPath 式 / ↓:: s/ ↓:: a/ ↓:: d を表しており，これは G に関して妥当である．

5. 2. 2 XG グラフの形式的定義と辺に付与されるコスト
前節で示した XG グラフを形式的に定義し，その辺に付

最後に，XG グラフの各辺に付与するコストを考える．3. で定義した編集操作の種類に応じて，以下のコストが定義されているとする (実際の値は現状ユーザ等で指定するが，将来的には使用状況に応じていくつかのコスト群を提供する予定である)．

•

γ(l → l′ )：ラベル l を l′ に置換するコスト•

γ(ϵ → ax :: l)：ロケーションステップ ax :: l を追加す

るコスト

•

γ(ax :: l → ϵ)：ロケーションステップ ax :: l を削除す

るコスト
上記のコストに基づいて，XG グラフの辺 e ∈ E ′ のコスト γ(e)を次のように定義する．

•e ∈ Einssc のとき：e = li → li′ と表す．この辺は ↓:: l′の追加を表すので，γ(e) = γ(ϵ → ↓:: l′ ) と定義する．

•e ∈ Di のとき：e = li−1 → li と表す．この辺は ax[i] :: l[i]の削除を表すので，γ(e) = γ(ax[i] :: l[i] → ϵ) と定義する．

•e ∈ Ci のとき：e = li−1 → li′ と表す．この辺は ax[i] の↓ への置換と l[i] の l′ への置換を表すので，γ(e) = γ(ax[i] →↓) + γ(l[i] → l′ ) と定義する．
例として，次のコスト関数を考える．
{
0 l = l′ のとき′
γ(l → l ) =1 それ以外与されるコストを示す．ただし，軸の置換を表す辺の形式

γ(ϵ → ax :: l) = 1

定 義 ，及 び そ の コ ス ト に つ い て は 紙 面 の 都 合 上 省 略 す る ．

γ(ax :: l → ϵ) = 1

G = (N, T, S, P ) を正規木文法，G(P ) = (V, E) を遷移規
則グラフ，p = /ax[1] :: l[1]/ · · · /ax[m] :: l[m] を単純 XPath
式 と す る ．Gi (P ) = (Vi , Ei ) (0 <= i <= m) を G(P ) の 各
ノ ー ド に 添 え 字 i を 付 加 し た も の と 定 義 す る ．す な わ ち ，Vi = {(X, a)i | X → ar ∈ P } かつ Ei = {(X, a)i → (X ′ , a′ )i |X → ar ∈ P } である．XG グラフ G(p, G(P )) = (V ′ , E ′ ) は(2)

このとき，経路 (N, n)0 → (S, s)0 99K (A, a)1 99K (D, d)2 のコ
ストは γ(ϵ →↓:: s)+(γ(↓→↓)+γ(a → a))+(γ(↓→↓)+γ(d →d)) = 1 + 0 + 0 = 1 となる．

6. XPath 式に対する K 最適修正候補発見手法
本章では，正規木文法 G と XPath 式 p に対して，G の下で

の p に対する K 最適修正候補を発見するためのアルゴリズムについて述べる．まず，p が単純 XPath 式の場合について述
べ，次に一般の場合について説明する．また，グラフに対する
枝刈りについても考察する．

6. 1 単純 XPath 式に対するアルゴリズム

edges in Ai or D iedges in Ai or Ci or D i

{

..
.

G(P ) を正規規則グラフ，p = /ax[1] :: l[1]/ · · · /ax[m] :: l[m]...

edges in Ci

..
.

li

図3

{

..
.

e1
li

..
.

l’i

..
.

eK

ノード li に対する変換

を XPath 式 ，G(p, G(P )) = (V, E) を XG グ ラ フ と す る ．

(N, n)0 ∈ V を開始ノード，(X, l[m])m ∈ V を受理ノードと定める．ただし，l[m] が (タイプミス等の要因で) G(P ) に出現しないラベルであった場合，l[m] に最も類似したラベル lを持つノードを V から選択し，添字 m を付加したラベル lmをもつノードを受理ノードとする．現状，l[m] と (文字列間の)編集距離が最も小さいものを選択している．上記のコスト定義
から，p に対する K 最適修正候補を求めるには，合成グラフ

G(p, G(P )) の開始ノードから受理ノードまでの K 最短経路問
題を解き，得られた経路 p′1 , · · · , p′K が表す K 個の XPath 式を出力すればよい．次の定理が成り立つ (証明は省略する)．
［定理 2］ G = (N, T, S, P ) を正規木文法，p を XPath 式，Kl[i][exp[i]] の削除コストを γ(ax[i] :: l[i] → ϵ) + γ(exp[i] → ϵ)とする．ここで，“exp[i] → ϵ” は exp[i] における全てのロケー
ションステップを削除する編集操作列を表す (下記の 3-a 行目)．

•

exp[i] =| ϵ の 場 合 ，exp[i] の 修 正 コ ス ト も 必 要 で ある．これを求めるため，XPath 式 /l[i]/exp[i] と正規木文法

G = (N, T, l[i], P ) に対してアルゴリズムを再帰的に呼び出す．
その結果を図 3 の変換を用いて G(sp(p), G(P )) に組み込む．
ここで，再帰呼び出しで得られた K 個の編集操作列を図 3 右の K 個の辺 e1 , · · · , eK に割り当てる (下記の 3-b 行目)．

3-a 行目と 3-b 行目において，Di と Ci は式 (3) と式 (2) で定義される辺集合である．

を正整数とする．上記アルゴリズムは P の下での p に対する

K 最適修正候補を出力する．



提案アルゴリズムの時間計算量について考える．まず，正規木文法 G と XPath 式 p に対する XG グラフ G(p, G(P )) のサイズを考える．P を G に出現する遷移規則の集合とする．

G(p, G(P )) の各ノード n に対して，n を始点とする辺の数はFindKPaths(G, p, K)
入 力: 正 規 木 文 法 G = (N, T, S, P )，XPath 式 p = /ax[1] ::l[1][exp[1]]/ · · · /ax[m] :: l[m][exp[m]]，正整数 K ．
出力: D の下での p に対する K 最適編集操作列 s1 , · · · , sK ．
（ 1 ） 遷移規則グラフ G(P ) を構成する．

O(|P |) である．G(p, G(P )) のノード数は O(|p| · |P |) なので，

（ 2 ） XG グラフ G(sp(p), G(P )) を構成する．
（ 3 ） exp[i] =| ϵ なる任意の 1 <=i<= m に対して，G(sp(p), G(P ))G(p, G(P )) の辺の総数は O(|p| · |P |2 ) である．次に，この XGを次のように修正する．

グラフ上で K 最短経路問題を解くことを考える．K 最短経路

（ a ） 各辺 e ∈ Di に対して，γ(e) ← γ(e) + γ(exp[i] → ϵ) とする．

問題を解くアルゴリズムはいくつか提案されているが [8], [14]，（ b ） 各ノード li ∈ Vi に対して，次の (i) – (iii) を行う．

本稿では Dijkstra の最短経路アルゴリズムの拡張を用いるとする．そのアルゴリズムの時間計算量は O(K · |E| · log |V |)(E が辺集合，V はノード集合) である．XG グラフの辺数はi. li を図 3 に沿って変換する．
ii. FindKPaths(G′ , p′ , K) を 呼 び 出 す．こ こ で ，G′=(N, T, X, P )(X は X → ar ∈ P であるノード (X, li ) の X) かつ

O(|p| · |P | )，ノード数は O(|p| · |P |) なので，XG グラフ上で K

p′ = /li /exp[i] である（注 2）．得られた結果を sc′1 , · · · , sc′K とする．
iii. γ(ej ) ← γ(s′ ) と設定する (1 <
=j<
= K)．

最短経路問題を解く時間計算量は O(K · |p| · |P |2 · log(|p| · |P |))（ 4 ） G(sp(p), G(P )) 上 で K 最 短 経 路 問 題 を 解 く．結 果 をであり，これが提案アルゴリズムの時間計算量である．

sc1 , · · · , scK とする．

2

j

6. 2 一般の場合（ 5 ） sc1 (p), · · · , scK (p) を返す．

p = /ax[1] :: l[1][exp[1]]/ · · · /ax[m] :: l[m][exp[m]] を XPath

上記アルゴリズムの時間計算量は O(K ·|p|·|P |2 ·log(|p|·|P |))式とする．p から述語を用いたロケーションステップを削除した XPath 式を sp(p) と定義する．すなわち，

sp(p) = /ax[1] :: l[1]/ · · · /ax[m] :: l[m]である．
以下にアルゴリズムを示す．P の下での p に対する K 最適編
集操作列を求めるため，今回も XG グラフ G(sp(p), G(P )) を構成し，その上で K 最短経路問題を解く．しかし，今回は p が単純とは限らないため，K 最短経路問題を解く前に G(sp(p), G(P ))である．

6. 3 グラフの最適化・枝刈りに関する考察
以上で述べたアルゴリズムにおいては，遷移規則グラフ，XG
グラフ共に枝刈りについては考慮していなかった．しかし，遷移規則グラフにおいてノードを最適化し，XG グラフにおいて目的となる受理ノードに到達不可能なノードを削除することで計算量を削減できることが考えられる．
本章では，まず遷移規則グラフにおける最適化について述べ，
その後 XG グラフにおける枝刈りについて述べる．

を以下のように修正する．（注 1）•

exp[i] =| ϵ と す る ．ロ ケ ー ション ス テップ ax[i] ::（注 2）：li が p′ の 先 頭 に 付 加 さ れ て い る の で ，再 帰 呼 び 出 し に お い て は（注 1）：述語内の式 exp の右辺や (不) 等号を正確に修正するのは困難なため，

γ(n0 → l) = 0(l = (li )0 の場合)，γ(n0 → l) = ∞(l =| (li )0 の場合)

exp の左辺の修正のみ考える．

と仮定する．ここで n0 は開始ノードである．

達可能なノード (Xi , ai )，(Xj , aj ) が存在する状況で次の条件(S, s)

を全て満たす場合，下記 (1),(2) で遷移規則グラフの最適化が可能である．

(A1, a)(B, b)(A2, a)(C, c) (D, d)

図 4 非終端記号が競合している遷移規則グラフ•(Xi , ai ) から (Xj , aj ) には到達可能でない•(Xj , aj ) から (Xi , ai ) には到達可能でない•(Xi , ai ) の子として (Xi , ai ) を持ち得ない•(Xj , aj ) の子として (Xj , aj ) を持ち得ない

ここで，Ei , Ej ∈ E とする．
（ 1 ） Ei = {(Xi , ai ) → (Xi′ , a′i ) | Xi → ai r ∈ P, Xi′ が r(S, s)に出現，Xi′ =| Pcdata ，ある a′i ∈ T と N 上の正規表現 r′ に対して Xi′ → a′i r ′ ∈ P } と Ej = {(Xj , aj ) → (Xj′ , a′j ) | Xj →(A1, a)aj r ∈ P, Xj′ が r に出現，Xj′ =Pcdata|，ある a′j ∈ T と N 上(A2, a)の正規表現 r′ に対して Xj′ → a′j r′ ∈ P } に対し，a′i =| a′j の場合，E に (Xi , ai ) → (Xj′ , a′j ) を追加する．

(B, b)（ 2 ） Ej = {(Xj−1 , aj−1 ) → (Xj , aj ) | Xj → aj−1 r ∈(C, c) (D, d)

P, Xj が r に出現，Xj =| P cdata，ある aj ∈ T と N 上の正規

図 5 非終端記号が競合していない遷移規則グラフ

表現 r′ に対して Xj → aj r′ ∈ P } に対し，E から Ej を削除
し，E に (Xj−1 , aj−1 ) → (Xi , ai ) を追加する．

6. 3. 1 遷移規則グラフの最適化

6. 3. 2 XG グラフの枝刈りによる時間計算量の推移

正規木文法においては非終端記号の競合を許すため，同じ終G が局所木文法の場合は K 最短経路問題を解くにあたり，目端記号が遷移規則グラフの複数箇所に出現しうる．そのため，的となる受理ノードに到達不可能なノードを削除することで計出力された K 個の最適編集操作列 sc1 , · · · , scK を適用して得算量を削減できることが考えられる．

られた XPath 式 scK (p) の中で，文字列として同じ XPath 式が存在することがある．

目的ノードに到達可能であるか否かは →+ 軸と ←+ 軸の有無によって変わるため，場合分けをして考察を行う．

例として，

局所木文法 G = (N, T, S, P ) と XPath 式 p に対する XG グ
ラフ G(p, G(P )) のサイズを考える．また簡単のため， G の遷

N = {S, A1, A2, B, C, D, P cdata}

移規則グラフ G(P ) を完全 n 分木と仮定する．

T = {s, a, b, c, d, pcdata}(1) →+ 軸及び ←+ 軸が p に含まれない場合: 受理ノー

S = {S}

ドに到達可能な経路は，仮定よりただ 1 つとなる．よって，

P = {S → s(A1, A2), A1 → a(B, C), A2 → a(B, D)

G(P ) における有効なノード数は log |T | となり，XG グラフのサイズは O(|p| · log |T |) となる．この場合の時間計算量はB → b(P cdata), C → c(P cdata),
D → d(P cdata), P cdata → pcdata(ϵ)}

O(K · |p| · (log |T |)2 · log(|p| · log |T |)) である．
(2) →+ 軸または ←+ 軸が p に含まれる場合: →+ 軸またはである正木木文法 G = (N, T, S, P ) を考える．このとき，G の←+ 軸が最初に出現するノードの，文書要素からの深さを l と遷移規則グラフは図 4 になる．ここで，経路 (S, s) → (A1, a) →|する．仮定より，G(P ) において有効なノード数は |Tとなり，
2l(B, b) と経路 (S, s) → (A2, a) → (B, b) の各ノードの終端記号|
XG グラフのサイズは |p| · |Tとなる．このとき，l = 0，つま2lは同じであるため，XG グラフ上で K 最短経路問題を解いたとり文書要素に →+ 軸または ←+ 軸が出現することは起こり得

きに / ↓:: a/ ↓:: b という XPath 式が複数個出力されうる．こないため，XG グラフのサイズを 12 以下にすることが可能であのような重複を回避するため，図 4 のように同じ終端記号を持||る．この場合の時間計算量は O(K · |p| · |T
· log(|p| · |T
)) で
2l
2l

つノードを縮約する．以下，このような縮約について形式的に

ある．

述べる．
遷移規則グラフ G(P ) = (V, E) は次のように定義される有向グラフである．

2

7. む す び
本稿では XPath 式 p，正規木文法 G，正整数 K に対し，pに対し最も “近い” K 個の修正候補 XPath 式を発見するアルV = {(X, a) | X → ar ∈ P }ゴリズムを提案し，XPath 式修正候補発見問題の NP 困難性をE = {(X, a) → (X ′ , a′ ) | X → ar ∈ P ,

証明した．

X ′ が r に出現，X ′ =| Pcdata，ある a′ ∈ T と
′

′

′ ′

N 上の正規表現 r に対して X → a r ∈ P }Xi =| Xj , ai =| aj , かつノード {(S, a)|S → ar ∈ P } から到

今後の課題として，出力の質に繋がるコスト設定についての考察と，評価実験によるその実証が挙げられる．例えば，XPath
式においてルートに近いロケーションステップほど一般にはより重要であると考えられる．そこで，XG グラフにおいて遷移規則グラフを繋ぐ辺 Di , Ci のコストを添え字が小さくなるほど大きくし，出力される K 最適編集操作列 sc1 , · · · , scK がどのように変化するかを実験する必要がある．
また，動的計画法などを用いることでも，本稿で扱った最短経路問題を解くことと同様に有用な結果を得られるという見込みがあるが，今後それらの手法の違いについて詳しく検討していく必要がある．
さらに，XPath 式の修正の支援という観点からは，対象となる XPath 式のどの部分が妥当でないかを特定すること，及びそれを提示することは修正候補の提示と同じく重要であると考えられるため，それらについても検討を進めていきたい．
文献[1] 林 英志, 日高 隆博, 山本 晋一郎, 小林 隆志, 上原 正太, 間瀬 順
一, 鈴村 延保, 阿草 清磁 “メタ情報とコンテキスト情報を用いた入力補完機能と XPath 入力への応用”, 情報処理学会研究報
告, Vol.2010-SE-167, No.28, 2010.
[2] 森嶋 厚行, 松本 明, 北川 博之 “例示操作に基づく XQuery 問
合せの学習機構”, 日本データベース学会 Letters, Vol.1, No.1,
pp. 15-18, 2002.
[3] ALTOVA “XMLSpy”,
http://www.altova.com/jp/xmlspy.html.
[4] Sihem Amer-Yahia, SungRan Cho, and Divesh Srivastava“Tree Pattern Relaxation”, Proc. EDBT, pp. 89–102, 2002.
[5] Sihem Amer-Yahia, Laks V.S. Lakshmanan, and Shashank
Pandit “FleXPath: Flexible structure and full-text querying
for XML”, Proc. SIGMOD, pp. 83–94, 2004.
[6] B. Choi “What Are Real DTDs Like”, Proc. Fifth Int
l Workshop Web and Databases (WebDB’02), pp. 43–48,
2002.
[7] S. Cohen and T. Brodianskiy “Correcting queries for XML”,
Information Systems, Vol.34, No.8, pp. 690–710, 2009.
[8] D. Eppstein “Finding the k shortest paths”, SIAM J. Computing, Vol.28, No.2, pp. 652–673, 1998.
[9] G. Gang and C. Rada “Eﬃciently Querying Large XML
Data Repositories: A Survey”, IEEE Transactions on
Knowledge and Data Engineering, Vol.19, Issue 10, pp.
1341–1403, 2007.
[10] Z. G. Ives, A. Y. Halevy, and D. S. Weld “An XML query engine for network-bound data”, The VLDB Journal, Vol.11,
No.4, pp. 380–402, 2002.
[11] K. Ikeda and N. Suzuki, “Finding top-K Correct XPath
Queries of User’s Incorrect XPath Query”, The 23rd International Conference on Database and Expert Systems
Applications (DEXA 2012), LNCS 7446, pp.116–130, 2012.
[12] G. Li, J. Feng, J. Wang, and L. Zhou, “Eﬀective keyword
search for valuable lcas over xml documents”, Proc. CIKM,
pp.31–40, 2007.
[13] M. Makoto et.al.,“Taxonomy of XML schema languages using formal language theory”, ACM Trans. Internet Technol,
Vol.5, No.4, pp. 660–704, 2005.
[14] E. Martins “K-th shortest paths problem”,
http://www.mat.uc.pt/ eqvm/OPP/KSPP/KSPP.html.
[15] A. Marzal and E. Vidal, ”Computation of Normalized Edit
Distance and Applications”, IEEE Transactions on PatternAnalysis and Machine Intelligence, 15(9), pp.926–932, 1993.
[16] A. Morishima, H. Kitagawa, and A. Matsumoto “A machinelearning approach to rapid development of XML mapping
queries”, Proc. ICDE, pp. 276–287, 2004.
[17] A. Termehchy and M. Winslett, “Using structural information in XML keyword search eﬀectively”, ACM Trans.
Database Syst., 36(1), 2011.
[18] Schmidt, A., Waas, F., Kersten, M., Carey, M., Manolescu,
I., Busse, R.: Xmark: A benchmark for xml data man-agemet. In: Proc. VLDB. pp. 974–985 (2002)[19] Y. Wu, N. Lele, R. Aroskar, S. Chinnusamy, and S.Brenes“XQGen: an algebra-based XPath query generator for
micro-benchmarking”, Proc. CIKM, pp. 2109–2110, 2009.
[20] Y. Xu and Y. Papakonstantinou, “Eﬃcient keyword searchfor smallest LCAs in XML databases”, Proc. SIGMOD,
pp.527–538, 2005.