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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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;

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;

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;

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

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

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

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

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

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

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

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

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

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;

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;

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

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

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

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

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

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

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

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

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

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

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

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

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

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