文字列データの線形最小汎化問題に対するアルゴリズム

文字列データの線形最小汎化問題に対するアルゴリズム

Algorithms for Linear Least Common Generalization Problem on

Strings

里見 琢聞

1∗

_{小林 靖明}

2

_山本章博

2

Takumon Satomi

1

Yasuaki Kobayashi

2

Akihiro Yamamoto

2

1

_{京都大学工学部}

1

_{Faculty of Engineering, Kyoto University}

2

_{京都大学大学院情報学研究科}

2

_{Graduate School of Informatics, Kyoto University}

Abstract: A pattern is a string over Σ∪V , where Σ is an alphabet and V is a set of variables. We say that a string s in Σ∗is generated by a pattern p if s can be obtained by replacing each variable in p with a non-empty string in Σ∗. The problem we consider in this paper is to find a longest common pattern, called a least common generalization, that generates a set of given strings. We propose polynomial time algorithms for this problem. More specifically, given two strings of length

n and m, our algorithm finds a least common generalization in O(nm) time. This algorithm can

be generalized to the case where the input has k strings of length at most n. In this case, our algorithm runs in O(knk_{) time. Moreover, we prove this running time is nearly optimal under the}

Strong Exponential Time Hypothesis (SETH): there is no O(nk−ε) time algorithm for the least common generalization problem unless SETH fails.

1

はじめに

機械学習において，文字列データから共通する特徴 や規則性を発見する手段は重要である．そのためには 最大共通部分列や編集距離，アラインメントなどの手 法がよく知られており，パターンを用いた汎化もその ひとつである．パターンとは文字の他に変数を用いて 得られる列であり，パターン p の変数に非空な文字列 を代入してすべての入力文字列を得ることができると き p は入力データの共通汎化と呼ばれる．入力文字列 の集合 S の共通汎化の中で何らかの意味で “最小” なも のを得ることは機械学習の一種と捉えることができる． 従来の研究では，ふたつのパターン間の順序を代入 によって定義している，つまり pθ = q となる代入 θ が存在するとき p は q よりも一般的，q は p よりも具 体的であるという. 与えられた文字列データから，そ れらに共通するパターンのうち最も具体的であるもの を求める手続きを最小汎化もしくは最小共通汎化とい い，最小汎化を求める研究が現在までなされてきてい る [4, 15]．しかしパターン全体を扱うと，困難さが生 じることも知られている [3]．そこで本研究ではパター ∗_{連絡先：京都大学工学部}       〒 606-8501 京都府京都市左京区吉田本町        E-mail: [email protected] ンの有効長に着目し，有効長によってパターン間の順 序を定義する． パターンの有効長とはパターンに含ま れる変数でない文字数である．有効長によってパター ンの同値類を定義することができ，その代表元として 線形なものだけを取ることができる．また具体的なパ ターンほど有効長が大きくなるので，有効長が最大で あることはある意味最小の汎化であるとみなすことが できる．したがって線形パターンにおいて有効長の意 味での最小汎化を定義する． 本稿では入力文字列を生成するパターンのうち有効 長が最大のものを発見する問題に取り組む．具体的に は以下の定理を示す． 定理 1. 長さが n と m のふたつの文字列が与えられた とき，それらの最小汎化を求める O(nm) 時間アルゴリ ズムが存在する． 定理 2. 長さが高々n の文字列が k 個与えられたとき， それらの最小汎化を求める O(knk_{) 時間アルゴリズム} が存在する． 本稿の構成は以下の通りである．次節では記法や最 小汎化問題の定義についてまとめた後，第 3 節におい てふたつの文字列入力に対する最小汎化問題を解くア ルゴリズムを提案する．続く第 4 節では，一般の文字 人工知能学会研究会資料 SIG-FPAI-B803-14

列集合に対する問題に取り組み，同様のアルゴリズム によって解けることを概説する．さらに第 5 節では，最 大共通部分文字列問題からの帰着を与えることにより この問題の困難性について議論し，第 6 節において，本 研究のまとめと今後の課題について述べる．

2

準備

Σ をアルファベットとし，Σ∩ V = ∅ となる V の元 を変数と呼ぶ．Σ∪ V 上の文字列 p ∈ (Σ ∪ V )∗ _をパ ターンという．p に含まれる変数が互いに異なるとき， p を線形パターンという．パターン p における有効長 とは，p に含まれる変数でない文字の個数である．p の 有効長を_{∥p∥ と表す．} 文字列 σ の長さを|σ| で表す．1 ≤ i ≤ |σ| において， σ[i] で σ の i 番目の文字を表し，σiで σ の長さ i の接 頭辞を表す．ふたつの文字列 σ, τ ∈ Σ∗_{において，στ} で σ の直後に τ を連結して得られる文字を表す． パターン p∈ (Σ ∪ V )∗_{に含まれる変数 x に対する代} 入とは，x を非空なパターン q ∈ (Σ ∪ V )∗_{\ {ε} で置} き換えることである．線形なパターン p の各変数に対 して代入を適用してパターン p′ ∈ (Σ ∪ V )∗_が得られ るとき，p が p′_{を生成するという．p によって生成さ} れる文字列集合を_{L(p) ∈ Σ}∗と書く．本研究では，与 えられた文字列集合 S⊆ Σ∗_{について，S⊆ L(p) を満} たすパターン p で，その有効長が最大のものを見つけ る問題に取り組む．この問題を最小汎化問題と呼ぶこ とにする．この最適化問題において，一般性を失うこ と無く，求めるパターンは線形パターンであると仮定 できるため，以下では，特に断らない限り線形パター ンを単にパターンと呼ぶことにする．

3

ふたつの文字列に対する最小汎化

問題

この節では，与えられる文字列がふたつの場合につ いて，最小汎化問題を解く O(nm) 時間アルゴリズムを 与える．ここで，n と m はそれぞれふたつの入力文字 列の長さである．σ と τ を入力文字列とする．本節では n =|σ|，m = |τ| とする．アルゴリズムは，文字列の最 大共通部分文字列や編集距離などの類似度を計算する動 的計画法と類似している．LCG(σ, τ ) を{σ, τ} ⊆ L(p) を満たすパターン p の最大有効長とし， [LCG(σ, τ ) を そのような p において末尾が変数でない文字であるも のの最大有効長，LCG(σ, τ ) を末尾が変数であるもの] の最大有効長とする．[LCG において，対応するパター ンが存在しないときは_{−∞ をとると定義する．このと} き明らかに LCG(σ, τ ) = max{[LCG(σ, τ ), ]LCG(σ, τ )} である． 例 1. Σ ={0, 1}, V = {v1, v2, . . .} とする．σ = 010101, τ = 000111 のとき， LCG(σ, τ ) = ∥0v101v21∥ = 4, [ LCG(σ, τ ) = ∥0v101v21∥ = 4, ] LCG(σ, τ ) = ∥0v101v2v3∥ = 3 である． 例 2. Σ ={0, 1}, V = {v1, v2, . . .} とする．σ = 010100, τ = 11011 のとき， LCG(σ, τ ) = ∥v1101v2∥ = 3, [ LCG(σ, τ ) = −∞, ] LCG(σ, τ ) = ∥v1101v2∥ = 3 である． 提案する動的計画法は，σ と τ のすべての非空な接 頭辞の対に対して，LCG と ][ LCG の値を計算する．以 下の補題は，そのベースケースである． 補題 1. 任意の 2≤ i ≤ n と 2 ≤ j ≤ m について， [ LCG(σ1, τ1) = { 1 (σ[1] = τ [1]) −∞ (σ[1] ̸= τ[1]) [ LCG(σ1, τj) = −∞ [ LCG(σi, τ1) = −∞. 任意の 1≤ i ≤ n と 1 ≤ j ≤ m について， ] LCG(σ1, τj) = 0 ] LCG(σi, τ1) = 0 である． 補題 1 は定義より明らかであるが，2 ≤ i ≤ n と 2≤ j ≤ m における [LCG(σ1, τj)(同様に [LCG(σi, τ1)) には注意が必要で，たとえ σ1と τjの末尾が一致してい たとしても，パターン xa(x は変数，a = σ[1]) は τjを 生成できるが，σ1を生成できない．これは，代入操作 は非空なパターンでのみ可能であることから導かれる． 2≤ i ≤ n と 2 ≤ j ≤ m における，[LCG(σi, τj) は以 下の再帰式によって計算できる． 補題 2. 任意の 2 ≤ i ≤ n と 2 ≤ j ≤ m において， [ LCG(σi, τj) は      max { [ LCG(σi−1, τj−1), ] LCG(σi₋₁, τj₋₁) } + 1 (σ[i] = τ [j]) −∞ (σ[i]̸= τ[j])

によって計算可能である． 証明. σ[i]̸= τ[j] の場合，補題は明らかであるため，以 下では σ[i] = τ [j] の場合を考える． パターン p を有効長が [LCG(σi, τj) で{σi, τj} ⊆ L(p) かつ末尾が変数でない文字であるとする．このとき， σ[i] = τ [j] = a とすると p = p′a を満たすパターン p′で σi₋₁と τj₋₁を生成するものが存在する．よって∥p∥ = ∥p′_{a∥ ≤ LCG(σi} −1, τj₋₁) + 1 より， [LCG(σi, τj) ≤ max{[LCG(σi−1, τj−1), ]LCG(σi−1, τj−1)} + 1 である． 逆に有効長が LCG(σi−1, τj−1) であるようなパター ン p′で_{σi−1, τj−1} ⊆ L(p′) を満たすものを考える と，p = p′a とすると，σi−1, τj−1を生成する p′への代 入を p に適用すると σiと τj が生成できる．よって逆 側の不等式も成立するため，補題が得られる． 同様にLCG(σ] i, τj) についても以下の再帰式によっ て計算できる． 補題 3. 任意の 2 ≤ i ≤ n と 2 ≤ j ≤ m において， ] LCG(σi, τj) は max{[LCG(σi−1, τj−1), ]LCG(σi, τj−1), ]LCG(σi−1, τj)} によって計算可能である． 証明. ]LCG(σi, τj) = 0 のとき， [LCG(σi₋₁, τj₋₁) = −∞ と ]LCG(σi, τj₋₁) = ]LCG(σi₋₁, τj) = 0 より，補 題が成り立つ． ] LCG(σi, τj)≥ 1 のとき, ] LCG(σi, τj) = max 1≤i′<i, 1≤j′<j [ LCG(σi′, τj′) (1) が成り立てば，]LCG(σi, τj−1) = max 1≤i′<i, 1≤j′<j−1 [ LCG(σi′, τj′) とLCG(σ] i−1, τj) = max 1≤i′<i−1, 1≤j′<j [ LCG(σi′, τj′) より補題が 成り立つので，以下では等式 (1) を示す． パターン p を有効長が ]LCG(σi, τj) で{σi, τj} ⊆ L(p) かつ末尾が変数であるとする．このとき，p の先頭から p に現れる最も後ろの変数でない文字 ( ]LCG(σi, τj)≥ 1 より p に少なくともひとつ以上の変数でない文字が含 まれる) までを取り出した p の接頭辞を p′ とすると ∥p∥ = ∥p′_{∥ であり，p}′_{はある整数 i}′_{, j}′_{(1≤ i}′_{< i, 1≤} j′ < j) に対して{σi′, τj′} ⊆ L(p′) となる．p′の末尾 は変数でない文字であるから，LCG(σ] i, τj) = ∥p′∥ ≤ max 1≤i′<i, 1≤j′<j [ LCG(σi′, τj′) が成り立つ． 逆に， max 1≤i′<i, 1≤j′<j [ LCG(σi′, τj′) を達成するパラメータ i′, j′ に対して，有効長がLCG(σ] i′, τj′) で σi′, τj′ を生成す るパターン p′が存在して，p = p′x(x は p′に現れない 新たな変数) とすれば，{σi, τj} ⊆ L(p) となる．よって 逆の不等式も成立するため等式 (1) が成り立ち，補題 が得られる． 補題 1，補題 2 および補題 3 の再帰式を用いること で，O(nm) 時間で LCG(σ, τ ) を計算することが可能で ある．また，これらの計算した値から実際のパターン を構成することも，動的計画法の解の復元の標準的な テクニックで可能である．

4

文字列集合に対する最小汎化問題

前節では入力の文字列がふたつの場合を考えたが，本 節ではそれを一般化した場合を考える．いま，入力され る文字列が σ1_{, σ}2_{, . . . , σ}k_{の k 個である場合を考える．} LCGk(σ1, σ2, . . . , σk) を{σ1, σ2, . . . , σk} ⊆ L(p) を満 たすパターン p の最大有効長とし，[LCGk(σ1, σ2, . . . , σk) をそのような p において末尾が変数でない文字である ものの最大有効長，LCG]k(σ1, σ2, . . . , σk) を末尾が変 数であるものの最大有効長とする．LCG[k において， 対応するパターンが存在しないときは_{−∞ をとると} 定義する．このとき明らかに LCGk(σ1, σ2, . . . , σk) = max{[LCGk(σ1, σ2, . . . , σk), ]LCGk(σ1, σ2, . . . , σk)} で ある． 一般の文字列集合における最小汎化問題は, 前節で議 論した方法と同様にして動的計画法を構成できる． 具 体的には σ1_{, σ}2_{, . . . , σ}k_{のすべての非空な接頭辞の組み} 合わせに対して, [LCGkとLCG]kの値を計算すること で解くことができる．すなわち，ベースケースとして 長さ 1 の接頭辞を含む入力に対する [LCGk とLCG]k， および以下の再帰式 (補題 4，補題 5) によって計算で きる． 補題 4. 任意の 2≤ i1≤ |σ1|, . . . , 2 ≤ ik ≤ |σk| におい て，[LCGk(σ1i1, . . . , σ k ik) は σ 1_[i 1] =· · · = σk[ik] のとき max { [ LCGk(σi11−1, . . . , σ k ik−1), ] LCGk(σi11−1, . . . , σ k ik−1) } + 1, そうでないとき，_{−∞ によって計算可能である．} 補題 5. 任意の 2≤ i1 ≤ |σ1|, . . . , 2 ≤ ik ≤ |σk| にお いて，LCG]k(σi11, . . . , σ k ik) は max                  [ LCGk(σ1i1−1, σ 2 i2−1, . . . , σ k ik−1), ] LCGk(σ1i1−1, σ 2 i2, . . . , σ k ik), ] LCGk(σ1i1, σ 2 i2−1, . . . , σ k ik), .. . ] LCGk(σ1i1, σ 2 i2, . . . , σ k ik−1)                  によって計算可能である．

補題 4，補題 5 の正しさの証明は，第 3 節の補題 2， 補題 3 とほぼ同じであるので省略する．k 個の入力文 字列の最大長が n であるとき，ベースケースと，補題 4 および補題 5 の再帰式を用いることで，O(nk) ステッ プの再帰によって LCGk(σ1, . . . , σk) を計算することが 可能である．LCG]kは毎ステップ時にサイズ k + 1 の max を取るので，この問題は O(knk_{) 時間で解くこと} ができる．

5

最小汎化問題の困難性

k を非負整数とする．k-CNFSAT とは，CNFSAT の インスタンスにおいて，各節が高々k 個のリテラルを 持つと制限した問題である．n 変数の k-CNFSAT を解 く O(2δn_{) 時間アルゴリズムが存在するような δ の下} 限 (infinimum) を skとする．強指数時間仮説 (Strong

Exponential Time Hypothesis, SETH) とは s_∞= 1 で あるとする仮説である [10, 11]．この仮説が正しい場合 に導かれるひとつの結論は，任意の ε > 0 において一 般の CNFSAT を解く O(2(1−ε)n_{) 時間アルゴリズムが} 存在しないことである． Williams [14] は強指数時間仮説の元で，与えられふ たつの d 次元ベクトル集合の中に，直交するものが存在 するかを判定する問題の計算時間の下界を与えた．こ れらを元にして，“多項式時間の中の困難性” の枠組み が発展し，いくつかの既存のアルゴリズムの改善が難 しいことが明らかにされてきた． 長さが n の (文字) 列において，それらの間の類似 度を計算する実行時間が O(n2_{) の動的計画法が設計} できることは古くから知られているが，それらの結 果の実行時間の指数の肩を 2 から 1.99· · · へ改善す ることはできていない．例えば，最大共通部分文字列 に対する最善なアルゴリズムは，アルファベットサイ ズが定数であれば O(n2_{/ log}2 n) [13]，任意の場合は O(n2(log log n)/ log2n) [6, 9] である．これらの実行時

間は SETH を仮定することで O(n2−ε_{) へは改善できな} いことが示されている [1, 8]．他にも，Fr´echet 距離 [7]， 局所アラインメント [2]，編集距離 [5]， Dynamic time warping 距離 [1, 8] などは，SETH が正しいと仮定す ると同様な改善が不可能であることが示されている． この節では，SETH を仮定すると最小汎化問題に対 する提案アルゴリズムの改善が困難であることを示す． 定理 3. SETH が正しいならば，ε > 0 において最小汎 化問題を解く O(n2−ε_{) 時間アルゴリズムは存在しない．} この定理を証明するために，以下の定理を用いる． 定理 4 ([1, 8]). SETH が正しいならば，ε > 0 におい て最大共通部分文字列問題を解く O(n2−ε_{) 時間アルゴ} リズムは存在しない． 長さが n のふたつの文字列 σ, τ ∈ Σ∗_{に対して，σ と} τ の最大共通部分文字列の長さを LCS(σ, τ ) とする．文 字列 σ, τ が与えられたとき，以下のように文字列 σ′_{, τ}′ を構成する．σ に対して，各文字の前後に相異なる記 号 cσi∈ Σ/ ∗を挿入し σ′を得る．つまり， σ′= cσ0σ[1]cσ1σ[2]· · · cσn−1σ[n]cσn である．ただし，任意の 0≤ i < j ≤ n において cσi̸= cσjとする．同様に τ についても cτiを挿入し，τ′を得 る．ここで，τ に対して挿入した記号は σ に対して挿 入した記号とは異なるものを用いる．このとき，以下 の補題が成り立つ． 補題 6. LCS(σ, τ ) = LCG(σ′, τ′). 証明. p を|p| = LCS(s, t) を達成する s と t の共通部 分文字列とすると，上で構成したものと同様に p の各 文字の前後に変数記号を挿入したパターンを p′ とす る．明らかに_{s′_{, t}′_{} ⊆ L(p}′_{) であるため，LCS(s, t)≤} LCG(s′, t′) である． p′ を_∥p′_{∥ = LCG(s}′, t′) を満たし s′と t′を生成す るパターンとする．このとき p′ の各文字の前後には 変数記号が存在する．これは，s′ と t′のそれぞれは， Σ の記号の前後にユニークな Σ に含まれない記号が存 在することより得られる．よって，そのような変数記 号を p′から削除すると，p ∈ Σ∗_{である文字列が得ら} れ，これは s と t の共通部分文字列である．そのため， LCS(s, t)≥ LCG(s′, t′) が得られる． 長さが n のふたつ文字列 s, t が与えられたとき，上で 述べたように s′_{, t}′を構成する．このとき，_|s′_{| = |t}′_{| =} 2n + 1 である．もし，最小汎化問題を解く O(n2−ε) 時 間アルゴリズムが存在するとき，補題 6 より，そのアル ゴリズムを用いることで，s と t の最大共通部分文字列 が O(n2−ε_{) 時間で得ることができる．そのため，定理} 4 より SETH が反駁される．よって定理 3 が得られた． ここで示した最大共通部分文字列から最小汎化問題 への帰着は，入力の文字列が k≥ 2 である場合にも有 効である．そのため，以下の系が得られる． 系 1. 与えられる文字列の個数を入力も一部としたと き，最小汎化問題は NP 困難である． 系 2. SETH が正しいならば，ε > 0 において最小汎化 問題を解く O(nk_{−ε) 時間アルゴリズムは存在しない．} ここで，k は入力の文字列の数とする． これらの系はそれぞれ最大共通部分文字列の NP 困 難性 [12] と SETH を用いた O(nk−ε_{) の下界 [1] より得} られる．

6

おわりに

