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

В информатике самая короткая общая суперпоследовательность двух последовательностей X и Y — это самая короткая последовательность, которая имеет X и Y в качестве подпоследовательностей . Эта проблема тесно связана с проблемой самой длинной общей подпоследовательности . Учитывая две последовательности X = < x ₁ ,...,x _m > и Y = < y ₁ ,...,y _n >, последовательность U = < u ₁ ,...,uk _> является общей суперпоследовательностью X , и Y если элементы можно удалить из U, произвести X и Y. чтобы

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

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

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

Кратчайшая общая суперстрока

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

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

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

Затем случай I можно решить с помощью алгоритма покрытия взвешенного набора, и алгоритм может вывести произвольную конкатенацию строк x, для которых алгоритм покрытия взвешенного набора выводит P ( 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 соответственно.

Ссылки

^ Дэвид Майер (1978). «Сложность некоторых задач о подпоследовательностях и суперпоследовательностях» . Дж. АКМ . 25 (2). ACM Press: 322–336. дои : 10.1145/322063.322075 . S2CID 16120634 .
^ Кари-Йуко Райха, Эско Укконен (1981). «Самая короткая общая задача суперпоследовательности в двоичном алфавите является NP-полной». Теоретическая информатика . 16 (2): 187–198. дои : 10.1016/0304-3975(81)90075-х .
^ Маттиас Энглерт, Николаос Мацакис и Павел Весел (2022 г.). «Улучшенная гарантия аппроксимации кратчайших суперстрок с использованием классификации циклов по соотношению перекрытия и длины» . Материалы 54-го ежегодного симпозиума ACM SIGACT по теории вычислений (PDF) . стр. 317–330. дои : 10.1145/3519935.3520001 . ISBN 9781450392648 . S2CID 243847650 .
^ Вазирани , с. 20.

Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. п. 228 А4.2: СР8 . ISBN 0-7167-1045-5 . Збл 0411.68039 .
Шпанковский, Войцех (2001). Анализ среднего случая алгоритмов на последовательностях . Серия Wiley-Interscience по дискретной математике и оптимизации. С предисловием Филиппа Флажоле. Чичестер: Уайли. ISBN 0-471-24063-Х . Збл 0968.68205 .
Vazirani, Vijay V. (2001), Approximation Algorithms , Springer-Verlag, ISBN 3-540-65367-8

Внешние ссылки

[1] Дэвид Майер (1978). «Сложность некоторых задач о подпоследовательностях и суперпоследовательностях» . Дж. АКМ . 25 (2). ACM Press: 322–336. дои : 10.1145/322063.322075 . S2CID 16120634 .

[2] Кари-Йуко Райха, Эско Укконен (1981). «Самая короткая общая задача суперпоследовательности в двоичном алфавите является NP-полной». Теоретическая информатика . 16 (2): 187–198. дои : 10.1016/0304-3975(81)90075-х .

[3] Маттиас Энглерт, Николаос Мацакис и Павел Весел (2022 г.). «Улучшенная гарантия аппроксимации кратчайших суперстрок с использованием классификации циклов по соотношению перекрытия и длины» . Материалы 54-го ежегодного симпозиума ACM SIGACT по теории вычислений (PDF) . стр. 317–330. дои : 10.1145/3519935.3520001 . ISBN 9781450392648 . S2CID 243847650 .

[FOOTNOTEVazirani20-4] Вазирани , с. 20.

[1]

[2]

[3]

[4]