Разработка алгоритмов анализа длинных последовательностей, создаваемых системами имитационного моделирования

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Разработка алгоритмов анализа длинных последовательностей, создаваемых системами имитационного моделирования

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

Для каждой задачи рассмотрены различные варианты ее решения, эффективность того или иного алгоритма, в конце будет описан алгоритм, выбранный для реализации на языках программирования Pascal и C. Выбор алгоритма основывается на затратах памяти, так как сеанс моделирования порождает строки, характеризующиеся большим объемом данных — в каждой строке не менее 1 элементов.

1. Общая информация

1.1 Имитационное моделирование

Имитационное моделирование является одним из самых мощных инструментов анализа при разработке сложных систем и анализе процессов их функционирования. Имитационное моделирование как метод научного исследования предполагает использование компьютерных технологий для имитации различных процессов или операций — моделирования. Результаты определяются случайным характером процессов. На основе этих данных можно получить устойчивую статистику.

Имитационное моделирование позволяет моделировать поведение системы во времени. Его используют, когда:

1. Дорого или невозможно экспериментировать на реальном объекте.

2. Невозможно построить аналитическую модель: в системе есть время, причинные связи, последствие, нелинейности, стохастические (случайные) переменные.

3. необходимо сымитировать поведение системы во времени.

Области применения:

— Бизнес-процессы

— Бизнес-симуляция

— Боевые действия

— Динамика населения

— Дорожное движение

— ИТ-инфраструктура

— Математическое моделирование исторических процессов

— Логистика

— Пешеходная динамика

— Производство

— Рынок и конкуренция

— Сервисные центры

— Цепочки поставок

— Уличное движение

— Управление проектами

— Экономика здравоохранения

— Экосистема

— Информационная безопасность

— Релейная защита [5]

1.2 Основные определения

Последовательность — упорядоченный набор элементов.

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

Строковая последовательность (строка для краткости) — частный случай строки, удовлетворяющий следующим правилам:

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−6, трактуется как одномерный массив. Произвольную строку x на алфавите A в виде массива можно задать следующим образом — x: array [1.n] of A.

Строка x длины n и строка y длины m равны в том случае, если:

1. n=m

2. x[i]=y[i], [1]

Строка б является подстрокой в, если в=гбд.

б называется префиксом в, если в=бг. [3]

б называется суффиксом в, если в=гб. [3]

б называется бордером в, если б одновременно является и суффиксом и префиксом в.

Число p называется периодом строки б (n=|б|) если. Кратность — количество повторений периода.

2. Алгоритмы анализа длинных подпоследовательностей, создаваемых системами имитационного моделирования

2.1 Расстояние между строками

Постановка задачи. Для данных строк и, где ||, || > 0, и метрики d, задающей расстояния между строками, вычислить d (,).

Расстояние Хемминга [Hamming, 1982].

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

Расстоянием Левенштейна [Levenshtein distance] называется минимальное количество операций вставки или удаления одного символа, замены одного символа на другой, необходимых для преобразования одной строки в другую.

Алгоритм Вагнера-Фишера [Wagner-Fischer]

Для нахождения редакционного расстояния был использован алгоритм Вагнера-Фишера с небольшим изменением. Алгоритм Вагнера — Фишера вычисляет редакционное расстояние, основываясь на наблюдении, что если мы зарезервируем матрицу для хранения редакционных расстояний между всеми префиксами первой строки и всеми префиксами второй, то мы можем посчитать все значения в матрице, «потоково» заполняя матрицу. В итоге расстоянием между двумя полными строками будет значение, которое будет посчитано последним. Чтобы вычислить редакционное расстояние (расстояние Левенштейна) необходимо вычислить матрицу D. Определим возможные операции, которые могут быть использованы для преобразования одной строки в другую:

§ с (a, b) — цена замены символа a на символ b

§ с (е, b) — цена вставки символа b

§ с (a, е) — цена удаления символа a

и цену этих операций:

§ с (a, а) = 0

§ с (a, b) = 1 при a? b

§ с (е, b) = 1

§ с (a, е) = 1 [2]

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

Пусть и — две строки (длиной M и N соответственно) над некоторым алфавитом, тогда расстояние Левенштейна d (можно подсчитать по следующей формуле:, где

где m (a, b) равно нулю, если a=b и единице в противном случае min (a, b, c) возвращает наименьший из аргументов. Шаг по i представляет собой удаление из первой строки, по j — вставку в первую строку, а шаг по i и j символизирует замену символа или отсутствие изменений.

Очевидно, справедливы следующие утверждения:

— 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):

Рисунок 4 — Массив стоимостей на 3 шаге

4) 3?16, сдвигаем строки, вычисляем значения 2 строки, увеличиваем счетчик строк (Рисунок 5):

Рисунок 5 — Массив стоимостей на 4 шаге

5) 4?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 6):

Рисунок 6 — Массив стоимостей на 5 шаге

6) 5?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 7):

Рисунок 7 — Массив стоимостей на 6 шаге

7) 6?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 8):

Рисунок 8 — Массив стоимостей на 7 шаге

8) 7?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 9):

Рисунок 9 — Массив стоимостей на 8 шаге

9) 8?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 10):

Рисунок 10 — Массив стоимостей на 9 шаге

10) 9?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 11):

Рисунок 11 — Массив стоимостей на 10 шаге

11) 10?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 12):

Рисунок 12 — Массив стоимостей на 11 шаге

12) 11?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 13):

Рисунок 13 — Массив стоимостей на 12 шаге

13) 12?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 14):

Рисунок 14 — Массив стоимостей на 13 шаге

14) 13?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 15):

Рисунок 15 — Массив стоимостей на 14 шаге

15) 14?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 16):

Рисунок 16 — Массив стоимостей на 15 шаге

16) 15?16, сдвигаем строки, вычисляем новые значения, увеличиваем счетчик строк (Рисунок 17):

Рисунок 17 — Массив стоимостей на 16 шаге

16=16, расстояние Левенштейна вычислено.

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

2.2 Вычисление наибольшей общей подпоследовательности

Постановка задачи. Для данных строк и (||, || > 0) найти |LCS(,)|, где LCS(,) — самая длинная общая подпоследовательность (longest common subsequence) и.

Подпоследовательность последовательности 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).

Заполнение происходит в двойном цикле по i и j с увеличением значений на 1, таким образом, на каждой итерации нужные на этом шаге значения ячеек уже вычислены. После того, как произойдет полное заполнение матрицы, соединив ячейки, в которых происходило увеличение значений, мы получим искомую НОП. Соединять при этом нужно двигаясь от максимальных индексов к минимальным, если в ячейке увеличивалось значение, то добавляем соответствующий элемент к LCS, если нет, то двигаемся вверх или влево в зависимости от того где находится большее значение в матрице (Рисунок 18, 19).

Рисунок 18 — Заполненная матрица похожести для строк и

Рисунок 19 — Выделение LCS

Временная сложность алгоритма — O (m*n), по памяти O (m*n). Очевидно, что для работы с большими объемами данных он не подходит, так будет требоваться много памяти.

Алгоритм Ханта-Шиманского [Hunt, Szymanski]

Метод выделения LCS для двух входных строк и Ханта и Шиманского эквивалентен нахождению максимального монотонно возрастающего пути в графе, состоящего из точек (i, j), таких, что = . На рисунке 20 иллюстрируется LCS (longestsunsequense, needlemanwunsh)=neeun, определенная с помощью «наибольшей» строго убывающей и непрерывной ломаной линии, проходящей через узлы сетки, представляющие совпадения =.

Рисунок 20 — LCS, определенная с помощью «наибольшей» строго убывающей и непрерывной ломаной линии Ключевым в методе является массив значений. Установим некоторые свойства массива j, которые будут использованы в данном алгоритме.

Лемма 1. Для всех целых i1. и 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].

Далее, поскольку элемент 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]. Что и требовалось доказать.

Лемма 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], если такого не существует.

Доказательство. Сначала рассмотрим, как более простой, второй вариант вычисления 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].

Теперь предполагаем, что существует наименьшее целое из интервала 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? 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. Вычисление массива 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 были упорядочены в убывающем порядке.

Шаг 2. Начальное задание значений массива

Полагаем < 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). Для реализации был выбран этот алгоритм.

Теорема 1. (1).

Обозначим длину LCS для суффиксов (i+1, m) и (j+1, n) как =|LCS ((i+1, m),(j+1, n))| (2), где: — первая строка; n — длина первой строки; - вторая строка; m — длина второй строки.

Для 0

Определим формулой:, тогда для 0< i

