Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

ЗАВДАННЯ НА ЛАБОРАТОРНУЮ РАБОТУ

АЛГОРИТМИ ПОШУКУ

 

Мета роботи: Освоїти і закріпити прийоми роботи з алгоритмами пошуку числових і строкових даних. Отримати навички застосування алгоритмів пошуку для практичних задач.

Ключові поняття, які необхідно знати: лінійний (послідовний) пошук, бінарний пошук, інтерполяційний пошук, алгоритм Кнута-Моріса-Пратта, алгоритм Боуер-Мура-Хорспула, алгоритм Рабіна-Карпа.

 

 

ТЕОРЕТИЧНА ЧАСТИНА

 

Одна з найбільш часто зустрічаючихся в програмуванні дій - пошук. З точки зору програмування розрізняють пошук серед числових і строкових даних.

Для числових даних найбільш споживані такі алгоритми, як:

- Послідовний (лінійний) пошук,

- Бінарний пошук,

- Інтерполяційний пошук.

Для пошуку текстових даних (пошук підрядка в тексті) найбільш використовувані такі алгоритми:

- Лінійний (послідовний) пошук підрядка,

- Алгоритм Кнута-Моріса-Пратта,

- Алгоритм Боуер-Мура-Хорспула,

- Алгоритм Рабіна-Карпа.

 

Пошук числових даних

Розглянемо методи пошуку числових даних для наступного завдання: дан масив mas [N] чисельних значень (ключів) розміром N елементів; необхідно знайти позицію заданого ключа K в масиві mas, в разі успішного пошуку, або повідомити про те, що К не міститься в mas.

1.1.1 Послідовний (лінійний) пошук.«Почати з початку і продовжувати, поки не буде знайдений шуканий ключ (значення); потім зупинитися »- ця послідовна процедура являє собою очевидний і найпростіший шлях пошуку [1]. Він застосовується, якщо немає ніякої додаткової інформації про розшукувані дані.

Приклад послідовного пошуку наведено в програмному прикладі 1.

 


/*== Программный пример 1 – Последовательный поиск ==*/

int LineSearch(int[] mas, int k)

{ //k - искомое значение в массиве mas

//результат – позиция значения k в массиве mas

// или -1, если k не содержится в массиве mas

int N = mas.Length; //Длина массива

for (int i = 0; i < N; i++) //Цикл по всем элементам массива

{ if (mas[i] == k) //Проверка очередного элемента массива c k

return i; //Элемент k найден на позиции i

}

return -1; //Элемент k в массиве не найден

}

Коли розмір масиву невеликий, послідовний пошук працює досить швидко. Послідовний пошук досить простий, але час його роботи прямо пропорційний кількості даних, які потрібно переглянути; подвоєння кількості елементів призведе до подвоєння часу на пошук, якщо шуканого елемента в масиві немає.

1.1.2 Бінарний пошук. Добре відомо, що пошук можна зробити значно ефективнішим, якщо дані будуть впорядковані. Один з простих методів пошуку в упорядкованому масиві є бінарний пошук (пошук діленням навпіл), який полягає в наступному:

а) перевіряємо середній елемент масиву з шуканим;

б) якщо це значення більше, ніж шукане, то шукаємо далі в першій частині; в іншому випадку шукаємо у другій частині;

в) повторюємо з п. а) до тих пір, поки не знайдемо потрібний елемент або не переконаємося, що його в масиві немає.

/*== Программный пример 2 – Бинарный поиск ==*/

int BinarySearch(int[] mas, int k)

{ //k - искомое значение в массиве mas

//результат – позиция значения k в массиве mas

// или -1, если k не содержится в массиве mas

int L = 0; //Нижняя граница рассматриваемого диапазона

//Верхняя граница рассматриваемого диапазона

int H = mas.Length - 1;

int m;

while (L <= H) //Пока рассматриваемый диапазон не будет пуст

{ m = (L + H) / 2;//Индекс среднего элемента

if(mas[m] == k) //Проверка очередного элемента массива c k

return m; //Элемент k найден на позиции m

if (mas[m] > k)

H = m - 1; //Сдвиг верхней границы

else

L = m + 1; //Сдвиг нижней границы

}

return -1; //Элемент k в массиве не найден

}

Максимальне число порівнянь для бінарного пошуку дорівнює log2N, округленому до найближчого цілого. Таким чином, цей метод істотно виграє в порівнянні з послідовним пошуком, адже там очікуване число порівнянь – N/2.

Слід зауважити, що попереднє сортування масиву (з часом порядка N2), вимагає часу більшого ніж для виконання безпосереднього пошуку. Тому, бінарний пошук в порівнянні з послідовним пошуком дає виграш за часом тільки при багаторазовому використанні.

