Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Shortest Common Superstring Problem

Anna | 4.06.2014 | нет комментариев
Задача кратчайшей всеобщей надстроки формулируется дальнейшим образом: обнаружить кратчайшую строку, такую, что всякая строка из заданного комплекта являлась бы её подстрокой. Эта задача имеет место как в биоинформатике (задача сборки генома в всеобщем случае) так и в сжатии данных (взамен данных беречь их надстроку и последовательность пар, вида (индекс вступления, длина)).

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

Осмотрительно, 4 мегабайта!

По большей части, статья — попытка перевести на внятный язык, проиллюстрировать, приправить примером, и, безусловно же, реализовать на Java 4-приближённый алгорифм конструирования надстроки из книжки Дэна Гасфилда (см. использованную литературу). Но вначале малое вступление и 2-приближенный, алчный алгорифм.

В простейшем случае (если бы в наименовании задачи не было слова “кратчайшей”) решением задачи будет примитивное конкатенирование входных строк в произвольном порядке. Но при данной постановке задачи мы имеем дело с NP-полнотой, что обозначает, что в реальное время не существует алгорифма, с поддержкой которого дозволено было бы решить эту задачу на машине Тьюринга за время, не превосходящее полинома от размера данных.

Ввод: S1, S2, …, Sn — уйма строк финального алфавита E*.
Итог: X — строка алфавита E* содержащая всякую строку S1..n в качестве подстроки, где длина |X| минимизирована.

Пример. Возьмём уйма строк S = {abc, cde, eab}. В случае с конкатенированием длина выходной надстроки будет 9 (X = abccdeeab), что, видимо, не наилучший вариант, так как строки могут иметь суффиксно-префиксное совпадение. Длину этого совпадения мы будем называть overlap. (Выбор английского слова произведён неслучайно, так как определенного и однозначного перевода на русский язык оно не имеет. В русскоязычной литературе традиционно применяются термины наложение, пересечение, перекрытие и суффиксно-префиксное совпадение).

Отхождение. Представление overlap является одним из важнейших в процессе реализации алгорифмов конструирования надстрок. Вычисление overlap’a для упорядоченной пары строк (Si, Sj) сводится к нахождению длины максимального совпадения суффикса строки Si с префиксом строки Sj.

image

Один из методов запрограммировать нахождение overlap’a представлен в дальнейшем листинге.

      /*
      * Функция вычисляет максимальную длину суффикса строки s1
      * совпадающего с префиксом строки s2 (длину наложения s1 на s2)
      */
      private static int overlap(String s1, String s2)
      {
        int s1last = s1.length() - 1;
        int s2len = s2.length();
        int overlap = 0;
        for (int i = s1last, j = 1; i > 0 && j < s2len; i--, j  )
        {
          String suff = s1.substring(i);
          String pref = s2.substring(0, j);
          if (suff.equals(pref)) overlap = j; 
        }
        return overlap;
      }

Возврат к примеру. Если конкатенировать строки S = {abc, cde, eab} с учётом их overlap’ов, то получим строку X = abcdeab с длинной 7, которая короче предыдущей, но не самая короткая. Самая короткая строка получится при конкатенировании строк с учётом overlap’ов в порядке 3-1-2, тогда результирующая строка X = eabcde будет иметь длину 6. Таким образом, мы свели задачу к нахождению оптимального порядка конкатенирования строк с учётом их overlap’ов.

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

Алчный алгорифм

В этом алгорифме на всякой итерации мы пытаемся обнаружить наивысший overlap 2-х всяких строк и слить их в одну. Мы верим, что итог этого алгорифма будет близко приближён к реально оптимальному.

1. Пока S содержит больше одной строки, находим две строки с максимальным overlap’ом и сливаем их в одну (скажем, ABCD CDEFG = ABCDEFG).
2. Возвращаем одну оставшуюся в S строку.

Пример реализации этого алгорифма представлен в дальнейшем листинге.

      /*
      * Функция сливает строки с максимальным наложением до тех пор,
      * пока не останется исключительная строка (всеобщая надстрока). 
      */
      public static String createSuperString(ArrayList<String> strings)
      {
        while (strings.size() > 1)
        {
          int maxoverlap = 0;
          String msi = strings.get(0), msj = strings.get(1);
          for (String si : strings)
            for (String sj : strings)
            {
               if (si.equals(sj)) continue;
               int curoverlap = overlap(si, sj); 
               if (curoverlap > maxoverlap)
               {
                 maxoverlap = curoverlap;
                 msi = si; msj = sj;
               }
            }

          strings.add(merge(msi, msj, maxoverlap));
          strings.remove(msi);
          strings.remove(msj);
        }
        return strings.get(0);
      }

В этом листинге возникла иная простая функция merge, которая сливает две строки в одну с учётом их overlap’a. Так как конечный теснее был вычислен, разумно легко передать его в качестве параметра.

      /*
      * Функция сливает строки s1 и s2 на длину len, вычисленную с
      * поддержкой функции overlap(s1, s2)
      */
      private static String merge(String s1, String s2, int len)
      {
        s2 = s2.substring(len);
        return s1   s2;
      }

Один пример (наихудший случай):
дозволено обнаружить, сводя эту задачу к “задаче о назначениях”. Выходит, задачей стало обнаружить полное предназначение максимального веса (как оказалось, данный шаг алгорифма занимает доминантное время). Стремительней и проще ([1] п.16.19.13) это предназначение дозволено обнаружить алчным способом.

Алчное предназначение ([1] п.16.19.13)

Начальные данные: матрица A размером k k!br/> Тестирование выполняется с поддержкой функции test класса Main.

      private static int test(ArrayList<String> substrings, String superstring)
      {
         int errors = 0;

         for (String substring : substrings)
            if (superstring.indexOf(substring) < 0)
               errors  ;
           return errors;
      }

Использованная письменность

[1]: Дэн Гасфилд. Строки, деревья и последовательности в алгорифмах. Информатика и вычислительная биология. Невский Диалект, БХВ-Петербург, 2003г. – 656 с.: ISBN 5-7940-0103-8, 5-94157-321-9, 0-521-58519-8.
www.ozon.ru/context/detail/id/1393109/

[2]: Dan Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE, 1997г. – 534 с.: ISBN-10: 0521585198, ISBN-13: 978-0521585194.
www.amazon.com/Algorithms-Strings-Trees-Sequences-Computational/dp/0521585198

[3]: Shunji Li, Wenzheng Chi. Lecture #3: Shortest Common Superstring – CS 352 (Advanced Algorithms), Spring 2011.
cs.carleton.edu/faculty/dlibenno/old/cs352-spring11/L03-shortest-superstring.pdf

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB