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

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

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

2つの入力シーケンスに対して、最長共通部分シーケンス（LCS）からSCSを簡単に形成できます。例えば、XとYの最長共通部分シーケンスはZです。LCS以外のシンボルを元の順序を維持したままZに挿入すると、最短共通スーパーシーケンスUが得られます。特に、この式は任意の2つの入力シーケンスに対して成立します。 ${\displaystyle [1..m]=abcbdab}$ ${\displaystyle [1..n]=bdcaba}$ ${\displaystyle [1..L]=bcba}$ ${\displaystyle [1..S]=abdcabdab}$ ${\displaystyle L+S=m+n}$

3つ以上の入力シーケンスの最短共通スーパーシーケンスと最長共通サブシーケンスの間には、同様の関係は存在しません（特に、LCSとSCSは双対問題ではありません）。しかし、どちらの問題も動的計画法を用いて1000分以内に解くことができます。ここで、はシーケンスの数、はシーケンスの最大長です。任意の数の入力シーケンスの一般的なケースでは、この問題はNP困難です。^[1]${\displaystyle O(n^{k})}$ ${\displaystyle k}$ ${\displaystyle n}$

最短共通超弦

有限の文字列の集合S = { s ₁ , s ₂ ,..., s _n }のスーパー文字列である最小長の文字列を見つけるという密接に関連する問題も NP 困難です。^[2]さらに、これはAPX完全です。^[3] 長年にわたっていくつかの定数倍近似が提案されており、現在最もよく知られているアルゴリズムの近似係数は 2.475 です。^[4]しかし、おそらく最も簡単な解決策は、集合カバーインスタンスの最適解の重みが最短のスーパー文字列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と定義する${\displaystyle {\mathcal {U}}}$
• 宇宙の部分集合の集合を{ P ( x ) | x∈S∪M }と定義する。
• 各サブセットP (x)のコストを| x |（xの長さ）と定義します。

インスタンスIは重み付き集合被覆アルゴリズムを用いて解くことができ、そのアルゴリズムは重み付き集合被覆アルゴリズムがP ( x )を出力する文字列xの任意の連結を出力することができる。^[5]

例

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

${\displaystyle {\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 です。

参考文献

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. Blum, Avrim, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis. 「最短超弦の線形近似」Journal of the ACM (JACM) 41, no. 4 (1994): 630-647.
4. Matthias Englert、Nicolaos Matsakis、Pavel Vesel (2022). 「重複と長さの比率によるサイクル分類を用いた最短超弦の近似保証の改善」第54回ACM SIGACT計算理論シンポジウム議事録(PDF) pp.  317– 330. doi :10.1145/3519935.3520001. ISBN 9781450392648. S2CID  243847650。
5. ヴァジラニ 2001、20ページ。

• ゲイリー、マイケル・R.、ジョンソン、デイビッド・S. (1979). 『コンピュータとイントラクタビリティ：NP完全性理論へのガイド』WHフリーマン著. p. 228 A4.2: SR8. ISBN 0-7167-1045-5. Zbl  0411.68039.
• Szpankowski, Wojciech (2001).シーケンス上のアルゴリズムの平均ケース解析. Wiley-Interscience Series in Discrete Mathematics and Optimization. Philippe Flajoletによる序文付き. Chichester: Wiley. ISBN 0-471-24063-X. Zbl  0968.68205.
• Vazirani、Vijay V. (2001)、近似アルゴリズム、Springer-Verlag、ISBN 3-540-65367-8

外部リンク

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