本研究では，文字列に対する最小汎化問題を解く多 項式時間アルゴリズムを設計した．具体的には，与え られた文字列がふたつの場合は，O(nm) 時間で動作す るアルゴリズムである．ここで，n と m は与えられる ふたつの文字列の長さとする．さらに，このアルゴリ ズムを k 個の文字列に一般化したとき，O(knk_{) 時間で} 動作するアルゴリズムを与えた．n は入力文字列の最 大長である．これらのアルゴリズムは強指数時間仮説 (SETH) の下でほぼ最適であることを最大共通部分文 字列からの帰着を与えることで示した． 今後の課題としては以下のような方向性が考えられ る．最大共通部分文字列問題に対して，O(n2_{−ε) 時間} の近似アルゴリズムの存在は重要な未解決問題である． |Σ| が定数であるとき，定数近似率の線形時間アルゴ リズムは以下のようにして得られる．ふたつの文字列 において，共通して最も出現するを文字をカウントし， その文字のみからなる文字列を解とする．この単純な アルゴリズム 1/|Σ| 近似を達成することが知られてい る．同様の手法は単純には最小汎化問題には適用でき ないため，そのような近似率を達成することができる かは今後の課題である．SETH に基づく最大共通部分 文字列の下界はアルファベットサイズが定数でも成立 するが，今回与えた最小汎化問題への帰着は任意のサ イズのアルファベットが必要である．そのため，定数 アルファベットのみを使って最小汎化問題への帰着が できるかどうかは興味深い問題であろう．

謝辞

本研究の一部は JSPS 科研費 JP17H01788，JST CREST JPMJCR1401 の助成を受けたものである．

参考文献

[1] A. Abboud, A. Backurs, V. V. Williams: Tight hardness results for LCS and other sequence sim-ilarity measures. In Proceedings of FOCS 2015, IEEE, pp. 59–78 (2015)

[2] A. Abboud, V. V. Williams, O. Weimann: Con-sequences of faster alignment of Con-sequences. In

Proceedings of ICALP 2014, LNCS vol. 8572,

pp.39–51 (2014)

[3] D. Angluin: Finging Patterns Common to a Set of Strings. Journal of Computer and System

Sci-ences, 21(1), 46–62 (1979)

[4] H. Arimura, T. Shinohara, S. Otsuki: Finging minimal generalizations for unions of pattern lan-guages and its application to inductive infer-ence from positive data. In Proceedings of STACS

1994, LNCS, vol. 775, pp. 649–660 (1994)

[5] A. Backurs, P. Indyk: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Un-less SETH is False). SIAM Journal on

Comput-ing, 47(3), 1087–1097 (2018)

[6] P. Bille, M. F.-Colton: Fast and compact reg-ular expression matching. Theoretical Computer

Science, 409(3), 486–496 (2008)

[7] K. Bringmann: Why walking the dog takes time: Fr´echet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings of

FOCS 2014, IEEE, pp. 661–670 (2014)

[8] K. Bringmann, M. K¨unnemann: Quadratic con-ditional lower bounds for string problems and dynamic time warping. In Proceedings of FOCS

2015, IEEE, pp. 79–97 (2015)

[9] S. Grabowski: New tabulation and sparse dy-namic programming based techniques for se-quence similarity problems. Discrete Applied

Mathematics, 212, 96–103 (2016)

[10] R. Impagliazzo, R. Paturi: On the complexity of

k-sat. Journal of Computer and System Science,

62(2), 367–375 (2001)

[11] R. Impagliazzo, R. Paturi, F. Zane: Which problems have strongly exponential complexity?

Journal of Computer and System Science, 63(4),

512–530 (2001)

[12] D. Maier: The complexity of some problems on subsequences and supersequences. Journal of the

ACM, 25(2), 322–336 (1978)

[13] W. J. Masek, M. S. Paterson: A faster algorithm computing string edit distances. Journal of

Com-puter and System Science, 20(1), 18–31 (1980)

[14] R. Williams: A new algorithm for optimal 2-constraint satisfaction and its implications.

Theoretical Computer Science, 348(2), 357–365

(2005)

[15] 榊原康文, 小林聡, 横森貴: 計算論的学習. 培風館 (2001)