Доказательство: пусть для j=. — произвольная LCS ((i, j),(i,), — произвольная LCS ((i+1, n),(, тогда с= является общей подпоследовательностью и, ее длина равна M. Таким образом, ?(3).

Пусть — произвольная LCS (,), тогда является подпоследовательностью, равной S1S2, где S1 — подпоследовательность (1, i), а S2 — подпоследовательность (i+1, n). Таким образом, существует значение, такое, что S2 является подпоследовательностью (1,), а S2 — подпоследовательностью (, m).

Длины S1 и S2 удовлетворяют следующим условиям:

|S1|?|LCS ((1, i),(1,))|? согласно (1).

|S2|?|LCS ((i+1, n),(+1, m))|? согласно (2)

Таким образом: (4)

Из неравенств (3) и (4) получаем. Что и требовалось доказать.

Алгоритм:

1) Сначала необходимо проверить не тривиальный ли случай. Если хотя бы одна из строк пуста, то в качестве результата возвращается пустая строка. Если хотя бы одна из строк односимвольная, то проверяется, содержится ли этот символ в другой строке. Если содержится, то в качестве результата возвращается этот символ, в противном случае — пустая строка.

2) Если случай нетривиальный, первая строка делится пополам, после чего ищутся длина наибольшей общей подпоследовательности ее первой половины и префиксов второй строки различной длины и длина LCS ее второй половины и суффиксов второй строки различной длины.

3) По теореме 1 ищется первая позиция во второй строке К такая, что LCS первой половины первой строки и первых К символов второй строки в соединении с LCS второй половины первой строки и последних m-K (m — длина второй строки) символов второй строки равна требуемой LCS первой и второй строк.

4) Найденное К используется для решения двух подзадач, для которых так же вычисляются шаги 1−4.

5) В конечном итоге все подзадачи сводятся к тривиальным и их результаты объединяются.

Вычисление длины 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.

После решения двух задач (для каждой половины) получим два вектора .) и будет длиной LCS для строк и.

2.3 Вычисление длины периода и количество повторений периода (кратность)

Постановка задачи. Для данной строки, || = n > 0, найти самую длинную подстроку, встречающуюся в больше одного раза. Самая длинная повторяющаяся подстрока — это самая длинная из строк максимальной длины x, такая, что = uxvxw для некоторых строк u, v и w, где |u|0, |v|0 и |w| 0. Если же существует несколько периодов максимальной длины, то выбрать период с максимальной кратностью.

Алгоритм Крочемора [Crochemore]

Основная идея алгоритма Крочемора: выполнение декомпозиции подпоследовательностей на каждом уровне? только относительно последовательностей, которые на этом уровне являются малыми.

На уровне ?? 2 разбиение множества позиций строки на отдельные непересекающиеся множества (последовательности) — это декомпозиция разбиения на уровне? ? 1.

В декомпозиции последовательности на подпоследовательности (,, …,) (q ?1) назовем одну подпоследовательность с самым большим количеством элементов большой, а остальные q — 1 подпоследовательностей — малыми. Для уровня? = 1 каждая последовательность малая.

Основная сложность в реализации этого алгоритма заключается в структурах данных, обеспечивающих время выполнения алгоритма за O (n log n).

Структуры необходимые для обеспечения работы алгоритма за 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].

— Стек INDEXSTACK: стек неиспользованных индексов последовательностей, инициализированный для размещения индексов 1,2,…, 2n.

Всякий раз, когда необходимо сформировать новую последовательность или на уровне 1, или в качестве части декомпозиции существующей последовательности, из стека INDEXSTACK извлекается индекс последовательности. Если последовательность становится пустой в результате ее декомпозиции на подпоследовательности, индекс последовательности возвращается в стек INDEXSTACK. Всякий раз, когда к последовательности с индексом j добавляется позиция i, выполняются операторы присваивания SEQ[i] < j; SEQSIZE[j] < SEQSIZE[j] + 1, а номер i добавляется в конец списка SEQLIST[j]. Если i-я позиция удаляется из последовательности с индексом j в результате его вхождения в подпоследовательность с индексом j, выполняется присваивание SEQSIZE[i]

2. Управление малыми последовательностями.

— Очередь SMALL: очередь индексов j малых последовательностей, организованная таким образом, что (для? > 1) все имеющиеся в ней малые последовательности являются подпоследовательностями одной и той же последовательности предыдущего уровня.

— Очередь QUEUE: очередь пар (i, j), где i — позиция в малой последовательности с индексом j, которая должна использоваться для декомпозиции текущего уровня; для каждого j позиции i располагаются в возрастающем порядке.

— Массив LASTSMALL [1.2n]: LASTSMALL[] = j > 0 тогда и только тогда, когда j — это индекс малой последовательности, использованной последней по времени для декомпозиции последовательности с индексом.

Для? = 1 очередь SMALL содержит все индексы, которые первоначально вычисляются в соответствии с каждым символом строки x; для? > 1 очередь SMALL создается повторно путем просмотра подпоследовательностей, тех последовательностей, для которых была выполнена декомпозиция на уровне ?, и добавлением к очереди SMALL всех подпоследовательностей, кроме единственной «большой» подпоследовательности (см. описание массивов SPLIT и SUBSEQ в следующем пункте). Для каждого элемента j в очереди SPLIT эти действия можно выполнить за один просмотр списка, на который указывает элемент SUBSEQ[j]. Таким образом, очередь SMALL модифицируется за время, пропорциональное количеству имеющихся в ней элементов.

Очередь 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[.

3. Организация подпоследовательностей.

— Массив SPLITFLAG [1.2n]: SPLITFLAG[j] = 1 тогда и только тогда, когда последовательность с индексом j будет подвергнута декомпозиции на текущем уровне (с использованием последовательностей, которые хранятся в очереди SMALL).

— Список SPLIT: список последовательностей j, которые будут подвергнуты декомпозиции на текущем уровне (т.е. для которых SPLITFLAG[j] = 1).

— Массив SUBSEQ [1.2n]: при декомпозиции последовательности j на текущем уровне SUBSEQ[j] указывает на список индексов подпоследовательностей последовательности j, первым элементом в этом списке будет сам индекс j.

Все эти структуры данных инициализируются для каждого уровня? > 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 массивы GAP и GAPLIST обновляются при удалении элемента (i, j) из очереди QUEUE, что приводит к декомпозиции последовательности = SEQ [i?1], при которой позиция i?1 в SEQLIST[] будет перемещена в конец SEQLIST[]. Поскольку списки, на которые указывают и SEQLIST и GAPLIST, двусвязные, повторное вычисление элементов массива GAP, необходимое из-за удаления позиции i? 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.

Для описания процедуры C3 (u, v) (ищет квадраты класса С3) вначале отметим, что новые квадраты в строке uv могут быть двух видов:

· правый квадрат, когда второе вхождение w в строку uv полностью находится в подстроке v;

· левый квадрат, когда в подстроке u имеется непустой префикс второго вхождения w.

Например, подстроки u = aba и v = ba порождают правый квадрат = (ba и левый квадрат = (ab.

Процедура 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).

Например, для строки v = abaababa массив LP [2.9] = 1 303 010. Если u=abaab, тогда LS [1.8] = 2 005 020. Приближенно можно сказать, что массив LP рекуррентно определяет максимальные длины префиксов v внутри самой v, а массив LS определяет вхождения суффиксов u максимальной длины в строку v.

Лемма 1. Пусть u [1.] и v [1.] - произвольные непустые строки и пусть p? и I? p.2p?1 — положительные целые числа. В uv имеется квадрат длиной 2p, заканчивающийся на i-й позиции строки v, тогда и только тогда, когда: 2p? LS[p] ?i ?p + LP [p + 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], что и завершает доказательство.

Правый квадрат возможен только для тех значений p и i, которые удовлетворяют условиям леммы 1. Кроме того, для каждого допустимого значения p? 1. соответствующие допустимые значения величины i могут находиться только в интервале 2p? LS[p]. .p + LP [p + 1].

Для вычисления левых квадратов нужны аналогичные массивы:

· Массив L [2.]: для каждой позиции i = 2,3,…, строки u L [i]= lcp (u[i.], v).

· Массив L [1.? 1]: для каждой позиции i = 1,2,…,? 1 строки u

L [i] = lcs (u[?.. i], u).

Временная сложность алгоритма — O (n log n), емкостная — O (n).

3. Описание программы

3.1 Средства, используемые в разработке

Microsoft Visual Studio

Visual Studio — это полный набор инструментов и служб для разработки приложений для настольных компьютеров, Интернета, мобильных устройств и облачных систем. Visual Studio позволяет создавать как консольные приложения, так и приложения с графическим интерфейсом. Основными языками Visual Studio являются Visual C#, Visual Basic и C++. [11]

Microsoft Visual Studio объединяет в себе огромное количество функций, позволяющих осуществлять разработки для Windows всех версий, в том числе и 8, Интернета, SharePoint, различных мобильных устройств и облачных технологий. Visual Studio включает в себя редактор исходного кода с поддержкой технологии IntelliSense и возможностью рефакторинга кода. Встроенный отладчик может работать как отладчик уровня исходного кода, так и как отладчик машинного уровня. Остальные встраиваемые инструменты включают в себя редактор форм для упрощения создания графического интерфейса приложения, веб-редактор, дизайнер классов и дизайнер схемы базы данных. Visual Studio позволяет создавать и подключать сторонние дополнения (плагины) для расширения функциональности практически на каждом уровне.

Плюсом Microsoft Visual Studio для разработки на С является наличие стандартной утилиты анализа кода Code Analysis. Эта утилита позволяет быстро отыскивать «слабые» места в коде. Например, использование не безопасных функций, утечки памяти, выход за границы массива.

В этой работе для создания проекта используется Visual Studio Professional 2013.

В качестве языка разработки используется C.

PascalABC.NET

PascalABC.NET — это среда разработки, поддерживающая язык Pascal нового поколения, включающий классический Pascal, большинство возможностей языка Delphi, а также ряд собственных расширений. Он реализован на платформе Microsoft.NET и содержит все современные языковые средства: классы, перегрузку операций, интерфейсы, обработку исключений, обобщенные классы и подпрограммы, сборку мусора, лямбда-выражения, средства параллельного программирования.

PascalABC.NET является мультипарадигменным языком: на нем можно программировать в структурном, объектно-ориентированном и функциональном стилях.

PascalABC.NET — это также простая и мощная интегрированная среда разработки, поддерживающая технологию IntelliSense, содержащая средства автоформатирования, встроенный отладчик и встроенный дизайнер форм.

Самое большое преимущество среды разработки PascalABC.NET перед другими является наличие удобного режима отладки. В этом режиме пользователю доступны следующие средства отладки: возможность задания точек останова программы, пошаговое выполнение кода программы со входом в подпрограмму и без входа в подпрограмму, а так же просмотр текущих значений глобальных и локальных переменных.

Динамическое программирование Динамическое программирование — метод решения сложных задач путем их разбиения на более простые. Основная идея: основная задача разбивается на меньшие отдельные задачи (подзадачи), они решаются, после чего необходимо объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход метода заключается в решении каждой подзадачи один раз. Это приводит к сокращению вычислений. Этот подход полезен в случаях, когда число повторяющихся подзадач экспоненциально велико.

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

1. Разбиение задачи на подзадачи меньшего размера.

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

3. Использование полученного решения подзадач для конструирования решения исходной задачи.

Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же), динамическое программирование пользуется следующими свойствами задачи:

· перекрывающиеся подзадачи;

· оптимальная подструктура;

· возможность запоминания решения часто встречающихся подзадач.

Динамическое программирование бывает двух видов:

· нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.

· восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи, просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.

3.2 Структура программы

Структура программы на языке Pascal

Структуры данных:

IntArray = array of longint — массив целых чисел.

IntMatrix = array of array of longint — массив массивов целых чисел.

Функции и процедуры:

function Min (X: integer; Y: integer) — функция возвращающая минимальное значение из пары чисел X и Y.

function Max (X: integer; Y: integer) — функция возвращающая максимальное значение из пары чисел X и Y.

function SubString (STR: IntArray; SubSTR: IntArray; FirstIndex: longint) — поиск индекса первого вхождения подмассива SubSTR в массив STR с элемента FirstIndex.

procedure ReadFromFile (file1: text; path: string; var S: IntArray) — процедура считывающая значения массива из файла. На вход подается переменная текстового файла file1, путь к файлу path, массив S, который будет заполняться.

procedure InitSEQ () — процедура, инициализирующая подпоследовательность. Изначально заполняет LCS -1, то есть LCS пуста.

procedure LCS_LENGTH (M: integer; N: integer; X: IntArray; Y: IntArray; var LL: IntArray) — Процедура, вычисляющая вектор, равный последней строке матрицы LCS. Входные параметры: X — первая строка, Y — вторая строка, LL — массив, в который будет помещен результат.

procedure FindMaxPeriod (STR: IntArray) — процедура, которая находит период максимальной длины. На вход подается массив STR, в котором содержится строка для которой необходимо произвести поиск.

procedure LCS (M: integer; N: integer; X: IntArray; Y: IntArray; var C: IntArray) — процедура, которая вычисляет LCS. На вход подаются: длина первой строки M; длина второй строки N; массив X, содержащий первую строку; массив Y, содержащий вторую строку; массив C, в который будет записываться LCS.

function EditDinst (D: IntMatrix; X: IntArray; Y: IntArray; i, j: longint) — функция, заполняющая массив стоимостей. На вход функция получает: массив стоимостей D; массив X, содержащий первую строку; массив Y, содержащий вторую строку; текущий элемент i в массиве X; текущий элемент j в массиве Y.

function Levenshtein (X: IntArray; Y: IntArray; l1: longint; l2: longint) — функция, вычисляющая расстояние Левенштейна. Входные параметры: массив X, содержащий первую строку; массив Y, содержащий вторую строку; длина первой строки l1; длина второй строки l2.

procedure PrintLCS () — выводит результат вычислений LCS.

procedure PrintEditDinst () — выводит результат вычислений расстояния Левенштейна.

procedure PrintLCSToFile () — записывает в файл результат вычислений LCS.

procedure PrintEditDinstToFile () — записывает результат вычисления редакционного расстояния.

Структура программы на языке C

Функции и процедуры:

int Min (int X, int Y) — возвращает минимальное значение из пары чисел X и Y.

int Max (int X, int Y) — возвращает максимальное значение из пары чисел X и Y.

long int subString (int str[], long int strSize, int subStr[], long int subStrSize, long int firstIndex) — поиск индекса первого вхождения подмассива subStr[], длинной subStrSize, в массив str[], длинной strSize, с элемента firstIndex.

int * lcsLength (long int m, long int n, int X[], int Y[], int LL[]) — вычисление вектора, который равен последней строке матрицы LCS. Входные параметры: X[] - первая строка; Y[] - вторая строка; LL[] - массив, в который будет помещен результат; m — длина первой строки; n — длина второй строки.

int * lcs (long int m, long int n, int X[], int Y[], int C[]) — вычисляет LCS. Входные параметры: длина первой строки m; длина второй строки n; массив X[], содержащий первую строку; массив Y[], содержащий вторую строку; массив C[], в который будет записываться LCS.

long int editDinst (long int D[], long int n, int X[], int Y[], long int i, long int j) — заполнение массива стоимостей D[]. n — длина второй строки; X[] - первая строка; Y[] - вторая строка; i — текущий элемент в массиве X; j — текущий элемент в массиве Y.

long int levenshtein (int X[], int Y[], long int l1, long int l2) — вычисление расстояния Левенштейна. X[] - первая строка; Y[] - вторая строка; l1 — длина первой строки; l2 — длина второй строки.

void findMaxPeriod (int str[], long int length) — нахождение периода максимальной длины. Входные параметры: str[] - строка, в которой необходимо найти период максимальной длины; length — длина строки.

void printLCSToFile (int C[]) — запись результата вычисления LCS в файл.

void printEDToFile (long int editDinstance) — запись результата вычисления расстояния Левенштейна в файл.

3.3 Описание и структура программы, создающей строки с заданными параметрами

Программа StringGenerator создана для генерации тестовых данных. Так как основная программа решает три задачи: нахождение расстояния Левенштейна двух строк, нахождение наибольшей общей подпоследовательности и нахождение максимального периода максимальной кратности (не меньше 2), то к тестовым данным были предъявлены следующие условия:

— Первая строка должна генерироваться с указанными параметрами периодичности и длины.

— Вторая строка должна получаться путем изменения указанного числа элементов первой строки.

Эти два условия позволяют создать тестовые данные одновременно для всех трех решаемых задач, так как:

— Заранее заданные параметры периодичности позволяют оценивать правильность определения наличия периода в строке (при этом стоит учитывать, что, например, период длины 3 кратности 4 будет определяться программой как период длины 6 кратности 2, и это правильно, так как программа ищет максимальный период).

— Получение второй строки путем изменения первой позволяет определять правильность нахождения расстояния Левенштейна и наибольшей общей подпоследовательности.

При запуске программы пользователю предлагается ввести параметры для генерации первой строки:

1) Длина периода.

2) Кратность периода.

3) Смещение периода (указывается, чтобы период начинался не с начала строки).

4) Длина строки.

Во время ввода проверяется корректность вводимых данных, отсеиваются отрицательные значения и значения длины, меньшие минимально возможного (Смещение + Длина периода * Кратность периода).

После окончания процесса генерации первой строки данные записываются в файл «S1.txt», а пользователю, для генерации второй строки, предлагается ввести количество отличий второй строки от первой.

