Главная » Java, Структуры данных и алгоритмы » Критерий подобия текста

0

Общей проблемой обработки текста, возникающей в генетике и программном проектировании, является определение степени подобия двух текстовых строк. В приложениях для генетических исследований две строки могут соответствовать двум цепочкам ДНК, принадлежащим двум разным людям, считающимся генетически близкими, если обнаружится достаточно протяженный общий отрезок в обеих цепочках. Точно так же в программном проектировании две строки могут принадлежать двум версиям исходного кода одной программы, и требуется определить, какие изменения сделаны при переходе от одной версии к другой. На самом деле определение сходства двух строк представляется вполне обычной операцией, которая в операционной среде Unix/Linux выполняется программой diff, применяемой для сравнения текстовых файлов.

Проблема наиболее длинной общей подпоследовательности

А Существует несколько разных способов определения подобия двух строк. Один из наиболее простых, часто встречающихся способов применяет символьные строки и их подпоследовательности. Допустим, имеется строка X = хоХ]Х2… хп_ j. Подпоследовательностью строки Сбудет любая строка, имеющая вид хрса … xik, где /} < /} + 1; то есть это набор символов, необязательно расположенных подряд, но тем не менее существующих в X. Например, строка AAAG является подпоследовательностью строки CGATAATTGAGA. Заметьте, что концепция подпоследовательности строки отличается от концепции подстроки, описанной в разделе 11.1.

Постановка задачи

Особое место при определении подобия строк занимает проблема наиболее длинной общей подпоследовательности (longest common subsequence).

Задача состоит в том, чтобы из двух строк символов, Х= xqX\X2 ••• хп- 1 и Y= УоУ\У2 • •• Ут – 1 некоторого алфавита (например, алфавита {А, С, G, 7), принятого в генетических исследованиях), определить наиболее длинную строку S, являющуюся подпоследовательностью обеих строк Хи Y.

Одним из вариантов решения этой задачи является перебор всех подпоследовательностей в X и выбор самой длинной из них, одновременно являющейся и подпоследовательностью в Y. Поскольку каждый символ в X либо находится в подпоследовательности, либо нет, существует потенциально 2" различных подпоследовательностей X, каждая из которых требует О(т) времени для определения, является ли она подпоследовательностью Y Таким образом, силовой алгоритм соответствует экспоненциальному алгоритму, выполняющемуся за 0(2пт) времени, что явно неэффективно. Ниже рассмотрен динамический метод решения задачи поиска наиболее длинной общей подпоследовательности, работающий намного быстрее.

Динамическое программирование

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

Методика динамичного программирования используется в первую очередь для оптимизационных задач, когда требуется определить «наи- . лучший» способ выполнения некоторого действия. Зачастую количество разных способов выполнения такого действия экспоненциально, поэтому примитивный силовой поиск недопустим, разве только для очень небольших задач. В таких ситуациях можем применить технологию динамического программирования, если задача содержит определенное количество структур, которые могут быть использованы. Такая структура включает три следующие компоненты.

Простая подзадача: общая оптимизационная задача должна иметь возможность разбиения на подзадачи. Более того, должен существовать простой способ обозначения подзадач всего несколькими индексами типа /, j, к и т.п.

Оптимизация подзадачи: оптимальным решением общей задачи должна стать комбинация оптимальных решений подзадач. Вряд ли возможно найти оптимальное решение всей задачи, содержащее субоптимальные подзадачи.

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

Перечислив основные составляющие технологии динамического программирования, рассмотрим их применение для поиска наиболее длинной общей подпоследовательности.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии