General Algorithms for Mining Closed Flexible Patterns
under Various Equivalence Relations○井 智弘, 荏隈 勇樹, 坂内 英夫, 竹田 正幸
頻出飽和文字列パターン列挙問題

Flexible パターン

入力：テキスト集合 S, 頻度の閾値 , 同値関係 S
出力： S 中の  個以上の文字列に出現する飽和パターンを列挙

Sパターン PPb r c dab ad br ca daabr bra ada brb cad dab
abra adab brab brbr cada dabradabr brabr cadab dabra
adabra brabra cadabr
cadabra パターン上の半順序

テキスト T  x, xab, x, xrax  x, xab, xrax, x  xabx, , x, xrax  xabx, , xrax, x

簡潔で見やすい出力
うまく計算すると探索・出力コスト減

 パターン P  Q に対して,

 a b  e  r a 1234567c  a b r e r a b  aP パターンの出現区間, 極小出現区間

 同値関係を導入するメリット
1.
2.

埋め込み   c, r, , ba を適用

c d a b r e r r a b r aパターン P wi   ：i 番目のセグメント

 a b  e  r a 

埋め込み   cd, r, r, bra を適用a

a b r ab r a b r a
d a b r a
c a d a b r ab r b r

 k  1     ：ギャップ文字

1 w1 2 w2 3  k wk k1

  2 のときの頻出飽和部分文字列パターン列挙

例

九州大学

89P  Q なる埋め込みが存在するとき
Q は P より具体的であるという

10 11 12 13 14y a b x a b e x r a x r a y

 a b  e  r a P
極小埋め込み   , xb, x, xr を適用

出現区間(P, T)  {[2, 10], [2, 13], [5, 10], [5, 13]}
極小出現区間(P, T)  {[5, 10]}

 a b x  b e x r a x r Q

Flexible パターン上の様々な同値関係に対して統一的な多項式時間遅延アルゴリズムを提案
同値関係

同値関係の粗化

遅延計算量

説明
出現区間の一致O(|Σ| S d)の拡張

O(|Σ| S d) 全ての極小出現に関して左右に共通の文字列で極小出現区間の一致

O(|Σ| S d)の拡張１O(|Σ| S d)の拡張２O(|Σ| S2 d)出現の開始位置集合の一致（有村&宇野）
S ：テキスト長の総和
d ：セグメント数の最大値

パターン P abra
パターン P’ abrax
パターン P’’ abraxx
・・・O(|Σ| S) 次の親子関係で定義される探索木を深さ優先探索するxxabraxx
xxabraxxx
xxabraxxxx 任意の x   に対して, x の親は  任意の x  , w1,…, wk   に対して,

ab

ab

aa ab

ba

これらも同値とする

・・・xabraxxxxabraxy

これは同値ではないP   w1  w2  w3  w 4 

任意のギャップ文字に関して, 見る範囲は重ならないのでO(S) 時間でチェックできる （全体で O(Sk) 時間）w3 w4  w1 w2 x w3 w4  w1 w2 w3 x w4 Tw1aa

abraパターン P
パターン P’ xabraabraxx
パターン P’’における内部飽和チェック 〈O(Sk) 時間〉

 w1 x w2   {a, b} のときの探索木

xzaberaxxxxaborayxyxxx

テキスト T non-erasingw1wkx と w1wkx の親は w1wk（ただし, 極小出現区間の数が変わらない範囲で）では,極小出現区間が異なるため各々異なる同値類に属する

・・
・

計算領域はいずれも O(Sd) さらに, ギャップ付でも左右に伸ばせるようにする

xxaberaxxxxaboraxxxxxx

テキスト TO(|Σ| S)の拡張
伸長できるとき, それらのパターンも同値とする

O(|Σ| S)出現の終了位置集合の一致bb ba ab

w1

w2

w1

w2
w3

w2

w2

w3

w3

w4

w4

w4

 erasingaba abb aba abb w1  任意のパターン P に対して以下が成り立つ



w1 w2

 w1 w3 w4 w4 w2 w3
w2 

w3 w4

 頻度チェック

テキストの各位置に対して, w2 w3 が次に出現する位置を記録しておけばO(S) 時間でチェックできる （全体で O(Sk) 時間）
出現区間の右側に必ず“xxxx”が出現するとき

xxabraxxabraxx

・・・

xxabraxx

・・・xxabrax・・・・・・・・・

xxabraxxxx
あしひきのやまほとときすさとなれてたそかれときになのりすらしも 山家集（1552首）に対して, 頻度の閾値 σ を 2, 4, 8 に設定し,各同値関係における頻出飽和パターンの数と計算時間を比較（画面表示はオフ）
 「御裳濯和歌集序文」と「八代集の各首」の間で,,,における共通飽和パターンを列挙し結果を比較
御裳濯和歌集序文
やまとうたはあしはらのなかつくによりおこり、いなたひめすかのさとよりひろまれり、あとをたれたまへるしんみやうもこのみちをむねとし、あらはれいてたまへるふつたもこのこと
わさをすてたまはす、おほよそわかくにのふうそくとしてむかしよりいまにたゆることなし、つらつらちよくせんをたつぬれはすてにはちたいになれり、ところところのうちききしふそのかすまたおほし、かれにしたふこころすすみて、…… （1241文字）

 最初のセグメントから最後のセグメントの距離が 38 の出現のみを考える セグメントの長さの総和が 15 以上のパターンのみ表示する

