Поиск данных. Постановка задачи поиска данных Первый атрибут: набор данных –совокупность данных, среди которых осуществляется поиск; –Элементы набора. - презентация

1 Поиск данных

2 Постановка задачи поиска данных Первый атрибут: набор данных –совокупность данных, среди которых осуществляется поиск; –Элементы набора называются записями; –Записи состоят из полей; Второй атрибут: ключ поиска –Поле записи, по значению которого происходит поиск; Третий атрибут: критерий поиска –Условие, которому должно удовлетворять значение ключа поиска в искомой записи.

3 От чего зависит время поиска? как организован набор данных в информационном хранилище; каким алгоритмом поиска пользуются.

4 Организация набора данных Данные могут быть не организованы; Данные структурированы (данные упорядочены) Структурированные системы данных, хранящиеся на каких-либо носителях, называют структурами данных.

5 Последовательный поиск Последовательный перебор всех элементов множества до нахождения нужного; Число просмотров при последовательном поиске приблизительно равно N/2, где N - размер набора данных.

6 Алгоритм последовательного перебора Начало поиска Имеются непроверенные элементы? Выбрать очередной элемент Выполняется критерий поиска? Искомые данные получены Искомые данные не обнаружены Конец поиска

7 Поиск половинным делением Согласно методу половинного деления, количество элементов каждый раз уменьшают в два раза. Метод половинного деления для упорядоченного набора данных работает гораздо быстрее, чем метод последовательного поиска

8 Если максимальное число диапазона N не равно целой степени двойки, то оптимальное количество вопросов не будет постоянной величиной, а будет равно одному из двух значений: X или X+1, где 2 X < N < 2 X+1 Пример: Искомое число в диапазоне от 1 до 7, то его можно угадать за 2 или 3 вопроса 2 2 < N < 2 3

9 Блочный поиск Несколько страниц, помеченных одной буквой – блок; Индекс – часть ключа поиска; Блочно-последовательный метод: 1) с помощью алфавитного индекса выбирается блок с нужной буквой; 2) внутри блока поиск производится путем последовательного перебора.

10 Поиск в иерархической структуре Многоуровневые блочные структуры хранения данных называются иерархическими структурами. –В файловой системе блоки это каталоги. –Чтобы найти файл, нужно знать путь к файлу по дереву каталога. –Метод поиска в дереве каталогов называют методом спуска по дереву каталогов.