1.1.3 Інтерполяційний пошук.Інтерполяційний пошук заснований на принципі пошуку в телефонній книзі, словнику. Замість порівняння кожного елемента з шуканим як при лінійному пошуку, даний алгоритм виробляє пророкування місцезнаходження елемента: пошук відбувається подібно бінарним пошуку, але замість поділу області пошуку на дві рівні частини, інтерполяційний пошук виробляє оцінку новій галузі пошуку по відстані між ключем і поточним значенням елемента. Іншими словами, бінарний пошук враховує лише знак різниці між ключем і поточним значенням, а інтерполяційний ще враховує і модуль цієї різниці і за даним значенням виробляє пророкування позиції наступного елементу для перевірки.

Алгоритмічно, відміну интерполяционного пошуку від бінарного полягає у формулі розрахунку індексу елемента ділить область пошуку на дві частини:

m = L + (k - mas[L]) / (mas[H] - mas[L]) * (H - L);

замість аналогічної формули для бінарного пошуку

m = (L + H) / 2;

В середньому, інтерполяційний пошук виробляє log(log(N)) операцій. Число необхідних операцій залежить від рівномірності розподілу значень серед елементів. У поганому випадку (наприклад, коли значення елементів експоненціально зростають) інтерполяційний пошук може зажадати до N операцій.

 

1.2 Пошук підрядка в тексті

Завдання пошуку підрядка в тексті (зразка в тексті) дуже часто зустрічається в програмуванні, наприклад, при трансляції (при пошуку лексем і розпізнаванні операторів), пошуку рядка запиту в Інтернеті.

Задачу пошуку зразка в тексті визначимо наступним чином. Нехай заданий масив S із N символів (текст) і масив P з M символів (зразок, шаблон, відшукуване слово), до того ж 0 < MN. Якщо для деякого значення K виконується рівність S[K+j] = P[j], j = 0..M-1, то кажуть, що зразок P входить в текст S із зсувом K.

Потрібно знайти значення зсуву K першого входження зразка P в текст S. Будемо вважати результатом пошуку значення К або значення -1, якщо рядок не містить зразок.

1.2.1 Лінійний (послідовний) пошук.Найпростіший алгоритм пошуку полягає в безпосередній перевірці всіх можливих зсувів. Перевірка полягає в послідовному порівнянні символів зразка з символами тексту (зліва направо). При першій розбіжності зразок зсувається на одну позицію вправо і порівняння символів триває з першого символу зразка.

Приклад. Текст S = «АБГАБВ», зразок P = «АБВ». Підкресленням показані символи зразка беруть участь у порівняннях.

Итерация Сравнения
  S = А Б Г А Б В
P = А Б В
P = А Б В
P = А Б В
P = А Б В

Приклад лінійного пошуку підрядка приведений в програмному прикладі 3. Для позначення номерів (індексів) порівнюваних символів в рядках S і P використовуються змінні i і j відповідно.

/*== Программный пример 3- Линейный поиск подстроки ==*/

int LineSearch(char[] S, char[] P)

{ int i, j, N, M;

N = S.Length;

M = P.Length;

i = -1;

do {

i++;

j = 0;

//Сравнение символов для смещения i

while(j < M && S[i+j] == P[j])

j++;

//Пока не найден образец и не закончится текст

}while(j < M && i <= N - M);

// Вывод результата поиска

if(j == M) //Образец найден по смещению i

return i;

else

return -1; //Образец не найден

}

Умова j = M відповідає результату «знайдено». Умова i> N-M відповідає тому, що ніде в рядку збігу із зразком немає. Достатня ефективність цього алгоритму досягається, якщо всього лише після декількох порівнянь пари символів у внутрішньому циклі фіксується їх розбіжність Або, якщо зразок розташований в рядку, але не в кінці тексту. В гіршому випадку (якщо слово в тексті відсутнє або присутнє в самому кінці тексту) при пошуку буде потрібно виконати M * (N-M + 1) порівнянь.

1.2.2 Алгоритм Кнута-Морріса-Пратта. Алгоритм, винайдений авторами приблизно в 1970 році, вимагає порядку N + M порівнянь символів навіть у найгіршому випадку. Основний принцип алгоритму - не знищувати цінну інформацію попереднього порівняння. Після часткового збігу початкової частини образу з символами рядка при кожній розбіжності двох символів зразок зсувається на максимально можливу кількість символів (d ≥ 1) і порівняння рядка із зразком (з початку зразка) триває.

КМП-алгоритм дає виграш, тільки коли невдачі передувало деяке число збігів. Лише в цьому випадку зразок зсувається більш ніж на одну позицію (див. Рисунок 1).

Рисунок 1 - Ідея алгоритму Кнута-Морріса-Пратта.

