Задачи поиска в структурах данных


The Presentation inside:

Slide 0

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


Slide 1

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


Slide 2

Задачи поиска в структурах данных d


Slide 3

Задачи поиска в структурах данных Var a: array[0..N -1] of Item; Item описывает запись с некоторым полем, играющим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному аргументу поиска x


Slide 4

Задачи поиска в структурах данных Полученный в результате индекс i, удовлетворяющий условию а[i].key = x, обеспечивает доступ к другим полям обнаруженного элемента. Так как мы рассматриваем, прежде всего, сам процесс поиска, то мы будем считать, что тип Item включает только ключ key


Slide 5

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


Slide 6

Линейный поиск Алгоритм 1. i:=0; while (i<N) and (а[i]<>х) do i:=i+1;


Slide 7

Линейный поиск Алгоритм 2.( алгоритм линейного поиска с барьером ) а: array[0..N] of integer a[N]:=x; i:=0; while a[i]<>x do i:=i+1;


Slide 8

Поиск делением пополам (двоичный поиск) массив A упорядочен, т. е. удовлетворяет условию ak-1? ak, 1? k< N


Slide 9

Поиск делением пополам (двоичный поиск)


Slide 10

Поиск делением пополам (двоичный поиск) L:=0; R:=N-1; Found:=false; while(L<=R) and not Found do begin          m:=(L+R) div 2;          if a[m]=x then Found:= true                          else                             if a[m]<x then L:=m+1 else R:=m-1                      end;


Slide 11

Поиск делением пополам (двоичный поиск) Максимальное число сравнений для этого алгоритма равно log2n Линейный поиск - N/2


Slide 12

Поиск делением пополам (двоичный поиск) Быстрый алгоритм L:=0; R:=N; while L<R do begin            m:=(L+R) div 2;            if а[m]<x then L:=m+1 else R:=m end; If a[R] = x then …. {элемент найден}


Slide 13

Поиск в таблице Поиск в массиве иногда называют поиском в таблице, особенно если ключ сам является составным объектом, таким, как массив чисел или символов Type String = array[0..М-1] of char; отношение порядка для строк x и y: x = y, если xj = yj для 0=< j < M x < y, если xi < yi для 0=< i < M и xj = yj для 0 =< j < i


Slide 14

Поиск в таблице Схема поиска с концевым символом i:=0; while (x[i]=y[i]) and (x[i]<>*) do i:=i+1 Концевой символ работает здесь как барьер


Slide 15

Поиск в таблице Пусть таблица T и аргумент поиска x определяются следующим образом: T: array[0..N-1] of String; x: String; Пусть N достаточно велико и таблица упорядочена в алфавитном порядке


Slide 16

Поиск в таблице L:=0; R:=N; while L<R do begin              m:=(L+R) div 2; i:=0;            while (T[m,i]=x[i]) and (x[i]<>*) do i:=i+1;               if T[m,i]<x[i] then L:=m+1 else R:=m end;


Slide 17

Поиск в таблице if R<N then begin            i:=0;            while (T[R,i]=х[i]) and (х[i]<>*) do i:=i+1 end {(R<N) and (T[R,i]=x[i]) фиксирует совпадение}


Slide 18

Прямой поиск строки Пусть задан массив s из N элементов и массив p из M элементов, причем 0 < M =< N. Описаны они так: s: array[0..N-1] of Item р: array[0..M-1] of Item Поиск строки обнаруживает первое вхождение p в s.


Slide 19

Прямой поиск строки Алгоритм прямого поиска i:=-1; repeat            i:=i+1; j:=0;            while (j<M) and (s[i+j]=p[j]) do j:=j+1; until (j=M) or (i=N-M)


Slide 20

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


Slide 21

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


Slide 22

Алгоритм Кнута, Мориса и Пратта Общая схема КМП-алгоритма i:= 0; j:=0; While (j<M) and (i<N) do begin While (j>=0) and (s[i] <>p[j]) do j:=d; i:= i+1; j := j+1 end shift


Slide 23

Алгоритм Кнута, Мориса и Пратта Program KMP; const         Mmax = 100; Nmax = 10000; var         i, j, k, M, N: integer;         p: array[0..Mmax-1] of char; {слово}         s: array[0..Nmax-1] of char; {текст}         d: array[0..Mmax-1] of integer;


Slide 24

Алгоритм Кнута, Мориса и Пратта begin {Ввод текста s и слова p} Write('N:'); Readln(N); Write('s:'); Readln(s); Write('M:'); Readln(M); Write('p:'); Readln(p); {Заполнение массива d} j:=0; k:=-1; d[0]:=-1;


Slide 25

Алгоритм Кнута, Мориса и Пратта while j<(M-1) do begin             while(k>=0) and (p[j]<>p[k]) do k:=d[k];             j:=j+1; k:=k+1;             if p[j]=p[k] then d[j]:=d[k]             else d[j]:=k; end;


Slide 26

Алгоритм Кнута, Мориса и Пратта {Поиск слова p в тексте s} i:=0; j:=0; while (j<M) and (i<N) do begin          while (j>=0) and (s[i]<>p[j]) do j:=d[j]; {Сдвиг слова}           i:=i+1; j:=j+1; end;


Slide 27

Алгоритм Кнута, Мориса и Пратта {Вывод результата поиска} if j=M then Writeln('Yes') {найден } else Writeln('No'); {не найден} Readln; end. Число сравнений – m+n


Slide 28

Алгоритм Боуера и Мура


Slide 29

Алгоритм Боуера и Мура Program BM; const         Mmax = 100; Nmax = 10000; var         i, j, k, M, N: integer;          ch: char;         p: array[0..Mmax-1] of char; {слово}        s: array[0..Nmax-1] of char; {текст}         d: array[' '..'z'] of integer;


Slide 30

Алгоритм Боуера и Мура begin {Ввод текста s и слова p} Write('N:'); Readln(N); Write('s:'); Readln(s); Write('M:'); Readln(M); Write('p:'); Readln(p); {Заполнение массива d} for ch:=' ' to 'z' do d[ch]:=M;


Slide 31

Алгоритм Боуера и Мура for j:=0 to M-2 do d[p[j]]:=M-j-1; i:=M; repeat           j:=M; k:=i;           repeat {Цикл сравнения символов }                      k:=k-1; j:=j-1; {слова, начиная с правого.}           until (j<0) or (p[j]<>s[k]); {Выход, если сравнили все}           {слово или несовпадение. }           i:=i+d[s[i-1]]; {Сдвиг слова вправо } until (j<0) or (i>N);


Slide 32

Алгоритм Боуера и Мура {Вывод результата поиска} if j<0 then Writeln('Yes') {найден } else Writeln('No'); {не найден} Readln; end.


×

HTML:





Ссылка: