§11 Поиск данных

Информатика и ИКТ 10-11 класс Семакин, Информатика 10-11 класс Семакин, Поиск данных, Постановка задачи поиска данных, Организация набора данных, Последовательный поиск, Поиск половинным делением, Блочный поиск, Поиск в иерархической структуре данных

Вспомните, как часто приходится вам искать какие-нибудь данные. Таких примеров много и в бытовых ситуациях, и в учебном процессе. Например, в программе телепередач вы ищете время начала трансляции футбольного матча; в расписании поездов — сведения о поезде, идущем до нужной вам станции. На уроке физики, решая задачу, ищете в таблице удельный вес меди. На уроке английского языка, читая иностранный текст, ищете в словаре перевод слова на русский язык. Работая за компьютером, вам нередко приходится искать на его дисках файлы с нужными данными или программами.
Постановка задачи поиска данных
Во всех компьютерных информационных системах поиск данных является основным видом обработки информации. При выполнении любого поиска данных имеются три составляющие, которые мы назовем атрибутами поиска:
Первый атрибут: набор данных. Это вся совокупность данных, среди которых осуществляется поиск. Элементы набора данных будем называть записями. Запись может состоять из одного или нескольких полей. Например, запись в записной книжке состоит из полей: фамилия, адрес, телефон.
Второй атрибут: ключ поиска. Это то поле записи, по значению которого происходит поиск. Например, поле ФАМИЛИЯ, если мы ищем номер телефона определенного человека.
Третий атрибут: критерий поиска, или условие поиска. Это то условие, которому должно удовлетворять значение ключа поиска в искомой записи. Например, если вы ищете телефон Сидорова, то критерий поиска заключается в совпадении фамилии Сидоров с фамилией, указанной в очередной записи в книжке.
Заметим, что ключей поиска может быть несколько, тогда и критерий поиска будет сложным, учитывающим значения сразу нескольких ключей. Например, если в справочнике имеется несколько записей с фамилией Сидоров, но у них разные имена, то составной критерий поиска будет включать два условия: ФАМИЛИЯ — Сидоров, ИМЯ — Владимир.
Как при «ручном» поиске, так и при автоматизированном важнейшей задачей является сокращение времени поиска. Оно зависит от двух обстоятельств:
1) как организован набор данных в информационном хранилище (в словаре, в справочнике, на дисках компьютера и пр.);
2) каким алгоритмом поиска пользуется человек или компьютер.
Организация набора данных
Относительно первого пункта могут быть две ситуации: либо данные никак не организованы (такую ситуацию иногда называют «кучей»), либо данные структурированы.
Под словами «данные структурированы» понимается наличие какой-то упорядоченности данных в их хранилище: в словаре, в расписании, в компьютерной базе данных.
Говоря о системах в § 5, мы выделяли важнейшее свойство всякой системы — наличие структуры. Это свойство присуще как материальным системам, так и информационным системам. Названные выше примеры хранилищ информации, а также архивы, библиотеки, каталоги, журналы успеваемости учащихся и многие другие являются системами данных с определенной структурой.
Структурированные системы данных, хранящиеся на каких-либо носителях, будем называть структурами данных.
Однако бывает и так, что хранимая информация не систематизирована. Представьте себе, что вы записывали адреса и телефоны своих знакомых в записную книжку без алфавитного индекса («лесенки» из букв по краям листов). Записи вели в порядке поступления, а не в алфавитном порядке. А теперь вам нужно найти телефон определенного человека. Что остается делать? Просматривать всю книжку подряд, пока не попадется нужная запись! Хорошо, если повезет и запись окажется в начале книжки. А если в конце? И тут вы поймете, что книжка с алфавитом гораздо удобнее.
Последовательный поиск
Ситуацию, описанную выше, назовем поиском в неструктурированном наборе. Разумный алгоритм для такого поиска остается один: последовательный перебор всех элементов множества до нахождения нужного. Конечно, можно просматривать множество в случайном порядке (методом случайного перебора), но это может оказаться еще хуже, поскольку неизбежны повторные просмотры одних и тех же элементов, что только увеличит время поиска.
Опишем алгоритм поиска методом последовательного перебора. Для описания алгоритма воспользуемся известным вам способом блок-схем (рис. 2.7).
Алгоритм поиска последовательным перебором
В алгоритме учтем два возможных варианта результата: 1) искомые данные найдены; и 2) искомые данные не найдены. Результаты поиска нередко оказываются отрицательными, если в наборе нет искомых данных.
Символика блок-схем должна быть вам понятна. Из схемы видно, что если искомый элемент найден, то поиск может закончиться до окончания просмотра всего набора данных. Если же элемент не обнаружен, то поиск закончится только после просмотра всего набора данных.
Зададимся вопросом: какое среднее число просмотров приходится выполнять при использовании метода последовательного перебора? Есть два крайних частных случая:
 - Искомый элемент оказался первым среди просматриваемых. Тогда просмотр всего один.
 - Искомый элемент оказался последним в порядке перебора. Тогда число просмотров равно N, где N — размер набора данных. То же будет, если элемент вообще не найден.