Символ * означає будь-яку кількість будь-яких символів

 

Величина d [j] дорівнює розміру найдовшої послідовності символів зразка, безпосередньо передуючої j-му символу, яка збігається з початком зразка (для j = 0 приймають d [j] = -1). Величина d [j] залежить тільки від зразка і може бути обчислена заздалегідь перед операцією пошуку (див. Приклад у таблиці 1).

 

Таблиця 1 - Обчислення значень d [j] для зразка P = «абракадабра»

Позиция несовпадающего символа – j Совпавшая часть Значение d[j]
- -1
А
АБ
АБР
4 АБРА
АБРАК
6 АБРАКА
АБРАКАД

 

Позиция несовпадающего символа – j Совпавшая часть Значение d[j]
АБРАКАДА
АБРАКАДАБ
АБРАКАДАБР

 

Приклад. Пошук зразка «абракадабра» в тексті «ЗААБРАКАДАБРИЛАСЬ_АБРАКАДАБРА». Підкресленням показані символи зразка беруть участь у порівняннях.

j Сдвиг j-d[j] Сравнения
    З А А Б Р А К А Д А Б Р И Л А С Ь _ А Б Р А К А Д А Б Р А
0 – (–1) = 1 А Б Р А К А Д А Б Р А
1 – 0 = 1 А Б Р А К А Д А Б Р А
10 – 3 = 7 А Б Р А К А Д А Б Р А
3 – 0 = 3 А Б Р А К А Д А Б Р А
0 – (–1) = 1 А Б Р А К А Д А Б Р А
0 – (–1) = 1 А Б Р А К А Д А Б Р А
1 – 0 = 1 А Б Р А К А Д А Б Р А
0 – (–1) = 1 А Б Р А К А Д А Б Р А
0 – (–1) = 1 А Б Р А К А Д А Б Р А
0 – (–1) = 1 А Б Р А К А Д А Б Р А
    А Б Р А К А Д А Б Р А

Приклад алгоритму Кнута-Морріса-Пратта приведений в програмному прикладі 4. Для позначення номерів (індексів) порівнюваних символів в рядках S і P використовуються змінні i і j відповідно.

/*== Программный пример 4 - Алгоритм Кнута-Морриса-Пратта ==*/

int KMPSearch(char[] S, char[] P)

{ int i, j, k, N, M;

int []d; //Массив сдвигов

N = S.Length;

M = P.Length;

d = new int[M];

// Заполнение массива сдвигов d

j = 0;

k = -1;

d[0] = -1;

while(j < M-1)

{ while(k >= 0 && P[j] != P[k])

k = d[k];

j++;

k++;

if(P[j] == P[k])

d[j] = d[k];

else

d[j] = k;

}

// Поиск слова P в тексте S

i = 0;

j = 0;

while(j < M && i < N)

{ while(j >= 0 && S[i] != P[j])

j = d[j]; //Сдвиг слова

i++;

j++;

}

// Вывод результата поиска

if(j == M)

return i - j; //Образец найден по смещению i-j

else

return -1; //Образец не найден

}

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

У пошуку БМХ порівняння символів починає з кінця зразка. У разі часткового збігу зразок зсувається на величину, що залежить від символу тексту, що стоїть навпроти останнього символу зразка (рисунок 2).

 

Малюнок 2 - Ідея алгоритму Боуера-Мура-Хорспула.

Символ * означає будь-яку кількість будь-яких символів

 

Величина зсуву d [x] - визначається як відстань від найбільш правого в зразку входження х до його кінця (число букв в зразку праворуч від останнього входження літери). Для решти символів d [x] = M, де M - довжина зразка. Якщо символ х міститься тільки в кінці зразка (і тільки один раз), то для нього d [х] дорівнює M.

Величина зсуву d [x] залежить тільки від зразка і може бути розрахована заздалегідь перед фактичним пошуком (див. Приклад у таблиці 2).

 

Таблиця 2 - Обчислення значень d [х] для зразка P = «абракадабра»

Символ А Б Р К Д Остальные символы
Сдвиг d[x]

 

Приклад. Пошук зразка «абракадабра» в тексті «ЗААБРАКАДАБРИЛАСЬ_АБРАКАДАБРА». Підкресленням показані символи зразка які беруть участь у порівняннях, жирним шрифтом виділено символи, які стоять навпроти останньої букви зразка і використовувані для розрахунку зсувів.

 

Сдвиг d[х] Сравнения
  З А А Б Р А К А Д А Б Р И Л А С Ь _ А Б Р А К А Д А Б Р А
d[Б] = 2 А Б Р А К А Д А Б Р А
d[И] = 11 А Б Р А К А Д А Б Р А
d[А] = 3 А Б Р А К А Д А Б Р А
d[Б] = 2 А Б Р А К А Д А Б Р А
  А Б Р А К А Д А Б Р А

 

