Кратчайшая общая суперпоследовательность

В информатике кратчайшая общая суперпоследовательность двух последовательностей X и Y — это кратчайшая последовательность, которая имеет X и Y в качестве подпоследовательностей . Это проблема, тесно связанная с проблемой самой длинной общей подпоследовательности . Если даны две последовательности X = < x 1 ,...,x m > и Y = < y 1 ,...,y n >, последовательность U = < u 1 ,...,uk > является общей суперпоследовательностью X и Y , если элементы могут быть удалены из U для получения X и Y .

Кратчайшая общая суперпоследовательность (SCS) — это общая суперпоследовательность минимальной длины. В задаче о кратчайшей общей суперпоследовательности даны две последовательности X и Y , и задача состоит в том, чтобы найти кратчайшую возможную общую суперпоследовательность этих последовательностей. В общем случае SCS не является уникальной.

Для двух входных последовательностей SCS может быть легко сформирована из самой длинной общей подпоследовательности (LCS). Например, самая длинная общая подпоследовательность X и Y — это Z. Вставляя символы, не входящие в LCS, в Z , сохраняя их исходный порядок, мы получаем самую короткую общую суперпоследовательность U. В частности, уравнение справедливо для любых двух входных последовательностей. [ 1.. м ] = а б с б г а б {\displaystyle [1..m]=abcbdab} [ 1.. н ] = б г с а б а {\displaystyle [1..n]=bdcaba} [ 1.. Л ] = б с б а {\displaystyle [1..L]=bcba} [ 1.. С ] = а б г с а б г а б {\displaystyle [1..S]=abdcabdab} Л + С = м + н {\displaystyle L+S=m+n}

Аналогичной связи между кратчайшими общими суперпоследовательностями и длиннейшими общими подпоследовательностями трех или более входных последовательностей не существует. (В частности, LCS и SCS не являются двойственными задачами .) Однако обе задачи могут быть решены со временем с помощью динамического программирования, где — число последовательностей, а — их максимальная длина. Для общего случая произвольного числа входных последовательностей задача является NP-трудной . [1] О ( н к ) {\displaystyle O(n^{k})} к {\displaystyle к} н {\displaystyle n}

Самая короткая общая суперстрока

Тесно связанная задача поиска строки минимальной длины, которая является суперстрокой конечного набора строк S = { s 1 , s 2 ,..., s n }, также является NP-трудной. [2] За прошедшие годы было предложено несколько приближений с постоянным множителем, и самый известный на данный момент алгоритм имеет коэффициент приближения 2,475. [3] Однако, возможно, самым простым решением будет переформулировать задачу как случай взвешенного покрытия множеств таким образом, чтобы вес оптимального решения для случая покрытия множеств был меньше удвоенной длины кратчайшей суперстроки S . Затем можно использовать O(log( n ))-приближение для взвешенного покрытия множеств, чтобы получить O(log( n ))-приближение для кратчайшей суперстроки (обратите внимание, что это не приближение с постоянным множителем).

Для любой строки x в этом алфавите, определим P ( x ) как множество всех строк, которые являются подстроками x . Экземпляр I множества cover формулируется следующим образом:

  • Пусть M будет пустым.
  • Для каждой пары строк s i и s j , если последние k символов строки s i совпадают с первыми k символами строки s j , то к M добавляется строка , состоящая из конкатенации с максимальным перекрытием строки s i с s j .
  • Определить вселенную экземпляра множества обложки как S У {\displaystyle {\mathcal {U}}}
  • Определим множество подмножеств вселенной как { P ( x ) | x∈S∪M }
  • Определим стоимость каждого подмножества P (x) как | x |, длину x .

Экземпляр I затем может быть решен с помощью алгоритма для взвешенного покрытия множеств, и алгоритм может вывести произвольную конкатенацию строк x, для которой алгоритм взвешенного покрытия множеств выводит P ( x ). [4]

Пример

Рассмотрим множество S = { abc, cde, fab }, которое становится вселенной экземпляра взвешенного множества. В этом случае M = { abcde, fabc }. Тогда множество подмножеств вселенной равно

{ П ( х ) | х ∈ С ∪ М } = { П ( х ) | х ∈ { а б с , с г е , ф а б , а б с г е , ф а б с } } = { П ( а б с ) , П ( с г е ) , П ( ф а б ) , П ( а б с г е ) , П ( ф а б с ) } } = { { а , б , с , а б , б с , а б с } , { с , г , е , с г , г е , с г е } , … , { ф , а , б , с , ф а , а б , б с , ф а б , а б с , ф а б с } } } {\displaystyle {\begin{align}\{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{align}}}

которые имеют стоимость 3, 3, 3, 5 и 4 соответственно.

Ссылки

  1. ^ Дэвид Майер (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. ^ Маттиас Энглерт и Николаос Мацакис и Павел Весел (2022). «Улучшенные гарантии аппроксимации для кратчайших суперстрок с использованием классификации циклов по соотношению перекрытия к длине». Труды 54-го ежегодного симпозиума ACM SIGACT по теории вычислений (PDF) . стр. 317–330. doi :10.1145/3519935.3520001. ISBN 9781450392648. S2CID  243847650.
  4. ↑ Вазирани, стр. 20.ошибка sfn: нет цели: CITEREFVazirani ( помощь )
  • Словарь алгоритмов и структур данных: кратчайшая общая суперпоследовательность
  • Кратчайшая общая суперпоследовательность
  • 1092. Кратчайшая общая суперпоследовательность
  • Кратчайшая общая суперпоследовательность
  • Кратчайшая общая суперпоследовательность
  • Кратчайшая общая суперпоследовательность (SCS)
Получено с "https://en.wikipedia.org/w/index.php?title=Самая короткая_общая_суперпоследовательность&oldid=1188083555"