Поиск подстрок

Июль 21, 2022

Главная
Информатика
Поиск подстрок

Содержание

2. Поиск точно заданной подстроки в строке
3. В задачах поиска традиционно принято обозначать шаблон поиска как needle (англ.В задачах поиска традиционно принято обозначать
4. Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W
5. Пример: Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca Образец входит в текст
6. Идея алгоритма: 1. I=1, 2. сравнить I-й символ массива T с первым символом массива W, 3.
7. Недостатки алгоритма: 1. Высокая сложность — O(N*M). 2. После несовпадения просмотр всегда начинается с первого символа
8. i = –1; //n – длина строки m-подстроки do { i++; j = 0; while((j j++;
9. Алгоритм Рабина-Карпа (РК-поиск)
10. ИДЕЯ Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый
11. На примере русского алфавита: ЕГОР = 5 3 14 16 = 5*343+ 3*342 +14*34+ 16 =
12. Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Пример. Пусть шаблон имеет
13. k1=31415(mod 13)=7 – вхождение подстроки, k2=67399(mod 13)=7 – холостое срабатывание. Из равенства ki= kj (mod q)
14. Трудоемкость Если простое число q достаточно велико, то дополнительные затраты на анализ холостых срабатываний будут невелики.
15. Пример: Сколько холостых срабатываний k сделает алгоритм РК, если q= 11, 13, 17. Пусть W={2 6}
17. Скачать презентацию

Слайд 2

Поиск точно заданной подстроки в строке

Слайд 3

В задачах поиска традиционно принято обозначать шаблон поиска как needle (англ.В задачах поиска

традиционно принято обозначать шаблон поиска как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ.В задачах поиска традиционно принято обозначать шаблон поиска как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»).

Слайд 4

Поиск строки формально определяется следующим образом. Пусть задан массив Т из

N элементов и массив W из M элементов, причем 0Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки совпадение с шаблоном.

Слайд 5

Пример:
Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca
Образец

входит в текст только один раз, со сдвигом S=3, индекс i=4.

Слайд 6

Идея алгоритма: 1. I=1, 2. сравнить I-й символ массива T с первым символом

массива W, 3. совпадение → сравнить вторые символы и так далее, 4. несовпадение → I:=I+1 и переход на пункт 2,
Условие окончания алгоритма: 1. подряд М сравнений удачны, 2. I+M>N, то есть слово не найдено.

Алгоритм прямого поиска

Слайд 7

Недостатки алгоритма:
1. Высокая сложность — O(N*M).
2. После несовпадения просмотр всегда начинается

с первого символа образца и поэтому может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени).

3. Информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.

Слайд 8

i = –1; //n – длина строки m-подстроки
do {
i++;
j =

0;
while((j < m) && (haystack[i + j] == needle[j]))
j++;
}
while ((j != m) && (i < n – m));

Слайд 9

Алгоритм Рабина-Карпа (РК-поиск)

Слайд 10

ИДЕЯ
Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7,

8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│.

Слайд 11

На примере русского алфавита:
ЕГОР = 5 3 14 16 = 5*343+

3*342 +14*34+ 16 = 200480

Слайд 12

Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8,

9}
Пример. Пусть шаблон имеет вид W = 3 1 4 1 5 Вычисляем значения чисел из окна длины |W|=5 по mod q, q — простое число.

23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=3 …
31415(mod 13)=7

Слайд 13

k1=31415(mod 13)=7 – вхождение подстроки,
k2=67399(mod 13)=7 – холостое срабатывание.
Из равенства ki=

kj (mod q) не следует, что ki= kj (например, 31415=67399(mod 13), но это не значит, что 31415=67399). Если ki= kj (mod q), то ещё надо проверить, совпадают ли строки W[1…m] и T[s+1…s+m] на самом деле.

Слайд 14

Трудоемкость
Если простое число q достаточно велико, то дополнительные затраты на анализ

холостых срабатываний будут невелики. В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).
Очевидно, что количество холостых срабатываний k является функцией от величины простого числа q (если функция обработки образца mod q) и, в общем случае, от вида функции для обработки образца W и текста Т.

Слайд 15

Пример:
Сколько холостых срабатываний k сделает алгоритм РК, если q= 11, 13, 17.

Пусть W={2 6}

26 mod 11=4 → k =3 холостых срабатывания, 26 mod 13=0 → k =1 холостое срабатывание, 26 mod 17=9 → k =0 холостых срабатываний.

Поиск подстрок

Содержание

Поиск точно заданной подстроки в строке

В задачах поиска традиционно принято обозначать шаблон поиска как needle (англ.В задачах поиска

Поиск строки формально определяется следующим образом. Пусть задан массив Т из

Пример:Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabcaОбразец

Идея алгоритма: 1. I=1, 2. сравнить I-й символ массива T с первым символом

Недостатки алгоритма: 1. Высокая сложность — O(N*M).2. После несовпадения просмотр всегда начинается

i = –1; //n – длина строки m-подстрокиdo { i++; j =

Алгоритм Рабина-Карпа (РК-поиск)

ИДЕЯПусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7,

На примере русского алфавита:ЕГОР = 5 3 14 16 = 5*343+

Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8,

k1=31415(mod 13)=7 – вхождение подстроки, k2=67399(mod 13)=7 – холостое срабатывание. Из равенства ki=

ТрудоемкостьЕсли простое число q достаточно велико, то дополнительные затраты на анализ

Пример:Сколько холостых срабатываний k сделает алгоритм РК, если q= 11, 13, 17.

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