Поиск. Задача поиска. (Лекция 7)

Июль 27, 2022

Главная
Информатика
Поиск. Задача поиска. (Лекция 7)

Содержание

2. Задача поиска Объекты в общем случае будем рассматривать как записи произвольной природы, однако имеющие в своей
3. Последовательный поиск Начинаем просмотр с первого элемента массива, продвигаясь дальше до тех пор, пока не будет
4. Бинарный поиск в массиве Условие применения: массив должен быть отсортированным. Идея: массив на каждом шаге делится
5. Бинарный поиск - программа int seek_binary(key x, key a[], int N) { int left = O;
6. Прямой поиск подстроки Пусть заданы строка s из N элементов и строка q из М элементов,
7. Прямой поиск подстроки - алгоритм Вход: Строка s длины N и строка q длины M, где
8. Прямой поиск подстроки - программа int seek_substring_A (char s[], char q[]) { int i, j, k,
9. Алгоритм Бойера—Мура поиска подстроки в строке Данный алгоритм ведет сравнение символов из строки и шаблона, начиная
10. Пример построения таблицы сдвигов Для шаблона “аbсаbеаbсе” (М = 10) d['a'] = 3, d['b'] = 2,
11. Алгоритм Бойера-Мура - описание Будем последовательно сравнивать шаблон q с подстроками s[i – М + 1..i]
12. Реализация алгоритма Бойера-Мура на си int seek_substring_BM(unsigned char s[], unsigned char q[]) { int d[256]; int
13. Пример работы алгоритма Бойера - Мура а friend in need is a friend indeed indeed М
15. Скачать презентацию

Слайд 2

Задача поиска
Объекты в общем случае будем рассматривать как записи произвольной

природы, однако имеющие в своей структуре один и тот же ключ — поле, содержащее значение, которое сравнивается в процессе поиска с искомым ключом. В более общем случае ключ можно рассматривать как числовую функцию, которая строит значение ключа на основании сколь угодно сложного анализа всех данных, представленных в записи.
Далее при рассмотрении методов поиска и сортировки мы для простоты будем отождествлять записи с их ключами.
Следующие описания структур данных будут использоваться в дальнейших алгоритмах:

Слайд 3

Последовательный поиск
Начинаем просмотр с первого элемента массива, продвигаясь дальше

до тех пор, пока не будет найден нужный элемент или пока не будут просмотрены все элементы массива.
int seek_linear(key x, key a[], int N)
{
int i=0;
while ((i i++;
if (i return i; /* элемент найден */
еlse
return -1; /* элемент не найден */
}

Слайд 4

Бинарный поиск в массиве
Условие применения:
массив должен быть отсортированным.
Идея:
массив

на каждом шаге делится пополам и выбирается та его часть, в которой должен находиться искомый элемент.

X = 33

[

]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Слайд 5

Бинарный поиск - программа
int seek_binary(key x, key a[], int N)
{

int left = O;
int right= N-l;
int middle;
do
{
middle=(left+right)/2;
if (x == a[middle])
return middle;
else
if(a[middle]< x)
left = middle + l;
else right = middle - l;
}
while (left <= right);
return -1;
}
Максимальное число сравнений равно log2N .

Слайд 6

Прямой поиск подстроки
Пусть заданы строка s из N элементов и

строка q из М элементов,
где 0 < М ≤ N.
Требуется определить, содержит ли строка s подстроку q, и в случае положительного результата выдать позицию k, с которой начинается вхождение q в s.
q[0] = s[k], q[1] = s[k+1], ..., q[M − 1] = s[k + M − 1].
Будем называть строку q шаблоном поиска.
Задача прямого поиска заключается в поиске индекса k, указывающего на первое с начала строки s совпадение с шаблоном q.

abcdaaccbbssacbaszzzaaa

cbbss

Слайд 7

Прямой поиск подстроки - алгоритм
Вход: Строка s длины N и строка

q длины M, где 0 < М ≤ N.
Шаг 1. Шаблон q «накладывается» на строку s начиная с первого символа строки.
k = 0; // номер символа строки, соответствующий
// первому символу шаблона
Шаг 2. i = 0;
Выполняется последовательное сравнение соответствующих символов, начиная от первого символа шаблона.
Если до i-й позиции шаблона соответствующие символы строки совпали,
a q[i]≠ s[k + i], и i < M, то надо «сдвинуть» шаблон, т. е. «наложить» его на строку, начиная со следующего символа строки:
k = k + 1;
Шаг 3. Если k < N – М + 1, и i < M то перейти на Шаг 2.
Выход: Если q[1 .. М] = s[k .. k+M – 1], то выдать k,
иначе выдать сообщение, что подстрока не найдена.
Данный алгоритм реализуется с помощью двух вложенных циклов и в худшем случае требуется произвести (N - М)⋅ М сравнений.

Слайд 8

Прямой поиск подстроки - программа
int seek_substring_A (char s[], char q[])
{

int i, j, k, N, M;
N = strlen(s);
M = strlen(q);
k = -1;
do {
k++; /* k - смещение шаблона по строке */
j = 0; /* j - смещение по шаблону; */
while ((j j++;
if (j == M)
return k; /* шаблон найден */
}
while (k < N - M );
return -1; /* шаблон не найден */
}

Слайд 9

Алгоритм Бойера—Мура поиска подстроки в строке
Данный алгоритм ведет сравнение символов из

строки и шаблона, начиная с q[М – 1] и с s[i + М – 1] элементов в обратном порядке.
В нем используется дополнительная таблица сдвигов d.
Для каждого символа x из алфавита (кроме последнего в шаблоне)
d[x] есть расстояние от самого правого вхождения х в шаблоне до последнего символа шаблона. Для последнего символа в шаблоне d[x] равно расстоянию от предпоследнего вхождения х до последнего или М, если предпоследнего вхождения нет.

‘b’

M–1

M – j – 1

Слайд 10

Пример построения таблицы сдвигов
Для шаблона “аbсаbеаbсе” (М = 10)
d['a'] =

3,
d['b'] = 2,
d['c'] = 1,
d['e'] = 4
и для всех символов х алфавита, не входящих в шаблон,
d[x] = 10.

Слайд 11

Алгоритм Бойера-Мура - описание
Будем последовательно сравнивать шаблон q с подстроками
s[i

– М + 1..i] (в начале i = М).
Введем два рабочих индекса: j = М, М – 1, ... , 1 — пробегающий символы шаблона, k = i, ... ,i – M+1 — пробегающий подстроку.
Оба индекса синхронно уменьшаются на каждом шаге.
Если все символы q совпадают с подстрокой (т. е. j доходит до 0), то шаблон q считается найденным в s с позиции k (k = i – M+1).
Если q[j]≠s[k] и k = i, т. е. расхождение случилось сразу же, в последних позициях, то q можно сдвинуть вправо так, чтобы последнее вхождение символа s[i] в q совместилось с s[i].
Если q[j] ≠ s[k] и k < i. т. е. последние символы совпали, то q сдвинется так, чтобы предпоследнее вхождение s[i] в q совместилось с s[i].
В обоих случаях величина сдвига равна d[s[i]], по построению.
В частности, если s[i] вообще не встречается в q, то смещение происходит сразу на полную длину шаблона М.

Слайд 12

Реализация алгоритма Бойера-Мура на си
int seek_substring_BM(unsigned char s[], unsigned char q[])
{

int d[256];
int i, j, k, N, M;
N = strlen(s);
M = strlen(q);
/* построение d */
for (i=0; i<256; i++)
d[i]=M; /* изначально М во всех позициях */
for (i=0; i d[(unsigned char)q[i]]= M-i-1;/* кроме последнего символа*/
/* поиск */
i= M-l;
do {
j = M-l; /* сравнение строки и шаблона */
k = i; /* j – по шаблону, k – по строке */
while ((j >= 0) && (q[j] == s[k])) {
k--; j--;
}
if (j < 0) return k+1; /* шаблон просмотрен полностью */
i+=d[(unsigned)s[i]];/*сдвиг на расстояние d[s[i]]вправо*/
} while (i < N);
return -1;
}

Слайд 13

Пример работы алгоритма Бойера - Мура
а friend in need is a

friend indeed

indeed

М = 6
d[ ‘i’] = 5
d[ ‘n’] = 4
d[ ‘d’] = 3
d[ ‘e’] = 1

Шаг 1 – сдвиг на 1
Шаг 2 – сдвиг на 4
Шаг 3 – сдвиг на 4
Шаг 4 – сдвиг на 1
Шаг 5 – сдвиг на 3
Шаг 6 – сдвиг на 6
Шаг 7 – сдвиг на 5
Шаг 8 – сдвиг на 5

indeed

Поиск. Задача поиска. (Лекция 7)

Содержание

Задача поиска Объекты в общем случае будем рассматривать как записи произвольной

Последовательный поиск Начинаем просмотр с первого элемента массива, продвигаясь дальше

Бинарный поиск в массиве Условие применения: массив должен быть отсортированным. Идея: массив

Бинарный поиск - программаint seek_binary(key x, key a[], int N) {

Прямой поиск подстроки Пусть заданы строка s из N элементов и

Прямой поиск подстроки - алгоритмВход: Строка s длины N и строка

Прямой поиск подстроки - программаint seek_substring_A (char s[], char q[]) {

Алгоритм Бойера—Мура поиска подстроки в строкеДанный алгоритм ведет сравнение символов из

Пример построения таблицы сдвиговДля шаблона “аbсаbеаbсе” (М = 10) d['a'] =

Алгоритм Бойера-Мура - описаниеБудем последовательно сравнивать шаблон q с подстроками s[i

Реализация алгоритма Бойера-Мура на сиint seek_substring_BM(unsigned char s[], unsigned char q[]){

Пример работы алгоритма Бойера - Мураа friend in need is a

Похожие презентации