После ввода указанное количество случайных элементов второй строки заменяется новыми, при этом проверяется, чтобы несколько раз не был изменен один и тот же элемент, а так же, что генератор случайных чисел выдал новое случайное число, не равное уже существующему элементу. Данные проверки гарантируют, что вторая строка будет иметь то количество отличий, которое указал пользователь. После окончания процесса генерации второй строки данные записываются в файл «S2.txt» и программа заканчивает свою работу.

3.4 Инструкция пользователю

Программа StringGenerator создает строки с заданными характеристиками. В ней можно задать: длину строки, длину периода, кратность периода, смещение периода, количество отличий второй строки от первой. Результат работы записывается в текстовый файл S1 или файлы S1и S2. При запуске пользователю будет предложено ввести длину периода, затем кратность, смещение периода относительно начала строки, длину строки и количество отличий второй строки от первой (Рисунок 25).

Рисунок 25 — Диалоговое меню программы StringGenerator

Все алгоритмы анализа строк реализованы в основной программе. Программа имеет реализацию на 2 языках программирования: С и Pascal. Программа на С написана с использованием стандарта С-99. При запуске пользователю будет предложено выбрать конкретный алгоритм для выполнения или вычислить все.

Диалоговое меню программы на языке С (Рисунок 26):

Рисунок 26 — Диалоговое меню программы на языке С Диалоговое меню программы на языке Pascal (Рисунок 27):

Рисунок 27 — диалоговое меню программы на языке Pascal

Необходимо ввести число от 1 до 4 для выполнения определенной задачи или задач:

1. При вводе 1 будет вычислена LCS.

2. При вводе 2 будет вычислено расстояние Левенштейна.

3. При вводе 3 будет найден период максимальной длины и его кратность, так дополнительно необходимо указать для какой строки необходимо выполнить поиск: необходимо ввести 1 для поиска в первой строке, 2 для поиска во второй.

4. При вводе 4 будет вычислено расстояние Левенштейна, найдена LCS и наибольший период и его кратность. Так же необходимо уточнение в какой из строк следует искать период: вводится 1 для поиска в 1 строке, 2 для поиска во второй.

Данные на вход программе должны подаваться в виде файлов, содержащих пары чисел (State_i, s_i), где s_i — момент системного времени, в который произошло i-е событие в модели, State_i — состояние системы в этот момент (целое положительное число). Рекомендуется, чтобы каждая пара чисел находилась в новой строке. Файлы должны называться S1. txt и S2. txt для первой и второй строки соответственно.

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

a) редакционного расстояния будет находиться в файле EditDinst. txt (Рисунок 28).

Рисунок 28 — Результат вычисления расстояния Левенштейна

b) наибольшей общей подпоследовательности в файле LCS. txt (Рисунок 29).

Рисунок 29 — Результат вычисления LCS

c) максимального периода максимальной кратности в файле Period. txt (Рисунок 30).

Рисунок 30 — результат вычисления периодической структуры

При новом запуске программы все старые файлы решений будут удалены.

3.5 Примеры работы программы

Примеры работы программы будут приведены на строках небольшого размера (40−80 символов) для наглядности и возможности оценки корректности вычислений.

Вычисление расстояния Левенштейна.

1) Строки совпадают.

Первая строка (Рисунок 31):

Рисунок 31 — первая строка Вторая строка (Рисунок 32):

Рисунок 32 — вторая строка

Результат вычислений (Рисунок 33):

Рисунок 33 — результат вычисления расстояния Левенштейна

1) Строки абсолютно разные.

Первая строка (Рисунок 34):

Рисунок 34 — первая строка Вторая строка (Рисунок 35):

Рисунок 35 — вторая строка

Результат вычислений (Рисунок 36):

Рисунок 36 — результат вычисления расстояния Левенштейна

2) Строки частично разные, длина строк совпадает.

Первая строка (Рисунок 37):

Рисунок 37 — первая строка Вторая строка (Рисунок 38):

Рисунок 38 — вторая строка Результат вычислений (Рисунок 39):

Рисунок 39 — Результат вычисления расстояния Левенштейна

Строки частично разные, длина строка разная.

Первая строка (Рисунок 40):

Рисунок 40 — Первая строка Вторая строка (Рисунок 41):

Рисунок 41 — Вторая строка Результат вычислений (Рисунок 42):

Рисунок 42 — Результат вычисления расстояния Левенштейна Нахождение наибольшей общей подпоследовательности.

1) Строки совпадают.

Первая строка (Рисунок 43):

Рисунок 43 — Первая строка Вторая строка (Рисунок 44):

Рисунок 44 — Вторая строка

Результат вычислений (Рисунок 45):

Рисунок 45 — Результат вычисления LCS

2) Строки абсолютно разные.

Первая строка (Рисунок 46):

Рисунок 46 — Первая строка

Вторая строка (Рисунок 47):

Рисунок 47 — Вторая строка Результат вычислений (Рисунок 48):

Рисунок 48 — Результат вычисления LCS

3) Строки частично разные, длина строк совпадает.

Первая строка (Рисунок 49):

Рисунок 49 — Первая строка

Вторая строка (Рисунок 50):

Рисунок 50 — Вторая строка Результат вычислений (Рисунок 51):

Рисунок 51 — Результат вычисления LCS

4) Строки частично разные, длина строк разная.

Первая строка (Рисунок 52):

Рисунок 52 — Первая строка

Вторая строка (Рисунок 53):

Рисунок 53 — Вторая строка Результат вычислений (Рисунок 54):

Рисунок 54 — Результат вычисления LCS

Нахождения периода максимальной кратности.

1) Период кратности более 2 не встречается в строке Строка (Рисунок 55):

Рисунок 55 — Первая строка

Результат вычислений (Рисунок 56):

Рисунок 56 — Результат вычисления периодической структуры

2) В строке только один максимальный период Строка (Рисунок 57):

Рисунок 57 — Строка, в которой необходимо найти период максимальной длины Результат вычислений (Рисунок 58):

Рисунок 58 — Результат вычисления периодической структуры

3) В строке несколько периодов максимальной длины Строка (Рисунок 59):

Рисунок 59 — Строка, в которой необходимо найти период максимальной длины Результат вычислений (Рисунок 60):

Рисунок 60 — Результат вычисления периодической структуры

Заключение

В ходе работы были рассмотрены различные алгоритмы решения каждой из задач. Был проведен сравнительный анализ этих алгоритмов. Для каждой из задач был реализован один алгоритм, менее требовательный к памяти. Программа была реализована на 2 языках программирования: Pascal и C.

Так же была разработана программа, генерирующая строки с заданными параметрами. Генерация строк с различными параметрами необходима для качественного тестирования. Тестирование на строках длиной более 10⁵ показало удовлетворительные результаты. Результат вычислений записывается в файл, что позволяет хранить результаты продолжительное время и использовать в других программах.

Список использованных источников

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

3. http://neerc.ifmo.ru/wiki/index.php? title=Основные_определения,_связанные_со_строками

4. Строгалев В. П., Толкачева И. О. Имитационное моделирование. — МГТУ им. Баумана, 2008.

5. Толстуев Ю. И., Планковский С. И. Моделирование и симуляция логических систем. Курс лекций. Харьковский авиационный институт. 2009.

6. Baeza-Yates R.A. (1989b) «String searching algorithms revisited,» Lecture Notes in Computer Science, Vol. 382, p. 75−96.

7. http://habrahabr.ru/post/142 825/

8. http://ru.wikipedia.org/wiki/PascalABC.NET

9. Беллман Р. Динамическое программирование. — М.: Изд-во иностранной литературы, 1960.

10. String Search / Graham A Stephen — October 1992.

11. http://ru.wikipedia.org/wiki/Visual_Studio

Приложение

Код основной программы на языке Pascal

type

IntArray = array of longint;

IntMatrix = array of array of longint;

var

file1: text;

S1, S2: IntArray; // Строки

Length1, Length2: longint; // Длины строк

SEQ: IntArray; // НОП и всп. массив

mode, strNum: integer;

// Поиск минимального значения

function Min (X: integer; Y: integer): integer;

begin

if X < Y then Min:= X

else Min:= Y;

end;

// Поиск максимального значения

function Max (X: integer; Y: integer): integer; begin

if X > Y then Max:= X

else Max:= Y;

end;

// Поиск подстроки в строке

function SubString (STR: IntArray; SubSTR: IntArray; FirstIndex: longint): longint;

var

i, j, LastIndex: longint;

isFind: boolean;

begin

SubString:= -1; // Изначально вхождение не найдено

LastIndex:= Length (STR) — Length (SubSTR);

if (FirstIndex <= LastIndex) Then

for i:= FirstIndex to LastIndex do

begin

isFind:= true;

