近似文字列照合

Gonzalo Navarro, Ricardo Baeza-yates,
Erkki Sutinen, Jorma Tarhio:
Indexing Methods for Approximate
String Matching
近似文字列照合
IEEE Data Engineering Bulletin , 2001
( Oct.7, 2008, 勝俣 担当)
近似文字列照合とは
• パターン類似文字列をテキストからサーチ
(⇔完全一致文字照合)
• 応用可能な分野
– 音楽：類似楽節のチェック
– 生物：突然変異DNA配列の発見
– 文章：テキストタイプミス、スペルミスの発見
パターン
照合例
ABCDE
ABCDE
ABC1DE
ABCE
AB1DE
定義
• テキスト(被照合文章) ： T1…n (|T| = n)
• パターン(照合文字列) ： P1…m (|P| = m)
• アルファベット ： Σ (|Σ| = σ )
T∈Σ*、P∈Σ*
• パターン照合におけるエラーの最大値： k
• T,P比較時のエラー → 距離d(P, T)
⇒距離： d(P, T) ≦ k が条件
編集距離(edit distance)
• ２文字列の異なり度合を距離として示す
• マッチング操作：挿入、削除、置換
• 操作１回でコスト１(文字列照合までの操作回数)
P
T1
パターン
挿入
abcde abc1de
T2
T3
削除
abcd
置換
abc1e
コスト１
⇒ d(P, T1) = d(P, T2) = d(P, T3) = 1
エラーレベル
• パターン長さはm
⇔ 照合時の許容エラー数： 0 < k < m
• エラーレベル・・・照合で許すエラー割合(近似度)
α = k／m
近似文字列照合研究の流れ
• 10年前まで⇒オンラインサーチ研究中心
– パターンにのみチェック用の前処理→テキスト照合
– 現在： O(mn)→O((k+logσm)n/m)に改善
高速なアルゴリズムもアリ
but.文を多く扱うアプリケーションにはまだ×
• 最近10年⇒インデックスサーチが中心
– テキストで索引を作ってパターン照合
• 最近10年⇒インデックスサーチにも注目
– 文字列で索引を作って相手文字列と照合
• インデックスとオンラインの組合せで使うものもアリ
①.インデックスサーチ
–
–
–
–
suffix tree(接尾辞木)
suffix array(接尾辞配列)
q-grams
q-sample
②.オンラインサーチ
– Neighborhood Generation(全近傍列挙)
– Partitioning into Exact Searching(部分完全一致)
– Intermediate Partitioning
Suffix tree&array
• 接尾辞(suffix)とは…
– 語の後ろにつき派生語生成、品詞を変換する形態素
ex. 圧倒的、 耐熱性、 reliable、 happiness
• ここではテキスト位置i番目以降の部分文字列を指す
※ i=1~n
ex. abcdef の bcdef、 def、 abcdef など
suffix tree (接尾辞木)
• テキストからできる全接尾辞を木構造に
– 左から右に辞書順ソート
1. ABCABDABE$
2. BCABDABE$
3.
CABDABE$
4.
ABDABE$
5.
BDABE$
6.
DABE$
7.
ABE$
8.
BE$
9.
E$
接尾辞木作成法(１)
• 各文字列先頭から１文字ずつ連結
• 同じ深さに同じ文字ノード⇒１本にまとめる
• 終端に文字列開始位置を格納
A
A
A
B
B
B
C
D
E
B
B
B
C
D
E
A
A
C
D
E
A
A
$
B
B
A
A
$
B
B
D
E
B
B
D
E
A
$
D
E
A
$
B
A
$
B
E
B
E
$
E
$
$
$
suffix tree で近似照合
①．深さ＋１下に、左から探索
②．そのノードまでの文字列とパターンをDP
⇒パターンから取った深さと同じ長さ分の文字列と比較
③．≧k ⇔ さらに深さ＋１
＜k ⇔ 同じ深さの隣のノードに進む
suffix array (接尾辞配列)
• 部分文字列開始位置番号を配列化
– ①．文字列の接尾部を全列挙
– ②．その接尾部を辞書順にソート
– ③．順に開始位置番号だけ配列に
②
①
1. abracadabra$
2.
bracadabra$
3.
racadabra$
4.
acadabra$
5.
cadabra$
6.
adabra$
7.
dabra$
8.
abra$
9.
bra$
10.
ra$
11.
a$
11.
8.
1.
4.
6.
2.
9.
5.
7.
10.
3.
a$
abra$
abracadabra$
acadabra$
adabra$
bracadabra$
bra$
cadabra$
dabra$
ra$
racadabra$
③
suffix array –特徴• 辞書順ソート⇒二分探索による探索
– Suffix treeのシミュレートが可能
suffix array –特徴• 時間計算量
– 完全一致 ： O(m log n)
• 空間計算量
– Array生成 ： 最悪O(n log n) , 平均O(n log ( log n))
– 補助記憶域保存でO(n^2 log M /M)
※M：主記憶利用域
最善でテキストサイズの約４倍
Suffix Arrayで近似照合(１)
• Suffix Treeのシミュレートにより照合
– ①．深さ＋１の出現文字の範囲を調べる
– ②．深さ分のパターン文字列と近似照合
– ③．エラーｋ以内なら①・②の再帰
⇒LCP配列を使う？？
s[0] 11.
s[1]
8.
1.
s[2]
s[3]
4.
6.
s[4]
s[5]
2.
s[6]
9.
s[7]
5.
7.
s[8]
s[9] 10.
s[10] 3.
a$
abra$
abracadabra$
acadabra$
adabra$
bracadabra$
bra$
cadabra$
dabra$
ra$
racadabra$
パターン ： abcd
a:0～4
比較
b:5～6
c:7
d:8
b : 9 ～ 10
a (1文字目)
Q-grams
• 長さｑの部分文字列を１字ずらして取り出し
– そのテキスト位置と共にインデックス化
– 重複したらテキスト開始位置を共に格納
生成されるQ-gram数： (n-q+1)個
index
文字列にエラーがあったら…
• ｋエラーに対し、最大kq個のq-gramにエラー出現
⇒ パターンと照合するなら(m-q+1-kq)個が完全一致
Text
エラー0
エラー1
ＡＢＣＤＥＦGＨＩＪＫＬＭＮＯ
ＡＢＣＤＥＦ１ＨＩＪＫＬＭＮＯ
EFG
Q-gram
(q = 3)
EF1
FGH
F1H
GHI
1HI
Q-samples
• Q-gramを少なく配置
– 互いに重ならない
– 使用メモリ少 ⇒長文に対して効果期待
• Partition into Exact Searchなどと組み合わせ照合
両者の特徴
•
•
•
•
パターンがQ-gramと一致⇒その周辺を近似照合
インデックス作成に線形時間
長文に対してはO(n log (n/M))
使用領域はｑによりテキストサイズ0.5~3倍
編集距離計算
• 動的計画法(DP)により距離計算
– 与えられた２文字列(行：T、列：P)よりグラフ作成
– 左上からの各パスが文字の比較の仕方に対応
テキスト
テキスト
パターン
パターン
ノードNijの値Ｃij＝編集距離d(P1…i , T1…j)
動的計画法
• あるノードの値 Ｃj,i ＝ d(p1…j , t1…i)
• δ(pi, t j)：文字piとt jの置換コスト(pi = t j ⇔ 0 , pi ≠ t j ⇔ 1)
• pi：パターンのi番目の文字，t j：テキストのj番目の文字
Cj,i = min
Cj-1,i-1 + δ(pi , t j )
Cj-1,i + 1
Cj,i-1+1
Ｃj,i-1
Ｃj-1,i-1
δ(pi,t j)
C0,i = i (1≦i≦m)
Cj,0 = ｊ (1≦j≦n)
Ｃj-1,i
Ｃj,i
テキスト検索での動的計画法
• １行目の値をすべて０(全 jにおいて Cｊ,0 = 0)
⇒どんなテキスト位置からでもマッチング開始可能
Cj,i = min
Cj-1,i-1 + δ(a, b)
Cj-1,i + 1
Cj,i-1+1
C0,i = i (1≦i≦m)
Cj,0 = 0 (1≦j≦n)
テキスト途中から計算してもOK！
DPの欠点
グラフ作成O(mn) ・・・ 計算量大
エラーｋ以上の計算は余分
省ければ効率的 ⇒ Landau-Vishkinアルゴリズム
Landau-Vishkin アルゴリズム
• 列ごとの計算から対角線ごとの計算でグラフ作成
• 各対角線⇒ストロークに分割
– ストローク ： ある対角線での同じエラー数集合
• 列⇒エラー数e : 0~k
• 行⇒対角線番号d : d = j - i (-e ~ n)
• L[d, e] : 対角線におけるエラーe以内の対角線の長さ
j(テキストT)
d(対角線：j – i )
eエ(ラー数
)
パ
i (ターン P)
Ld,-1 = Ln+1,e = －1 , for all e,d
Ld,|d|－2 = |d|－2 , for －(k+1)≦d≦－1
Ld,|d|－1 = |d|－1 , for －(k+1)≦d≦－1
row : eストロークが現れるまでの対角線の長さ
Neighborhood Generation(全近傍列挙)
• パターンに対するエラーｋ以内の文字列を列挙
– Pの「k近傍」集合: Uk(P) = {x ∈ Σ* , d(x, P) ≦ k}
– | Uk(P) | = O( (mσ)^k ) ⇒ k ,m, σ増加で計算量急増
テキスト
照合
パターン
Neighborhood Generation(全近傍列挙)
• suffix tree/array と組合せて照合
①．パターンからのｋ近傍文字列
②．テキストから生成したsuffix tree/array、q-gram
⇒①、②で完全一致照合したらそれが近似一致文字列
パターンのｋ近傍文字列集合
partitioning into Exact Searching(分割完全一致検索)
• エラーがあってもある部分はパターン完全一致
ex) ｋ＝１でパターンABCDE (パターンをABC、DEに分割)
テキストにマッチング ⇔ ABC or DEが存在するはず！
完全一致したらそのテキスト部分周辺で近似照合
無い範囲は調べる必要なし(Filtering)
テキスト
• αが小さければ効率的に働く
パターン
• 定理
①．２文字列A,Bに対し、 d(A,B)≦k が成立
②．A = A1x1A2x2…xk+s-1Ak+s (s≧1)
– 少なくとも部分文字列s = Ai1…Ais はBに完全一致で存在
– 近似一致部分にはk+1個以上のエラーはない
• 想定されるエラー発生場所によりアルゴリズム差異
– パターンでエラー / テキストでエラー
パターンでエラー
• パターンを (ｋ＋ｓ)個に分割して完全一致照合
⇒近似しているなら ｓ個は必ず完全一致
ex) アルファベットABCDE…YZ に k=2 の近似
パターン：A１C２DE (Ｂを置換、ＣＤ間に挿入で２)
3分割(s = 1) : A1, C2, DE
4分割(s = 2) : A1, C, 2, DE
⇒ s個完全一致なら、近傍m+2k以内の距離部分を近似チェック
• インデックスサーチと組合せて照合
– 接尾辞木O(m) 、接尾辞配列O(m log n)で断片探索可能
– さらに近似照合平均時間O(m^2＊kn / σ^(m/k+1))
※s = 1のとき
• ｓ増で範囲内で必要一致数も増
– パターンが長いとうまく働く
– 断片も短くなるためパターン短いと検証が複雑化
テキストでエラー
• テキストを長さhの「テキスト窓」に分割
– h≧q
(h≦[(m-k-q+1) / (k+s)
• パターンからはq-gram⇒テキスト窓と照合
– s個の完全一致あればその付近でパターンと検証
• 最善のq = Θ(logσ n)
• ｓ値についてはまだ最善値は未分析
– ただし、sが大きければ検証が少なくすむかも・・・
Intermediate Partitioning
• パターンが長い⇒断片にしてもエラーがある可能性大
• but. 分割でエラー数減少 ⇒ そこで全近傍列挙
分割完全一致検索と全近傍列挙の組合せ照合
(片方ずつの方法より優れている)
定理 –Intermediate Partition• 2文字列Ａ、Ｂ間の編集距離d(A,B)≦k
• A = A1x1A2x2…xj-1Ajk
定理：まだ未編集・・・
パターンでエラー(Intermediate Partition)
1.パターンをｊ個に分割 (完全完全一致検索)
⇒ 長さ [m / j] , エラー許容 [k / j]個 , エラーレベルはαのまま
2.エラー減小した各断片を全近傍列挙
3.インデックス作成したテキストと[k / j]近傍照合
ｊ値について
• 計算量
j = 1 : 全近傍列挙に同じ
j = k+1 : O(m)
• 完全一致数
j = 2 : 1個以下 , j = 4 : 2個以下 ・・・ , j = k+1 : 最大
• 最善の j : Θ(m / logσn)
– 計算量 : O(n^λ) for 0≦λ≦1 (λ＜1, for α＜1-e/√σ)
時間と一致数のトレードオフ
テキストでエラー(Intermediate Partition)
• テキスト側
– テキストを長さｈで分割 (h ≦ [ (m-k-q+1) / j ])
– 各ｈ部分でq-sample
テキスト
分割
• パターン側
– パターンを j 分割
– パターンでブロック作成: Qi = P(i−1)h+1...ih+q−1+k
パターン
• テキストのq-sampleをQブロックから検索
– 連続sampleがkエラー以内で存在
⇒そこの部分でオンラインサーチ
テキストでエラー(続き)
• 未編集
e値について
• 最善のe = [k / j] (最小値)
– e が大きくなると検索コストが増大してしまう
– まだ十分な結果ではないが実験した結果の最善値