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

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

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

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

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

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

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

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

Пусть M пусто.
Для каждой пары строк s _i и s _j , если последние k символов s _i такие же, как первые k символов s _j , тогда добавьте строку к M, которая состоит из конкатенации с максимальным перекрытием s _i с s _j .
Определите вселенную установленного экземпляра обложки как S ${\mathcal {U}}$
Определим набор подмножеств вселенной как { 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). «Сложность некоторых задач о подпоследовательностях и суперпоследовательностях». J. ACM . ACM Press. 25 (2): 322–336. DOI : 10.1145 / 322063.322075 .
^ Kari-Jouko Räihä, Esko Ukkonen (1981). «Самая короткая общая задача суперпоследовательностей над двоичным алфавитом является NP-полной» . Теоретическая информатика . 16 (2): 187–198. DOI : 10.1016 / 0304-3975 (81) 90075-х .
^ Марек Карпински и Ричард Шмид (2013). «Об улучшенных результатах о несовместимости кратчайших суперструн и связанных с ними задачах» (PDF) . Материалы 19-го CATS CRPIT . 141 : 27–36.
^ Вазирани , стр. 20.

Гарей, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . WH Freeman. п. 228 A4.2: SR8 . ISBN 0-7167-1045-5. Zbl 0411.68039 .
Шпанковский, Войцех (2001). Анализ среднего случая алгоритмов на последовательностях . Серия Wiley-Interscience по дискретной математике и оптимизации. С предисловием Филиппа Флажоле. Чичестер: Вайли. ISBN 0-471-24063-X. Zbl 0968.68205 .
Вазирани, Виджай В. (2001), Алгоритмы приближения , Springer-Verlag, ISBN 3-540-65367-8

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

Словарь алгоритмов и структур данных: кратчайшая общая суперпоследовательность

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

[2] Kari-Jouko Räihä, Esko Ukkonen (1981). «Самая короткая общая задача суперпоследовательностей над двоичным алфавитом является NP-полной» . Теоретическая информатика . 16 (2): 187–198. DOI : 10.1016 / 0304-3975 (81) 90075-х .

[3] Марек Карпински и Ричард Шмид (2013). «Об улучшенных результатах о несовместимости кратчайших суперструн и связанных с ними задачах» (PDF) . Материалы 19-го CATS CRPIT . 141 : 27–36.

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

[1]