Міністерство освіти і науки України
Курсова робота на тему:
«Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів у масивах»
Зміст
Вступ
Розділ І. Стандартні алгоритми пошуку
1.1 Лінійний пошук
1.2 Алгоритм пошуку діленням пополам (бінарний пошук)
1.3 Пошук по «дереву Фібоначе»
1.4 Метод екстраполяції
Розділ ІІ. Пошук підрядка в рядку
2.1Прямий пошук підрядка
2.2Алгоритм Рабіна-Карпа
2.3Алгоритм Кнута-Морріса-Пратта
Висновки
Література
Вступ
Задачі, пов’язані із пошуком певного елемента, послідовності елементів у певному масиві, множині або структурі, є досить поширеними і часто використовуваними. Так, у будь якій таблиці, базі даній чи структурі практично завжди присутні методи по пошуку і сортуванню. Кожен, хто виконував різноманітні задачі з допомогою комп’ютера в тому чи іншому випадку обов’язково зустрічався із проблемою пошуку. Якщо ви простий користувач Інтернету, ви обов’язково проводили пошук на пошукових серверах потрібної вам інформації, проводили пошук інформації на окремих сайтах по ключовим словам. Якщо ви працюєте із текстовим редактором MS Word чи Open Office ви обов’язково проводили пошук певних слів у тексті з метою їх редагування чи заміни. Аналогічні дії ви обов’язково проводили і при роботі з іншими програмами будь-то довідник чи окрема база даних. Кожен, хто програмував не зміг би оминути тему «масиви», а отже так чи інакше стикався із необхідністю створення алгоритму пошуку елементів у ньому. Більшість із нас знали, що на різноманітних сайтах, форумах з метою недопущення порушення норм людської поведінки користувачі не мають права вводити образливі слова, заклики до агресії по відношенню до інших і т.п. За це вони можуть бути позбавленні права на певний термін часу відвідувати даний сайт, форум. Зрозуміло, за цим не може слідувати людина, отже існує програма, що зчитує вхідні слова, дані, аналізує їх, проводить пошук і порівняння із забороненими словами у своїй базі і вже відповідно до отриманих результатів проводить певні дії, вимикає, наприклад, доступ до сайту. Ці програми, скрипти, запрограмовані таким чином, щоб проводити як найбільш швидкий пошук. Проте рідко хто задумувався над тим, як же вони працюють і які алгоритми вкладені в пошук.
Із вищесказаного можна зробити висновок, що алгоритми пошуку є дуже важливими. Вони бувають різні, в залежності від виду оброблюваних даних, так, при їх програмуванні, інколи буває простіше і вигідніше з урахуванням процесорного часу, часу проведення пошуку, кількості використаних операцій провести сортування масиву даних, а вже потім проводити пошук з допомогою одного із методів пошуку. Проте, інколи сортування масиву є лишнім, оскільки в деяких випадках витрати часу на сортування масиву не перекривають затрат виконаних на пошук масиву простим, лінійним перебором елементів масиву. Аналогічно, не завжди можна використати простий перебір елементів, як от наприклад, коли необхідно визначити елемент, який найбільш наближений до середнього арифметичного у масиві.
В даній курсовій роботі ми проведемо детальний аналіз найбільш використовуваних алгоритмів, їх математичних моделей, реалізуємо їх на мові програмування Turbo Pascal і визначимо, які і в яких випадках найбільш правильно використовувати.
Актуальність нашої роботи полягає в тому, що користувач зможе чітко усвідомити різноманітність алгоритмів пошуку, вибрати оптимальний для вирішення тієї чи іншої проблеми.
Метою нашої роботи полягає у вивченні і реалізації найбільш використовуваних у сучасному програмуванні алгоритмів пошуку. В своїй роботі ми спробуємо показати, як можна змінити стандартні алгоритми в залежності від певної поставленої задачі.
Розділ І. Стандартні алгоритми пошуку
1.1 Лінійний пошук
Якщо не має ніякої додаткової інформації про відшукувані дані, то очевидним підходом є простий послідовний перегляд масиву із збільшенням крок за кроком тієї його частини, де потрібного елемента не знайдено. Такий метод називається лінійним пошуком.
Нехай маємо масив довільного типу: a: array [1..N] of basetype.
Умовою припинення пошуку буде одна із наступних :
) шуканий елемент знайдений в деякій позиції i, тобто a[i]=x ;
) весь масив переглянутий і шуканий елемент відсутній.
Таким чином, алгоритм лінійного пошуку можна записати у вигляді послідовності команд :
i:=1;
while (ix) do i:=i+1;
Очевидно, що закінчення циклу гарантоване, і в найгіршому випадку, коли необхідного елемента не виявиться, це станеться через N кроків.
Виникає питання, чи можливо пошук пришвидшити? Єдиний вихід — спростити умову в заголовку циклу, оскільки вона складається із двох логічних множників. Потрібно сформулювати просту умову, яка буде еквівалентною вихідній. Це можна зробити, якщо гарантувати, що співпадіння з шуканими ключем завжди буде. Тому помістимо вкінець масиву додатковий елемент — «бар’єр» із шуканим значенням x. Звичайно, при цьому необхідно попередньо розширити на один елемент масив a та діапазон допустимих значень індекса :
a: array [1..N+1] of basetype.
Алгоритм в цьому випадку матиме вигляд :
i:=1; a[N+1]:=x;
while a[i]x do i:=i+1;
В обох випадках алгоритму істинність умови i=N+1 свідчить про відсутність шуканого елемента в масиві.
Аналіз лінійного пошуку. Очевидним є той факт, що кількість основних операцій порівняння, необхідних для встановлення входження шуканого елемента, залежить від його позиції і взагалі від його наявності в масиві. Оскільки тип масиву basetype може бути досить складним і великим по об’єму пам’яті, то можна вважати порівняння елементів цього типу складнішою операцією ніж порівняння індексів. Спочатку оцінимо кількість порівняння ключів. Зрозуміло, що для обох алгоритмів вона буде однаковою. В найкращому випадку, коли потрібний елемент знаходиться на першому місці, виконається лише одна операція. В найгіршому випадку, коли шуканого елемента не має, виконається N операцій. Середня ж кількість порівнянь — N/2. Якщо враховувати і порівняння індексів для встановлення кінця масиву, то початковий варіант алгоритму потребуватиме додатково ще таку ж саму кількість.
Реалізація алгоритму на Turbo Pascal. Нехай маємо масив із N символів, необхідно знайти елемент K і вивести якщо він є в масиві його індекс.
Program Seach_1_1;
Uses Crt;
Const n=10;
Var a:array [0..n] of integer;
i, k:integer;
Begin
ClrScr;
Randomize;
For i:=1to n do
Begin
A[i]:=Random(10);
Write(A[i]:3);
End;
Writeln;
Writeln(‘Vvedit k’);
Readln(k);
A[0]:=k;
I:=n;
While a[i]k do
Dec(i);
Writeln(‘element ’,k,’ mae index ‘,i );
Readln;
End.
1.2 Алгоритм пошуку діленням пополам (бінарний пошук)
Очевидно, що ніякого іншого способу підвищення ефективності пошуку в масиві не має, якщо відсутня додаткова інформація про дані. Пошук можна значно покращити, якщо елементи в масиві попередньо будуть впорядковані. Даний метод – ділення пополам ще називають «метод дихотомії», «бінарне дерево». Бінарним деревом його називають тому, що можна схематично зообразити дерево, по якому буде проводитися пошук (Рис. 1).
Рис. 1. Дерево порівнянь, що відповідає бінарному пошуку для N=16
Нехай масив a є впорядкованим по зростанню, тобто
/>, />.
Розглядуваний алгоритм базується на таких принципах :
) вибирається довільно деякий елемент, наприклад am;--PAGE_BREAK--
) проводиться порівняння am з аргументом пошуку x ;
) якщо значення співпадають, то пошук припиняється, якщо am, то відкидаються з розгляду всі елементи масиву до am включно, якщо am>x, то відкидаються з розгляду всі елементи масиву після am включно.
Такий процес послідовного вибору та порівняння елемента із шуканим ключем продовжується поки або не буде встановлено входження в масив, або не залишиться жодного елемента для вибору, тобто входження не має.
Введемо наступні позначення: L, R — індексні змінні, що відмічають відповідно лівий і правий кінці частини масиву, де ще можна знайти потрібний елемент. Алгоритм такого пошуку можна записати у вигляді послідовності команд :
L:=1; R:=N; f:=true;
while (L
begin
m:=k; {k — довільне значення між L і R}
if a[m]=x then f:=false else
if a[m]
end;
Очевидно, що вибір m може бути довільним. Однак найкраще — відкидати на кожному кроці, незалежно від результату порівняння, якомога більше елементів. Оптимальним є вибір серединного елемента в розглядуваній частині, оскільки завжди рівноімовірно відкидатиметься половина масиву. В результаті максимальна кількість порівнянь округлює число log(2)N до найближчого цілого. Це значно краще від лінійного пошуку (середня кількість порівнянь — N/2).
Ефективність алгоритму можна дещо покращити. Перевірку на рівність із шуканим ключем можна виконувати в другу чергу, оскільки вона зустрічається лише один раз і приводить до припинення пошуку. Крім того ймовірність точного попадання в потрібне значення є меншою ніж попадання в більше або менше значення. Тому варто поміняти місцями заголовки умовних операторів :
if a[m]
if a[m]>x then R:=m-1 else f:=false;
Однак, можна ще покращити ефективність, якщо спростити умову припинення алгоритму. Для цього необхідно відмовитися від бажання припинення пошуку при фіксації співпадання. Тоді пошук продовжуватиметься доти, доки досліджувана частина масиву не стягнеться до одного елемента, який і буде шуканим :
L:=1; R:=N;
while L
begin
m:=(L+R) div 2;
if a[m]
end;
Умова припинення циклу L>=R досягається. Адже для цілочисельного серединного значення m справедлива нерівність L, якщо попередньо виконувалася умова L. Отже, або L збільшується при присвоєнні йому значення m+1, або R зменшується при присвоєнні йому значення m. Таким чином, різниця R-L на кожному кроці зменшується, і при досягненні нульового значення (L=R) повторення циклу припиняється.
Варто зауважити, що виконання умови L=R ще не гарантує знаходження потрібного ключа. Потрібно враховувати, що елемент a[R] в порівнянні ніколи участі не бере. Тому необхідна додаткова перевірка після циклу на рівність a[R]=x.
Розглянутий алгоритм як і алгоритм лінійного пошуку знаходить шуканий елемент з найменшим індексом, тобто перше входження в масив. А простий бінарний пошук — довільний із співпадаючих елементів.
Реалізація алгоритму на Turbo Pascal. Нехай дано впорядкований масив елементів цілочисельного типу, знайти заданий елемент і вивести його позицію у масиві використовуючи бінарний пошук.
Program Seach_1_2;
Uses Crt;
Const n=10;
Var a:array [1..n] of integer;
i, k,l,r:integer;
Begin
ClrScr;
For i:=1 to n do
Readln(A[i]);
Writeln(‘Vvedit k’);
Readln(k);
l:=1; r:=n;
while l
begin
i:=(l+r) div 2;
if a[i]
else r:=i
end;
Writeln(‘element ’,k,’ mae index ‘,i+1 );
Readln;
End.
1.3 Пошук по «дереву Фібоначе».
Існує ще один метод подібний до методу описаного вище, проте ефективність його дещо вища ніж пошуку по бінарному дереву, хоча така ж пропорціональність log(2)N. В дереві Фібоначе числа в дочірніх вузлах відрізняються від батьківських на одну і ту ж величину, а саме на число Фібоначе (рис. 2.).
Суть даного метода в тому, що порівнюючи наше шукане значення з наступним значенням в масиві, ми не ділимо навпіл нову зону пошуку, як в бінарному пошуку, а відступаємо від попереднього значення, з яким порівнювали, в потрібну сторону на число Фібоначе.
Рис. 2. Дерево Фібоначе порядку 6
Ефективність даного метода вища за ефективність методу бінарного дерева в тому, що метод Фібоначе включає в себе тільки такі арифметичні операції, як додавання і віднімання, немає необхідності в діленні на 2, тим самим економиться процесорний час. Адже, як відомо виконання операцій віднімання і додавання проходить на порядок швидше ніж операція множення чи ділення.
Даний метод був винайдений в 60-ті роки.
Реалізація алгоритму на Turbo Pascal. Нехай дано впорядкований масив Nелементів цілочисельного типу, знайти заданий елемент і вивести його позицію у масиві використовуючи метод Фібоначе.
Program Seach_1_3;
Uses Crt;
Var a:array [1..200] of integer;
i,n,k,j,l,x,y,z,tmp,q,p:integer;
Begin
ClrScr;
Write('Vvedit kilkist chleniv poslidovnocti');
readln(n);
for j:=1 to 3 do
begin
l:=1;x:=1;y:=0;
While l
begin
z:=x; l:=l+1;
x:=x+y; y:=z;
end;
Case j of
1:i:=x;
2:p:=x;
3:q:=3;
end;
end;
Writeln('-----------------------------');
For i:=1 to n do
Readln(A[i]); продолжение
--PAGE_BREAK--
Writeln('-----------------------------');
Writeln('Vvedit k');
Readln(k);
while a[i]k do
begin
if k
else begin i:=i+q; p:=p-q; q:=q-p; end;
end;
Writeln('element ',k,' mae index ',i);
Readln;
End.
1.4 Метод екстраполяції
Даний метод в деякій мірі подібний до «методу дихотомії», наведеного вище. Проте, щоб краще зрозуміти даний метод, давайте представимо собі, що нам потрібно взнати, як перекладається на українську мову англійське слово treasure. Тобто в нас задача – знайти це слово в словнику.
По суті, всі наші дії будуть нічим іншим, як реалізацією деякого алгоритму пошуку. Масив значень – це словник, всі значення в ньому відсортовані за алфавітом. Шукане слово нам відомо. Тобто будемо проводити пошук в відсортованому масиві. З першого погляду стає зрозумілим, що ми не будемо перебирати всі слова словника, як і не будем ділити книгу навпіл, дивитися що там в середині і відраховувати в одну і другу сторону рівно ¼ сторінок словника і т.д. (за умови що словник великий). Тобто метод дихотомії і лінійний пошук буде проігноровано.
Більш ніж вірно що ми спочатку відкриємо словник дещо дальше ніж на середині (літера t за серединою латинського алфавіту). Якщо відкрили на літері R, ясно, що шукати потрібно в другій частині словника, а на скільки відступити? На половину? «Навіщо ж на половину, це більше, чим потрібно», скажете ви і будете праві. Адже нам не просто відомо, в якій частині масиву шукане значення, ми володіємо ще і інформацією про те наскільки далеко потрібно зробити наступний крок!
Ось ми і підійшли до суті розглядуваного методу. На відміну від перших двох методів, він не лише визначає зону нового пошуку, а і оцінює величину кроку. Алгоритм називається екстраполяційний метод і має швидкість сходження більшу, ніж метод поділу навпіл.
Якщо при пошуку по бінарному дереву за кожний крок масиву пошуку зменшується з N до значення N/2, то при цьому методі за кожен крок зона зменшується з N значення до кореня квадратного з N. Якщо K лежить в межах Knі Km, то наступний крок робимо від n на величину (n — m)*(K — Kn)/(Km — Kn). Швидкість екстраполяційного методу розпочинає суттєво перевершувати швидкість метода половинного ділення при великих значеннях.
Реалізація алгоритму на Turbo Pascal. Нехай дано впорядкований масив Nелементів цілочисельного типу, знайти заданий елемент і вивести його позицію у масиві використовуючи екстраполяційний метод.
Program Seach_1_4;
Uses Crt;
Var a:array [1..200] of integer;
i,j,n,k,l,r:integer;
Begin
ClrScr;
Write('Vvedit kilkist chleniv poslidovnocti = ');
readln(n);
Writeln('-----------------------------');
For i:=1 to n do Readln(A[i]);
Writeln('-----------------------------');
Writeln('Vvedit k');
Readln(k);
l:=1; r:=n; i:=1;
while r>l do
begin
i:=(((r-l)*(K-a[l])) div (a[r]-a[l]));
if (K
else l:=i+1;
if K=a[i] then Writeln('element ',k,' mae index ',l);
end;
readln;
End.
Розділ ІІ. Пошук підрядка в рядку
2.1 Прямий пошук підрядка
Часто доводиться зустрічатися із специфічним пошуком — так званим пошуком рядка. Мається на увазі визначення позиції в одній послідовності елементів, починаючи з якої інша послідовність повністю в неї входить. Така операція часто зустрічається в задачах обробки текстів.
Нехай задано масив a із N елементів та масив b із M елементів, які називаються відповідно базовим рядком та підрядком або образом, причому />:
a: array [1..N] of basetype; b: array [1..M] of basetype ;
Пошук рядка передбачає встановлення першого входження образа b в базовий рядок a.
Прямий пошук полягає в повторюваному порівнянні елементів двох масивів. У випадку неспівпадання чергової пари елементів образ зсувається на одну позицію вздовж базового масиву і процес порівняння проводиться знову починаючи з першого елемента шуканого підрядка.
x y z t u x y t
x y t
x y z t u x y t
x y t
x y z t u x y t
x y t
x y z t u x y t
x y t
x y z t u x y t
x y t
x y z t u x y t
x y t
Процес порівняння елементів може припинитися при виконанні однієї із двох умов :
всі елементи образа співпали з відповідними елементами бази — це означає, що позиція входження встановлена ;
після чергового неспівпадання елементів та зсуву образа відбувся вихід підрядка за межі бази — це означає, що шуканий підрядок не входить в базовий.
Якщо позначити біжучий індекс по базі через i, а індекс по образу через j, то ці умови можна записати у вигляді диз’юнкції логічних виразів (j>M) or (i>N-M+1) .
Таким чином програмна реалізація прямого пошуку підрядка в рядку матиме вигляд процедури :
Var
i, j, k: integer;
Begin
i:=1; j:=1; k:=0;
while (j
begin
j:=k+1; k:=j; i:=1;
while a[j]=b[i] do
begin inc(v); i:=i+1; j:=j+1; end;
end;
if i>m then writeln('номер позиції входження ',(j+1)-i,' важких операцій виконується N=',v+w )
else writeln('не має входження образу в базу, важких операцій виконується N=',v+w);
readln;
END. продолжение
--PAGE_BREAK--
Просто і елегантно, вроді би так і потрібно. Дійсно, це не важко у виконанні, але і не дуже ефективно на практиці. Давайте проведемо оцінку швидкості роботи цього алгоритму. В ньому присутні два цикли (один вкладений), час роботи зовнішнього циклу більшою мірою залежить від n, а внутрішній в гіршому випадку дає m операцій. Таким чином, час роботи всього алгоритму рівний O((n-m+1)m). Для малих рядків пошук пройде досить швидко, але якщо в деякому багатомегабайтному файлі буде потрібно знайти послідовність довжиною 100 Кб, то час затрачений на пошук буде дуже великий.Основним недоліком даного методу є те, що приходиться виконувати багато «лишньої» роботи. Наприклад, знайшовши рядок aabc і виявивши невідповідність в четвертому символі (співпало тільки aab), алгоритм буде продовжувати порівнювати рядок, починаючи із наступного символу, хоча це однозначно не приведе до вірного результату. Даний алгоритм найбільш придатний до невеликого об’єму тексту.
Реалізація алгоритму на Turbo Pascal. Нехай маємо рядок і підрядок, що складаються лише з малих літер англійського алфавіту, використовуючи прямий пошук знайти позицію першого входження даного підрядка в рядок.
Program Seach_2_1;
Uses Crt;
Const nmax=10000;
var p:string; {підрядок}
s:array[1..nmax]of char; {рядок}
d:array[char]of byte; {масив зрушень}
c:char;
m,i,j,k:integer;
begin
ClrScr;
Randomize;
for i:=1 to nmax do
begin
s[i]:=chr(97+random(26));
write(s[i]);
end;
Writeln(‘-----------------------------------’);
Writeln(‘Vvedit pidrjadok’);
Readln(p);
m:=length(p);{довжина підрядка}
for c:=chr(0) to chr(255) do d[c]:=m;
for j:=1 to m-1 do d[p[j]]:=m-j;
{масив d визначений}
i:=m+1;
repeat {вибір фрагмента в рядку}
j:=m+1; k:=i;
repeat {перевірка збігу}
k:=k-1; j:=j-1
until (js[k]);
i:=i+d[s[i-1]];{зрушення}
until (jnmax+1);
Writeln;
Writeln(‘--------------------’#10#13’pozucia = ‘);
if j
readln;
end.
2.2 Алгоритм Рабіна-Карпа
Ідея, яку запропонували Рабін і Карп, має на меті поставити в відповідність кожному рядку деяке унікальне число, і замість того щоб порівнювати самі рядка, порівнювати числа, що теоретично і практично є набагато швидшою дією. Проблема в тому, що шуканий рядок може бути великою, і рядків у тексті теж. А так як кожному рядку потрібно спів ставити унікальне число, то чисел повинно бути багато, а відповідно, числа будуть теж великими (порядку Dm, де D – кількість різних символів), працювати з ними буде так само незручно. Розглянемо реалізацію даного алгоритму для тексту, що складається лише із цифр, і рядка довжиною до 8 символів.
Program RabinKarpSearch;
Var T: array[1..40000] of 0..9;
S: array[1..8] of 0..9;
i,j: longint;
n,m: longint;
v,w: longint; {v — число, що характеризує шуканий рядок, w характеризує рядок довжиниm в тексті}
k: longint;
const D: longint = 10; {кількість різних символів (10 цифр 0,1,2,..9)}
Begin
{Ввід тексту і зразка}
…
v:=0;
w:=0;
for i:=1 to m do
begin
v:=v*D+S[i]; {обчисленняv, рядок подається як число}
w:=w*D+T[i]; {обчислення початкового значенняw}
end;
k:=1;
for i:=1 to m-1 do {k потрібне для багаторазового обрахункуw і має значенняDm-1}
k:=k*D;
for i:=m+1 to n+1 do
begin
if w=v then {якщо числа рівні, то рядки співпадають, а значить, зразок знайдений в тексті}
writeln('Зразок входить в текст із ',i-m,'-ого символу');
if i
w:=d*(w-k*T[i-m])+T[i]; {обчислення нового значенняw}
end;
End.
За цим алгоритмом виконується лінійний прохід по рядку (m кроків) і лінійний прохід по всьому тексту (n кроків), отже загальний час роботи рівний O(n+m).
Час роботи алгоритму лінійно залежить від розміру рядка і тексту, тобто програма працює досить швидко. Проте, виникає питання в доцільності алгоритму для роботи лише із короткими рядками і цифрами. Розробники алгоритму придумали, як покращити свій же алгоритм без особливих втрат в швидкості роботи.
Як видно, спочатку ставили в відповідність рядку його числовий еквівалент, проте виникала проблема великих чисел. Її можна оминути, якщо виконувати всі арифметичні дії по модулю якогось простого числа (постійно брати остачу від ділення на це число). Таким чином, знаходимо не саме число, що характеризує рядок, а його остачу від ділення на деяке просте число. Тепер ми ставимо число в відповідність не одному рядку, а цілому класу, так як класів буде дуже багато (стільки, скільки різних остач від ділення на це просте число), то додаткову перевірку прийдеться виконувати доволі рідко.
Var T: array[1..40000] of char;
S: array[1..10000] of char;
i,j: longint;
n,m: longint;
v,w: longint;
k: longint;
const P: longint = 7919; {1000-е простое число}
D: longint = 256; {кількість різних символів(кількість різних символів типуchar)}
Begin
{Ввід тексту і зразка} продолжение
--PAGE_BREAK--
…
v:=0;
w:=0;
for i:=1 to m do {обчисленняv іw}
begin
v:=(v*D+ord(S[i])) mod P; {ord повернення коду символа}
w:=(w*D+ord(T[i])) mod P;
end;
k:=1;
for i:=1 to m-1 do
k:=k*D mod P; {k має значенняDm-1 mod P}
for i:=m+1 to n+1 do
begin
if w=v then {якщо числа рівні, то рядки належать одному класу, і потрібно перевірити, чи вони рівні}
begin
j:=0;
while (j
j:=j+1;
if j=m then {кінцева перевірка}
writeln('Зразок входить в текст починаючи з ',i-m,'-ого символу ');
end;
if i
w:=(d*(w+P-(ord(T[i-m])*k mod P))+ord(T[i])) mod P;
end;
End.
І так, нам все ж приходиться порівнювати рядки посимвольно використовуючи даний алгоритм, проте, оскільки «холостих» порівнювань буде небагато (в 1/Р випадках), то очікуваний час роботи буде невеликий. В загальному випадку, час роботи = O(m+n+mn/P), mn/P досить не велике, так що складність роботи практично лінійна. Зрозуміло, що просте число потрібно вибирати велике, чим більше це число, тим швидше буде працювати програма. Цей алгоритм набагато швидший за алгоритм прямого пошуку підрядка в рядку і його застосування більш доцільне при роботі із дуже довгими рядками.
Реалізація алгоритму на Turbo Pascal. Нехай маємо рядок і підрядок, що складаються лише з малих літер англійського алфавіту, використовуючи метод Рабіна-Карпа знайти позицію першого входження даного підрядка в рядок.
Program Seach_2_2;
Uses Crt;
Var T: array[1..40000] of char;
S: array[1..10000] of char;
i,j: longint;
n,m: longint;
v,w: longint;
k: longint;
c:char;
const P: longint = 7919; {1000-е простое число}
D: longint = 256; {кількість різних символів(кількість різних символів типуchar)}
Begin
ClrScr;
Randomize;
Writeln(‘ Vvedit dovguny texty n’);
Readln(n);
Writeln(‘ Vvedit dovguny pidradka m, m
Readln(m);
for i:=1 to ndo
begin
T[i]:=chr(97+random(26));
write(T[i]);
end;
Writeln;
Writeln(‘-----------------------------------’);
Writeln(‘Vvedit pidrjadoksumvolu a..z’);
I:=1;
While i
Begin
C:=readkey;
If (ord(c)>96)and(ord(c)
S[i]:=c;
Write(s[i]);
Inc(i);
End;
End;
Writeln;
v:=0;
w:=0;
for i:=1 to m do {обчисленняv іw}
begin
v:=(v*D+ord(S[i])) mod P; {ord повернення коду символа}
w:=(w*D+ord(T[i])) mod P;
end;
k:=1;
for i:=1 to m-1 do
k:=k*D mod P; {k має значенняDm-1 mod P}
for i:=m+1 to n+1 do
begin
if w=v then {якщо числа рівні, то рядки належать одному класу, і потрібно перевірити, чи вони рівні}
begin
j:=0;
while (j
j:=j+1;
if j=m then {кінцева перевірка}
writeln('Зразок входить в текст починаючи з ',i-m,'-ого символу ');
end;
if i
w:=(d*(w+P-(ord(T[i-m])*k mod P))+ord(T[i])) mod P;
end;
End.
2.3 Алгоритм Кнута-Морріса-Пратта
Ще одним важливий метод, — алгоритм Кнута-Морріса-Пратта, один із найкращих на сьогоднішній момент, працює за лінійний час для довільного тексту і довільного рядка.
Метод виконує предобробку шуканого рядка, а саме: на її основі створюється так звана префікс-функція. Суть цієї функції в знаходженні для кожного підрядка S[1..i] рядка S найбільшого підрядка S[1..j] (j), що присутній одночасно і в початку і в кінці підрядка (як префікс так і суфікс). Наприклад для підрядка abcHelloabc таким підрядком відповідно є abc (одночасно і префікс, і суфікс). Зміст даної префікс-функції полягає в тому, що ми можемо відкинути завідомо невірні варіанти, тобто, якщо при пошуку співпав підрядок abcHelloabc (наступний символ не співпав), то нам є смисл продовжити перевірку вже із четвертого символу (перші три і так співпадуть). Ось як можна обрахувати цю функцію для всіх значень параметра від 1 до m: продолжение
--PAGE_BREAK--
var S: array[1..10000] of char;
P: array[1..10000] of word; {масив, в якому зберігаються значення префікс-функції}
i,k: longint;
m: longint;
…
Procedure Prefix; {процедура, що знаходить префікс-функцію}
Begin
P[1]:=0; {префікс рядка із одного символу має нульову довжину}
k:=0;
for i:=2 to m do {обраховуємо для префіксів рядки довжиною від 2 до m символів}
begin
while (k>0) and (S[k+1]S[i]) do
k:=P[k]; {значення функції може бути отримане із обчислень, проведених раніше}
if S[k+1]=S[i] then
k:=k+1;
P[i]:=k; {присвоєння префікс-функції}
end;
End;
Давайте тепер розглянемо дану функцію, і перевіримо, чи правильно обраховується префікс-функція. Використовується наступна ідея: якщо префікс (він же суфікс) рядка довжиною і довший одного символу, то він же одночасно і префікс підрядка довжиною і-1. Таким чином, ми перевіряємо префікс попереднього підрядка, якщо ж він не підходить, то префікс її префікса і т.д. Діючи таким способом, ми знаходимо найбільший шуканий префікс. Наступне питання, на який потрібно відповісти: чому час роботи процедури ми вказали лінійний, якщо в ній присутній вкладений цикл? Ну, по-перше, присвоєння префікс-функції виконується чітко m раз, решта часу міняється змінна k. Так як в циклі while вона зменшується (P[k]), але не стає меншою 0, то зменшуватися вона може не частіше, чи зростати. Змінна k зростає на 1 не частіше m раз. Значить, змінна k міняється всього не більше як 2m разів. Звідки слідує, що час роботи всієї процедура рівний O(m).
Розглянемо всю программу, що шукає рядок в тексті.
Program KnutMorrisPrattSearch;
…
{Опис процедури Prefix і пов’язаних з нею змінних}
…
var n: longint;
T: array[1..40000] of char;
Begin
{Ввід тексту і зразку}
…
Prefix; {Обчислення префікс-функції}
k:=0; {кількість символів, що співпадають на даний час}
for i:=1 to n do
begin
while (k>0) and (S[k+1]T[i]) do
k:=P[k];
if S[k+1]=T[i] then
k:=k+1;
if k=m then {якщо співпали всі символи}
begin
writeln('Зразок входить в текст починаючи з ',i-m+1,'-ого символу');
k:=P[k];
end;
end;
End.
Довести, що ця програма працює за лінійний проміжок часу, можна аналогічно доведенню, наведеному вище для процедури Prefix. Отже, загальний час роботи програми рівний O(n+m), тобто лінійний час.
Алгоритм Кнута-Морріса-Пратта більш громіздкий ніж наведені вище, проте час роботи із великими об’ємами даних є набагато меншим, тобто він більш швидше працює із великими об’ємами тексту ніж решта алгоритмів.
Реалізація алгоритму на Turbo Pascal. Нехай маємо рядок і підрядок, що складаються лише з літер англійського алфавіту, використовуючи метод Кнута-Морріса-Пратта знайти позицію першого входження даного підрядка в рядок.
Program Seach_2_3;
Uses Crt;
var
n: longint;
T: array[1..40000] of char;
S: array[1..1000] of char;
P: array[1..1000] of word; {масив, в якому зберігаються значення префікс-функції}
i,k: longint;
m: longint;
{---------------------------------------------------------}
Procedure Prefix; {процедура, що знаходить префікс-функцію}
Begin
P[1]:=0; {префікс рядка із одного символу має нульову довжину}
k:=0;
for i:=2 to m do {обраховуємо для префіксів рядки довжиною від 2 до m символів}
begin
while (k>0) and (S[k+1]S[i]) do
k:=P[k]; {значення функції може бути отримане із обчислень, проведених раніше}
if S[k+1]=S[i] then
k:=k+1;
P[i]:=k; {присвоєння префікс-функції}
end;
End;
{---------------------------------------------------------------------------------}
Begin
ClrScr;
Randomize;
Writeln(‘ Vvedit dovguny texty n’);
Readln(n);
Writeln(‘ Vvedit dovguny pidradka m, m
Readln(m);
for i:=1 to ndo
begin
T[i]:=chr(97+random(26));
write(T[i]);
end;
Writeln;
Writeln(‘-----------------------------------’);
Writeln(‘Vvedit pidrjadoksumvolu a..z’);
I:=1;
While i
Begin
C:=readkey;
If (ord(c)>96)and(ord(c)
S[i]:=c; продолжение
--PAGE_BREAK--
Write(s[i]);
Inc(i);
End;
End;
Writeln;
Prefix; {Обчислення префікс-функції}
k:=0; {кількість символів, що співпадають на даний час}
for i:=1 to n do
begin
while (k>0) and (S[k+1]T[i]) do
k:=P[k];
if S[k+1]=T[i] then
k:=k+1;
if k=m then {якщо співпали всі символи}
begin
writeln('Зразок входить в текст починаючи з ',i-m+1,'-ого символу');
k:=P[k];
end;
end;
Readln;
End.
Висновки
У даній курсовій роботі ми провели розгляд такого важливого поняття в програмуванні як пошук елементів. Важливість цієї проблеми видно вже хоча б з того, наскільки широко розповсюджені самі алгоритми пошуку. Вибір оптимального за швидкістю роботи і його функціональними можливостями алгоритму в великій мірі покладається на плечі самого програміста. Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.
Оскільки ми не ставили собі за мету вивчити можливість тих чи інших методів пошуку у конкретних задачах, то із поставленою метою, а саме із вивченням і реалізацію найбільш використовуваних у сучасному програмуванні алгоритмів пошуку ми справилися повністю.
У відповідності до мети та завдання курсової роботи були виконані наступні кроки:
1. Було проведено детальний аналіз літератури та Інтернет джерел за темою «Пошук елементів у масиві», що дало змогу сформувати як теоретичні основи понять лінійного пошуку, пошуку за допомогою дерева так і визначено основні алгоритми реалізації пошуку елементів. У курсовій роботі наведено графічне представлення деревоподібного пошуку для більшої наглядності і проведено детальний розгляд кожного кроку алгоритмів.
2. Було проаналізовано застосування методів пошуку на практиці, що дало змогу визначити, в яких цілях і з якою метою є їх найбільш доцільну використання. Було показано, що на даний час існує ряд специфічних задач і областей застосування, де без використання алгоритмів пошуку обійтись не можливо. Як наслідок, це дало змогу поставити завдання для реалізації конкретних завдань з допомогою мови програмування високого рівня — Turbo Pascal, вибір даної мови програмування був обумовлений тим, що вона найбільш підходить для навчальних цілей. Оскільки в школах і вузах початки програмування і алгоритмізацію показуються саме з допомогою Turbo Pascal. Вибір цієї мови програмування був зумовлений ще і її гнучкістю і простотою в застосуванні і розумінні. Всі програми, які показані в курсовій роботі відповідним чином названі у відповідності до розділу, до якого вони належать. У програмах було зроблено коментарі, які роблять їх більш зрозумілими для розуміння;
3. В своїй роботі ми розбили матеріал на дві окремі частини, в першій частині ми провели розгляд найбільш використовуваних методів пошуку елементів на прикладі одновимірного масиву, знаючи ці алгоритми, досить просто перенести їх для пошуку елементів у багатовимірних масивах, структурах. В другій частині роботи ми більшу увагу приділили більш сучасним алгоритмам пошуку підрядка в тексті, які набувають більшої популярності в нас час, коли практично будь-яку текстову інформацію можна знайти в мережі Інтернет.
4. Виконуючи курсову роботу, крім практичної реалізації методів пошуку елементів, ми провели порівняльний аналіз ефективності та складності цих алгоритмів. Проаналізувати математичні моделі для оцінки швидкодії алгоритмів. Ми побачили, що деякі відомі алгоритми відрізняються лише діями які в них виконуються, наприклад алгоритм пошуку «бінарним деревом» і алгоритм пошуку методом Фібоначе мають практично однакову швидкість виконання (теоретично), але практично метод Фібоначе є швидший за рахунок того, що в ньому не використовуються операції множення та ділення, так званні «важкі» операції, а використовується лише додавання та віднімання. А ці дії, як відомо, виконуються на порядок швидше. Проте ця перевага перекривається складністю його реалізації, оскільки потрібно чітко усвідомлювати залежність між самими числами Фібоначе.
Виконуючи курсову роботу, ми дійшли висновку, що використання одних алгоритмів пошуку у відношенню до інших може бути мінливе навіть не в залежності від швидкості дій, а в залежності від поставленої мети. Так, наприклад, швидкість виконання алгоритму лінійним пошуком елемента в масиві N— невеликої кількості більш прийнятна, ніж застосування пошуку «бінарним деревом», оскільки затрати на реалізацію даного методу не оправдовують його застосування.
У курсовій роботі ми не проводили огляд пошуку у більш складних структурах даних, як то графи, списки, черги, стеки де можливе було б використання рекурсивних функцій, більш складних алгоритмів пошуку. Це пов’язано із тим, що ми виклали найбільш використовувані алгоритми, їх математичні моделі і вже знаючи ці методи, можна досить просто перевести їх використання і подальше удосконалення на практиці. Всі алгоритми пошуку у динамічних структурах є в якійсь мірі синтезом більш простих, удосконалених, перевірених часом стандартних методів.
Література
Turbo Pascal – Издательская група К.: ВНV, 2000. – 320 с.
Абрамов В. Г. Введение в язык Pascal: Учебное пособие для студентов вузов по специальности Прикладная математика. – М.: Наука, 1988. – 200 с.
Абрамов С. А., Зима Е. В. Начала программирования на языке Pascal. — М.: Наука, 1987. – 126 с.
Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М.: Лаборатория базовых знаний, 2000.– 201 с.
Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: «Вильямс», 2000.– 163 с.
Вирт Н. Алгоритмы и структуры данных. M.: Мир, 1989.– 142 с.
Власик А.П. Практикум з програмування в середовищі Turbo Pascal. Ч 1.- Рівне: НУВГП, 2005. – 179 с.
Грис Д. Наука программирования. M.: Мир, 1984.– 230 с.
Д. Кнут «Искусство программирования для ЭВМ», 1978г, издательство «МИР», том 3 «Сортировка и поиск». – 530 с.
Джонс Ж., Харроу К. Решение задач в системе Турбо Паскаль. М, 1991. – 709 с.
Зуев Е. А. Язык программирования Турбо Паскаль 6.0, 7.0. – М.: Радио и связь, 1993. – 150 с.
Клюшин Д. А. Полный курс С++. Москва: Санкт-Петербург, 2004. – 668 с.
Кнут Д.Э. Искуство програмирования, том 3. Поиск и сортировка, 3-е изд.: Пер. с англ.: Уч. Пос. – М.: Издательский дом «Вильямс», 2000. – 750 с.
Ковалюк Т.В. Основи програмування. Київ: Видавнича група ВНV, 2005. – 385 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.– 93 с.
Культин Н. Б. Программирование в TurboPascal 7.0 и Delphi. — Санкт- петербург,1999. – 120 с.
Культин Н. Б. С/С++ в задачах и примерах. – М., 2002. – 288 с.
Кучеренко В. Языкпрограммирования С++ для начинающих и не только. – М.: Майор, 2001. – 160 с.
Львов М. С., Співаковський О. В. Основи алгоритмізації та програмування. Херсон, 1997. – 240 с.
Марченко А.И., Марченко Л.А. Программирование в среде TurboPascal7.0. К.: ВЕК, 2000. – 441 с.
Окулов С.M. Сортировка и поиск. «Информатика», №35, 2000.– 73 с.
Окулов С.М. Основы программирования. «Информатика», №27, 2001.— 430 с.
Перминов О. Н. Программирование на языке Паскаль. – М.: Радио и связь, 1988. – 97 с.
Перминов О. Н. Язык программирования Pascal. – М.: Радио и свіязь,1989. – 205 с.
Популярные лекции по математике, выпуск №6. 1969г. Издательство «Наука» Н.Н. Воробьев. «Числа Фибоначчи» – 105 с.
Шень А. Программирование: теоремы и задачи. М.: МЦНМО.– 205 с.