Всякие средние величины принято определять по большому числу проведенных опытов. На этом принципе основана целая наука по,д; названием математическая статистика. Нетрудно понять, что если число опытов (поисков) будет очень большим, то среднее число просмотров во всех этих опытах окажется приблизительно равным N/2. Эта величина определяет длительность поиска — главную характеристику процесса поиска.
Поиск половинным делением
Возьмем для примера игру в угадывание целого числа в определенном диапазоне. Например, от 1 до 128. Один играющий загадывает число, второй пытается его угадать, задавая вопросы, на которые ответом может быть «да» или «нет». Ключом поиска в этом случае является число, а критерием поиска — совпадение числа, задуманного первым игроком, с числом, называемым вторым игроком.
Если вопросы задавать такие: «Число равно единице?». Ответ: «Нет». Вопрос: «Число равно двум?» и т. д., то это будет последовательный перебор. Среднее число вопросов при многократном повторении игры с загадыванием разных чисел из данного диапазона будет равно 128/2 = 64.
Однако поиск можно осуществить гораздо быстрее, если учесть упорядоченность натурального ряда чисел, благодаря чему между числами действуют отношения больше/меньше. С подобной ситуацией мы с вами уже встречались в § 4, говоря об измерении информации. Там обсуждался способ угадывания одного значения из четырех (пример с оценками за экзамен) и одного из восьми (пример с книжными полками). Применявшийся метод поиска называется методом половинного деления. Согласно этому методу, вопросы надо задавать так, чтобы каждый ответ уменьшал число неизвестных в два раза.
Так же надо искать и одно число из 128. Первый вопрос: «Число меньше 65?» — «Да!» — «Число больше 32?» — «Нет!» и т. д. Любое число угадывается максимум за 7 вопросов. Это связано с тем, что 128 = 2'. Снова работает главная формула информатики.
Метод половинного деления для упорядоченного набора данных работает гораздо быстрее (в среднем), чем метод последовательного перебора.
На рис. 2.8 наглядно показан процесс поиска (угадывания) числа «3» из диапазона целых чисел от 1 до 8.
Выполнение поиски половинным делением
Если максимальное число диапазона N не равно целой степени двойки, то оптимальное количество вопросов не будет постоянной величиной, а будет равно одному из двух значений: X или Х+1, где
2х < N < 2x+1.
Например, если число ищется в диапазоне от 1 до 7, то его можно угадать за 2 или 3 вопроса, поскольку
22 < 7 < 23.
Число из диапазона от 1 до 200 можно угадать за 7 или 8 вопросов, поскольку
27 < 200 < 28.
Проверьте эти утверждения экспериментально.
Половинным делением можно искать, например, нужную страницу в толстой книге: открыть книгу посередине, понять, в какой из половин находится искомая страница. Затем открыть середину этой половины и т. д.
Набор данных может быть упорядочен не только по числовому ключу. Другой вариант упорядочения — по алфавиту. Половинным делением можно осуществлять поиск в орфографическом словаре или в словаре переводов слов с иностранного языка.
Блочный поиск
Снова вспомним пример с записной книжкой. Пусть в вашей записной книжке имеется алфавитный индекс в виде вырезанной «лесенки» или в виде букв вверху страницы. Несколько страниц, помеченных одной буквой, назовем блоком. Имеется блок «А», блок «Б» и т. д. до блока «Я».
Индекс — это часть ключа поиска (например, первая буква).
Записи телефонов и адресов расставлялись в записной книжке по блокам в соответствии с первой буквой. Однако внутри блока записи не упорядочены в алфавитном порядке следующих букв, как это делается в словарях и энциклопедиях. Записи в книжке мы ведем в порядке поступления. При такой организации данных поиск нужного телефона будет происходить блочно-последовательным методом:
1) с помощью алфавитного индекса выбирается блок с нужной буквой;
2) внутри блока поиск производится путем последовательного перебора.
Большинство книг в начале или в конце текста содержат оглавления:
список названий разделов с указанием страниц, с которых они начинаются. Разделы — это те же блоки. Поиск нужной информации в книге начинается с просмотра оглавления, с дальнейшим переходом к нужному разделу, который затем просматривается последовательно. Очевидно, это тот же блочно-последовательный метод поиска.
Списки с указанием на блоки данных называются списками указателей.
Разбиение данных на блоки может быть многоуровневым. В толстых словарях блок на букву «А» разбивается, например, на блоки по второй букве: блок от «АБ» до «АЖ», следующий от «АЗ» до «АН» и т. д. Такой порядок называется лексикографическим.
В поисковом множестве с многоуровневой блочной структурой происходит поиск методом спуска: сначала отыскивается нужный блок первого уровня, затем второго и т. д. Внутри блока последнего уровня может происходить либо последовательный поиск (если данных в нем относительно немного), либо оптимизированный поиск типа половинного деления. Поиску методом спуска часто помогают многоуровневые списки указателей.
Поиск в иерархической структуре данных
Многоуровневые блочные структуры хранения данных называются иерархическими структурами. По такому принципу организовано хранение файлов в файловой системе компьютера. То, что мы называли выше блоками, в файловой системе называется каталогами или папками, а графическое изображение структуры блоков-папок называется деревом каталогов. Пример отображения на экране компьютера дерева каталогов показан на рис. 2.9.
Дерево каталогов
Чтобы найти файл, нужно знать путь к файлу по дереву каталогов. Операционная система поможет найти запрашиваемый вами файл по команде Поиск. Результат поиска представляется в виде пути к файлу, начиная от корневого каталога последовательно по уровням дерева до каталога (папки), непосредственно содержащего ваш файл. Например, при поиске файла с именем ke.exe будет выдан следующий ответ:
E:\GAME\GAMES\ARCON\ke.exe
Здесь указан полный путь к файлу на логическом диске Е: от корневого каталога до самого файла. Имея такую подсказку, вы легко отыщете нужный файл на диске методом спуска по дереву каталогов. Каталог иерархической структуры файловой системы компьютера является многоуровневым списком указателей.
Система основных понятий

