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

В Информатика, то кратчайшая общая суперпоследовательность двух последовательностей Икс и Y - кратчайшая последовательность, имеющая Икс и Y в качестве подпоследовательности. Это проблема, тесно связанная с проблема самой длинной общей подпоследовательности. Учитывая две последовательности Икс = <х1,...,Иксм > и Y = <у1, ..., yп >, последовательность U = 1, ..., тыk > - обычная суперпоследовательность Икс и Y если элементы могут быть удалены из U производить Икс и Y.

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

Для двух входных последовательностей SCS может быть сформирован из самая длинная общая подпоследовательность (LCS) легко. Например, самая длинная общая подпоследовательность Икс и Y является Z. Вставив символы, отличные от LCS, в Z при сохранении их первоначального порядка получаем кратчайшую общую суперпоследовательность U. В частности, уравнение выполняется для любых двух входных последовательностей.

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

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

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

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

  • Позволять M быть пустым.
  • Для каждой пары струн sя и sj, если последний k символы sя такие же, как и первые k символы sj, затем добавьте строку в M который состоит из конкатенации с максимальным перекрытием sя с sj.
  • Определить вселенную установленного экземпляра обложки, чтобы быть S
  • Определите набор подмножеств вселенной как { п(Икс) | Икс ∈ S ∪ M }
  • Определите стоимость каждого подмножества п(x) быть |Икс|, длина Икс.

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

Пример

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

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

Рекомендации

  1. ^ Дэвид Майер (1978). «Сложность некоторых задач о подпоследовательностях и суперпоследовательностях». J. ACM. ACM Press. 25 (2): 322–336. Дои:10.1145/322063.322075.
  2. ^ Кари-Йоуко Райха, Эско Укконен (1981). «Самая короткая общая задача суперпоследовательностей над двоичным алфавитом является NP-полной». Теоретическая информатика. 16 (2): 187–198. Дои:10.1016 / 0304-3975 (81) 90075-х.
  3. ^ Тао Цзян и Мин Ли (1994). «Об аппроксимации кратчайших общих суперпоследовательностей и самых длинных общих подпоследовательностей». SIAM Журнал по вычислениям. 24 (5): 1122–1139. Дои:10.1137 / s009753979223842x.
  4. ^ Марек Карпински и Ричард Шмид (2013). "Об улучшенных результатах о несовместимости кратчайшей суперструны и связанных с ней задачах" (PDF). Материалы 19-го CATS CRPIT. 141: 27–36.
  5. ^ Вазирани, п. 20.

внешняя ссылка