Эффективность индексно-последовательного поиска.

Эффективность индексно-последовательного поиска.

m=n/p, где n-размер индекса, p-размер шага

Q=(n+1)/2+(p+1)/2= (n/p+1)/2 + (p+1)/2= n/2p+p/2+1

4. (реферат по «поиск в таблице» на 5 страниц, титульный лист- название вуза, кафедры, студент, Краснодар 2012)

5. Алгоритм:

· Символы подвергаются сравнению

· При несовпадении пары символов, слово сдвигается на все пройденное расстояние

· Меньшие сдвиги не могут привести к полному совпадению

Пример: ABCABCABAABCABD

ABCABD

ABCABC

Пусть j определяет позицию в слове, содержащую первый несовпадающий элемент. Величина сдвига j-D. D – размер самой длинной последовательности, зависит только от слова и не зависит от текста. Для каждого j будет своя D, dj. Перед началом поиска можно вычислить вспомогательную таблицу d.

Анализ алгоритма.

Требуется M+N сравнений символов.

Примеры:

1. Дан массив: 4, 7, 9, 11, 14, 23, 29, 30, 34, 37, 40, 42. Найти элемент с ключом 23, линейный поиск.

2. Дан массив: 9, 12, 34, 17, 22, 38, 40, 51. Найти элемент с ключом 17, двоичный поиск.

9, 12, 17, 22, 34, 38, 40, 51

9, 12, 17, 22

6. Считается наиболее быстрым среди алгоритмов поиска. Был разработан в 1977 году. Преимущества: не нужно сравнивать шаблон с каждой исходной буквой текста, так как некоторые из них можно пропустить. Суть действия:

1. Строится таблица смещения для искомого шаблона (совмещается начало текста и шаблона, проверка начинается с последнего символа шаблона)

2. Если последний символ шаблона и соответствующий символ строки не совпадают, то образец сдвигается относительно строки на полученную величину, взятую из таблицы смещений

3. Берем символ из строки, а не из шаблона, и смотрим соответствующий сдвиг в таблице

4. Сдвигаем и снова начинаем проверку с последнего символа. Если символы совпадают, то производится сравнение предпоследнего символа

5. Если все символы шаблона совпали с наложенными символами строки, то поиск окончен

6. Если какой-то символ шаблона не совпадает с соответствующим символом строки (не последний символ), то шаблон сдвигается на 1 символ вправо и проверка начинается с последнего символа

7. Алгоритм выполняется до тех пор, пока не будет найдет вхождение искомого образца, либо не достигнут конец строки