for j:= 0 to SubSTR. Length — 1 do

if (SubSTR[j] <> STR [i + j]) then isFind:= false;

if (isFind) then

begin

SubString:= i;

break;

end;

end;

end;

// Процедура, считывающая значения массива из файла

procedure ReadFromFile (file1: text; path: string; var S: IntArray);

var A: integer;

c: char;

Length: longint;

i: longint;

begin

assign (file1, path);

reset (file1);

Length:= 0;

while (not eof (file1)) do // Придется полностью просматривать файл

begin // т.к. FileSize работает некорретно

while (c = ' ') do

read (file1, c);

read (file1, c);

A:= (ord (c) — 48);

read (file1, c);

while (c <> ' ') do

begin

A:= A * 10 + (ord (c) — 48);

read (file1, c);

end;

INC (Length);

read (file1, c);

if (eof (file1)) then break;

read (file1, c);

while (c <> #13) do

read (file1, c);

read (file1, c);

end;

reset (file1);

setLength (S, Length); // Выделяем память под массив

i:= 0;

while (not eof (file1)) do // Придется полностью просматривать файл

begin // т.к. FileSize работает некорретно

while (c = ' ') do

read (file1, c);

read (file1, c);

A:= (ord (c) — 48);

read (file1, c);

while (c <> ' ') do

begin

A:= A * 10 + (ord (c) — 48);

read (file1, c);

end;

S[i]: = A;

read (file1, c);

if (eof (file1)) then break;

read (file1, c);

while (c <> #13) do

read (file1, c);

read (file1, c); // Сам символ перевода каретки

INC (i);

end;

close (file1);

end;

// Процедура, инициализирующая подпоследовательность

// Изначально заполняет НОП -1-ми, т. е. НОП — пуста

procedure InitSEQ ();

var j: longint;

begin

Length1:= Length (S1);

Length2:= Length (S2);

if (Length1 < Length2) then // Длина C — минимум из M и N (приходится

begin // брать с запасом, т.к. пока мы не знаем

SetLength (SEQ, Length1); // длину НОП

for j:= 0 to Length1 — 1 do

SEQ[j]: = -1; // -1 показывает конец НОП,

end // изначально НОП пуста

else

begin

SetLength (SEQ, Length2);

for j:= 0 to Length2 — 1 do

SEQ[j]: = -1;

end;

end;

// Процедура, вычисляющая вектор, равный последней строке матрицы НОП

// Входные параметры: X — первая строка, Y — вторая строка, LL — массив,

// в который будет помещен результат

procedure LCS_LENGTH (M: integer; N: integer; X: IntArray; Y: IntArray; var LL: IntArray);

var

i, j: longint; // Итерационные счетчики

H: IntMatrix; // Двумерный массив, хранящий i-ю и (i-1) — ю строки матрицы НОП

begin

SetLength (H, 2); // Устанавливаем размер открытого массива H

SetLength (H[0], N + 1);

SetLength (H[1], N + 1);

for i:= 0 to N do // Инициализируем 2-ю строку массива H

H [1, i]: = 0;

for i:= 0 to M — 1 do // Вычисляем H

begin

for j:= 0 to N do // Сдвигаем вторую строку вверх

H [0, j]: = H [1, j];

for j:= 0 to N — 1 do // Само вычисление

if (X[i] = Y[j]) then H [1, j + 1]: = H [0, j] + 1

else H [1, j + 1]: = Max (H[1, j], H [0, j + 1]);

end;

for j:= 0 to N do // Копируем результат в выходной вектор

LL[j]: = H [1, j];

end;

// Нахождение максимального периода максимальной кратности

procedure FindMaxPeriod (STR: IntArray);

var

SubSTR: IntMatrix; // Матрица подстрок текущей длины

MaxCurrMult: IntArray; // Массив максимальных кратностей для подстрок текущей длины

PeriodLength, offset, index, prev_index, i, j: longint;

MaxMult, CurrMult: longint;

AlreadyWas: boolean;

begin

PeriodLength:= Length (STR) div 2;

MaxMult:= 1;

while (PeriodLength > 0) do // Начинаем с подстрок большей длины. Если находим период с кратностью >1, то закончили

begin

SetLength (SubSTR, Length (STR));

SetLength (MaxCurrMult, Length (STR));

offset:= 0;

while ((Length (STR) — (offset + 2 * PeriodLength)) + 1 > 0) do // Если в строке осталось меньше элементов, чем в подстроке, то берем след.

begin

SetLength (SubSTR[offset], PeriodLength);

index:= 0;

CurrMult:= 1;

MaxCurrMult[offset]: = 1;

for i:= 0 to PeriodLength — 1 do

SubSTR [offset, i]: = STR [i + offset];

prev_index:= SubString (STR, SubSTR[offset], 0);

while (index <> -1) do // Поочередно ищем вхождения, определяя, период это или нет.

begin

index:= SubString (STR, SubSTR[offset], prev_index + 1);

if (index = prev_index + PeriodLength) then

begin

INC (CurrMult);

if (CurrMult > MaxCurrMult[offset]) then MaxCurrMult[offset]: = CurrMult;

end

else CurrMult:= 1;

prev_index:= index;

end;

if (MaxCurrMult[offset] > MaxMult) then MaxMult:= MaxCurrMult[offset];

INC (offset);

end;

if (MaxMult > 1) then break;

DEC (PeriodLength);

end;

assign (output, 'Period.txt');

rewrite (output);

if (MaxMult < 2) then

writeln ('Периодов кратности не менее 2 в исходной строке нет')

else

begin

writeln ('Максимальный период: ', Length (SubSTR[0]));

writeln ('Кратность периода: ', MaxMult);

j:= 0;

for offset:= 0 to Length (STR) do

begin

try

begin

AlreadyWas:= false;

if (MaxCurrMult[offset] = MaxMult) then

begin

for i:= 0 to offset — 1 do

if (SubString (SubSTR[i], SubSTR[offset], 0) <> -1) then AlreadyWas:= true;

if (AlreadyWas) then continue;

INC (j);

writeln ('Период #', j, ':');

for i:= 0 to Length (SubSTR[offset]) — 1 do

write (SubSTR[offset, i], ' ');

writeln ();

end;

end;

except

begin

close (output);

break;

end;

end;

end;

end;

try

close (output);

except

end;

end;

// Процедура, вычисляющая НОП

procedure LCS (M: integer; N: integer; X: IntArray; Y: IntArray; var C: IntArray);

var

i, j, k: longint; // Итерационные счетчики

L1, L2: IntArray; // Последнии строки матрицы H

SUB_X, SUB_Y: IntArray; // Подстроки

C1, C2: IntArray;

notEmpty: boolean; // Флаг непустой подпоследовательности

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

SetLength (L1, N + 1);

SetLength (L2, N + 1);

notEmpty:= false;

if ((M = 0) or (N = 0)) then // Тривиальный случай

C[0]: = -1

else if (M = 1) then

begin

while ((notEmpty <> true) and (i < N)) do

begin

if (X[0] = Y[i]) then

notEmpty:= true;

INC (i);

end;

if (notEmpty = true) then C[0]: = X[0] // Если НОП не пуста, присваиваем ед. возможное значение

else C[0]: = -1; // Иначе — код ошибки

end

else if (N = 1) then

begin

while ((notEmpty <> true) and (i < M)) do

begin

if (Y[0] = X[i]) then

notEmpty:= true;

INC (i);

end;

if (notEmpty = true) then C[0]: = Y[0] // Если НОП не пуста, присваиваем ед. возможное значение

else C[0]: = -1; // Иначе — код ошибки

end

else begin // Начинается рассм. нетривиального случая

x_index:= M div 2; // Делим X напополам

SetLength (SUB_X, x_index);

SetLength (SUB_Y, N);

for i:= 0 to x_index — 1 do // Заполняем подматрицы

SUB_X[i]: = X[i];

for i:= 0 to N — 1 do

SUB_Y[i]: = Y[i];

LCS_LENGTH (x_index, N, SUB_X, SUB_Y, L1); // Вычисляем L1

SetLength (SUB_X, M — x_index); // Меняем длину «подмассива» X

last_i:= High (SUB_X); // Получаем индекс последнего эл-та SUB_X

for i:= 0 to last_i do // Заполняем подматрицы

SUB_X[i]: = X [M — i — 1];

for i:= 0 to N — 1 do

SUB_Y[i]: = Y [N — i — 1];

LCS_LENGTH (M — x_index, N, SUB_X, SUB_Y, L2); // Вычисляем L2

lcs_max:= 0;

for i:= 0 to N do // Находим Max (L1j + L2n-j)

if (lcs_max < L1 [i] + L2 [N — i]) then

lcs_max:= L1 [i] + L2 [N — i];

if (lcs_max = 0) then exit; // Если lcs пуста, выходим.

i:= 0;

Found:= false;

while ((Found = false) and (i <= N)) do // Находим y_index

begin

if (lcs_max = L1 [i] + L2 [N — i]) then

begin

y_index:= i;

Found:= true

end;

INC (i);

end;

SetLength (SUB_X, x_index);

SetLength (SUB_Y, y_index);

for i:= 0 to x_index — 1 do // Заполняем подматрицы

SUB_X[i]: = X[i];

for i:= 0 to y_index — 1 do

SUB_Y[i]: = Y[i];

SetLength (C1, lcs_max);

SetLength (C2, lcs_max);

j:= High (C1);

for i:= 0 to j do

begin

C1 [i]: = -1;

C2 [i]: = -1;

end;

LCS (x_index, y_index, SUB_X, SUB_Y, C1);

SetLength (SUB_X, M — x_index);

SetLength (SUB_Y, N — y_index);

last_i:= High (SUB_X);

for j:= 0 to last_i do // Заполняем подматрицы

SUB_X[j]: = X [x_index + j];

last_i:= High (SUB_Y);

for j:= 0 to last_i do

SUB_Y[j]: = Y [y_index + j];

LCS (M — x_index, N — y_index, SUB_X, SUB_Y, C2);

k:= 0;

j:= Length (C1);

while ((k < j) and (C1 [k] <> -1)) do // Объединяем С1 и С2 в С

begin

C[k]: = C1 [k];

INC (k);

end;

i:= k;

k:= 0;

j:= Length (C2);

while ((k < j) and (C2 [k] <> -1)) do

begin

C [i+k]: = C2 [k];

INC (k);

end;

end;

end;

// Заполнение матрицы расстояний

function EditDinst (D: IntMatrix; X: IntArray; Y: IntArray; i, j: longint): longint;

var

res, prev, m: longint;

begin

res:= D [1, j — 1] + 1;

prev:= D [0, j] + 1;

if (res > prev) then res:= prev;

if X [i — 1] = Y [j — 1] then m:= 0

else m:= 1;

prev:= D [0, j — 1] + m;

if (res > prev) then res:= prev;

EditDinst:= res;

end;

// Функция вычисляющая расстояние Левенштейна

function Levenshtein (X: IntArray; Y: IntArray; l1: longint; l2: longint): longint;

var i, j: longint;

D: IntMatrix;

begin

SetLength (D, 2);

SetLength (D[0], l2 + 1);

SetLength (D[1], l2 + 1);

for i:= 0 to l2 do // Заполняем первую строку

D [0, i]: = i;

for i:= 1 to l1 do

begin

D [1, 0]: = i; // Первый элемент в строке

for j:= 1 to l2 do

D [1, j]: = EditDinst (D, X, Y, i, j);

for j:= 0 to l2 do

D [0, j]: = D [1, j];

end;

Levenshtein:= D [1, l2];

end;

// Процедура, выводящая на печать результаты

// вычислений

procedure PrintLCS ();

var i: longint;

begin

writeln ('Первая строка:');

for i:= 0 to Length1 — 1 do

write (S1 [i], ' ');

writeln ();

writeln ('Вторая строка:');

for i:= 0 to Length2 — 1 do

write (S2 [i], ' ');

writeln ();

writeln ('Наибольшая общая подпоследовательность: ');

i:= 0;

if (SEQ[0] = -1) then

writeln ('НОП пустая')

else

while ((i <= High (SEQ)) and (SEQ[i] <> -1)) do

begin

write (SEQ[i], ' ');

INC (i);

end;

end;

procedure PrintEditDinst ();

begin

writeln ();

write ('Редакционное расстояние: ', Levenshtein (S1, S2, Length1, Length2));

end;

// Процедура, осуществляющая вывод результатов в файл

procedure PrintLCSToFile ();

var i: longint;

begin

assign (output, 'LCS.txt'); // Файл OUTPUT определен в System и указывает устройство вывода

// => просто и элегантно перенаправляем вывод в файл

rewrite (output); //

writeln ('Наибольшая общая подпоследовательность: ');

i:= 0;

if (SEQ[0] = -1) then

writeln ('НОП пустая')

else

while ((i <= High (SEQ)) and (SEQ[i] <> -1)) do

begin

writeln (SEQ[i]);

INC (i);

end;

close (output);

end;

procedure PrintEditDinstToFile ();

begin

assign (output, 'EditDinst.txt');

rewrite (output);

write ('Редакционное расстояние: ', Levenshtein (S1, S2, Length1, Length2));

close (output);

end;

begin

assign (file1, 'EditDinst.txt');

erase (file1);

assign (file1, 'LCS.txt');

erase (file1);

assign (file1, 'Period.txt');

erase (file1);

mode:= -1;

writeln ('Выберите, что необходимо сделать (необходимо ввести число и нажать Enter): ');

writeln ('1. Наибольшая общая подпоследовательность');

writeln ('2. Редакционное расстояние');

writeln ('3. Наибольший период наибольшей кратности');

writeln ('4. Всё');

writeln ('0. Выход');

while ((mode <> 1) and (mode <> 2) and (mode <> 3) and (mode <> 4) and (mode <> 0)) do

try

begin

write ('Ввод: ');

readln (mode);

end;

except

mode:= -1;

end;

try

begin

ReadFromFile (file1, 'S1.txt', S1);

if Length (S1) = 0 then

begin

writeln ('Файл S1. txt пуст');

exit;

end;

end;

except

begin

writeln ('Данные в файле S1. txt представлены в неверном формате.');

writeln ('Представьте данные в правильном формате и удалите пустые строки');

exit;

end;

end;

try

begin

ReadFromFile (file1, 'S2.txt', S2);

if Length (S2) = 0 then

begin

writeln ('Файл S2. txt пуст');

exit;

end;

end;

except

begin

writeln ('Данные в файле S2. txt представлены в неверном формате.');

writeln ('Представьте данные в правильном формате и удалите пустые строки');

exit;

end;

end;

InitSEQ (); // Инициализируется матрица и определяются Length1 и Length2

CASE mode of

0: begin

writeln ('Работа программы прервана пользователем');

exit;

end;

1: begin

writeln ('Результаты будут помещены в файл LCS. txt');

writeln ('Дождитесь окончания работы программы…');

LCS (Length1, Length2, S1, S2, SEQ);

PrintLCSToFile ();

end;

2: begin

writeln ('Результаты будут помещены в файл EditDinst. txt');

writeln ('Дождитесь окончания работы программы…');

PrintEditDinstToFile ();

end;

3: begin

writeln ('В какой строке искать период? (введите число и нажмите Enter)');

writeln ('1. Первая строка');

writeln ('2. Строка');

write ('Ввод: ');

while ((strNum <> 1) and (strNum <> 2)) do

try

readln (strNum);

except

strNum:= 0;

end;

writeln ('Результаты будут помещены в файл Period. txt');

writeln ('Дождитесь окончания работы программы…');

if (strNum = 1) then

FindMaxPeriod (S1)

else

FindMaxPeriod (S2);

end;

4: begin

writeln ('В какой строке искать период? (введите число и нажмите Enter)');

writeln ('1. Первая строка');

writeln ('2. Строка');

write ('Ввод: ');

while ((strNum <> 1) and (strNum <> 2)) do

try

readln (strNum);

except

strNum:= 0;

end;

writeln ('Результаты будут помещены в файлы LCS. txt, EditDinst. txt и Period. txt');

writeln ('Дождитесь окончания работы программы…');

if (strNum = 1) then

FindMaxPeriod (S1)

else

FindMaxPeriod (S2);

LCS (Length1, Length2, S1, S2, SEQ);

PrintLCSToFile ();

PrintEditDinstToFile ();

end;

end;

try

close (Output);

except

end;

writeln ('Работа программы окончена.');

end.

Код основной программы на языке C

#include

#include

#include

// Вычисление минимального значения

int Min (int X, int Y)

{

if (X < Y)

return X;

else

return Y;

}

// Вычисление максимального значения

int Max (int X, int Y)

{

if (X > Y)

return X;

else

return Y;

}

// Поиск подстроки в строке

long int subString (int str[], long int strSize, int subStr[], long int subStrSize, long int firstIndex)

{

_Bool isFind;

int lastIndex = strSize — subStrSize;

if (firstIndex <= lastIndex) {

for (long int i = firstIndex; i <= lastIndex; i++)

{

isFind = true;

for (long int j = 0; j < subStrSize; j++)

if (subStr[j]≠ str [i + j])

isFind = false;

if (isFind == true) return i;

}

}

return -1;

}

// Процедура, вычисляющая вектор, равный последней строке матрицы НОП

int * lcsLength (long int m, long int n, int X[], int Y[], int LL[]) {

long int **H = (long int **) malloc (2 * sizeof (long int *));

long int i = 0, j = 0;

for (i = 0; i < 2; i++)

H[i] = (long int *) malloc ((n + 1) * sizeof (long int));

for (i = 0; i <= n; i++) // Инициализируем вторую строку

H[1] [i] = 0;

for (i = 0; i < m; i++) // Вычисляем Н

{

for (j = 0; j <= n; j++) // Сдвигаем вторую строку вверх

H[0] [j] = H[1] [j];

for (j = 0; j < n; j++)

{

if (X[i] == Y[j])

H[1] [j + 1] = H[0] [j] + 1;

else

{

if (H[1] [j] > H[0] [j + 1])

H[1] [j + 1] = H[1] [j];

else

H[1] [j + 1] = H[0] [j + 1];

}

}

}

for (j = 0; j <= n; j++)

LL[j] = H[1] [j];

for (i = 0; i < 2; i++) // Освобождаем память

free (H[i]);

free (H);

H = NULL;

return LL;

}

// Вычисление LCS

int * lcs (long int m, long int n, int X[], int Y[], int C[]) {

long int i = 0, j = 0; // Инициализация для цикла While

int *L1 = (int *) malloc ((n + 1) * sizeof (int));

int *L2 = (int *) malloc ((n + 1) * sizeof (int));

for (i = 0; i <= n; i++)

{

L1 [i] = 0;

L2 [i] = 0;

}

_Bool notEmpty = false;

if ((m == 0) | (n == 0)) // Тривиальный случай

{

C[0] = -1;

return C;

}

else if (m == 1)

{

i = 0;

while ((notEmpty≠ true) & (i < n))

{

if (X[0] == Y[i])

notEmpty = true;

i++;

}

if (notEmpty == true) // Если НОП не пуста, присваиваем ед. возможное значение

C[0] = X[0];

else

C[0] = -1; // Иначе — код ошибки

//C = NULL;

return C;

}

else if (n == 1)

{

i = 0;

while ((notEmpty≠ true) & (i < m))

{

if (Y[0] == X[i])

notEmpty = true;

i++;

}

if (notEmpty == true) // Если НОП не пуста, присваиваем ед. возможное значение

C[0] = Y[0];

else

C[0] = -1; // Иначе — код ошибки

//C = NULL;

return C;

}

else // Начинается рассм. нетривиального случая

{

long int x_index = m / 2; // делим X напополам

int *SUB_X = (int *) malloc ((x_index)* sizeof (int));

int *SUB_Y = (int *) malloc ((n)* sizeof (int));

for (i = 0; i < x_index; i++) // заполняем подматрицы

SUB_X[i] = X[i];

for (i = 0; i < n; i++)

SUB_Y[i] = Y[i];

L1 = lcsLength (x_index, n, SUB_X, SUB_Y, L1); // Вычисяем L1

free (SUB_X);

free (SUB_Y);

SUB_X = (int *) malloc ((m — x_index)* sizeof (int));

SUB_Y = (int *) malloc ((n)* sizeof (int));

long int last_i = m — x_index;

for (i = 0; i < last_i; i++) // заполняем подматрицы

SUB_X[i] = X [m — i — 1];

for (i = 0; i < n; i++)

SUB_Y[i] = Y [n — i — 1];

L2 = lcsLength (m — x_index, n, SUB_X, SUB_Y, L2); // Вычисляем L2

long int lcs_max = 0;

for (i = 0; i <= n; i++)

lcs_max = Max (lcs_max, L1 [i] + L2 [n — i]);

if (lcs_max == 0) return C; // Если lcs пуста, выходим.

i = 0;

_Bool found = false;

long int y_index;

while ((found == false) & (i <= n)) // находим y_index

{

if (lcs_max == L1 [i] + L2 [n — i])

{

y_index = i;

found = true;

}

i++;

}

free (SUB_X); // Освобождаем память

free (SUB_Y);

free (L1);

free (L2);

SUB_X = (int *) malloc ((x_index)* sizeof (int));

SUB_Y = (int *) malloc ((y_index)* sizeof (int));

for (i = 0; i < x_index; i++) // Заполняем матрицы

SUB_X[i] = X[i];

for (i = 0; i < y_index; i++)

SUB_Y[i] = Y[i];

int *C1 = (int *) malloc ((lcs_max + 1)* sizeof (int));

int *C2 = (int *) malloc ((lcs_max + 1)* sizeof (int));

for (i = 0; i <= lcs_max; i++)

{

C1 [i] = -1;

C2 [i] = -1;

}

C1 = lcs (x_index, y_index, SUB_X, SUB_Y, C1);

free (SUB_X); // Освобождаем память

free (SUB_Y);

SUB_X = (int *) malloc ((m — x_index)* sizeof (int));

SUB_Y = (int *) malloc ((n — y_index)* sizeof (int));

last_i = m — x_index;

for (j = 0; j < last_i; j++)

SUB_X[j] = X [x_index + j];

last_i = n — y_index;

for (j = 0; j < last_i; j++)

SUB_Y[j] = Y [y_index + j];

C2 = lcs (m — x_index, n — y_index, SUB_X, SUB_Y, C2);

long int k = 0;

while ((k < m — x_index) && (C1 [k]≠ -1))

{

C[k] = C1 [k];

k++;

}

long int k₁ = k;

k = 0;

while ((k < n — y_index) && (C2 [k]≠ -1))

{

C [k₁ + k] = C2 [k];

k++;

}

//C [k₁ + k] = -1;

free (C1); // не забываем освобождать память

free (C2);

free (SUB_X);

free (SUB_Y);

return C;

}

}

// Заполнение матрицы расстояний

long int editDinst (long int D[], long int n, int X[], int Y[], long int i, long int j) {

int m;

long int res = D [1 * n + j — 1] + 1;

long int prev = D [0 * n + j] + 1;

if (res > prev)

res = prev;

if (X [i — 1] == Y [j — 1])

m = 0;

else m = 1;

prev = D [0 * n + j — 1] + m;

if (res > prev)

res = prev;

return res;

}

// Вычисление расстояния Левенштейна

long int levenshtein (int X[], int Y[], long int l1, long int l2) {

long int i = 0, j = 0;

long int *D = (long int *) malloc (2 * (l2 + 1) * sizeof (long int));

for (i = 0; i <= l2; i++)

D[i] = i;

for (i = 1; i <= l1; i++)

{

D [1 * (l2 + 1)] = i;

for (j = 1; j <= l2; j++)

D [1 * (l2 + 1) + j] = editDinst (D, l2, X, Y, i, j);

for (j = 0; j <= l2; j++)

D [0 * (l2 + 1) + j] = D [1 * (l2 + 1) + j];

}

long int res = D [1 * (l2 + 1) + l2];

free (D); // освобождаем память

D = NULL;

return res;

}

// Вычисление максимального периода

void findMaxPeriod (int str[], long int length) {

long int periodLength = length / 2;

long int maxMult = 1;

long int i = 0, j = 0;

long int index;

long int prev_index;

long int currMult;

long int offset;

long int size;

int *subStr = NULL;

long int *maxCurrMult = NULL;

while (periodLength > 0) // Начинаем с подстрок большей длины. Если находим период с кратностью >1, то закончили

{

size = ((length — (2 * periodLength)) + 1) * periodLength;

subStr = (int *) malloc (size * sizeof (int));

for (i = 0; i < size; i++)

subStr[i] = -1;

maxCurrMult = (long int *) malloc (length * sizeof (long int));

offset = 0;

while ((length — (offset + 2 * (periodLength)) + 1) > 0)

{

index = 0;

currMult = 1;

maxCurrMult[offset] = 1;

for (i = 0; i < periodLength; i++)

subStr [periodLength * offset + i] = str [i + offset];

prev_index = subString (str, length, &subStr [periodLength * offset], periodLength, 0);

while (index≠ -1)

{

index = subString (str, length, &subStr [periodLength * offset], periodLength, prev_index + 1);

if (index == prev_index + periodLength) {

currMult++;

if (currMult > maxCurrMult[offset])

maxCurrMult[offset] = currMult;

}

else

currMult = 1;

prev_index = index;

}

if (maxCurrMult[offset] > maxMult)

maxMult = maxCurrMult[offset];

offset++;

}

if (maxMult > 1)

break;

if (periodLength > 1) {

free (subStr);

free (maxCurrMult);

}

subStr = NULL;

maxCurrMult = NULL;

periodLength -;

}

FILE *file;

if ((file = fopen («Period.txt», «w»))≠ NULL) {

if ((maxMult < 2) || (subStr == NULL))

fprintf (file, «There is no periods of multiplicity 2 in the initial stringn»);

else

{

fprintf (file, «Maximum period:%dn», periodLength);

fprintf (file, «Multiplicity:%dn», maxMult);

j = 0;

_Bool alreadyWas;

long int offset;

for (offset = 0; offset < size; offset++)

{

alreadyWas = false;

if (maxCurrMult[offset] == maxMult)

{

for (i = 0; i < offset; i++)

if (subString (&subStr[i * length], periodLength, &subStr [offset * length], periodLength, 0)≠ -1)

alreadyWas = true;

if (alreadyWas) continue;

j++;

fprintf (file, «Period #%d:n», j);

for (i = 0; i < periodLength; i++)

fprintf (file, «%d», subStr [offset * periodLength + i]);

fprintf (file, «n»);

}

}

}

fclose (file);

}

free (subStr);

free (maxCurrMult);

subStr = NULL;

maxCurrMult = NULL;

}

void printLCSToFile (int C[]) {

long int i;

FILE *file1;

if ((file1 = fopen («LCS.txt», «w»))≠ NULL) {

fprintf (file1, «LCS:n»);

i = 0;

while (C[i] > 0)

{

fprintf (file1, «%dn», C[i]);

i++;

}

fclose (file1);

}

}

void printEDToFile (long int editDinstance) {

FILE *file;

if ((file = fopen («EditDinst.txt», «w»))≠ NULL) {

fprintf (file, «EditDinst:%d», editDinstance);

fclose (file);

}

}

int main () {

long int i;

int A = -1, B = -1;

FILE *file1;

long int length1 = 0;

long int length2 = 0;

int *S1;

int *S2;

char strNum;

remove («LCS.txt»);

remove («EditDinst.txt»);

remove («Period.txt»);

// Читаем из первого файла

if ((file1 = fopen («S1.txt», «r»)) == NULL) {

printf («File „S1.txt“ not Existn»);

return EXIT_FAILURE;

}

else

{

while (fscanf (file1, «%d % d», &A, &B)≠ EOF)

{

if ((A < 0) || (B < 0))

{

printf («Data in file „S1.txt“ is incorrectn»);

return EXIT_FAILURE;

}

length1++;

}

if (length1 == 0) {

printf («File „S1.txt“ is emptyn»);

return EXIT_FAILURE;

}

S1 = (int *) malloc (length1 * sizeof (int));

i = 0;

fclose (file1);

file1 = fopen («S1.txt», «r»);

while (fscanf (file1, «%d % d», &A, &B)≠ EOF) {

S1 [i] = A;

i++;

}

fclose (file1);

}

// Читаем из второго файла

A = -1, B = -1;

if ((file1 = fopen («S2.txt», «r»)) == NULL) {

printf («File „S2.txt“ not Existn»);

return EXIT_FAILURE;

}

else

{

while (fscanf (file1, «%d % d», &A, &B)≠ EOF)

{

if ((A < 0) || (B < 0))

{

printf («Data in file „S2.txt“ is incorrectn»);

return EXIT_FAILURE;

}

length2++;

}

if (length2 == 0) {

printf («File „S2.txt“ is emptyn»);

return EXIT_FAILURE;

}

S2 = (int *) malloc (length2 * sizeof (int));

i = 0;

fclose (file1);

file1 = fopen («S2.txt», «r»);

while (fscanf (file1, «%d % d», &A, &B)≠ EOF) {

S2 [i] = A;

i++;

}

fclose (file1);

}

long int editDinstance;

long int size = Max (length1, length2);

int *C = (int *) malloc (size * sizeof (int));

for (int i = 0; i < size; i++)

C[i] = -1;

printf («Choose what need to do (input the number and press Enter):n»);

printf («1. Largest common subsequencen»);

printf («2. Edit dinstance (Levenshtein)n»);

printf («3. The largest period of the largest multiplicityn»);

printf («4. Alln»);

printf («0. Exitn»);

char choice;

char err;

do

{

printf («Input:»);

choice = getchar ();

if ((err = getchar ())≠ 'n') choice = '9';

fflush (stdin);

} while (! strchr («12 340», choice));

switch (choice)

{

case '0':

printf («Program aborted by user. n»);

return EXIT_FAILURE;

break;

case '1':

printf («The results will be placed in file „LCS.txt“ n»);

printf («Please, wait until the end of work. n»);

C = lcs (length1, length2, S1, S2, C);

printLCSToFile (C);

break;

case '2':

printf («The results will be placed in file „EditDinst.txt“ n»);

printf («Please, wait until the end of work. n»);

editDinstance = levenshtein (S1, S2, length1, length2);

printEDToFile (editDinstance);

break;

case '3':

printf («Choose string to find periodn»);

printf («1. First stringn»);

printf («2. Second stringn»);

do

{

printf («Input:»);

strNum = getchar ();

if ((err = getchar ())≠ 'n') choice = '9';

fflush (stdin);

} while (! strchr («12», strNum));

printf («The results will be placed in file „Period.txt“ n»);

printf («Please, wait until the end of work. n»);

if (strNum == '1')

findMaxPeriod (S1, length1);

else

findMaxPeriod (S2, length2);

break;

case '4':

printf («Choose string to find periodn»);

printf («1. First stringn»);

printf («2. Second stringn»);

do

{

printf («Input:»);

strNum = getchar ();

if ((err = getchar ())≠ 'n') choice = '9';

fflush (stdin);

} while (! strchr («12», strNum));

printf («The results will be placed in files „LCS.txt“, „EditDinst.txt“ and „Period.txt“ n»);

printf («Please, wait until the end of work. n»);

if (strNum == '1')

findMaxPeriod (S1, length1);

else

findMaxPeriod (S2, length2);

C = lcs (length1, length2, S1, S2, C);

printLCSToFile (C);

editDinstance = levenshtein (S1, S2, length1, length2);

printEDToFile (editDinstance);

break;

default:

break;

}

printf («Program is complete successfully. n»);

free (C);

free (S1);

free (S2);

return 0;

}

Код программы, генерирующей строки с заданными характеристиками

var

strLength, periodLength, periodMult, generated: longint;

offset, globalIndex, i, j, differs, changeIndex: longint;

period, str, changesIndexes: array of integer;

alreadyWas: boolean;

file1: text;

begin

strLength:= 0;

writeln ('Генерация первой последовательности');

repeat

write ('Длина периода: ');

readln (periodLength);

until (periodLength > -1);

if (periodLength > 0) then

begin

repeat

write ('Кратность периода: ');

readln (periodMult);

until (periodMult > 0);

repeat

write ('Смещение начало периода относительно начала строки: ');

readln (offset);

until (offset > -1);

end

else

begin

periodMult:= 0;

offset:= 0;

end;

repeat

write ('Длина строки: ');

readln (strLength);

if ((offset + periodLength * periodMult) > strLength) then

writeln ('Указанная длина строки меньше, чем (Смещение + Длина периода * Кратность) = ', offset + periodLength * periodMult)

until (offset + periodLength * periodMult <= strLength);

if (strLength < 1) then

begin

writeln ('Введенные параметры соответствуют пустой строке, генерация прервана.');

EXIT;

end;

setLength (period, periodLength);

setLength (str, strLength);

randomize;

for i:= 0 to periodLength — 1 do

period[i]: = random (1000);

globalIndex:= 0;

while (globalIndex < offset) do

begin

str[globalIndex]: = random (1000);

inc (globalIndex);

end;

for j:= 1 to periodMult do

for i:= 0 to periodLength — 1 do

begin

str[globalIndex]: = period[i];

inc (globalIndex);

end;

while (globalIndex < strLength) do

begin

str[globalIndex]: = random (1000);

inc (globalIndex);

end;

assign (output, 'S1.txt');

rewrite (output);

for i:= 0 to strLength — 2 do

writeln (str[i], ' ', i);

write (str[strLength — 1], ' ', strLength — 1);

close (output);

writeln ('Сгенерированная строка помещена в файл «S1.txt» ');

writeln ();

writeln ('Генерация второй последовательности');

write ('Введите количество отличий второй строки от первой: ');

readln (differs);

setLength (changesIndexes, strLength);

for i:= 0 to strLength — 1 do

changesIndexes[i]: = 0;

i:= 0;

while (i < differs) do

begin

alreadyWas:= false;

changeIndex:= random (strLength — 1);

if (changesIndexes[changeIndex] = 0) then

begin

generated:= random (1000);

repeat

if (generated <> str[changeIndex]) then

str[changeIndex]: = random (1000);

until (generated <> str[changeIndex]);

inc (i);

end

else

changesIndexes[changeIndex]: = 1;

end;

assign (output, 'S2.txt');

rewrite (output);

for i:= 0 to strLength — 2 do

writeln (str[i], ' ', i);

write (str[strLength — 1], ' ', strLength — 1);

close (output);

writeln ('Сгенерированная строка помещена в файл «S2.txt» ');

end