Алгоритм пошуку в рядках. Алгоритм Хорспула

Київський національний університет  будівництва і архітектури

 

Кафедра інформаційних технологій проектування та прикладної математики

 

КУРСОВА РОБОТА

Теорія алгоритмів

На тему: «Алгоритм пошуку в рядках. Алгоритм Хорспула»

 

 

Студента 2 курсу 1 група

                                                                                  напряму підготовки КН

                                                                           спеціальності ІУСТ

                                                                   Мирка. Б.Ф.

 

                                                           Керівник

                                                                                     Доцент Білощицька С. В.

                                                                               

                                                                            Національна шкала

                                                                     Кількість балів

                                                                  Оцінка ECTS

 

Члени комісії

(підпис)                               (прізвище та ініціали)

(підпис)                               (прізвище та ініціали)

 

(підпис)                                (прізвище та ініціали)

 

м. Київ – 2013 рік

Київський національний університет  будівництва і архітектури

Кафедра інформаційних технологій проектування та прикладної математики

Спеціальність ІУСТ

Курс 2 Група 1 Семестр 3

ЗАВДАННЯ

На курсову роботу студентці

Мельник Ірині Михайлівні

 

1. Тема курсової роботи: «Алгоритми на графах. Орієнтований граф»
2. Термін здачі студентом закінченої роботи: 25 грудня 2013 р.

Вихідні дані до (роботи): Кількість шляхів заданої довжини. Загальна кількість шляхів між двома заданими вершинами.

3. Довжина мінімального шляху між двома заданими вершинами.Зміст пояснювальної записки (перелік питань, які належить розробити): опис постановки задачі (вхідні, вихідні дані), обґрунтування вибору структури даних, побудова математичної моделі, схема алгоритму розв’язку задачі, оцінка коректності алгоритму, аналіз алгоритму, опис програми, контрольний приклад, список літератури і додатки.
4. Перелік графічного матеріалу (з точним зазначенням обов’язкових креслень): схема алгоритму.
5. Дата видачі завдання «1» листопада 2013 р.

 

 

Студентка Мельник І. М.                                   (підпис)

 

Керівник Білощицька С. В.                                (підпис)

 

 

 

 

КАЛЕНДАРНИЙ ПЛАН

№ п/п	Назва етапів курсової роботи	Термін виконання етапів курсової роботи	Примітки
1	опис постановки задачі	01.11.13. – 03.11.13.
2	обґрунтування вибору структури  даних	04.11.13. – 05.11.13.
3	побудова математичної моделі	06.11.13. – 09.11.13.
4	схема алгоритму розв’язку  задачі	10.11.13. – 13.11.13.
5	оцінка коректності алгоритму	14.11.13. – 16.11.13.
6	аналіз алгоритму	17.11.13. – 19.11.13.
7	розробка програми	20.11.13. – 27.11.13.
8	опис програми	28.11.13. – 10.11.13.
9	контрольний приклад	10.11.13. – 18.11.13.
10	список літератури і додатки	18.12.13. – 21.12.13
11	оформлення пояснювальної  записки	21.12.13. – 23.12.13

 

 

Студентка Мельник І. М.                                   (підпис)

 

Керівник Білощицька С. В.                                (підпис)

Зміст:

1. Завдання на курсову роботу.
2. Постановка задачі.
3. Теоретичні відомості.
4. Аналіз поставленої задачі, вхідні та вихідні дані.
5. Математична постановка задачі.
6. Схема алгоритму.
7. Оцінка складності алгоритму.
8. Тестовий приклад.
9. Опис програми.
10. Результати роботи програми.
11. Список літератури.
12. Додаток 2: текст програми.

 

Постановка  задачі:

Послідовність ДНК являє  собою текст алфавіту {A, C, G, T}, а  ген або відрізок гену – зразок пошуку.

З заданим зразком гену знайти:

• Ген в послідовності ДНК за допомогою алгоритму Хорспула.

Теоретичні  відомості:

Алгоритими пошуку рядка (англ. string searching algorithms) — важливий клас рядкових алгоритмів, що намагаються знайти місце де один або декілька текстових рядків (зразків, англ. pattern) входять у довший рядок або текст. Формальна постановка задачі пошуку рядка (англ. string-matching problem) така:

Нехай текст задано у вигляді  масиву   довжини  , а зразок — масиву   довжини  . Передбачається, що елементи масивів — символи із скінченного алфавіту  . Наприклад, алфавіт може мати вигляд   чи  . Зразок   зустрічається у тексті   зі зсувом  ,   якщо   і   (іншими словами  ). Якщо зразок   зустрічається у тексті   зі зсувом  , то величину   називають допустимим зсувом; інакше її називають недопустимим зсувом. Задача полягає в знаходженні всіх допустимих зсувів, з якими зразок   зустрічається у тексті  .

Алгоритм Хорспула — алгоритм пошуку рядка — спрощений алгоритму Бояра — Мура. АБМХ працює краще алгоритму Бояра — Мура на випадкових текстах. До того ж, вимагає багатьох попередніх обчислень евристика співпала суфікса опускається.

 

 

 

 

Аналіз  поставленої задачі, вхідні та вихідні  дані:

Вхідні дані:	Вихідні дані:
Текст алфавіту символів A, C, G, T – char s1[]=”F” де F – текст алфавіту	Поточна позиція зразку s2 в тексті s1.
Зразок пошуку – char s2[]=”T”, де T – зразок тексту.

 

 

Для розрахунку поточної позиції  зразку  s2 в тексті s1 використовується програма-функція Horspool(). В Пр-Ф використовуються так зміні:

int i, j, k, needle_len, haystack_len, needle_table[256], char *p,  

i – лічильник поточного останнього символу в s1.

j – лічильник поточного символу в s2, k – в s1.

needle_len, haystack_len – довжина s2 та s1 відповідно.

*р – покажчик на  символ

needle_table[256] – Для збереження таблиці символів використаємо статичний масив розміром 256, так як таблиця символів ASCII складається з 256-ти символів.

 

 

 

 

 

Математична постановка задачі:

1. Будуємо таблицю символів:

for (i = 0; i < 256; i++) {needle_table[i] = needle_len;}

2. Кожному символу з таблиці ставитися у відповідність його порядковий номер з needle:

for (i = 1; i < needle_len; i++) {needle_table[needle[i-1]] = needle_len-i;}

3. Порівняння символів тексту та шаблону з кінця: Якщо вони однакові ()

while (j > 0 && haystack[k-1] == needle[j-1]) { --k; --j; }

Якщо вони однакові (haystack[k-1] == needle[j-1]) то переходимо до попередніх елементів (--k; --j;). Якщо j==0, то шаблон та текст співпали.

 

 

 

 

 

 

 

 

 

 

 

 

Схема алгоритму:

 

 

 

 

 

 

 

 

 

 

 

Рис. 1. Блок-схема  алгоритму головної програми.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 2.1. Блок-схема алгоритму підпрограми Horspool.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 2.2. Блок-схема алгоритму підпрограми Horspool.

 

 

 

 

Рис. 2.3. Блок-схема алгоритму підпрограми Horspool.

Оцінка  складності алгоритму:

Алгоритм Хорспула працює краще алгоритму Бойєр - Мура на випадкових текстах, оцінка в середньому від до на один символ тексту. До того ж, вимагає багатьох попередніх обчислень евристика совпавшего суфікса опускається.

Втім, оцінка (в гіршому  випадку на неперіодичних шаблонах) у АХ становить |needle|·|haystack| (замість 3·|haystack| у Бойєр-Мура).   
Тестовий приклад:

Знайдемо зразок «ACGT» в тексті «ACTTGTCACGTACGTAC»

A	C	G	T(та всі інші символи)
1	2	3	4

Таблиця символів: 

 

 

При першому порівнянні співпали 4-ті елементи, але не співпали 3-ті елементи. Стоп-символ в тексті «Т» – пересуваємо  шаблон на 4.

Далі:

Стоп-символ «А» – на 1. 

Стоп-символ «С» – на 2. 

Текст повністю співпав с шуканим  зразком. Результат 8.

Опис  процедур і функцій програми:

Підпрограма int Horspool(char *haystack, char *needle) – будує таблицю символів, порівнює символи та пересуває шаблон на відповідну позицію, згідно таблиці символів.

Результати  роботи програми:

Рис. 3. Виконання програми.

Список використаної літератури:

1. Конспект лекцій з курсу «Алгоритми і структури даних» Білощицька С.В.
2. Основы алгоритмизации и программирования. Голицына О.Л., Попов И.И. Москва – 2008.
3. Абстракция данных и решение задач на Си++. Френк Каррано, Джанет Причард. М. - С. - К. – 2003.

 

Додаток 1: Текст програми.

#include <vcl.h>

#include <iostream>

#include <string>

#include <vector>

#pragma hdrstop

#define ASIZE 255

using namespace std;

typedef unsigned char byte;

typedef vector <int> arr;

//---------------------------------------------------------------------------

 

#pragma argsused;

int Horspool(char *haystack, char *needle)

{

        int i,j,k, needle_len = 0,haystack_len = 0;

        int needle_table[256]; // таблиця символів

 

        char *p; // покажчик на символ

        for ( p = needle; *p; *p++) // кіл-ть символів в needle

                ++needle_len;

        for ( p = haystack; *p; *p++) // кіл-ть символів в haystack

                ++haystack_len;

 

        if (needle_len < haystack_len) //

        {

                for (i = 0; i < 256; i++) // в таблицю заноситься для кожного символу довжина needle

                        needle_table[i] = needle_len;

 

                for (i = 1; i < needle_len; i++) // кожному символу з таблиці ставиться у відповідність його порядковий номер із needle

                        needle_table[needle[i-1]] = needle_len-i;

 

                i = needle_len; // i - лічильник поточного останього символа в haystack

                j = i; // j - лічильник в needle кіл-ті однакових символів (співпавших з таблицею) з кінця

 

                while (j > 0 && i <= haystack_len) // если j==0 то співпадання знайдено

                {

                        j = needle_len; // заново виконуємо присвоєння, щоб порівняти рядки з кінця

                        k = i; // k - покажчик поточного символа в haystack

                               // j - покажчик поточного символа в needle

                        while (j > 0 && haystack[k-1] == needle[j-1]) // порівняння останніх символів

                        { // якщо однакові, переходимо до  попередніх

                                --k;

                                --j;