Лекция 5 Поиск. Задача поиска Объекты в общем случае будем рассматривать как записи произвольной природы, однако имеющие в своей структуре один и тот. - презентация

1 Лекция 5 Поиск

2 Задача поиска Объекты в общем случае будем рассматривать как записи произвольной природы, однако имеющие в своей структуре один и тот же ключ поле, содержащее значение, которое сравнивается в процессе поиска с искомым ключом. В более общем случае ключ можно рассматривать как числовую функцию, которая строит значение ключа на основании сколь угодно сложного анализа всех данных, представленных в записи. Далее при рассмотрении методов поиска и сортировки мы для простоты будем отождествлять записи с их ключами. Следующие описания структур данных будут использоваться в дальнейших алгоритмах: /* описания глобальных констант, типов и данных */ #define N 100 /* размер входного массива */ typedef int key; /* тип ключа */ static key а[N]; /* входной массив */

3 Последовательный поиск Начинаем просмотр с первого элемента массива, продвигаясь дальше до тех пор, пока не будет найден нужный элемент или пока не будут просмотрены все элементы массива. int seek_linear(key x, key a[], int N) { int i=0; while ((i

4 Бинарный поиск в массиве Условие применения: массив должен быть отсортированным. Идея: массив на каждом шаге делится пополам и выбирается та его часть, в которой должен находиться искомый элемент X = 33 []

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

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 s q

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

9 Алгоритм РабинаКарпа поиска подстроки Пусть строка и шаблон состоят из символов алфавита А. Каждый символ этого алфавита будем считать d-ичной цифрой, где d = A. Строку из k символов можно рассматривать как запись d-ичного k-значного числа. Тогда поиск шаблона в строке cводится к серии из N – М сравнений числа, представляющего шаблон, с числами, представляющими подстроки s длины М. Cравнение чисел может быть выполнено за время, пропорциональное М, и тогда эффективность поиска будет O(N + М). Для начала предположим, что А = {0,1,..., 9}. Число, десятичной записью которого является шаблон q, обозначим через t q. Аналогично, обозначим через t k число, десятичной записью которого является под­строка s[k... k + М – 1]. Подстрока s[k... k + М – 1] совпадает с шаблоном q тогда и Только тогда, когда t q = t k.

10 По схеме Горнера значения t q и t 1 можно вычислить за время, пропорциональное М. Временно забудем о том, что вычисления могут привести к очень большим числам. Из t k (1 < k N – М) за константное время можно вычислить t k+1. По схеме Горнера:

11 Чтобы получить t k+1 из t k, надо удалить последнее слагаемое из формулы (10) ( т. е. вычесть 10M-1 s[k]), результат умножить на 10 и добавить к нему s[k+M]. В результате получим следующее рекуррентное соотношение:

12 Вычислив все t k, мы можем по очереди сравнить их с t q, определив тем самым совпадение или несовпадение шаблона q с подстроками s[k... k + М – 1]. Время работы этого алгоритма пропорционально N-M. До сих пор мы не учитывали того, что числа могут быть слишком велики. С этой трудностью можно справиться следующим образом. Надо проводить вычисления чисел t q и t k и вычисления по формуле (11) по модулю фиксированного числа р. Тогда все числа не превосходят р и действительно могут быть вычислены за время порядка М. Обычно в качестве р выбирают простое число, для которого d р помещается в машинное слово, все вычисления в этом случае упрощаются.

13 Рекуррентная формула (11) приобретает вид: где. Из равенства t q t k (mod p) еще не следует, что t q = t k и, стало быть, что q = s[k... k + М – 1]. В этом случае надо для надежности проверить совпадение шаблона и подстроки.

14 Алгоритм А5: вход: q - шаблон, s - строка, М - длина шаблона, N - длина строки, М < N, d - число символов в алфавите. По схеме Горнера вычислить числа и по модулю р; цикл по k от 1 до N – М + 1 если = то сравнить шаблон q с подстрокой s[k... k + М – 1]; если они совпадают, то выдать k - результат сравнения; выход по формуле (12) вычислить конец цикла выход: k - позиция начала вхождения шаблона в строку. /* d - число символов в алфавите */ /* р - число, по модулю которого производятся вычисления */ /* возвращает смещение вхождения q в s относительно начала строки */

15 int Robin_Carp_Matcher(char s[], char q[], int d, int p) { int i, h, k, M, N, t_q, t_k; N = strlen(s); М = strlen(q); /* вычисление h=(dM-l)mod p */ h=l; for(i=l; i

16 7 7 mod 13 (а) вхождение образца холостое срабатывание ……… (б) mod Цифра старшего разряда Цифра старшего разряда (в) (mod 13) Цифра старшего разряда Цифра старшего разряда

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

18 Пример построения таблицы сдвигов Для шаблона аbсаbеаbсе ( М = 10) d[' a '] = 3, d[' b '] = 2, d[' c '] = 1, d[' e '] = 4 и для всех символов х алфавита, не входящих в шаблон, d[x] = 10.

19 Алгоритм Бойера - Мура Будем последовательно сравнивать шаблон 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, то смещение происходит сразу на полную длину шаблона М.

20 Реализация алгоритма Бойера-Мура 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

21 Пример работы алгоритма Бойера - Мура а 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

22 Анализ алгоритма Бойера - Мура Определение длин исходных строк выполняется в Си поиском заключительного нулевого символа и требует, таким образом, времени N + М. Для построения таблицы d необходимо занести значение М во все позиции таблицы и выполнить один проход по всем элементам шаблона q, т. е. таблица строится за время (256 + М). Считаем, что М намного меньше N. Как правило, данный алгоритм требует значительно меньше N сравнений. В благоприятных обстоятельствах, а именно если последний символ шаблона всегда попадает на несовпадающий символ текста, максимальное число сравнении символов есть N/M.

23 Алгоритм КнутаМоррисаПратта Каждый раз при неудачном сравнении шаблона с подстрокой оба индекса-указателя возвращаются к некоторым уже просмотренным позициям, и сравнение начинается, по сути, заново. Полученная информация о том, что некоторый префикс (начало) шаблона q совпал с суффиксом (концом) просмотренной подстроки s, теряется. Пример. Пусть q наложен на s начиная с позиции k, до позиций i и j они совпадают, а в i и j расходятся: 1 k i l s: b a a b a b a b a c a b a t q: a b a b a c a 1 jM

24 Здесь j = 6 символов строки, следующих за позицией k, уже известны, поэтому можно, не выполняя сравнений, установить, что некоторые последующие сдвиги шаблона заведомо бесперспективны. Например, сдвиг на 1 позицию бесперспективен, так как при этом q[1] ='a' сравнится с уже известным s[k+1] ='b' и совпадения не будет. А вот сдвиг на 2 позиции сразу отвергнуть нельзя: q[1...4] совпадает с уже известной подстрокой s[k+2... k+5]. Совпадут ли остальные М - 4 символа, станет известно только при рассмотрении последующих символов s, причем сравнение можно начинать сразу с 5-й позиции шаблона. Таким образом, при неудаче очередного сравнения надо сдвинуть шаблон вперед так, чтобы его начало совпало с уже прочитанными символами строки. Если таких сдвигов можно указать несколько, следует выбрать кратчайший из них.

25 КМП-алгоритм (Кнут, Моррис, Пратт) КМП-алгоритм (Кнут, Моррис, Пратт) Алгоритм А4: вход: q - шаблон, s - строка, М - длина шаблона, N - длина строки, М < N. i := l; j := 1; пока (i N) и (j М) цикл пока (j > 0) и s([i] q[j]) цикл j:=dj; /*0 dj < j */ конец цикла; i := i + 1; j := j + 1; конец цикла; выход: если j > М то шаблон q найден в позиции i - М; иначе /* i > N */ шаблон q не найден.

26 Индекс-указатель i пробегает строку s без возвратов (что обеспечи­вает линейность времени работы алгоритма). Индекс j синхронно пробегает шаблон q, однако может возвращаться к некоторым предыдущим позициям dj. которые будут выбираться так, чтобы обеспечить на всем протяжении алгоритма инвариантность следующего условия Eq(i,j): «все символы шаблона, предшествующие позиции j, совпадают с таким же числом символов строки, предшествующих позиции i » :

27 Истинность условия Eq(i, M+1) означает, что шаблон q входит в s начиная с позиции i–M. Выполнение условия Eq(N+1, j) при j < М означает, что шаблона в строке нет. Eq(i,j): 1i N+1 и 1 j M +1 и pref(q,j-1)=suff(pref(s,i-1),j-1), где pref(str,k)=str[1…k] – k-префикс str suff(str,k)=str[l-k+1…l] – k-суффикс str[] (l – длина str) (пример str[i..i-1]= )

28 При первом входе в цикл индексы указывают на начала строк и Eq(i,j) = Eq(1, 1), очевидно, истинно. На каждом проходе цикла указатель i сдвигается на одну позицию строки вперед без возвратов. Пока очередные символы совпадают, внутренний цикл не выполняется и j просто увеличивается синхронно с i, что обеспечивает сохранение условия Eq(iнов, jнов) = Eq(i+1,j+1) без сдвига шаблона относительно строки.

29 При несовпадении очередных символов надо сдвинуть шаблон так, чтобы некоторый dj-префикс q продолжал совпадать с dj-суффиксом просмотренной строки s [1.. i], тем самым сохраняя инвариант Eq (iнов, jнов) = Eq (i + 1, dj + 1) для следующей итерации цикла. Изменение соответствия позиций с (i, j) на (i+1, dj+1) означает сдвиг q относительно s на D = j - dj > 0 позиций вперед. Отсюда dj < j. Ес­ли таких dj-префиксов можно указать несколько, надо выбрать из них наибольший по длине, чтобы сдвиг D был кратчайшим. Если таких префиксов нет, возьмем dj = 0, так как Eq(i+1, 1) всегда истинно. Это соответствует сдвигу шаблона на D=j, к позиции s[i+l]; т. е. следующее сравнение начнется со следующей непрочитанной позиции строки, имея «нулевую историю» совпадений.

30 До сдвига pref (q, j–1) совпадает с suff (pref (s,i1), dj 1). Чтобы сдвиг шаблона на D=j – dj был перспективен, префикс pref (q, j – D – 1) = pre f (q, dj – 1 ) должен совпадать с суффиксом suff (pref (s, i – 1), dj – 1), с которым до сдвига совпадал suff (pref (q, j–1), dj–1). Отсюда pref(q, dj –1) = suff (pref (q, j –1), dj –1), т. е. q[1...dj–1] = q[j–dj j–1]. (7) Это условие необходимо для перспективности сдвига на D = j – dj, но еще не достаточно; из сравнения нам еще известно, что s[i] не совпадает с q[j]. Поэтому если q[dj] = q[j], то сдвиг бесперспективен. Сделаем соответствующее уточнение в формуле (7): q[1...dj –1] = q[j–dj j–1] и q[dj] q[j] (8)

31 Добавив теперь условие максимальности длины префикса dj, выразим зависимость dj от j cледующей префикс-функцией: d [j] = max{d d < j и q [1...d –1] = q [j–d j–1] и q [d] q [j] }. (9) Как можно видеть, префикс-функция зависит только от шаблона q, но не от строки s, поэтому она может быть вычислена ещё до начала поиска и задана в алгоритме таблицей значений. Однако зависимость dj от строки все же имеется: если q[dj] s[i], то сдвиг тоже заведомо бесперспективен. В этом случае вычисленное d[j] следует отвергнуть и Так как j > dj, все длины перспективных префиксов q образуют последовательность, убывающую до нуля: d[j] > d[d[j]] > d[d[d[j]]] >... > d[...d[j]...] = 0.

32 Выбором подходящего dj, с учетом всего сказанного, занимается внутренний цикл КМП-алгоритма. Ниже приведены значения префикс-функции и величины сдвига для шаблона аbаbаса из примера выше: - по формуле (9) j: q[j]: a b a b a c a d[j]: по фломуле (9) D=j-d[j]:

33 1 i N s: b a a b a b a b a c a b a b ^ q: a b a b a c a 1 ^d j M q: j-d a b a b a c a 1 ^d M - E q(i,j): j = 6,d[j] = 4 -pref(q,3) = suff(pref(s,i-1),3) - d-1 = 3 – длина совпадения - условие (8) выполнено и q[d] = s[i] -сдвиг на j-d = 2 совмещает префикс с суфиксом - d-префикс совпадает Eq(i+1,d+1) - продолжаем сравнение с (i+1,d+1)Пример

34 Допустим, что для всех позиций k шаблона, предшествующих и включая i, d[k] уже вычислены и d[i] = j+1. Это означает, что pref (q, j) = suff (pref(q, i), j). Сравним q [i + 1] и q [j + 1]: если они равны, то pref(q, j + 1) = suff (pref (q, i+ 1), j + 1), т. е. d[i + 1] = j +2; если они не равны, то выберем для испытаний следующий по длине префикс q, являющийся суффиксом pref (q, i ), т. е. d[j].

35 int seek_substring_KMP (char s[], char q[]){ int i, j, N, M; N = strlen(s); M = strlen(q); int *d =(int*)malloc(M*sizeof(int));/* динамический массив длины М+1*/ /* Вычисление префикс-функции */ i=0; j=-l; d[0]=-l; while (i < M-l) { while((j>=0) && (q[j]!=q[i])) j = d[j]; i++; j++; if(q[i]==q[j]) d[i] = d[j]; else d[i]= j; } /* поиск */ for(i=0,j=0;(i