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

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

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

3 CAOD, dep.OSU3 Задачи поиска в структурах данных d

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

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

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

7 CAOD, dep.OSU7 Линейный поиск Алгоритм 1. a: [0..N -1] of Item; i 0; while (i х) do i i+1; Временная сложность O(n)

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

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

10 CAOD, dep.OSU10 Поиск делением пополам (двоичный поиск)

11 CAOD, dep.OSU11 Поиск делением пополам (двоичный поиск) L 0; R N-1; Found false; while (L

12 CAOD, dep.OSU12 Поиск делением пополам (двоичный поиск) Максимальное число сравнений для этого алгоритма равно log 2 n Временная сложность O(log 2 n)

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

14 CAOD, dep.OSU14 Поиск в таблице Поиск в массиве иногда называют поиском в таблице, особенно если ключ сам является составным объектом, таким, как массив чисел или символов 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 CAOD, dep.OSU15 Поиск в таблице Схема поиска с концевым символом i:=0; while (x[i]=y[i]) and (x[i]*) do i:=i+1 Концевой символ работает здесь как барьер

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

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

18 CAOD, dep.OSU18 Поиск в таблице if R

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

20 CAOD, dep.OSU20 Прямой поиск строки Алгоритм прямого поиска i -1; repeat i i+1; j 0; while (j

21 CAOD, dep.OSU21 Прямой поиск строки

22 CAOD, dep.OSU22 Прямой поиск строки Временная сложность T(n) = O((n-m+1)m) T(n) = O (nm) demo

23 CAOD, dep.OSU23 Алгоритм Кнута, Мориса и Пратта R F

24 CAOD, dep.OSU24 Алгоритм Кнута, Мориса и Пратта T(n) = O (n+m)

25 CAOD, dep.OSU25 Алгоритм Кнута, Мориса и Пратта Общая схема КМП-алгоритма i 0; j 0; While (j

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

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

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

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

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

31 CAOD, dep.OSU31 Алгоритм Боуера и Мура Сканирование слева направо, сравнение справа налево. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

32 CAOD, dep.OSU32 Алгоритм Боуера и Мура

33 CAOD, dep.OSU33 Алгоритм Боуера и Мура Таблица сдвигов: Для символов, отсутствующих в образце, сдвиг равен длине образца Для символов из образца сдвиг равен расстоянию от последнего вхождения символа в образец до конца образца

34 CAOD, dep.OSU34 Алгоритм Боуера и Мура

35 CAOD, dep.OSU35 Алгоритм Боуера и Мура

36 CAOD, dep.OSU36 Алгоритм Боуера и Мура

37 CAOD, dep.OSU37 Алгоритм Боуера и Мура T(n) =O(n+m+| |) demodemo

38 CAOD, dep.OSU38 Алгоритм Боуера и Мура 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;

39 CAOD, dep.OSU39 Алгоритм Боуера и Мура 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;

40 CAOD, dep.OSU40 Алгоритм Боуера и Мура 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);

41 CAOD, dep.OSU41 Алгоритм Боуера и Мура {Вывод результата поиска} if j

42 CAOD, dep.OSU42 Алгоритм Рабина-Карпа Рабин (Rabin) и Карп (Каrр) (1987г.) предложили алгоритм поиска подстрок, показывающий на практике хорошую производительность в поиске совпадений множественных шаблонов.RabinКаrр В алгоритме Рабина-Карпа время O (m) затрачивается на предварительную обработку, а время его работы в наихудшем случае равно O ((n m + 1)m)

43 CAOD, dep.OSU43 Алгоритм Рабина-Карпа В общем случае можно предположить, что каждый символ это цифра в системе счисления с основанием d, где d = | | Строку из k последовательных символов можно рассматривать как число длиной k. Таким образом, символьная строка соответствует числу

44 CAOD, dep.OSU44 Алгоритм Рабина-Карпа Для заданного образца Р [1..m] обозначим через р соответствующее ему десятичное значение. Аналогично, для заданного текста T[1..n] обозначим через t s десятичное значение подстроки Т [s + l..s + m] длиной m при s = 0,1,..., n-m

45 CAOD, dep.OSU45 Алгоритм Рабина-Карпа Очевидно, что t s = р тогда и только тогда, когда T[s + l..s + m] = Р [1..m] таким образом, s допустимый сдвиг тогда и только тогда, когда t s = р.

46 CAOD, dep.OSU46 Алгоритм Рабина-Карпа Если бы значение р можно было вычислить за время O (m), а все значения t s за суммарное время O (n-m+1), то значения всех допустимых сдвигов можно было бы определить за время O(m) + O(n-m + 1) = O (n) путем сравнения значения р с каждым из значений t s

47 CAOD, dep.OSU47 Алгоритм Рабина-Карпа Вычисление р (по схеме Горнера) – O(m) Значение t o можно вычислить из массива Т[1..m] за время O(m) аналогичным способом. Чтобы вычислить остальные значения t 1,t 2,…t n-m за время O (n-m) Можно использовать рекуррентную формулу Удаление цифры в старшем разряде Добавле ние цифры в младший разряд

48 CAOD, dep.OSU48 Алгоритм Рабина-Карпа Для вычисления чисел p и t s можно использовать операцию деление по модулю –q и вычисление t s трансформируется в где h= d m-1 (mod q)

49 CAOD, dep.OSU49 Алгоритм Рабина-Карпа

50 CAOD, dep.OSU50 Алгоритм Рабина-Карпа

51 CAOD, dep.OSU51 Алгоритм Рабина-Карпа Во многих приложениях ожидается небольшое количество допустимых сдвигов (возможно, выражающееся некоторой константой с); в таких приложениях математическое ожидание времени работы алгоритма равно сумме величины O((n-m+1) + cm) = O(n + m) и времени, необходимого для обработки ложных совпадений.

52 CAOD, dep.OSU52 Алгоритм Рабина-Карпа можно показать, что число ложных совпадений равно О (n/q), потому что вероятность того, что произвольное число t s будет эквивалентно р по модулю q, можно оценить как 1/q. Поскольку имеется всего О (n) позиций, в которых проверка в строке 10 дает отрицательный результат, а на обработку каждого совпадения затрачивается время О (m), математическое ожидание времени сравнения в алгоритме Рабина-Карпа равно O(n)+ O(m(v+n/q)), Где v-кол-во допустимых сдвигов

53 CAOD, dep.OSU53 Алгоритм Рабина-Карпа если v=O(1) а q m, то T(n) = O(n) demo