Имитационное моделирование, принципы и алгоритм. Расстояние между строками и вычисление наибольшей общей подпоследовательности. Средства, используемые в разработке, требования к программе. Инструкция пользователю. Структура программы, создающей строки.
При низкой оригинальности работы "Разработка алгоритмов анализа длинных последовательностей, создаваемых системами имитационного моделирования", Вы можете повысить уникальность этой работы до 80-100%
Для примера возьмем строки } и Заполненный массив стоимостей для данных строк будет выглядеть следующим образом (Рисунок 1): Рисунок 1 - Заполненный массив стоимостей для строк } и Минимальная стоимость преобразования находится в ячейке D [m, n], где m - длина строки n - длина строки . 2) Поскольку 1?16 сдвигаем значения из второй строки в первую и вычисляем новые значения второй строки, счетчик строк увеличиваем на 1 (Рисунок 3): Рисунок 3 - Массив стоимостей на втором шаге 4) 3?16, сдвигаем строки, вычисляем значения 2 строки, увеличиваем счетчик строк (Рисунок 5): Рисунок 5 - Массив стоимостей на 4 шаге 7) 6?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 8): Рисунок 8 - Массив стоимостей на 7 шаге) 7?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 9): Рисунок 9 - Массив стоимостей на 8 шаге 3) По теореме 1 ищется первая позиция во второй строке К такая, что LCS первой половины первой строки и первых К символов второй строки в соединении с LCS второй половины первой строки и последних m-K (m - длина второй строки) символов второй строки равна требуемой LCS первой и второй строк.В ходе работы были рассмотрены различные алгоритмы решения каждой из задач. Для каждой из задач был реализован один алгоритм, менее требовательный к памяти.while (index-1) do // Поочередно ищем вхождения, определяя, период это или нет. begin index:= SUBSTRING (STR, SUBSTR[offset], prev_index 1); Found: boolean; // Флаг нахождения y_index x_index: longint; // Индекс деления строки X y_index: longint; // Индекс деления строки Y last_i: longint; // переменная, для индекса последнего элемента SUB_X lcs_max: longint; // максимальная L1j L2n-j begin i:= 0; // Инициализация для цикла While if (NOTEMPTY = true) then C[0]:= Y[0] // Если НОП не пуста, присваиваем ед. возможное значение else C[0]:=-1; // Иначе - код ошибки end else begin // Начинается рассм.
Введение
программа моделирование имитационный пользователь
В данной работе рассматриваются задачи анализа строк, создаваемых системами имитационного моделирования. В качестве задач были рассмотрены - вычисление редакционного расстояния, нахождение наибольшей общей подстроки, нахождение периода. Поскольку имитационное моделирование позволяет воссоздавать процессы, происходящие в различных областях: от бизнес-процессов до информационной безопасности, алгоритмы решения задач анализа строк, создаваемых при моделировании, позволяют анализировать довольно разные данные без изменений в коде программы.
Для каждой задачи рассмотрены различные варианты ее решения, эффективность того или иного алгоритма, в конце будет описан алгоритм, выбранный для реализации на языках программирования Pascal и C. Выбор алгоритма основывается на затратах памяти, так как сеанс моделирования порождает строки, характеризующиеся большим объемом данных - в каждой строке не менее 1 элементов.
1.
Общая информация
1.1 Имитационное моделирование
Имитационное моделирование является одним из самых мощных инструментов анализа при разработке сложных систем и анализе процессов их функционирования. Имитационное моделирование как метод научного исследования предполагает использование компьютерных технологий для имитации различных процессов или операций - моделирования. Результаты определяются случайным характером процессов. На основе этих данных можно получить устойчивую статистику [4].
Имитационное моделирование позволяет моделировать поведение системы во времени. Его используют, когда: 1. Дорого или невозможно экспериментировать на реальном объекте.
2. Невозможно построить аналитическую модель: в системе есть время, причинные связи, последствие, нелинейности, стохастические (случайные) переменные.
3. необходимо сымитировать поведение системы во времени [4].
Области применения: - Бизнес-процессы
- Бизнес-симуляция
- Боевые действия
- Динамика населения
- Дорожное движение
- ИТ-инфраструктура
- Математическое моделирование исторических процессов
- Логистика
- Пешеходная динамика
- Производство
- Рынок и конкуренция
- Сервисные центры
- Цепочки поставок
- Уличное движение
- Управление проектами
- Экономика здравоохранения
- Экосистема
- Информационная безопасность
- Релейная защита [5]
1.2 Основные определения
Последовательность - упорядоченный набор элементов [1].
Алфавит - конечное непустое множество, описывающее природу элементов строки. Члены этого множества называются буквами [1]. В данной работе алфавит состоит из целых положительных чисел.
Строковая последовательность (строка для краткости) - частный случай строки, удовлетворяющий следующим правилам: 1. Каждый элемент последовательности имеет уникальную метку
2. Каждый элемент с некоторой меткой x (за исключением не более одного элемента, который называется самый левый элемент) имеет единственный предшествующий элемент с меткой p(x).
3. Каждый элемент с некоторой меткой x (за исключением не более одного элемента, который называется самый правый элемент) имеет единственный последующий элемент с меткой s(x).
4. Для любого элемента с меткой x, который не является самым левым, выполняется равенство x=s (p(x)).
5. Для любого элемента с меткой x, который не является самым правым, выполняется равенство x=p (s(x)).
6. Для двух различных элементов с метками x и y существует такое целое положительное число k, что x= [1].
В данной работе строковая подпоследовательность, удовлетворяющая правилам 1-6, трактуется как одномерный массив. Произвольную строку x на алфавите A в виде массива можно задать следующим образом - x: array [1..n] of A [1].
Строка x длины n и строка y длины m равны в том случае, если: 1. n=m
2. x[i]=y[i], [1]
Строка ? является подстрокой ?, если ?=???. ? называется префиксом ?, если ?=??. [3] ? называется суффиксом ?, если ?=??. [3] ? называется бордером ?, если ? одновременно является и суффиксом и префиксом ? [3].
Число p называется периодом строки ? (n=|?|) если . Кратность - количество повторений периода [3].
2. Алгоритмы анализа длинных подпоследовательностей, создаваемых системами имитационного моделирования
2.1 Расстояние между строками
Постановка задачи. Для данных строк и , где | |, | | > 0, и метрики d, задающей расстояния между строками, вычислить d( , ) [6].
Расстояние Хемминга [Hamming, 1982].
Расстоянием Хемминга между двумя строками является число позиций, в которых не совпадают элементы сравниваемых строк. Если строки одинаковой длины и разрешена только операция замены, стоимость которой равна единице, то минимальная цена преобразования будет равна числу позиций, в которых не совпадают элементы [2].
Расстоянием Левенштейна [Levenshtein distance] называется минимальное количество операций вставки или удаления одного символа, замены одного символа на другой, необходимых для преобразования одной строки в другую [2].
Алгоритм Вагнера-Фишера [Wagner-Fischer]
Для нахождения редакционного расстояния был использован алгоритм Вагнера-Фишера с небольшим изменением. Алгоритм Вагнера - Фишера вычисляет редакционное расстояние, основываясь на наблюдении, что если мы зарезервируем матрицу для хранения редакционных расстояний между всеми префиксами первой строки и всеми префиксами второй, то мы можем посчитать все значения в матрице, «потоково» заполняя матрицу. В итоге расстоянием между двумя полными строками будет значение, которое будет посчитано последним [2]. Чтобы вычислить редакционное расстояние (расстояние Левенштейна) необходимо вычислить матрицу D. Определим возможные операции, которые могут быть использованы для преобразования одной строки в другую: § с (a, b) - цена замены символа a на символ b
§ с (?, b) - цена вставки символа b
§ с (a, ?) - цена удаления символа a и цену этих операций: § с (a, а) = 0
§ с (a, b) = 1 при a?b
§ с (?, b) = 1
§ с (a, ?) = 1 [2]
Будем считать, что все c неотрицательны, а так же действует правило треугольника: если 2 последовательные операции можно заменить одной, то общая цена не ухудшается [2].
Пусть и - две строки (длиной M и N соответственно) над некоторым алфавитом, тогда расстояние Левенштейна d( можно подсчитать по следующей формуле: , где где m (a, b) равно нулю, если a=b и единице в противном случае min (a, b, c) возвращает наименьший из аргументов. Шаг по i представляет собой удаление из первой строки, по j - вставку в первую строку, а шаг по i и j символизирует замену символа или отсутствие изменений [2].
Очевидно, справедливы следующие утверждения: -
-
- d( [2]
Доказательство
Рассмотрим формулу более подробно. Очевидно, что расстояние Левенштейна между двумя пустыми строками будет равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной i, нужно совершить i операций удаления, а чтобы получить строку длиной j из пустой, нужно произвести j операций вставки.
Теперь рассмотрим нетривиальный случай, когда обе строки являются не пустым.
Заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. Рассмотрим две последовательные операции: · Две замены одного и того же символа - не оптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).
· Две замены разных символов можно менять местами
· Два стирания или две вставки можно менять местами
· Вставка символа с его последующим стиранием - не оптимально (можно их обе отменить)
· Стирание и вставку разных символов можно менять местами
· Вставка символа с его последующей заменой - не оптимально (излишняя замена)
· Вставка символа и замена другого символа меняются местами
· Замена символа с его последующим стиранием - не оптимально (излишняя замена)
· Стирание символа и замена другого символа меняются местами [2]
Пусть кончается на символ «a», кончается на символ «b». Есть три варианта: 1. Символ «а», на который кончается , в какой-то момент был стерт. Сделаем это стирание первой операцией. Тогда мы стерли символ «a», после чего превратили первые i-1 символов в (на что потребовалось D (i-1, j) операций), значит, всего потребовалось D (i-1, j) 1 операций
2. Символ «b», на который кончается , в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили в первые j-1 символов , после чего добавили «b». Аналогично предыдущему случаю, потребовалось D (i, j-1) 1 операций.
3. Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то, чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой не оптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа - его замена. Заменять его 2 или больше раз не оптимально. Значит, 1. Если a=b, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили D (i-1, j-1) операций.
2. Если a?b, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить D (i-1, j-1) операций, значит, всего потребуется D (i-1, j-1) 1 операций.
Для примера возьмем строки } и Заполненный массив стоимостей для данных строк будет выглядеть следующим образом (Рисунок 1):
Рисунок 1 - Заполненный массив стоимостей для строк } и Минимальная стоимость преобразования находится в ячейке D [m, n], где m - длина строки n - длина строки .
Алгоритм в выше описанном виде требует O (m*n) операций и такие же емкостные затраты. Последнее являлось стимулом к изменению алгоритма, так как для нахождения расстояния Левенштейна для строк длинной в потребуется около38 гигабайт памяти в Pascal и в С. Поскольку для вычисления следующей строки матрицы D требуется только предыдущая, было решено использовать массив, содержащий предыдущую строку, из которой вычисляется текущая, и, собственно, текущая строка. После модернизации алгоритм выглядит следующим образом: 1. На первом шаге заполняем первую строку матрицы по формуле
2. Счетчик строк равен 0
3. На основе первой строки, используя формулу, заполняем вторую строку
4. Увеличиваем счетчик строк на 1
5. Если он равен длине второй полной строки, то расстояние Левенштейна равно последнему элементу матрицы D, если нет, то переходим на следующий шаг
6. Сдвигаем значения второй строки матрицы в первую D [0, j]=D [1, j]
7. Переходим к шагу 2
После изменения классического алгоритма временная сложность O (m*n) при памяти O (min(n, m)).
После модернизации будет происходить следующее: 1) Заполняем первые 2 строки, счетчик строк равен 1 (Рисунок 2).
Рисунок 2 - Массив стоимостей на первом шаге
2) Поскольку 1?16 сдвигаем значения из второй строки в первую и вычисляем новые значения второй строки, счетчик строк увеличиваем на 1 (Рисунок 3):
Рисунок 3 - Массив стоимостей на втором шаге
3) 2?16, снова сдвигаем значения, вычисляем новые и увеличиваем счетчик строк (Рисунок 4):
Так же редакционное расстояние может быть вычислено и с помощью алгоритма нахождения наибольшей общей подпоследовательности - алгоритма Хиршберга (подробно описан далее). Временная и емкостная сложность этого алгоритма идентичны соответствующим сложностям измененного алгоритма Вагнера-Фишера. Модернизированный алгоритм Вагнера-Фишера был выбран поскольку он более прост в реализации, а так же алгоритм Хиршберга был реализован для поиска LCS.
2.2 Вычисление наибольшей общей подпоследовательности
Постановка задачи. Для данных строк и (| |, | | > 0) найти |LCS( , )|, где LCS( , ) - самая длинная общая подпоследовательность (longest common subsequence) и [6].
Подпоследовательность последовательности X получается в результате удаления нескольких элементов (не обязательно соседних) из последовательности X. Имея две подпоследовательности X и Y, наибольшая общая подпоследовательность определяется как самая длинная последовательность, являющаяся подпоследовательностью как , так и . Например, для последовательностей ={1, 3, 6, 2, 1, 1, 8} и ={1, 6, 2, 8, 9} LCS будет равна {1, 6, 2, 8}. Следует отметить, что наибольших общих подпоследовательностей, может быть несколько. [2]
Существуют множество различных подходов к решению данной задачи, были рассмотрены следующие: полный перебор, алгоритм Нидлмана-Вунша, алгоритм Ханта-Шуманского, алгоритм Хишберга.
Полный перебор
При полном переборе может быть осуществлен различными способами: можно перебирать варианты подпоследовательности, варианты вычеркивания из данных подпоследовательностей и т.д. Но какой бы подход не был использован, время работы программы будет экспонентой от длины строки.
Алгоритм Нидлмана-Вунша [Needleman-Wunsch]
Данный подход заключается в поэтапном заполнении матрицы, где строки являются элементами а столбцы элементы . При заполнении действуют два правила: 1. Если элемент = , то в ячейке (i, j) записывается значение ячейки (i-1, j-1) с добавлением единицы.
2. Если элемент ? , то в ячейку (i, j) записывается максимум из значений (i-1, j) и (i, j-1) [7].
Заполнение происходит в двойном цикле по i и j с увеличением значений на 1, таким образом, на каждой итерации нужные на этом шаге значения ячеек уже вычислены. После того, как произойдет полное заполнение матрицы, соединив ячейки, в которых происходило увеличение значений, мы получим искомую НОП. Соединять при этом нужно двигаясь от максимальных индексов к минимальным, если в ячейке увеличивалось значение, то добавляем соответствующий элемент к LCS, если нет, то двигаемся вверх или влево в зависимости от того где находится большее значение в матрице [7] (Рисунок 18, 19).
Рисунок 18 - Заполненная матрица похожести для строк и
Рисунок 19 - Выделение LCS
Временная сложность алгоритма - O (m*n), по памяти O (m*n). Очевидно, что для работы с большими объемами данных он не подходит, так будет требоваться много памяти.
Алгоритм Ханта-Шиманского [Hunt, Szymanski]
Метод выделения LCS для двух входных строк и Ханта и Шиманского эквивалентен нахождению максимального монотонно возрастающего пути в графе, состоящего из точек (i, j), таких, что = . На рисунке 20 иллюстрируется LCS (longestsunsequense, needlemanwunsh)=neeun, определенная с помощью «наибольшей» строго убывающей и непрерывной ломаной линии, проходящей через узлы сетки, представляющие совпадения = [1].
Рисунок 20 - LCS, определенная с помощью «наибольшей» строго убывающей и непрерывной ломаной линии
Ключевым в методе является массив значений. Установим некоторые свойства массива j, которые будут использованы в данном алгоритме [1].
Лемма 1. Для всех целых i 1.. и h выполняются нервенства: j [i ? 1, h ? 1] 1 ? j [i, h] ? j [i ? 1, h]. [1]
Доказательство тривиально при i = 1, поэтому будем считать, что i > 1.
Заметим, что если элемент j [i?1, h] определен, то также определены j [i ? 1, h ? 1] и j [i, h]. Если подстроки [1..i ? 1] и [1..j [i ? 1, h]] имеют LCS длиной h, тогда (по определению массива j) подстроки [1..i] и [1..j [i ? 1, h]] имеют общую подпоследовательность длиной не менее h. Отсюда следует, что j [i, h] ? j [i ? 1, h] [1].
Далее, поскольку элемент j [i, h] определен, подстроки [1..i] и [1..j [i, h]] имеют общую подпоследовательность длиной h. Удалив самые правые буквы из этих подстрок, можно уменьшить длину общей подпоследовательности не более, чем на единицу. Поэтому подстроки [1..i ? 1] и [1..j [i, h] ? 1] имеют общую подпоследовательность и, следовательно, LCS длиной не менее h?1. Это означает, что j [i ? 1, h ? 1] ? j [i, h]. Что и требовалось доказать [1].
Лемма 2. Для всех целых i?1.. и h?1..|LCS( [1..i], )| значение j [i, h] вычисляется по следующему правилу: j [i, h] равняется наименьшему целому ? j [i ? 1, h ? 1] 1..j [i ? 1, h], такому, что [i] = [ ] (если такое существует); j [i, h] = j [i ? 1, h], если такого не существует [1].
Доказательство. Сначала рассмотрим, как более простой, второй вариант вычисления j [i, h], когда такого не существует. Поскольку j [i, h] определяет наименьший префикс строки , то самым правым элементом в LCS для подстрок [1..i] и [1..j [i, h]] будет буква [j [i, h]]. Вследствие леммы 1 j [i, h] ?j [i ? 1, h ? 1] 1..j [i ? 1, h]. Но по нашему предположению не существует из этого интервала, такого, что [ ] = [i], поэтому [i] ? [j [i, h]]. Следовательно, та же самая LCS будет общей подпоследовательностью и для подстрок [1..i ? 1] и [1..j [i, h]] - в таком случае j [i, h] ? j [i ? 1, h]. Вследствие леммы 1 справедливо также обратное неравенство. Отсюда делаем заключение, что j [i, h] = j [i ? 1, h] [1].
Теперь предполагаем, что существует наименьшее целое из интервала j [i ? 1, h ? 1] 1..j [i ? 1, h], такое, что [i] = [ ]. Из этого предположения вытекает, что подстроки [1..i] и [1.. ] имеют общую подпоследовательность, состоящую из LCS( [1..i?1], [1..j [i?1, h?1]]) длиной h?1 и буквы x 2 [ ]. Отсюда заключаем, что j [i, h] не превышает Теперь покажем, что j [i, h] не меньше . Предположим, что имеет место строгое неравенство j [i, h] < . Тогда, вследствие леммы 1, j [i ? 1, h ? 1] <j [i, h] < . Поскольку - это наименьшее целое из интервала j [i ? 1, h ?1] 1..j [i ? 1, h], такое, что [i] = [ ], то отсюда заключаем, что [i] ? [j [i, h]]. Так как по условию |LCS( [1..i], [1..j [i, h]])| = h, поэтому подстроки [1..i ? 1] и [1..j [i, h]] также имеют общую подпоследовательность длиной h. Следовательно, j [i ? 1, h] ? j [i, h 1], а лемма 1 уточняет, что j [i?1, h] = j [i, h 1]. Но это невозможно, поскольку, как мы видели, j [i, h 1] < < j [i ? 1, h]. Это противоречие и доказывает, что j [i, h] не меньше . Имея также доказанным утверждение, что j [i, h] не превышает , делаем вывод, что j [i, h] = . Теорема доказана [1].
Этот алгоритм можно описать в виде последовательности таких шагов.
Шаг 1. Вычисление массива MATCHLIST
Из леммы 2 следует, что для вычисления значений j [i 1, 0..n-1] на основе значений j [i, 0..n-1] надо для каждого значения i ? 1.. знать такую позицию j в строке , для которой [i] = [j]. Эту информацию в подходящей форме будем получать из массива MATCHLIST, в котором каждая позиция i является указателем на список значений j, таких, что [i] = [j]. Для дальнейших вычислений на шаге 3 желательно, чтобы эти значения j были упорядочены в убывающем порядке [1].
Шаг 2. Начальное задание значений массива
Полагаем [0] < 0 и для всех h?1.. полагаем [h] < 1 (тем самым показываем, что элементы [h] не определены). [1]
Шаг 3. Вычисление значений j [i, h] на основе значений j [i?1, h], i = 1,2,…, . Эти вычисления выполняются путем замены значений в предыдущем массиве j [0.. ], соответствующем номеру i ? 1, на аналогичные значения, соответствующие номеру i. Напомним (лемма 2), что j [i, h] = j [i ? 1, h] (тогда значение [h] не изменяется) только в том случае, если не существует номера из интервала j [i ? 1, h ? 1] 1..j [i ? 1, h], такого, что [i] = [ ]. Поэтому для текущего значения i и для каждого значения ?MATCHLIST[i] по значениям массива надо найти такое значение , что [ ? 1] 1 ? ? [ ]. Тогда, согласно лемме 2, [ ] < . Каждое такое присвоение, которое изменяет значение [ ], соответствует одной из r точек сетки (как показано на рисунке выше), где [i] = [ ]. Это присвоение можно интерпретировать как создание конечного узла (листа) (i, , LINK[ ? 1]) на синтаксическом дереве, где LINK[ ? 1] - указатель на узел, созданный ранее при присвоении для [ ? 1]. (Для = 1 полагаем, что LINK[ ? 1] = NULL.) Когда лист создан, указатель на него хранится в LINK[ ]. После обработки всех i ? 1..n 1 наибольшее значение h, такое, что [h] < 1, равняется длине LCS( , ), а LINK[h] указывает путь длиной h по дереву от листа до корня. Этот путь и определяет LCS. [1]
Шаг 4. Запись LCS (x 1, x 2) в обратном порядке.
На дереве находится первый узел, который соответствует наибольшему значению h, такому, что [h] < 1. Затем записывается путь от этого узла до корня дерева - это и будет LCS( , ), записанная в обратном порядке.
Пример работы алгоритма Ханта-Шуманского.
={longestsubsequence}
={needlemanwunsh}
Заполненный массив MATCHLIST (Рисунок 21):
Рисунок 21 - Значения массива MATCHLIST
Значения элементов массива после i-й итерации следующие (Рисунок 22):
Рисунок 22
Время работы этого алгоритма равно O((r n) log n), где n - длина большей последовательности, а r - количество совпадений, в худшем случае при r = n*n, мы получаем время работы хуже, чем в предыдущем варианте решения. Требования по памяти остаются порядка O (r n).
Алгоритм Хиршберга [Hirschberg]
Хиршберг предложил алгоритм непосредственного вычисления LCS( за время порядка O (n*m) без явного вычисления массива стоимостей. Он так же показал, что этот алгоритм требует память объемом только O (min(m, n) [2]. Для реализации был выбран этот алгоритм.
Теорема 1. (1) [10].
Обозначим длину LCS для суффиксов (i 1, m) и (j 1, n) как =|LCS( (i 1, m), (j 1, n))| (2), где: - первая строка; n - длина первой строки; - вторая строка; m - длина второй строки [10].
Для 0<j<m значения являются длинами LCS префикса (1, i) и различных префиксов . Аналогично, значения являются длинами LCS обращенного суффикса и различных префиксов обращенной строки [10].
Определим формулой: , тогда для 0< i <n [10].
Доказательство: пусть для j= . - произвольная LCS( (i, j), (i, ), - произвольная LCS( (i 1, n), ( , тогда с= является общей подпоследовательностью и , ее длина равна M. Таким образом, ? (3) [10].
Пусть - произвольная LCS( , ), тогда является подпоследовательностью , равной S1 S2, где S1 - подпоследовательность (1, i), а S2 - подпоследовательность (i 1, n). Таким образом, существует значение , такое, что S2 является подпоследовательностью (1, ), а S2 - подпоследовательностью ( , m) [10].
Длины S1 и S2 удовлетворяют следующим условиям: |S1|?|LCS( (1, i), (1, ))| ? согласно (1).
|S2|?|LCS( (i 1, n), ( 1, m))| ? согласно (2)
Таким образом: (4)
Из неравенств (3) и (4) получаем . Что и требовалось доказать [10].
Алгоритм: 1) Сначала необходимо проверить не тривиальный ли случай. Если хотя бы одна из строк пуста, то в качестве результата возвращается пустая строка. Если хотя бы одна из строк односимвольная, то проверяется, содержится ли этот символ в другой строке. Если содержится, то в качестве результата возвращается этот символ, в противном случае - пустая строка [10].
2) Если случай нетривиальный, первая строка делится пополам, после чего ищутся длина наибольшей общей подпоследовательности ее первой половины и префиксов второй строки различной длины и длина LCS ее второй половины и суффиксов второй строки различной длины [10].
3) По теореме 1 ищется первая позиция во второй строке К такая, что LCS первой половины первой строки и первых К символов второй строки в соединении с LCS второй половины первой строки и последних m-K (m - длина второй строки) символов второй строки равна требуемой LCS первой и второй строк.
4) Найденное К используется для решения двух подзадач, для которых так же вычисляются шаги 1-4 [10].
5) В конечном итоге все подзадачи сводятся к тривиальным и их результаты объединяются [10].
Вычисление длины LCS.
Так как длина LCS любой строки и пустой строки равна 0, значения границ массива инициализируются нулями. В позиции (i, j), если , мы получаем новую LCS, присоединяя этот символ к текущей LCS префиксов x (1, i-1) и y (1, j-1), то есть L (i, j)=L (i-1, j-1) 1. Иначе длина текущей LCS просто равна максимальному из предыдущих значений. [10]
Так как для расчетов нам нужна только предпоследняя строка, можно сократить расходы памяти, храня только текущую и предыдущую строки. [10]
Эта задача решается для двух половин первой строки.
1. Заполняем вторую строку 0 (Рисунок 23).
Рисунок 23 - Состояние массива на 1 шаге
2. Сдвигаем строку вверх (Рисунок 24).
Рисунок 24 - Состояние массива на 2 шаге
Изначально после сдвига в первой строке будут 0, затем другие числа.
3. Рассчитываем текущую строку.
4. Пока не достигнем длины первой строки (первая строка в данном случае одна из половин ) повторяем шаги 2-3 [10].
После решения двух задач (для каждой половины ) получим два вектора . ) и будет длиной LCS для строк и [10].
2.3 Вычисление длины периода и количество повторений периода (кратность)
Постановка задачи. Для данной строки , | | = n > 0, найти самую длинную подстроку, встречающуюся в больше одного раза. Самая длинная повторяющаяся подстрока - это самая длинная из строк максимальной длины x, такая, что = uxvxw для некоторых строк u, v и w, где |u| 0, |v| 0 и |w| 0 [6]. Если же существует несколько периодов максимальной длины, то выбрать период с максимальной кратностью.
Алгоритм Крочемора [Crochemore]
Основная идея алгоритма Крочемора: выполнение декомпозиции подпоследовательностей на каждом уровне ? только относительно последовательностей, которые на этом уровне являются малыми [1].
На уровне ?? 2 разбиение множества позиций строки на отдельные непересекающиеся множества (последовательности) - это декомпозиция разбиения на уровне ? ? 1 [1].
В декомпозиции последовательности на подпоследовательности ( , , …, ) (q ?1) назовем одну подпоследовательность с самым большим количеством элементов большой, а остальные q - 1 подпоследовательностей - малыми. Для уровня ? = 1 каждая последовательность малая [1].
Основная сложность в реализации этого алгоритма заключается в структурах данных, обеспечивающих время выполнения алгоритма за O (n log n) [1].
Структуры необходимые для обеспечения работы алгоритма за O (n log n), классифицированные в соответствии с их основными функциями: 1. Запись текущей последовательности для каждой позиции в строке x.
- Массив SEQ [?..n]: SEQ[i] содержит индекс текущей последовательности, которой принадлежит i-я позиция в строке x.
- Массив SEQLIST [1..2n]: SEQLIST[j] - указатели на двусвязный список позиций, принадлежащих последовательности с индексом j и расположенных в порядке их возрастания.
- Массив SEQSIZE [1..2n]: SEQSIZE[j] равно количеству позиций в последовательности с индексом j, т.е. количеству позиций в списке, на который указывает элемент SEQLIST[j].
Всякий раз, когда необходимо сформировать новую последовательность или на уровне 1, или в качестве части декомпозиции существующей последовательности, из стека INDEXSTACK извлекается индекс последовательности. Если последовательность становится пустой в результате ее декомпозиции на подпоследовательности, индекс последовательности возвращается в стек INDEXSTACK. Всякий раз, когда к последовательности с индексом j добавляется позиция i, выполняются операторы присваивания SEQ[i] < j; SEQSIZE[j] < SEQSIZE[j] 1, а номер i добавляется в конец списка SEQLIST[j]. Если i-я позиция удаляется из последовательности с индексом j в результате его вхождения в подпоследовательность с индексом j, выполняется присваивание SEQSIZE[i] <SEQSIZE[j] ? 1, а i-я позиция удаляется из списка SEQLIST[i].
2. Управление малыми последовательностями.
- Очередь SMALL: очередь индексов j малых последовательностей, организованная таким образом, что (для ? > 1) все имеющиеся в ней малые последовательности являются подпоследовательностями одной и той же последовательности предыдущего уровня.
- Очередь QUEUE: очередь пар (i, j), где i - позиция в малой последовательности с индексом j, которая должна использоваться для декомпозиции текущего уровня; для каждого j позиции i располагаются в возрастающем порядке.
- Массив LASTSMALL [1..2n]: LASTSMALL[ ] = j > 0 тогда и только тогда, когда j - это индекс малой последовательности, использованной последней по времени для декомпозиции последовательности с индексом [1].
Для ? = 1 очередь SMALL содержит все индексы, которые первоначально вычисляются в соответствии с каждым символом строки x; для ? > 1 очередь SMALL создается повторно путем просмотра подпоследовательностей, тех последовательностей, для которых была выполнена декомпозиция на уровне ?, и добавлением к очереди SMALL всех подпоследовательностей, кроме единственной «большой» подпоследовательности (см. описание массивов SPLIT и SUBSEQ в следующем пункте). Для каждого элемента j в очереди SPLIT эти действия можно выполнить за один просмотр списка, на который указывает элемент SUBSEQ[j]. Таким образом, очередь SMALL модифицируется за время, пропорциональное количеству имеющихся в ней элементов [1].
Очередь QUEUE создается в начале обработки для каждого уровня ? > 1 путем удаления элементов из очереди SMALL. Для каждой последовательности j, обнаруженной в очереди SMALL, извлекаются найденные в списке SEQLIST[j] позиции i > 1, а элементы (i, j) добавляются к очереди QUEUE. Основная обработка каждого из уровней ? > 1 выполняется после того, как из очереди QUEUE один за другим удаляются элементы (i, j). Для каждой удаленной позиции I последовательность = SEQ [i?1] является той последовательностью, которая будет подвергнута декомпозиции. Следовательно, если LASTSMALL[ ] ?j, то последовательность была последней по времени подвергнута декомпозиции относительно некоторого другого класса, поэтому необходим новый индекс последовательности. Соответственно с этим устанавливаем LASTSMALL[ ] < j, извлекаем из стека INDEXSTACK следующий номер последовательности и добавляем его к списку, на который указывает SUBSEQ[ [1].
3. Организация подпоследовательностей.
- Массив SPLITFLAG [1..2n]: SPLITFLAG[j] = 1 тогда и только тогда, когда последовательность с индексом j будет подвергнута декомпозиции на текущем уровне (с использованием последовательностей, которые хранятся в очереди SMALL).
- Список SPLIT: список последовательностей j, которые будут подвергнуты декомпозиции на текущем уровне (т.е. для которых SPLITFLAG[j] = 1).
- Массив SUBSEQ [1..2n]: при декомпозиции последовательности j на текущем уровне SUBSEQ[j] указывает на список индексов подпоследовательностей последовательности j, первым элементом в этом списке будет сам индекс j [1].
Все эти структуры данных инициализируются для каждого уровня ? > 1 одновременно с формированием из очереди SMALL очереди QUEUE. В частности, когда (i, j) добавляется к очереди QUEUE, известно, что i будет использоваться для декомпозиции последовательности , в которой имеется позиция i ? 1 ( = SEQ [i ? 1]). Поэтому, если SPLITFLAG[ ] = 0, то в это время хранится в SPLIT - списке последовательностей, которые подлежат декомпозиции на уровне ?, в то время как выполняются следующие присваивания: SPLITFLAG[ ] < 1; SUBSEQ[ ] < ; LASTSMALL[ ] < 0. [1]
По завершении обработки каждого уровня ? (? > 1) последовательности j удаляются один за другим из списка SPLIT: если SEQSIZE[j] = 0, то эта последовательность уже пуста и поэтому ее индекс больше не требуется. Поэтому j помещается в стек INDEXSTACK и удаляется из списка, на который указывает SUBSEQ[j]. [1]
4. Вычисление кратных строк.
· Массив GAP [?..n]: элемент GAP[i] равен положительной разности между i-й позицией в строке x и следующей большей позицией в той же самой последовательности на текущем уровне; если нет большей позиции, то GAP[i] = ?.
· Массив GAPLIST [?..n]: GAPLIST[g] указывает на двусвязный список i-x позиций, для которых GAP[i] = g.
Для ? = 1 массивы GAP и GAPLIST инициализируются непосредственно путем обработки каждого списка, на который указывает SEQLIST[j], где j = 1,2,…, , вычисляя GAP[i] для каждой i-й позиции в списке SEQLIST[j], затем добавляя i-ю позицию к списку, на который указывает GAPLIST [GAP[i]] [1].
При ? > 1 массивы GAP и GAPLIST обновляются при удалении элемента (i, j) из очереди QUEUE, что приводит к декомпозиции последовательности = SEQ [i?1], при которой позиция i?1 в SEQLIST[ ] будет перемещена в конец SEQLIST[ ]. Поскольку списки, на которые указывают и SEQLIST и GAPLIST, двусвязные, повторное вычисление элементов массива GAP, необходимое изза удаления позиции i ? 1 из одного списка и ее вставки в другой список, можно выполнить непосредственно [1].
Мы видим, что, после создания последовательностей для уровня ?, каждый элемент в GAPLIST[?] описывает две идентичные подстроки строки x длиной ?, первые буквы которых находятся друг от друга на расстоянии ?, другими словами, имеем квадрат этой подстроки.
Для этого алгоритма обязательна упорядоченность алгоритма. Временная сложность - O (n log n), емкостная - O(n).
Алгоритм Мейна-Лоренца [Main, Lorentz]
Для реализации был выбран алгоритм Мейна-Лоренца, поскольку он работает с неупорядоченным алфавитом, но все равно выполняется за время порядка O(nlogn), а так же не требует реализации большого количества сложных структур данных. Это алгоритм типа «разделяй и властвуй», который вычисляет все квадраты подстрок, следовательно, все кратные строки в строковой последовательности x = x [?..n], распределяя их на три различных класса.
· Класс С1 - класс квадратов w 2, которые начинаются и заканчиваются в подстроке x [1.. ], т.е. = x [i..i 2|w| ? 1], где i 2|w| ? 1 ? .
· Класс С2 - класс квадратов , которые начинаются и заканчиваются в подстроке x[ 1..n], т.е. = x [i..i 2|w| ? 1], где i >
· Класс С3 - класс квадратов , которые начинаются в подстроке x [1.. ] и заканчиваются в подстроке x[ 1..n], т.е. здесь = x [i..i 2|w|?1], где 1 ? i ? и < i 2|w| ? 1 ? n.
Обозначим u = [1.. ] и v = x[ 1..n]. Основная идея алгоритма Мейна-Лоренца заключается в вычислении квадратов подстрок в строке x = uv на основе эффективного вычисления новых квадратов класса C3 [1].
Для описания процедуры C3 (u, v) (ищет квадраты класса С3) вначале отметим, что новые квадраты в строке uv могут быть двух видов: · правый квадрат, когда второе вхождение w в строку uv полностью находится в подстроке v;
· левый квадрат, когда в подстроке u имеется непустой префикс второго вхождения w [1].
Например, подстроки u = aba и v = ba порождают правый квадрат = (ba и левый квадрат = (ab [1].
Процедура C3 реализуется как комбинация процессов вычисления правых и левых квадратов. Пусть u = u [?.. ] и v = v [?.. ]. Чтобы в uv найти все правые квадраты, необходимо вычислить два массива. Массивы можно кратко определить следующим образом: · Массив LP [2.. 1]: для каждой позиции i = 2,3,…, строки v LP[i]=lcp (v[i.. ], v), при этом для i = 1 принимаем, что LP[i] = 0.
· Массив LS [1.. ]: для каждой позиции i = 1,2,…, строки v LS[i]=lcs (v[1..i], u) [1].
Например, для строки v = abaababa массив LP [2..9] = 01303010. Если u=abaab, тогда LS [1..8] = 02005020. Приближенно можно сказать, что массив LP рекуррентно определяет максимальные длины префиксов v внутри самой v, а массив LS определяет вхождения суффиксов u максимальной длины в строку v [1].
Лемма 1. Пусть u [1.. ] и v [1.. ] - произвольные непустые строки и пусть p ? и I ? p..2p?1 - положительные целые числа. В uv имеется квадрат длиной 2p, заканчивающийся на i-й позиции строки v, тогда и только тогда, когда: 2p ? LS[p] ?i ?p LP [p 1] [1].
Доказательство. В строке uv для любого квадрата w 2 длиной 2p, заканчивающегося на i-й позиции, первое вхождение w должно начинаться с буквы u[ ?2p i 1], а второе вхождение - с буквы v [i ? p 1]. Поэтому такой квадрат имеет «право на существование» тогда и только тогда, когда: u[ ? 2p i 1.. ] v [1..i ? p] = v [i ? p 1..i]; т.е. только тогда, когда: · u[ ? 2p i 1.. ] = v [i ? p 1..p] и · v [1..i ? p] = v [p 1..i].
Отметим, что если i = p, вследствие чего квадрат формируется из суффикса w строки u и префикса w строки v, второе условие сводится к утверждению, что ? = ?, и поэтому становится ненужным. [1]
Первое условие, которое говорит о том, что строка v [i?p 1..p] длиной 2p?I является суффиксом строки u, выполняется только тогда, когда LS[p] ? 2p ?i, т.е. только в случае выполнения неравенства 2p ? LS[p]? i. Второе условие эквивалентно неравенству i ? p LP [p 1], что и завершает доказательство [1].
Правый квадрат возможен только для тех значений p и i, которые удовлетворяют условиям леммы 1. Кроме того, для каждого допустимого значения p ? 1.. соответствующие допустимые значения величины i могут находиться только в интервале 2p ? LS[p]..p LP [p 1].
Для вычисления левых квадратов нужны аналогичные массивы: · Массив L [2.. ]: для ка
Вывод
В ходе работы были рассмотрены различные алгоритмы решения каждой из задач. Был проведен сравнительный анализ этих алгоритмов. Для каждой из задач был реализован один алгоритм, менее требовательный к памяти. Программа была реализована на 2 языках программирования: Pascal и C.
Так же была разработана программа, генерирующая строки с заданными параметрами. Генерация строк с различными параметрами необходима для качественного тестирования. Тестирование на строках длиной более 105 показало удовлетворительные результаты. Результат вычислений записывается в файл, что позволяет хранить результаты продолжительное время и использовать в других программах.
Список литературы
1. Смит Б. Методы и алгоритмы вычислений на строках. - М.: ООО «И.Д. Вильямс», 2006.
2. The String-to-String Correction Problem / Robert A. Wagner, Michael J. Fischer - Journal of the ACM Volume 21 Issue 1, Jan. 1974, Pages 168-173
