最短共通スーパーシーケンス

コンピュータサイエンスでは、2 つのシーケンスXとYの最短共通スーパーシーケンスは、 XとY をサブシーケンスとして持つ最短のシーケンスです。これは、最長共通サブシーケンス問題と密接に関連した問題です。 2 つのシーケンスX = < x ₁ ,...,x _m > とY = < y ₁ ,...,y _n > がある場合、シーケンスU = < u ₁ ,...,uk _>は、Uから項目を削除して X と Y を生成できる場合、XとYの共通スーパーシーケンスです。

最短共通スーパーシーケンス (SCS) は、長さが最小の共通スーパーシーケンスです。最短共通スーパーシーケンス問題では、2 つのシーケンスXとYが与えられ、これらのシーケンスの最短の共通スーパーシーケンスを見つけることが課題となります。一般に、SCS は一意ではありません。

2 つの入力シーケンスの場合、最長共通サブシーケンス(LCS)から SCS を簡単に形成できます。たとえば、XとYの最長共通サブシーケンスはZです。非 LCS シンボルを元の順序を維持しながらZに挿入すると、最短共通スーパーシーケンスUが得られます。特に、この式は任意の 2 つの入力シーケンスに当てはまります。 $[1..m]=abcbdab$ $[1..n]=bdcaba$ $[1..L]=bcba$ $[1..S]=abdcabdab$ $L+S=m+n$

3つ以上の入力シーケンスの最短共通スーパーシーケンスと最長共通サブシーケンスの間には、同様の関係はありません。（特に、LCSとSCSは双対問題ではありません。）ただし、両方の問題は、シーケンスの数、最大長がシーケンスの最大長である動的計画法を使用して時間内に解決できます。任意の数の入力シーケンスの一般的なケースでは、問題はNP困難です。^[1] $O(n^{k})$ $k$ $n$

最短共通超文字列

これに密接に関連する問題として、有限の文字列集合S = { s ₁ , s ₂ ,..., s _n } のスーパー文字列である最小長の文字列を見つけるという問題も NP 困難です。^[2] 長年にわたっていくつかの定数係数近似が提案されており、現在最もよく知られているアルゴリズムの近似係数は 2.475 です。^{[3]ただし、おそらく最も簡単な解決策は、}重み付きセットカバーのインスタンスとして問題を再定式化し、セットカバーインスタンスの最適解の重みが最短のスーパー文字列Sの長さの 2 倍未満になるようにすることです。次に、重み付きセットカバーのO(log( n )) 近似を使用して、最短のスーパー文字列のO(log( n )) 近似を取得できます (これは定数係数近似ではないことに注意してください)。

このアルファベットの任意の文字列xについて、 P ( x ) をxの部分文字列であるすべての文字列の集合として定義します。集合被覆のインスタンスIは次のように定式化されます。

Mを空にします。
文字列s _iとs _jの各ペアについて、 s _iの最後のk 個のシンボルがs _jの最初のk個のシンボルと同じである場合、 s _iとs _jの最大重複を伴う連結で構成される文字列をMに追加します。
集合カバーインスタンスのユニバースをSと定義する ${\mathcal {U}}$
宇宙の部分集合を{ P ( x ) | x∈S∪M }と定義する。
各サブセットP (x)のコストをxの長さ | x |と定義します。

インスタンスIは重み付き集合カバーアルゴリズムを使用して解決することができ、アルゴリズムは重み付き集合カバーアルゴリズムがP ( x )を出力する文字列xの任意の連結を出力することができる。^[4]

例

集合S = { abc, cde, fab }を考えます。これは重み付き集合カバーインスタンスのユニバースになります。この場合、M = { abcde, fabc }です。すると、ユニバースの部分集合の集合は次のようになります。

{\begin{aligned}\{P(x)|x\in S\cup M\}&=\{P(x)|x\in \{abc,cde,fab,abcde,fabc\}\}\\&=\{P(abc),P(cde),P(fab),P(abcde),P(fabc)\}\}\\&=\{\{a,b,c,ab,bc,abc\},\{c,d,e,cd,de,cde\},\ldots ,\{f,a,b,c,fa,ab,bc,fab,abc,fabc\}\}\\\end{aligned}}

それぞれコストは 3、3、3、5、4 です。

参考文献

^ David Maier (1978). 「サブシーケンスとスーパーシーケンスに関するいくつかの問題の複雑性」J. ACM . 25 (2). ACM Press: 322–336. doi : 10.1145/322063.322075 . S2CID 16120634.
^ カリ・ジョコ・ライハ、エスコ・ウコネン (1981)。「バイナリアルファベットに関する最も短い一般的な超列問題は NP 完全です。」理論的なコンピューターサイエンス。16 (2): 187–198。土井：10.1016/0304-3975(81)90075-x。
^ Matthias Englert、Nicolaos Matsakis、Pavel Vesel (2022)。「重複と長さの比率によるサイクル分類を使用した最短スーパーストリングの近似保証の改善」。第54回ACM SIGACTコンピューティング理論シンポジウムの議事録(PDF)。pp. 317–330。doi : 10.1145 / 3519935.3520001。ISBN 9781450392648. S2CID 243847650。
^ ヴァジラニ、20ページ。

ゲーリー、マイケル R. ;ジョンソン、デビッド S. (1979)。コンピュータと扱いにくさ: NP 完全性理論へのガイド。WH フリーマン。p. 228 A4.2: SR8。ISBN 0-7167-1045-5.ZBL 0411.68039 .
Szpankowski, Wojciech (2001)。シーケンス上のアルゴリズムの平均ケース分析。Wiley -Interscience 離散数学と最適化シリーズ。Philippe Flajolet による序文付き。チチェスター: Wiley。ISBN 0-471-24063-X.ZBL 0968.68205 .
Vazirani、Vijay V. (2001)、近似アルゴリズム、Springer-Verlag、ISBN 3-540-65367-8

外部リンク

アルゴリズムとデータ構造の辞書: 最短共通スーパーシーケンス
最短共通スーパーシーケンス
1092. 最短共通スーパーシーケンス
最短共通スーパーシーケンス
最短共通スーパーシーケンス
最短共通スーパーシーケンス (SCS)

[1] David Maier (1978). 「サブシーケンスとスーパーシーケンスに関するいくつかの問題の複雑性」J. ACM . 25 (2). ACM Press: 322–336. doi : 10.1145/322063.322075 . S2CID 16120634.

[2] カリ・ジョコ・ライハ、エスコ・ウコネン (1981)。「バイナリアルファベットに関する最も短い一般的な超列問題は NP 完全です。」理論的なコンピューターサイエンス。16 (2): 187–198。土井：10.1016/0304-3975(81)90075-x。

[3] Matthias Englert、Nicolaos Matsakis、Pavel Vesel (2022)。「重複と長さの比率によるサイクル分類を使用した最短スーパーストリングの近似保証の改善」。第54回ACM SIGACTコンピューティング理論シンポジウムの議事録(PDF)。pp. 317–330。doi : 10.1145 / 3519935.3520001。ISBN 9781450392648. S2CID 243847650。

[FOOTNOTEVazirani20-4] ヴァジラニ、20ページ。