вторник, 15 марта 2011 г.

Поиск наибольшей общей подпоследовательности(LCS) с помощью динамического программирования

[Все алгоритмы нахождения LCS]
Очень простой и понятный алгоритм, основанный на двумерном ДП.
Сложность по памяти и времени O(n*m).

Рассмотрим две строчки: A = “bedcadb” и B = “abcdede”. 
1) Буквы строчки A напишем перед строками матрицы, а элементы строчки B над столбцами матрицы.
2) Матрица будет иметь нулевые столбец и строку, состоящие из нулей.
3) Саму матрицу давайте назовем L.
4) В элементе матрицы L[i][j] будет хранится длина наибольшей общей подпоследовательности для префиксов A[1..i] и B[1..j].
Из п.4 делаем вывод, что нумерация букв в строках с единицы.
Префикс A[1..i] – это первые i символов строки A.

Для начала давайте заполним матрицу L по этим 4 принципам:

Разберем элемент L[3][4]. В данном случае рассматриваются два префикса: “bed” и “abcd”. Чисто интуитивно можно догадаться, что lcs для этих двух строк будет “bd”, поэтому в самом элементе храним 2. Все остальные элементы можно заполнить интуитивно.

Вот как раз на этом моменте выключаем интуицию(в рамках разумного) и начинаем искать “научный” принцип заполнения этой матрицы.

В ходе Ваших рассуждений должны появится следующие рекуррентные формулы:
             
           | L[i-1][j-1] + 1, если a[i] == b[j]
L[i][j] = < 
           | max(L[i-1][j],L[i][j-1]), иначе
Результирующая длина lcs для полных строк a и b находится в элементе L[7][7].

Теперь давайте научимся восстанавливать lcs по данной матрице. Эту задачу я поручаю на самостоятельное изучение. Если все таки эта задача вызовет затруднения, оставляю в качестве подсказки этот рисунок.

Оранжевая lcs: bed
Желтая    lcs: bcd
Затем тренируемся на задачах:
1) Найти длину LCS
2) По матрице восстановить саму LCS

Демонстрационное решение: здесь

17 комментариев:

  1. когда символы равны, то мы присваиваем L[i-1][j-1]+1.

    ОтветитьУдалить
  2. А разве это алгоритм н-вунша?
    Вы ничего не путаете?

    http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9D%D0%B8%D0%B4%D0%BB%D0%BC%D0%B0%D0%BD%D0%B0_%E2%80%94_%D0%92%D1%83%D0%BD%D1%88%D0%B0


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

    Автор, киньте пожалуйста ссылочки на биографии или прочую информацию авторов вашего алгоритма.

    ОтветитьУдалить
  3. http://www.rolfmuertter.com/code/nw.php вот еще ссылочка, с кодом алгоритма Нидлмана — Вунша. Внизу страницы.

    ОтветитьУдалить
  4. 1. "А разве это алгоритм н-вунша?"
    А разве нет? Обе ссылки, которые вы прислали решают одну и ту же задачу. А именно поиск наибольшей общей подпоследовательности. Исторически получилось так, что данный алгоритм был разработан для решения задачи в рамках молекулярной биологии. Задача формулируется так: имееется 2 модели молекулы ДНК, которые можно представить словом из букв четырехбуквенного алфавита {A,G,T,C}. Пусть длины таких строк равные N и M. Необходимо найти подпоследовательность наибольшоей длины, входящую в то и другое слово.

    2. "В более менее официальных источниках нигде не нашел информации про авторов алгоритма из текущего сабжа"
    Не знаю что такое "более менее официальные источники". Копайте в англоязычной литературе и на англоязычных сайтах раз вам так интересна эта тема. Я думаю про Питера Фенвика или Тима Петерсона тоже не так просто найти информацию.

    3."Автор, киньте пожалуйста ссылочки на биографии или прочую информацию авторов вашего алгоритма."
    Мне не интересна биография этих людей. Google в помощь.

    4. По поводу "Нидельман"/"Нудельман".
    Какая собственно разница как переводится имя этого товарища на русский язык? На моей памяти имя с фамилией Страуструпа писалось не меньше 5 различными способами.

    ОтветитьУдалить
  5. Похоже, я окончательно запутался.
    Это мне кажется, что у них (вашего и пруфнутого мной алгоритма) вывод разный получается, или так и есть на самом деле...?

    ОтветитьУдалить
  6. Ответы могут различаться. Главное чтобы длина была одинаковая. Это зависит от способа восстановления пути. На рисунке представлено два пути между клетками (7,7) и (1,2). Первый путь подсвечен ярко-оранжевым цветом, другой бледно-оранжевым. Как можно догадаться, для каждого пути будет получен свой ответ, но каждый из них удовлетворяет изначально поставленной задаче.

    ОтветитьУдалить
  7. Так алгоритм Нидлмана-Вунша ищет не наибольшую общую последовательность, а выравнивает две последовательности. Автор, скорее всего, вы неправильно озаглавили статью.

    ОтветитьУдалить
    Ответы
    1. А в чем разница между "ищет наибольшую общую подпоследовательность" и "выравнивает две последовательности"?

      Удалить
    2. Разница в выводе:
      Алгоритм LCS("ACTG", "CT") просто даст результат: "CT"
      Алгоритм Нидлмана-Вунша ("ACTG", "CT") даст результат:
      ACTG
      -CT-

      Алгоритм Нидлмана-Вунша имеет штрафы за разрыв (или же поощрения), несоответствие и соответствие.

      Например. Пусть даны две строки: S1 = "ACTCTCC" и S2 = "CC".
      Что даст LCS? Он просто выведет "CC".
      А как можно выравнять две последовательности? Это зависит от параметров. Но, очевидно, что есть некоторые равнозначные (на первый взгляд) варианты:
      1)
      ACTCTCC
      -C-C---
      2)
      ACTCTCC
      ---C-C-
      3)
      ACTCTCC
      -С----С

      Ну и т.д. Всего 8 вариантов, но, думаю, смысл ясен. Вот, алгоритм Нидлмана-Вунша позволяет управлять результатом за счёт задания величины штрафов.

      Удалить
    3. Не могу ответить ещё раз, так что отпишу сюда :-) Это был, скорее, ответ на вопрос:
      > в чем разница между "ищет наибольшую общую подпоследовательность" и "выравнивает две последовательности"?

      А то, что штрафы/баллы за открытие/конец цепи конкретно в этот алгоритм (а не его модификации), я сильно сомневаюсь :-) Тем не менее, задачи разные :-) Надеюсь, смог ответить на вопрос :-)

      Удалить
    4. В данном случае первична задача нахождения LCS. Модификация алгоритма Нудельмана–Вунша выбрана как средство.

      Удалить
    5. Извините, не понял вас :-) Ну, смотрите, в статье же нет ни слова вообще про реализацию алгоритма Нидлмана-Вунша. Нет даже описания того, зачем он нужен и что делает. Т.е. кроме названия самого алгоритма нет ничего. Статья отличная, просто не так озаглавлена. Было бы здорово, если бы вы это исправили.

      Я попал сюда в поисках, как раз, алгоритма Нидлмана-Вунша, а не longest common sequence на динамическом программировании). В итоге получил неправильную информацию, пришлось долго ещё разбираться.

      Игорь, пожалуйта, исправьте название статьи :-) Она просто неправильно проиндексирована. В заголовке одно, а в статье - совершенно другое.

      Удалить
    6. Динамическое программирование за O(n * m) как раз и есть алгоритм Нудельмана-Вунша. В статье, конечно, не сказано, что алгоритм считает чуть более общую вещь (когда заданы веса совпадений), но суть он отражает достаточно.

      Удалить
    7. > Динамическое программирование за O(n * m) как раз и есть алгоритм Нудельмана-Вунша.
      Динамическое программирование - это просто методология. Ни с каким конкретным алгоритмом она не связана. То, что алгоритм Нидлмана-Вунша решает задачу выравнивания строк именно по этой методологии, вовсе не значит, что он решает проблему поиска наибольшей общей последовательности.

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

      Методом ДП можно решать ещё задачи комбинаторной оптимизации (задача ранца), можно искать самую длинную строку (тоже LCS), и ещё много чего.

      Но это было бы просто неприлично: сказать, что в статье решают задачу комбинаторной оптимизации, но написать про проблему поиска longest common string. А потом говорить, что раз и тут, и там есть динамическое программирование, значит, тут всё правильно.

      Удалить
  8. Этот комментарий был удален администратором блога.

    ОтветитьУдалить