Тема выпускной квалификационной работы: «Разработка приложения для реализации алгоритмов вычисления паттернов в строковых последовательностях».Целью работы является разработка приложения для реализации и последующего сравнения алгоритмов вычисления частных паттернов в строковых последовательностях.Предметом исследования являются базовые алгоритмы вычисления паттернов в строковых последовательностях. Первым является алгоритм Кнута-Морриса-Пратта, вторым – алгоритм Бойера-Мура.Задачи, решаемые в ходе исследования:1.      Изучение основных видов и свойств строковых последовательностей, паттернов и алгоритмов.2.      Анализ принципов работы и реализация наиболее популярных алгоритмов вычисления паттернов в строковых последовательностях.3.      Выбор критериев сравнения эффективности выбранных алгоритмов.4.      Разработка приложения для реализации и последующего сравнения алгоритмов.5.      Тестирование алгоритмов на различных входных данных и анализ полученных результатов.В ходе работы были исследованы принципы работы и способы реализации выбранных алгоритмов.В результате выполнения работы разработано веб-приложение для сравнения работы выбранных алгоритмов, была продемонстрирована их эффективность при работе с текстами различного объема и разных алфавитов.

The topic of the final qualification work: "Development of an application for the implementation of algorithms for calculating patterns in string sequences."The aim of the work is to develop an application for comparing algorithms for computing private patterns in string sequences.The subject of the study is the basic algorithms for calculating patterns in string sequences - the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm.Tasks to be solved in the course of the study:1. Studying the main types and properties of string sequences, patterns and algorithms.2. Analysis of the principles of operation and implementation of the most popular algorithms for calculating patterns in string sequences.3. Choice of criteria for comparing the efficiency of the selected algorithms.4. Development of an application for the implementation of the comparison of algorithms;5. Testing algorithms on various input data and analyzing the results;In the course of the work, the principles of operation and methods for implementing the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm were investigated.As a result of the work, a web application was developed to compare the operation of the selected algorithms, and their effectiveness was demonstrated when working with texts of various sizes and different alphabets.

• Определения, обозначения и сокращения
• Введение
• 1 Строковые последовательности и алгоритмы
  • 1.1 Строковые последовательности и их свойства
    • Определение 1.1. Строковая последовательность – это набор элементов, которые удовлетворяют правилам 0-5 [9, c. 20].
  • 1.2 Линейные строковые последовательности
    • Определение 1.2. Линейными строковыми последовательностями на алфавите А называются элементы множества А+. Элементы множества А* называются конечными линейными строковыми последовательностями на алфавите A [9, c. 24].
    • Определение 1.3. Строка х, имеющая длину n, и строка у, имеющая длину m равны только вслучае, когда n = m и выполняется равенство x[i] = y[i] для всех і = 1, ..., n [3, c. 26].
    • Определение 1.4. Гранью b строки x называется любой собственный префикс этой строки, равный суффиксу х [9, c.27].
    • x[1.. β] = x[n – β + 1..n]. (1.1)
    • x[i] = x[i + p]. (1.2)
    • x = ,𝑢-,𝑟..𝑢', (1.3)
    • x = ur. (1.4)
    • Определение 1.5. Пусть строковая последовательность х = x[1..n] имест минимальный период р* и, соответственно. r* = n/p* и x[1..p*]. Тогда декомпозиция
    • x = ur*, (1.5)
    • Алгоритм 1.1 Вычисление массива граней
  • 1.3 Паттерны
    • 1.3.1 Внутренние паттерны
    • 1.3.2 Частные паттерны
    • 1.3.3 Характеристические паттерны
  • 1.4 Свойства алгоритмов
    • 1.4.1 Корректность
    • 1.4.2 Независимость от алфавита
    • 1.4.3 Временная и пространственная сложность
    • 1.4.4 Отсутствие возврата к ранее просмотренным данным
• 2 Базовые алгоритмы вычисления паттернов
  • 2.1 Наивный алгоритм
    • Алгоритм 2.1 Поиск первого вхождения строки p в строку x:
  • 2.2 Алгоритм Кнута-Морриса-Пратта (КМП)
    • Определение 3.4 Префикс-функцией от строки s называется массив p, где pi равно длине самого большого префикса строки s0s1s2…si, который также является и суффиксом i-того префикса, не считая весь i-й префикс [9, c.41].
    • Таблица 1. Префиксная функция для строки «cbcbecbc»
    • Алгоритм 2.2 Построения префикс-функции от строки
  • 2.3 Алгоритм Бойера – Мура
    • Алгоритм 2.3. Алгоритм Бойера-Мура
    • Таблица 2. Пример сдвига шаблона
    • Таблица 3. Сдвиг шаблона на стоп-симол
    • Таблица 4. Сдвиг шаблона на стоп-симол
    • Таблица 5. Эвристика совпавшего суффикса
    • 2.3.1 Таблица стоп-символов
    • 2.3.2 Таблица суффиксов
      • Таблица 7. Таблица суффиксов
      • Таблица 8. Иллюстрация:
      • Таблица 9. Таблица суффиксов
      • Таблица 10. Иллюстрация
• 3 Разработка приложения для сравнения КМП алгоритма и алгоритма Бойера-Мура
  • 3.1 Реализация алгоритмов на языке Javascript
    • 3.1.1 Алгоритм Кнута-Морриса-Пратта
    • 3.1.2 Алгоритм Бойера-Мура
  • 3.2 Описание приложения
  • 3.3 Замеры производительности
    • Случай 1. Орущие строки
      • Таблица 11 Результат выполнения
    • Случай 2. Последовательность ДНК
      • Таблица 12 Результат выполнения
    • 3.3.1 Случай 3. Естественный текст
      • Таблица 13. Результат выполнения с паттерном «беспеременно»
      • Таблица 14. Результат выполнения
      • Здесь полученные результаты отлично иллюстрируют преимущество концепции БМ – чем длиннее паттерн, тем более выигрышно показывает себя БМ-алгоритм, что и следовало из основной его особенности – возможности сдвига паттерна на всю его длину.
      • Таблица 15. Результат выполнения, паттерн «дуб»
• Заключение
• Список использованных источников
• Приложение 1. Поиск граней
• Приложение 2. Алгоритм КМП
• Приложение 3. Составления таблицы плохих символов
• Приложение 4. Алгоритм БМ
• Приложение 5. Использование React Context