Приклад алгоритму Боуера-Мура-Хорспула приведений в програмному прикладі 5. Для позначення номерів (індексів) порівнюваних символів в рядках S і P використовуються змінні i і j відповідно.

/*== Программный пример 5 - Алгоритм Боуера-Мура-Хорспула ==*/

int BMHSearch(char[] S, char[] P)

{ int i, j, k, pos = -1, N, M;

int []d = new int[256];

N = S.Length;

M = P.Length;

// Формирование таблицы сдвигов d

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

d[i] = M;

for(i = 0; i < M - 1; i++)

d[P[i]] = M – i - 1;

// Поиск образца P в тексте S

i = M;

do{

k = i;

j = M;

do{

j--;

k--;

}while(j >= 0 && S[k] == P[j]);

if(j == -1)

pos = i - M;

else

i += d[S[i - 1]];

}while(i <= N && j >= 0);

if(j > -1)

pos = -1;

return pos;

}

Алгоритм вимагає O (N) порівнянь. В найсприятливішому випадку, коли останній символ образу потрапляє на неспівпадаючий символ, потрібно N / M порівнянь.

1.2.4 Алгоритм Рабіна-Карпа.Алгоритм Рабіна-Карпа заснований на наступній ідеї. Виріжемо віконечко довжини M, будемо рухати його по вхідному тексту і дивитися, чи не збіжиться текст в віконечку з заданим зразком. Порівнювати по буквах довго. Замість цього створюємо деяку функцію, визначену на словах довжини M. Якщо значення цієї функції на тексті в віконечку і на зразку різні, то збігів немає. Якщо значення однакові, перевіряємо збіг по буквах. Виграш можливий за рахунок того, що при зсуві віконечка текст в віконечку не змінюється повністю, а лише додається літера наприкінці і прибирається на початку. Ці дані слід враховувати при зміні значення функції. При побудові функції можна замінити всі літери їх кодами. Тоді функція буде обчислювати суму цих чисел або значення многочлена ступеня M в точці х = 10 або в точці х = 2. У програмному прикладі 6 використаний останній варіант.

/*== Программный пример 6 - Алгоритм Рабина-Карпа ==*/

int RabinSearch(char[] S, char[] P)

{ int i,pos, c, N,M;

double a,b;

N=S.Length; //Длина текста

M=P.Length; //Длина образца

a=0;

for(i=0;i<M;i++) //Вычисление функции для образца

a=a*2+P[i];

b=0;

for(i=0;i<M;i++) //Вычисление функции для окошка в тексте

b=b*2+S[i];

i=M-1;

// Поиск образца в тексте

do{

i++;

c=S[i-M]; //первый (удаляемый) символ в окошечке

c=c<<(M-1); //функция для первого символа в окошечке

b=(b-c)*2+S[i]; //функция для сдвинутого окошечка в тексте

}while (i<N-1 && a!=b);

// Вывод результата

if(a==b)

return i-M+1;

else

return -1;

}

}

Даний програмний приклад перевіряє тільки збіг текстів у віконечку. Однієї цієї перевірки в деяких випадках може виявитися недостатньо.

Наприклад, є рядок «asdfgh» і зразок «fgh». Коди використовуваних символів мають такі значення:

a s d f g h

65 83 68 70 71 72

Значення функції на зразку «fgh» дорівнює 494 і значення функції на тексті «asd» у віконечку також дорівнює 494, а посимвольного збігу немає («asd» ≠ «fgh»).

Для усунення цього недоліку, слід доповнити алгоритм посимвольною перевіркою зразка і тексту в віконечку у разі рівності функцій (a = b).

ЗАВДАННЯ НА ЛАБОРАТОРНУЮ РАБОТУ

Завдання 1 (3 бали).

1. Згенерувати масив цілих випадкових чисел розміром N = 1000. (Для генерації випадкових чисел використовуйте клас System.Random).

2. Відсортувати отриманий масив будь-яким методом сортування.

3. Ввести з клавіатури деякий ціле число.

4. Використовуючи метод інтерполяційного пошуку, визначити, позицію введеного числа в масиві, якщо воно в ньому присутнэ.

Завдання 2 (+2 бали). Скласти програму, яка в заданому текстовому файлі шукає всі входження, введеного користувачем слова, формуючи список позицій (від початку файлу) шуканого слова. Метод пошуку — за варіантом по модулю 4

Варіанти:

1. Лінійний (послідовний) пошук підрядка,

2. Алгоритм Кнута-Моріса-Пратта,

3. Алгоритм Боуер-Мура-Хорспула,

4. Алгоритм Рабіна-Карпа.

 

 

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.