Finding Characteristic Substrings
from Compressed Texts○稲永俊介

坂内英夫（九州大学）

テキストマイニングとテキスト圧縮
テキストマイニング：与えられたテキストデータから，未知の規則や知識を半自動的に抽出する技術
テキスト圧縮：テキストの冗長性を排除して，データの記述長を短縮する技術

圧縮

展開

本研究

与えられた圧縮テキストに特徴的な部分文字列（パタン）を効率よく発見するアルゴリズムを提案する．
最長繰り返し部分文字列
最長重複なし繰り返し部分文字列
最頻出部分文字列
最頻出重複なし部分文字列
入力圧縮パタンの最大拡張パタン

Straight Line Programによるテキスト圧縮
SLP T
X1 = aX2 = b
X3 = X1X2
X4 = X3X1
X5 = X3X4
X6 = X5X5
X7 = X4X6
X8 = X7X5

T=SLP T は言語{T}を生成するChomsky標準形の文脈自由文法.

Straight Line Programによるテキスト圧縮
SLP T
X1 = aX2 = b
X3 = X1X2
X4 = X3X1
X5 = X3X4X6 = X5X5
X7 = X4X6
X8 = X7X5

T=

LZ系圧縮，文法圧縮，連長圧縮などで圧縮された文字列は高速にSLPに変換できる．

SLPの指数的圧縮能力
元テキストは，SLP圧縮されたテキストに対して指数的に大きくなりうる．
テキスト T = abababab…ab(abのN回繰り返し)SLP T : X1 = a, X2 = b, X3 = X1X2, X4 = X3X3,X5 = X4X4, ... , Xn = Xn-1Xn-1
N = O(2n)与えられた圧縮テキストを展開してから処理する
アルゴリズムは，最悪時には指数時間を要する．
本研究：圧縮テキストを陽に展開することなく，しかも圧縮サイズの多項式時間で動作する手法を提案

最長繰り返し部分文字列発見
入力: テキスト T を生成するSLP T
出力: T の最長繰り返し部分文字列≠T≠
例T = aabaabcabaabb

Key Observation – ６つの場合分けXi
Xl

Xi
Xr

Case 1

Xl

Case 4

Xr

Case 2Xi
Xl

Xi
Xl

Case 3Xi
Xr

Xl

Case 5

Xr

Xi
Xr

Xl

Case 6Xr

最長繰り返し部分文字列発見アルゴリズム
Input: SLP T
Output: LRS of text T
foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;最長繰り返し部分文字列発見アルゴリズム
Input: SLP T
Output: LRS of text T
foreach variable Xi of SLP T do
Xlcompute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
Case 1compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

XiXr最長繰り返し部分文字列発見アルゴリズム
Input: SLP T
Output: LRS of text T
foreach variable Xi of SLP T do
Xlcompute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
Case 1compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

XiXr最長繰り返し部分文字列発見アルゴリズム
Input: SLP T
Output: LRS of text T
foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;最長繰り返し部分文字列発見アルゴリズム
Input: SLP T
Output: LRS of text T
foreach variable Xi of SLP T doXlcompute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;compute LRS of Case 4;
Case 2compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

Xi
Xr最長繰り返し部分文字列発見アルゴリズム
Input: SLP T
Output: LRS of text T
foreach variable Xi of SLP T doXlcompute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
Case 2compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

XiXr最長繰り返し部分文字列発見アルゴリズム
Input: SLP T
Output: LRS of text T
foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;最長繰り返し部分文字列発見アルゴリズム
Input: SLP T
Output: LRS of text TXi
Xl

Xr

foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
Case 3compute LRS of Case 3;
compute LRS of Case 4;
compute LRS of Case 5;
compute LRS of Case 6;
return two positions andCase
the 3lengthofの最長繰り返し部分文字列は，
the “longest” LRSXabove;l と Xrの最長共通部分文字列である

SLP圧縮テキストの最長共通部分文字列定理１ [Matsubara et al. 2009]

すべてのSLP 変数 Xl と Xrの最長共通部分文字列をO(n4logn)時間で計算できる．

最長繰り返し部分文字列発見アルゴリズム
Input: SLP T
Output: LRS of text T

Xi
Xl

foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
Case 4compute LRS of Case 3;
compute LRS of Case 4;
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;Xr

Case 4Xi
XlXjXrCase 4-1
Xi
XlXj

Xr

Xs

Xj

Xt

Case 4-1

Xl

Xt

Xl と Xtの重複

Case 4-1
Xi
Xl
Xj

重複部分を左右に拡張

Xr

Xs

Xj

Xt

Xl と Xtの重複

Case 4-2
Xi
Xl

重複部分を左右に拡張

Xr

Xj

Xs

Xj

Xt

Xr と Xsの重複

重複の集合X

X と Y の重複の長さの集合

Y重複の集合OL(aabaaba, abaababb) = {1, 3, 6}
X

aabaabaabaababb
Yabaababb
YabaababbY重複の集合補題１ [Kaprinski et al. 1997]
任意の２つの変数Xi と Yjに対して，OL(Xi, Yj) は O(n) 個の等差数列をなす．

