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

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

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

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

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

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

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

7 Линейный поиск Алгоритм 1. i:=0; while (i х) do i:=i+1;

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

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

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

11 L:=0; R:=N-1; Found:=false; while(L

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

13 Поиск делением пополам (двоичный поиск) Быстрый алгоритм L:=0; R:=N; while L

14 Поиск в таблице Поиск в массиве иногда называют поиском в таблице, особенно если ключ сам является составным объектом, таким, как массив чисел или символов 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

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

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

17 Поиск в таблице L:=0; R:=N; while L

18 Поиск в таблице if R

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

20 Прямой поиск строки Алгоритм прямого поиска i:=-1; repeat i:=i+1; j:=0; while (j

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

22

23 Общая схема КМП-алгоритма i:= 0; j:=0; While (j

24 Алгоритм Кнута, Мориса и Пратта 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;

25 Алгоритм Кнута, Мориса и Пратта 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;

26 Алгоритм Кнута, Мориса и Пратта while j=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;

27 Алгоритм Кнута, Мориса и Пратта {Поиск слова p в тексте s} i:=0; j:=0; while (j

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

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

30 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;

31 Алгоритм Боуера и Мура 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;

32 Алгоритм Боуера и Мура 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 s[k]); {Выход, если сравнили все} {слово или несовпадение. } i:=i+d[s[i-1]]; {Сдвиг слова вправо } until (j N);

33 Алгоритм Боуера и Мура {Вывод результата поиска} if j