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

Если различаешь подстроку и подпоследовательность - переходи к «Теперь сам».

Как думаешь: самое большое перекрытие всегда выгодно?

Есть фрагменты журнала AAAB, AABA, ABAA. Первая пара склеивается на трёх символах; вторая тоже. Кажется, что локальная экономия должна вести к лучшей общей строке. Но после склейки два фрагмента становятся одним блоком: их уже нельзя независимо приставить к другим концам. Локальное решение выбрало часть будущего порядка. Предскажи, может ли эта фиксация стоить больше сэкономленных символов.

В задаче важны именно соседние позиции. Строка ABC содержит AC как подпоследовательность: можно выкинуть B. Подстрокой AC она не содержит. Здесь символы выкидывать нельзя. Если спецификация допускает пропуски, все дальнейшие алгоритмы решают другую задачу.

На что это похоже

Представь несколько полосок с печатью, которые кладут на одну ленту. Совпадающие концы разрешается наложить, сохранив все буквы. Но полоску нельзя разрезать и переставить её середину. Убрать полоску, уже целиком лежащую внутри другой, безопасно: более длинная уже выполняет её требование. А заменить две полоски их объединением - дополнительное решение о порядке, которое может помешать остальным.

Механизм: где спрятался выбор порядка

Обозначим через ov(a,b) длину наибольшего суффикса a, равного префиксу b. При склейке дописывается b[ov(a,b):]; прибавка к длине равна len(b) − ov(a,b). Направление существенно: ov(a,b) обычно отличается от ov(b,a).

После удаления вложенных строк оптимальную надстроку можно рассматривать как порядок их появления. Если первая строка уже написана, каждая следующая платит длиной неперекрытого хвоста. Поэтому минимизация длины соответствует максимизации суммы соседних перекрытий. Получается задача на ориентированном полном графе: вершины - строки, вес перехода - сэкономленные символы. Нужен путь через все вершины. В этой формулировке узнаётся трудность выбора порядка из урока о коммивояжёре.

Для n фрагментов перебираются n! порядков. Динамика хранит лучшее перекрытие для подмножества строк и последней строки: dp[mask][last]. При добавлении новой строки достаточно знать последний фрагмент, поскольку остальные уже находятся слева. Получается O(n²·2ⁿ) переходов после вычисления перекрытий. Это точный алгоритм, пока число строк невелико; длина самих строк тоже входит в стоимость подготовки.

Жадный алгоритм рассматривает все пары, выбирает наибольшее перекрытие, заменяет пару склейкой и повторяет. Он всегда выдаёт допустимый результат. Доказательство качества требует отдельной теоремы; выражение «каждый шаг сэкономил больше» такой теоремой не является. Не приписывай ему коэффициент два только потому, что он напоминает остовную эвристику для маршрута.

Правило

Кратчайшая общая надстрока минимизирует суммарную длину после совместимого выбора перекрытий. Наибольшее отдельное перекрытие не обязано входить в оптимальный порядок. Перед поиском удаляют дубликаты и вложенные строки; иначе формулировка через порядок всех фрагментов становится неудобной и может вводить в заблуждение.

Разбор: перебор против жадной склейки

Файл считает оба результата и сам находит небольшой контрпример среди четырёхбуквенных строк. Полный поиск здесь нужен для проверки эвристики, а не для обработки реальных геномов.

from itertools import permutations, product, combinations


def perekrytie(a, b):
    for k in range(min(len(a), len(b)), -1, -1):
        if a.endswith(b[:k]):
            return k


def skleit(a, b):
    if b in a:
        return a
    return a + b[perekrytie(a, b):]


def zhadno(stroki):
    s = list(stroki)
    while len(s) > 1:
        _, i, j = max((perekrytie(a, b), i, j)
                      for i, a in enumerate(s)
                      for j, b in enumerate(s) if i != j)
        novaya = skleit(s[i], s[j])
        s = [a for k, a in enumerate(s) if k not in (i, j)]
        s.append(novaya)
    return s[0]


def tochno(stroki):
    otvety = []
    for p in permutations(stroki):
        s = p[0]
        for b in p[1:]:
            s = skleit(s, b)
        otvety.append(s)
    return min(otvety, key=lambda s: (len(s), s))


slova = [''.join(p) for p in product('AB', repeat=4)]
for primer in combinations(slova, 3):
    g, t = zhadno(primer), tochno(primer)
    if len(g) > len(t):
        print('строки:', *primer)
        print('жадно:', g, len(g))
        print('точно:', t, len(t))
        print('содержит всё:', all(x in g for x in primer))
        break

строки: AAAA AAAB BAAA
жадно: BAAABAAAA 9
точно: BAAAAB 6
содержит всё: True

Здесь порядок разрешения равных перекрытий фиксирован выражением max: при равенстве выбираются большие индексы. Другой порядок может исправить один пример, но не превращает локальный критерий в доказательство оптимальности. Перебор сравнивает все шесть порядков трёх фрагментов. Во всех проверяемых фрагментах одинаковая длина, вложенных разных строк среди них нет.

Разбор: покрытие фрагментов и упаковка ресурсов

Для строк CAB, ABC, BCA существует надстрока CABCA длины пять. Склейки по два символа дают экономию четыре относительно трёх отдельных строк длины девять. Строку AB можно добавить к входу бесплатно: она уже внутри CAB и ABC. Увеличение числа требований не всегда увеличивает оптимальную длину.

С покрытием множеств связь видна через позиции: выбранная итоговая строка должна покрыть все требования «содержит фрагмент». Но стоимость склеек зависит от порядка, а не только от того, какие требования выполняются. Нельзя взять гарантию жадного покрытия ln n и объявить её гарантией жадного перекрытия. В упаковке множеств, наоборот, совместное использование ресурса запрещено; здесь совместное использование совпадающих букв как раз экономит место.

Что ломается без этого

Если забыть удалить вложенную строку, программа может специально вставить её второй раз и раздуть результат. Если посчитать перекрытие симметричным, получится недопустимое направление склейки. Если после выбора пары не пересчитать кандидатов, следующие перекрытия будут относиться к уже отсутствующим фрагментам. Каждый такой дефект проверяется на маленьком наборе, где ответ легко выписать вручную.

Зачем это в работе

Компактное хранение словарей строк, восстановление последовательностей и сборка фрагментов используют этот сюжет. Реальная сборка генома добавляет ошибки чтения, повторяющиеся области и статистику покрытия; чистая задача надстроки не обещает восстановить биологически правильную последовательность. В инженерной задаче сначала фиксируют точную модель, затем сравнивают эвристику с точным решателем на малых входах.

Теперь сам

Вход: ABCD, BCD, CDEF. Какие строки можно убрать? Какова кратчайшая общая надстрока?