Поиск данных

Атрибуты поиска

Набор данных - вся совокупность данных, среди которых осуще­ствляется поиск

Ключ поиска - поле записи, по значе­нию которого проис­ходит поиск

Критерий поиска - условие, которому должно удовлетворять значение клю­ча поиска в искомой записи

Организация набора данных4

Неструктуриро­ванный набор

Структура данных

Линейная упорядочен­ность по ключу

Блочная

одноуровневая

структура

Блочная многоуровне­вая (иерархическая) структура

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

Случайный

перебор.

Последовательный

перебор

Поиск

половинным

делением

Блочно-последова­тельный поиск. Использование индексов и списков указателей

Поиск методом спуска по дереву. Использование многоуровневых спис­ков указателей

Поиск данных

Атрибуты поиска

Набор данных - вся совокупность данных, среди которых осуще­ствляется поиск

Ключ поиска - поле записи, по значе­нию которого проис­ходит поиск

Критерий поиска - условие, которому должно удовлетворять значение клю­ча поиска в искомой записи

Организация набора данных4

Неструктуриро­ванный набор

Структура данных

Линейная упорядочен­ность по ключу

Блочная

одноуровневая

структура

Блочная многоуровне­вая (иерархическая) структура

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

Случайный

перебор.

Последовательный

перебор

Поиск

половинным

делением

Блочно-последова­тельный поиск. Использование индексов и списков указателей

Поиск методом спуска по дереву. Использование многоуровневых спис­ков указателей