補題２ [Kaprinski et al. 1997]
すべての変数 Xi と Yjに対して，OL(Xi, Yj) は O(n4logn) 時間で計算できる．

Case 4
補題 ３
任意の変数 Xiに対して，Case 4 の最長繰り返し部分文字列はO(n3logn)時間で計算できる．

[証明のスケッチ]• OL(Xi, Xj)の各等差数列の全要素をO(nlogn)時間で左右に拡張できる．
• OL(Xi, Xj) のサイズは O(n) （補題 １より）．
• Xiの子孫の数は高々n-1個．

最長繰り返し部分文字列発見アルゴリズム
Input: SLP T
Output: LRS of text TXi
Xl

Xr

foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
Case 5compute LRS of Case 3;
compute LRS of Case 4;
Case 4 と対称
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;最長繰り返し部分文字列発見アルゴリズム
Input: SLP T
Output: LRS of text TXiXlXr

foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
Case 6compute LRS of Case 3;
compute LRS of Case 4;
Case 4 と同様
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;最長繰り返し部分文字列発見アルゴリズム

定理２

テキスト T を生成するSLP T に対して, Tの最長繰り返し部分文字列をO(n4logn)時間で計算できる．

最長重複なし繰り返し部分文字列発見
入力: テキスト T を生成するSLP T
出力: T の最長重複なし繰り返し部分文字列例

T = ababababab

最長繰り返し部分文字列はabababab
最長重複なし繰り返し
部分文字列は abab

最長重複なし繰り返し部分文字列発見

定理３

テキスト T を生成するSLP T に対して, Tの最長重複なし繰り返し部分文字列をO(n6logn)時間で計算できる．

まとめと今後の課題
与えられたSLP圧縮テキストから，特徴的な部分文字列を多項式時間で発見するアルゴリズムを提案した．
圧縮テキストを陽に展開するあらゆるアルゴリズムは指数時間を要する．

異なるタイプの特徴的な部分文字列を効率よく発見できるだろうか？
Squares (xx という形の部分文字列)
Cubes (xxx という形の部分文字列)
Runs (xk という形の部分文字列．ただし k ≥ 2)

最頻出部分文字列発見
入力: テキスト T を生成するSLP T
出力: Tの最頻出部分文字列

常に空文字列εが解！

最頻出部分文字列発見
入力: テキスト T を生成するSLP T
出力: Tの長さ２の最頻出部分文字列

T最頻出部分文字列発見アルゴリズム|Σ|2 個の長さ2の部分文字列

Y1
Input: SLP T
Output: MFS of text T
aforeach substring P of T of length 2 doconstruct an SLP P which generates substring P;
compute num. of occurrences of P in T;
return substring of maximum num. of occurrences;

補題４
任意の２変数 Xi と Yjに対して， Xi 中の Yj の出現回数をO(n)時間で計算できる．
ただし，O(n2)時間の前処理が必要．

Y3Y2b最頻出部分文字列発見

定理４

テキスト T を生成するSLP T に対して, Tの長さ２の最頻出部分文字列をO(|Σ|2n2)時間で計算できる．

最頻出重複なし部分文字列発見
入力: テキスト T を生成するSLP T
出力: Tの長さ２の最頻出重複なし部分文字列例

T = aaaaababab

長さ２の最頻出部分文字列はaa長さ２の最頻出重複なし
部分文字列はab最頻出重複なし部分文字列発見

定理５

テキスト T を生成するSLP T に対して, Tの長さ２の最頻出部分文字列をO(n4logn)時間で計算できる．

入力圧縮パタンの最大伸張パタン発見
入力: テキスト T を生成するSLP T とパタン P を導出するSLP P
出力: 以下を満たす T の部分文字列 αPβ
テキストΤ 中において，α は常に P の直前に出現し，βは常に P の直後に出現する．
α と β は最長．

例

T = bbaabaabbaabb

P = ab
α = baβ=ε入力圧縮パタンの最大伸張パタン発見

最大伸張パタンの応用例
ブログスパム発見 [Narisawa et al. 2007]
最頻出部分文字列の最大伸張パタン発見

T入力圧縮パタンの最大伸張パタン発見

定理６テキスト T を生成するSLP T とパタン P を導出するSLP P に対して，T における P の最大伸張パタンをO(n4logn)時間で計算できる.

“串刺し”補題 [1/2]X
XlXrYYY

補題５ [Miyazaki et al. 1997]
任意の変数 X = XlXr と Y に対して，X の境界に触れる Y の出現は１つの等差数列をなす．

“串刺し”補題 [2/2]X
XlXru|u| は Y の最小周期v は u の接尾辞uv Yuuv Yuuv

Y

補題５ [Miyazaki et al. 1997]（つづき）
等差数列の要素数が３以上のとき，等差数列の交差は Y の最小周期である．

左右の最大伸張XXlαXruuv βαuuv βαuuv βY
左側の最大伸張 α はu の接尾辞である．

右側の最大伸張 βは uv[|v|: |uv|] の接頭辞である．