Пусть \(\Sigma\) – произвольное множество, которое мы будем называть алфавитом. Через \(\Sigma^{*}\) обозначим множество всевозможных конечных кортежей из элементов из алфавита \(\Sigma\). Мы их будем называть строками или словами. Через \(\Sigma^{+}\) обозначим множество всевозможных строк из алфавита \(\Sigma\), не содержащее пустое слово \(\varepsilon\).
Задача о кратчайшей суперстроке
Конечный алфавит \(\Sigma\) и множество строк \(U=\left\{ s_{1}, \ldots , s_{n}\right\} \subseteq \Sigma^{+}\).
Кратчайшую суперстроку \(s\), т.е. строку, которая содержит каждую строку \(s_{i}\) как подстроку.
Если какая-то строка \(s\) в \(U\) есть подстрока другой строки \(t\), то вместо \(U\) можно решать задачу для \(U' = U \setminus \left\{ s\right\}\). Ясно, что оптимальное решение у этих задач одинаковое. Поэтому, без ограничения общности, мы будем в дальнейшем считать, что каждая строка в \(U\) “уникальна”, т.е. никакая строка \(t\) не содержит другую строку \(s\) как подстроку.
Задача о кратчайшей суперстроке является \(NP\)-трудной. Рассмотрим несколько приближенных алгоритмов.
1 Жадный алгоритм
Перекрытием\(\operatorname {ov}(s, t)\) двух строк \(s, t\) назовем самую длинную строку \(y\), такую что \(s=x y\) и \(t=y z\) для некоторых непустых \(x, z\). Также пусть префикс\(\operatorname {pr}(s, t)\) строки \(s\) относительно \(t\) будет строкой \(x\) из приведённого выше определения. Таким образом, \(s=\operatorname {pr}(s, t) \operatorname {ov}(s, t)\). Обратите внимание, что \(\operatorname {pr}(s, t) t\) — самая короткая строка, содержащая \(s\) и \(t\) в указанном порядке. Мы называем эту строку слиянием\(s\) и \(t\).
Следующий естественный подход к задаче, называемый жадным алгоритмом, работает на удивление хорошо. Мы выбираем две строки \(s, t\) с наибольшим перекрытием из \(U\) и заменяем их слиянием. Алгоритм останавливается, когда остаётся только одна строка, и, очевидно, эта строка является суперстрокой всех \(s_{i}\).
Algorithm 1Жадный алгоритм для задачи о кратчайшей суперстроке
множество строк \(U = \{s_1, s_2, \ldots, s_n\}\).
суперстрока \(s\), содержащая все строки из \(U\) в качестве подстрок.
пока\(|U| > 1\)выполнять
Найти две различные строки \(s,t \in U\), для которых длина перекрытия \(\operatorname{ov}(s,t)\) максимальна среди всех пар строк из \(U\).
Объединить строки \(s\) и \(t\) в новую строку \[
r = \operatorname{pr}(s,t)t
\]
Удалить из \(U\) строки \(s\) и \(t\).
Удалить из \(U\) все строки, которые являются подстроками \(r\).
Добавить \(r\) в \(U\).
Пусть \(s'\) — единственная оставшаяся строка в \(U\).
Попарные перекрытия: \(\left|\operatorname {ov}(abc, bcb)\right| = 2\) (строка \(bc\)), \(\left|\operatorname {ov}(bcb, cbaa)\right| = 2\) (строка \(cb\)), остальные перекрытия имеют длину \(0\) или \(1\). Жадный алгоритм сольет одну из этих пар, например \(abc\) и \(bcb\) в \(abcb\); затем \(\left|\operatorname {ov}(abcb, cbaa)\right| = 2\), и слияние дает \(abcbaa\) длины \(6\). При другом разрешении ничьей (\(bcb\) и \(cbaa \to bcbaa\), затем слияние с \(abc\)) получается та же строка \(abcbaa\). Здесь жадный алгоритм нашел кратчайшую суперстроку из примера выше.
Enum-item(2)
Все три максимальных перекрытия имеют длину \(k\): \(\operatorname {ov}(a b^{k}, b^{k} c) = \operatorname {ov}(a b^{k}, b^{k+1}) = \operatorname {ov}(b^{k+1}, b^{k} c) = b^{k}\). Если сначала выбрать две первые строки, то их слияние \(a b^{k} c\) уже не перекрывается с \(b^{k+1}\), и жадный алгоритм получит строку \(a b^{k} c b^{k+1}\) длины \(2k+3\), тогда как кратчайшая суперстрока \(a b^{k+1} c\) имеет длину \(k + 3\). При \(k \to \infty\) отношение стремится к \(2\).
Плохой пример для жадного алгоритма склейки строк
Три строки \(ab^{k}\), \(b^{k+1}\), \(b^{k}c\). Сверху — оптимальная суперстрока \(ab^{k+1}c\) длины \(k+3\), где все три строки уложены «внахлёст». Снизу — результат жадного алгоритма: первым максимальным перекрытием (\(b^k\)) склеиваются \(ab^k\) и \(b^kc\), после чего результат уже не перекрывается с \(b^{k+1}\) — итоговая длина \(2k+3\). Наведите курсор на полоску, чтобы увидеть, какая строка где уложена.
4
Оптимум:
Жадный алгоритм:
Как видно из примера, коэффициент аппроксимации жадного алгоритма не меньше \(2\). Существует недоказанная гипотеза:
Теорема 1 (Гипотеза о жадном алгоритме) Жадный алгоритм имеет коэффициент аппроксимации \(2\).
Пример выше показывает, что лучше, чем \(2\), коэффициент жадного алгоритма быть не может. Сверху же строго доказано, что он не превышает \(4\) (Блум и др., 1991); Каплан и Шафрир улучшили эту границу до \(3.5\), а сейчас лучшая известная оценка – \(\approx 3.425\) (Энглерт и др., 2022).
2 Алгоритм через покрытия множествами
2.1 Сведение к задаче о покрытии множествами
2.1.1 Построение экземпляра
Используя исходное множество строк \(U\) задачи о кратчайшей суперстроке, построим соответствующий экземпляр задачи о покрытии множествами, который обозначим как \(\mathcal{S}\). Для каждой пары строк \(s_{i}, s_{j} \in U\) и для некоторого \(k \geq 1\), если последние \(k\) символов строки \(s_{i}\) совпадают с первыми \(k\) символами строки \(s_{j}\), можно построить новую строку \(\sigma_{ijk}\) как совмещение\(s_{i}\) и \(s_{j}\) по \(k\) позициям. Формально:
\[
\sigma _{ijk} = s_i[:-k] \; s_j
\]
(первые \(\left|s_i\right| - k\) символов строки \(s_i\), за которыми записана строка \(s_j\) целиком).
Например, если \(s_i = \text{cabab}\) и \(s_j = \text{ababc}\), то получаем:
При этом \(\sigma_{ij1}, \sigma_{ij3}, \ldots\) не существует.
Каждая строка \(\sigma_{ijk}\) соответствует множеству исходных строк из \(U\), которые она покрывает (т.е. которые являются её подстроками). Таким образом, получаем экземпляр задачи о покрытии множествами: множество всех таких \(\sigma_{ijk}\) покрывает исходное множество \(U\). Дальнейшее построение приближённого решения суперстроки сводится к поиску небольшого подмножества строк \(\sigma_{ijk}\), которое покрывает все строки \(U\).
Построение строки склейки \(\sigma_{ijk}\)
Последние \(k\) символов строки \(s_i\) совпадают с первыми \(k\) символами строки \(s_j\); результат склейки \(\sigma_{ijk}=s_i[:-k]\,s_j\) — вся строка снизу. Двигайте ползунок: чем больше перекрытие, тем короче склейка.
3
Пусть множество \(\mathcal{F}\) состоит из всех возможных допустимых строк \(\sigma_{i j k}\). Для каждой строки \(\pi \in \Sigma^{+}\) определим множество \(\operatorname {set}(\pi )=\{ s \in U \mid s\) является подстрокой \(\pi \}\). Множество элементов \(U\) требуется покрыть подмножествами \(\operatorname {set}(\pi )\), где \(\pi \in U \cup \mathcal{F}\). Вес множества \(\operatorname {set}(\pi )\) положим равным \(|\pi |\), т. е. длине строки \(\pi\).
2.1.2 Точность сведения
Пусть \(\operatorname {OPT}_{\mathcal{S}}\) и \(\operatorname {OPT}\) означают стоимость оптимального решения примера \(\mathcal{S}\) задачи о покрытии и длину кратчайшей суперстроки соответственно. Покажем, что эти величины могут отличаться друг от друга не более, чем в 2 раза.
Рассмотрим оптимальное покрытие \(\left\{ \operatorname {set}\left(\pi_{i}\right) \mid 1 \leq i \leq l\right\}\) и получим строку \(s\) соединением строк \(\pi_{i}, 1 \leq i \leq l\) в произвольном порядке. Очевидно, что \(|s|=\operatorname {OPT}_{\mathcal{S}}\). Так как каждая строка из \(U\) является подстрокой некоторой строки \(\pi_{i}\), то она также является подстрокой \(s\). Поэтому полученная строка является суперстрокой, и \(\operatorname {OPT}_{\mathcal{S}}=|s| \geq \operatorname {OPT}\).
Для доказательства второго неравенства рассмотрим кратчайшую суперстроку \(s^{*}\) для строк \(s_{1}, \ldots , s_{n},\left|s^{*}\right|=\operatorname {OPT}\). Покажем, что для примера \(\mathcal{S}\) задачи о покрытии существует некоторое покрытие веса не более \(2 \cdot \operatorname {OPT}\).
Рассмотрим самое левое появление строк \(s_{1}, \ldots , s_{n}\) в строке \(s^{*}\). Так как никакие из строк \(s_{1}, \ldots , s_{n}\) не являются подстроками друг друга, то крайние левые \(n\) строк начинаются с различных позиций. По той же самой причине они заканчиваются в различных позициях. Перенумеруем строки в порядке их появления. Так как никакая из строк не является подстрокой другой, то они будут заканчиваться в том же порядке.
Разобьем упорядоченный список строк \(s_{1}, \ldots , s_{n}\) на группы, как показано на рис. ниже. Каждая группа будет состоять из множества попарно пересекающихся строк. Обозначим через \(b_{i}\) и \(e_{i}\) индексы первой и последней строки в \(i\)-ой группе. Если группа \(i\) состоит только из одной строки, то \(b_{i}=e_{i}\). Положим \(b_{1}=1\). Пусть \(e_{1}\)- это наибольший индекс строки, которая перекрывается со строкой \(s_{1}\) (существует как минимум одна такая строка – сама \(s_{1}\)). В общем случае: если \(e_{i}<n\), то положим \(b_{i+1}=e_{i}+1\) и определим \(e_{i+1}\) как наибольший индекс строки, которая перекрывается со строкой \(s_{b_{i+1}}\). В конце процедуры получим \(e_{t}=n\) для некоторого \(t \leq n\).
Разбиение строк на группы
Крайние левые вхождения строк \(s_1,\dots,s_n\) в суперстроку \(s^{*}\), разбитые на группы попарно пересекающихся строк. \(s_{b_i}\) — первая (жирная) строка группы \(i\), \(s_{e_i}\) — последняя; отрезок \(\pi_i\) внизу — это склейка \(\sigma_{b_ie_ik_i}\), начинающаяся в позиции \(b_i\) и заканчивающаяся в позиции \(e_i\). Наведите курсор на группу, чтобы подсветить её и соответствующий \(\pi_i\).
Для каждой пары строк \(\left(s_{b_{i}}, s_{e_{i}}\right)\) существует \(k_{i}>0\), определяющее длину перекрытия этих строк в строке \(s\) (оно может отличаться от их максимального перекрытия). Пусть \(\pi_{i}=\sigma_{b_{i} e_{i} k_{i}}\). Тогда набор подмножеств \(\left\{ \operatorname {set}\left(\pi_{i}\right) \mid 1 \leq i \leq t\right\}\) является допустимым решением примера \(\mathcal{S}\), и его стоимость равна \(\sum_{i}\left|\pi_{i}\right|\).
Теперь заметим, что \(\pi_{i}\) не пересекается с \(\pi_{i+2}\). Докажем это утверждение для \(i=1\). Предположим, что строки \(\pi_{1}\) и \(\pi_{3}\) перекрываются. Тогда получается, что \(s_{b_{3}}\) перекрывается с \(s_{e_{1}}\) в строке \(s^{*}\). Однако по построению \(s_{b_{3}}\) не перекрывается с \(s_{b_{2}}\) (поскольку \(s_{b_{3}}\) относится к следующей группе). Следовательно, \(s_{e_{1}}\) заканчивается позже, чем \(s_{b_{2}}\). Получаем противоречие с тем, что строки должны заканчиваться в том же порядке, как и начинаются. Доказательство для других \(i\) строится аналогично.
В итоге получим, что каждый символ строки \(s^{*}\) входит не более чем в две строки \(\pi_{i}\). Отсюда получаем, что \(\operatorname {OPT}_{\mathcal{S}} \leq \sum_{i}\left|\pi_{i}\right| \leq 2 \cdot \operatorname {OPT}\).
2.2 Применение алгоритмов для задачи о покрытии множествами
После сведения можно использовать какой-то алгоритм для задачи о покрытии множествами. Рассмотрим, например, применение жадного алгоритма.
Algorithm 2Построение суперстроки через жадный алгоритм покрытия множествами
множество строк \(U = \{s_1, s_2, \ldots, s_n\}\).
приближённая суперстрока \(s\), содержащая все строки из \(U\) в качестве подстрок.
По всем парам строк из \(U\) и всем допустимым перекрытиям построить строки \(\sigma_{ijk}\) и семейство множеств \(\left\{\operatorname{set}(\pi) \mid \pi \in U \cup \mathcal{F}\right\}\) с весами \(\left|\pi\right|\).
Получить индивидуальную задачу о покрытии множествами: покрыть \(U\) множествами \(\operatorname{set}(\pi)\) минимального суммарного веса.
С помощью жадного алгоритма Хватала найти приближённое покрытие \(C = \{\operatorname{set}(\pi_{1}), \ldots, \operatorname{set}(\pi_{l})\}\).
Мощность множества элементов \(U\) в примере \(\mathcal{S}\) равна \(n\), то есть числу строк в задаче о суперстроке.
Теорема 2 Алгоритм @SSP:SetCov:GrAlg является \(2 H_{n}\)-приближенным алгоритмом для задачи о суперстроке, где \(n\) равно числу строк в заданном примере.
Mn-proofДоказательство
Длина построенной суперстроки равна \(\sum_{i=1}^{l} \left|\pi_i\right|\), т.е. весу найденного покрытия. Жадный алгоритм Хватала на универсуме из \(n\) элементов выдает покрытие веса не более \(H_n \cdot \operatorname {OPT}_{\mathcal{S}}\), а по лемме о точности сведения \(\operatorname {OPT}_{\mathcal{S}} \leq 2 \cdot \operatorname {OPT}\). Итого длина суперстроки не превосходит \(2 H_n \cdot \operatorname {OPT}\).
3 Алгоритмы на основе графов префиксов и перекрытий