情報システム基礎論2：第 11回 (担当：古賀構造を持つデータの類似度 1

情報システム基礎論２：第 11 回 (担当：古賀)
構造を持つデータの類似度
2014 年 7 月 1 日
レジュメ URL: http://sd.is.uec.ac.jp/koga/lecture/IF2/
一般に、集合では要素間の関係を表現できない。これに対して文字列・木・グラフなどのデータ構造で
は要素間の関係が構造によって表現され、より複雑な対象を記述できる。例えば、文字列では文字間の前
後関係が定義されている。木構造ではノード間に親子関係が定義される。
本講義では、構造を持つデータの中で最も単純な文字列に対する類似検索について論じる。
1
文字列の類似検索
文字列とは文字が 1 個以上連続して並んだもの。Σ をアルファベット集合とすると文字列 p は次のよう
に定義できる。l は文字列の長さを表す自然数。
定義 1 (文字列 p)
p = p1 , p2 , · · · , pl .
ただし、任意の pi ∈ Σ (1 ≤ i ≤ l)。
定義 2 (文字列の類似検索) 文字列の集合 S から、クエリ文字列 q と類似する文字列を探索すること。
文字列の類似検索は、遺伝子解析などパターン認識でよく用いられる。文字列の類似検索では、文字列
の長さや文字の出現位置の違いなどにより類似性判定が簡単でないことが問題となる。例えば、
• abcdef と eeeeeeabcdef は似ているのか?
• abcdef と bcdefg は似ているのか?
適切な文字列間類似度 (類似性を表す尺度) が必要。本講義では文字列間の代表的な類似度である、
1. 編集距離
2. LCS(Longest Common Subsequence)
の 2 つを紹介する。
2
文字列編集距離
文字列編集距離は文字列に対する基本的な非類似度。
2 つの文字列 p, q 間の距離 = 編集操作を繰り返して p から q へ変換するのに必要な最小コスト
編集操作以下の 3 種類。それぞれの操作に対してコストが定義される。
1
• 挿入操作：文字 x を挿入。挿入位置の指定も必要。
• 削除操作：文字 x を削除。
• 置換操作：文字 x を文字 y に置換。
編集操作のコストは NULL 文字 λ を導入することで 2 変数関数として記述できる。
• 文字 x を挿入するコスト：c(λ, x)
• 文字 x を削除するコスト：c(x, λ)
• 文字 x を文字 y に置換するコスト：c(x, y)
コスト関数はアプリケーションに応じて適切に設定する必要がある。挿入コスト、削除コストを 1、異
なるラベルへの置換コストを 1 と設定することが多い。つまり、
∀x ∈ Σ,
∀x, y ∈ Σ,
c(λ, x) = c(x, λ) = 1.
(
0, if x = y. 同じラベルへの置換
c(x, y) =
1, if x 6= y. 異なるラベルへの置換
文字列変換: p から q への変換方法は 1 通りではない。
例: p=acded から q=abcde への変換 (図 1)。同じラベルへの置換は省略して記載。
Method 2:
1 deletion
1 insertion
Method 1:
3substitutions
abded
abded
substitutions
delete d
abcde
abde
insert c
abcde
図 1: 文字列変換の複数のやり方
文字列変換のコストは、変換に含まれる編集操作のコストの合計。方法 1 では 3、方法 2 では 2。
文字列変換の性質 (図 2)
• p の各文字は、変換中に削除される、もしくは、削除されないで q のどれかの文字に対応する。
• 変換中に削除されなかった p の文字群は、q の中で (ラベルは変化する場合もあるが) 順序が維持さ
れる。
p = p1 p2 , · · · , pm とし、q = q1 q2 , · · · , qn とすると任意の文字列変換は m × n 個の格子上の点 (0,0) から
点 (m, n) までのパスに対応付けできる (図 3)。右への移動が挿入、下への移動が削除、対角線方向への移
動が置換（同一文字間の置換も含む）に相当する。
文字列編集距離: 最小コストを達成する変換方法のコストとして定義される。コスト関数 c(x, y) が距離公
理を満足する時、文字列編集距離 D(p, q) も距離公理を満たす。すなわち、任意の文字列 p, q, z に対して
2
deleted nodes
substituted nodes
p: fagbcded
q: abddehdh
inserted nodes
図 2: 文字列変換の性質
(0,0)
a b c
d e
a
b
d
e
d
(5,5)=(m,n)
図 3: 文字列変換のパスとしての表現
• 同一性：D(p, q) = 0. ⇔ p = q.
• 対称性：D(p, q) = D(q, p).
• 三角不等式：任意の文字列 z に対して D(p, q) ≤ D(p, z) + D(z, q).
3
文字列編集距離の計算
コスト最小となる文字列変換を求めればよい。これは動的計画法 (Dynamic Programming) によって計
算可能。
Dynamic Programming (DP)：複雑な問題を部分問題に分解して、部分問題の解を利用して元の問
題の解を求める手法。DP で解ける問題例としてフィボナッチ数列がある。
アルゴリズム: p = p1 p2 , · · · , pm とし、q = q1 q2 , · · · , qn とする。
• sd[i, j]: p の部分文字列 psub = p1 , p2 , · · · , pi と q の部分文字列 qsub = q1 , q2 , · · · , qj 間の文字列編集
距離 (1 ≤ i ≤ m, 1 ≤ j ≤ n)。したがって、D(p, q) = sd[m, n]。
この時、sd[i, j] は 3 つの部分問題の解 sd[i − 1, j],sd[i, j − 1],sd[i − 1, j − 1] から求められる (式 (1))。




 sd[i − 1, j] + c(pi , λ), 
.
(1)
sd[i, j] = min
sd[i, j − 1] + c(λ, qj ),


 sd[i − 1, j − 1] + c(p , q ) 
i j
3
この理由は次のように説明できる (図 4)。psub 内の文字は qsub への変換過程で、削除されるか、qsub
に残るかのどちらか。つまり、psub から qsub への文字列変換は以下の 2 種類に分類される。
1. pi を削除して qsub に変換する方法。この場合の最小コストは c(pi , λ) + sd[i − 1, j]。
2. pi を削除せずに qsub に変換する方法。この場合は pi を qsub のどの文字に対応（置換）させるかで
さらに 2 種類に分類される。
(a) pi を qj に対応させて変換。この場合の最小コストは c(pi , qj ) + sd[i − 1, j − 1]。
(b) pi を qk (k ≤ j − 1) に対応させて変換。この時は、変換中に qj を挿入する必要がある。この場
合の最小コストは c(λ, qj ) + sd[i, j − 1]。
Case 1
P1P2.....Pi-1
delete
Pi +
q1q2.....qj-1qj
Case 2(a)
P1P2.....Pi-1
Pi
+
qj
q1q2.....qj-1
Case 2(b)
P1P2.....Pi-1Pi
+
q1q2.....qj-1
insert
qj
図 4: sd の漸化式
さらに、i = 0 あるいは j = 0 の時は以下が成立。
• i = 0 の時は、psub は空文字列。よって、挿入を繰り返して qsub に変換するしかない。
sd[0, j] = sd[0, j − 1] + c(λ, qj )
• j = 0 の時は、qsub は空文字列。よって、psub から削除を繰り返して変換するしかない。
sd[i, 0] = sd[i − 1, 0] + c(pi , λ)
• sd[0, 0] = 0。
以上から、任意の i, j に対して sd[i, j] を計算可能。小さな i, j に対して sd[i, j] を決定後、より大きな
i, j に対して sd[i, j] を計算できる。
4
例： p=abded と q=abcde との文字列距離の計算
λ a
λ 0 1
a 1 0
b 2 1
d 3 2
e 4 3
d 5 4
b c d e
2 3 4 5
1
0
1
2
3
2
1
1
2
3
3
2
1
2
2
4
3
2
1
2
編集距離の計算量は (m + 1) 行、(n + 1) 列の 2 次元配列を埋めるのに必要な計算量に等しい。1 マスの
計算は 3 回の足し算および、3 つの数値から最小値を求めるだけなので、O(1)。従って、編集距離の計算
量は O(mn)。
編集スクリプト：
編集距離を実現する最小コストの文字列変換を編集スクリプトと呼ぶ。編集スクリプトは編集距離計算ア
ルゴリズムを拡張して簡単に求められる。
1. (m + 1) 行、(n + 1) 列の 2 次元配列 t を用意する。
2. sd[i, j] 計算時に、sd[i − 1, j],sd[i, j − 1],sd[i − 1, j − 1] のどれから sd[i, j] が決定されたかを t[i, j] に
記憶。
3. sd[m, n] 計算後に、t に従って (m, n) から後ろ向きに (0, 0) に到達するパスを求める。パスに対応す
る文字列変換が編集スクリプト。
4
LCS(Longest Common Subsequence)
3 つの文字列
p1 = abcde
p2 = abpqe
p3 = abpqcde
を考えてみよう。文字列編集距離は D(p1 , p2 ) = D(p1 , p3 ) = 2。しかし、見た目には p3 の方が p2 より p1
に近いと感じる。これは、p1 と p3 の方がより多くの部分シーケンスを共有しているためである。LCS は
このアイデアに基く文字列間類似度。
p を文字列とすると、
• 部分文字列 (substring)：p 内に存在する連続した文字列。
• 部分シーケンス (subsequence)：p 内の順序が維持された文字集合。
5
λ a
λ 0 0
a 0 1
b 0 1
p 0 1
q 0 1
d 0 1
e 0 1
b c d e
0 0 0 0
1
2
2
2
2
2
1
2
2
2
2
2
1
2
2
2
3
3
1
2
2
2
3
4
図 5: abcde と abpqde の LCS
定義 3 (Common Subsequence) 文字列 r = r1 , r2 , · · · , rl の各文字が、2 つの文字列 p と q の両方に
r1 , r2 , · · · , rl の順に出現しているならば、r を p と q の Common Subsequence と呼ぶ。
LCS は最長の Common Subsequence であり、LCS の長さは文字列間類似度として使用可能。
例：p1 と p3 の Longest Common Subsequnece は “abcde”。なお、Longest Common Substring は “cde”。
4.1
計算方法
p と q の LCS(p, q) は文字列編集距離と同様に Dynamic Programming で計算できる。
• l[i, j]: 文字列 p1 , p2 , · · · , pi と文字列 q1 , q2 , · · · , qj 間の LCS の長さ (1 ≤ i ≤ m, 1 ≤ j ≤ n)。した
がって、LCS(p, q) の長さ = l[m, n]。
この時、l[i, j] は 3 つの部分問題の解 l[i − 1, j], l[i, j − 1], l[i − 1, j − 1] から求められる。
• if pi 6= qj ,
l[i, j] = max {l[i − 1, j], l[i, j − 1]} .
• if pi = qj ,
l[i, j] = max {l[i − 1, j], l[i, j − 1], l[i − 1, j − 1] + 1} .
また、
• i = 0 の時は、for (0 ≤ j ≤ n), l[0, j] = 0。
• j = 0 の時は、for (0 ≤ i ≤ m), l[i, 0] = 0。
例： p=abpqde と q=abcde との LCS の計算。図 5 参照。
LCS 自体は、文字列編集距離において編集スクリプトを求めたのと似た手順で求められる。
6

Download Report