Everything is String.

xxabrax

・・・

xxabraxxxx

・・・

xxabraa

・・・・・・

和歌データを用いた実験

・・・・・・

P が頻出でないなら, P の子孫も頻出でない（枝刈り）
 左端飽和チェック
 最長共通接頭辞を用いた高速化
左端のギャップ文字を具体的にしてP と同値なパターンがあればP と P の子孫は飽和パターンではない（枝刈り）
 内部飽和チェック
極小出現区間の右側に必ず“xxxx”が出現するとき
左右端以外のギャップ文字を具体的にしてP と同値なパターンがあれば
xxabra
P と P の子孫は飽和パターンではない（枝刈り）
 右端飽和チェック
xxabraa
xxabraxxxabraz
右端のギャップ文字を具体的にしてP と同値なパターンがあるとき
xxabraxx
P は飽和パターンでは無いが・・
P の子孫に頻度が等しく飽和なパターンが必ず存在する・*あしひきのやまほとときす*たそかれ**あしひきのやまほとときす*たそかれと**あしひきのやまほとときす*たそかれとき**あしひきのやまほとときす*たそかれときに**あしひきのやまほとときす*たそかれときにな**あしひきのやまほとときす*たそかれときになの**あしひきのやまほとときす*たそかれときになのり**あしひきのやまほとときす*たそかれときになのり*し**あしひきのやまほとときす*たそかれときになのり*し*も**あしひきのやまほとときす*と*な*き**あしひきのやまほとときす*と*な*き*も**あしひきのやまほとときす*と*な*な**あしひきのやまほとときす*と*な*な*の**あしひきのやまほとときす*と*な*な*も**あしひきのやまほとときす*と*な*れ**あしひきのやまほとときす*と*な*れて**あしひきのやまほとときす*と*な*れて*か**あしひきのやまほとときす*と*な*れて*か*き**あしひきのやまほとときす*と*な*れて*き**あしひきのやまほとときす*と*な*れて*き*の**あしひきのやまほとときす*れ*れ*き**あしひきのやまほとときす*れ*れ*き*の**きのやまほとときす*たそかれとき**きのやまほとときす*たそかれときに**きのやまほとときす*たそかれときにな**きのやまほとときす*たそかれときになの**きのやまほとときす*たそかれときになのり**きのやまほとときす*たそかれときになのり*し**きのやまほとときす*たそかれときになのり*し*も**きのやまほとときす*と*な*れて*か*き**きのやまほとときす*と*な*れて*き*の**しひきのやまほとときす*たそかれ**しひきのやまほとときす*たそかれと**しひきのやまほとときす*たそかれとき**しひきのやまほとときす*たそかれときに**しひきのやまほとときす*たそかれときにな**しひきのやまほとときす*たそかれときになの**しひきのやまほとときす*たそかれときになのり**しひきのやまほとときす*たそかれときになのり*し**しひきのやまほとときす*たそかれときになのり*し*も**しひきのやまほとときす*と*な*き*も**しひきのやまほとときす*と*な*な*の**しひきのやまほとときす*と*な*な*も**しひきのやまほとときす*と*な*れて**しひきのやまほとときす*と*な*れて*か**しひきのやまほとときす*と*な*れて*か*き**しひきのやまほとときす*と*な*れて*き**しひきのやまほとときす*と*な*れて*き*の**しひきのやまほとときす*れ*れ*き*の**ときす*たそかれときになのり*し*も**とときす*たそかれときになのり*し**とときす*たそかれときになのり*し*も**のやまほとときす*たそかれときに**のやまほとときす*たそかれときにな**のやまほとときす*たそかれときになの**のやまほとときす*たそかれときになのり**のやまほとときす*たそかれときになのり*し**のやまほとときす*たそかれときになのり*し*も**ひきのやまほとときす*たそかれと**ひきのやまほとときす*たそかれとき**ひきのやまほとときす*たそかれときに**ひきのやまほとときす*たそかれときにな**ひきのやまほとときす*たそかれときになの**ひきのやまほとときす*たそかれときになのり**ひきのやまほとときす*たそかれときになのり*し**ひきのやまほとときす*たそかれときになのり*し*も**ひきのやまほとときす*と*な*れて*か**ひきのやまほとときす*と*な*れて*か*き**ひきのやまほとときす*と*な*れて*き**ひきのやまほとときす*と*な*れて*き*の**ほとときす*たそかれときになのり**ほとときす*たそかれときになのり*し**ほとときす*たそかれときになのり*し*も**まほとときす*たそかれときになの**まほとときす*たそかれときになのり**まほとときす*たそかれときになのり*し**まほとときす*たそかれときになのり*し*も**やまほとときす*たそかれときにな**やまほとときす*たそかれときになの**やまほとときす*たそかれときになのり**やまほとときす*たそかれときになのり*し**やまほとときす*たそかれときになのり*し*も*

83 個

15 個

7個

String Data Processing Laboratory