Организация поиска данных — Понятие информационной технологии

ОРГАНИЗАЦИЯ ПОИСКА ДАННЫХ

Записи логического файла идентифицируются с помощью уни­кальной группы символов — ключа. Обычно ключом является поле или совокупность полей фиксированной длины. В общем случае в ка­честве ключа может выступать любое поле записи. Каждому значению ключа может соответствовать одна или несколько записей файла. Ключ, каждому значению которого соответствует одна и только одна запись файла, называется первичным, или основным, ключом. Логиче­ские записи файла могут иметь несколько первичных ключей.

Каждой записи при ее хранении в памяти соответствует вполне определенное место, задаваемое адресом. Способ, задающий соответ­ствие между основным ключом записи и ее адресов памяти, называ­ется способом адресации. Основную проблему при адресации файла можно сформулировать следующим образом: как по основному клю­чу определить местоположение записи с данным ключом? Существу­ет много различных способов адресации файлов, которые можно от­нести к следующим трем основным группам: способы последова­тельной, индексной и прямой адресации. Используются также раз­личные комбинации этих основных способов адресации.

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

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

В зависимости от способов адресации файла могут использовать­ся различные способы локализации (поиска) записи с заданным зна­чением ключа. При последовательной адресации поиск записи может осуществляться только путем просмотра (сканирования) файла с про­веркой ключей записи.

Существует много различных способов поиска записей, например блочный и дихотомический поиск. Наиболее простым способом яв­ляется последовательное сканирование с проверкой ключа каждой записи.

При использовании способов индексной адресации поиск записи осуществляется путем предварительного просмотра индекса. В ре­зультате поиска в индексе сокращается объем просматриваемой па­мяти, занимаемой непосредственно записями файла. Сам индекс и его просмотр могут быть организованы различными способами. Поиск записей файлов, использующих прямую адресацию, осуществляется в соответствии с выбранным алгоритмом преобразования значения ключа записи в ее адрес.

Постановка задачи поиска данных
Во всех компьютерных информационных системах поиск данных является основным видом обработки информации. При выполнении любого поиска данных имеются три составляющие, которые мы назовем атрибутами поиска:
Первый атрибут: набор данных. Это вся совокупность данных, среди которых осуществляется поиск. Элементы набора данных будем называть записями. Запись может состоять из одного или нескольких полей. Например, запись в записной книжке состоит из полей: фамилия, адрес, телефон.
Второй атрибут: ключ поиска. Это то поле записи, по значению которого происходит поиск. Например, поле ФАМИЛИЯ, если мы ищем номер телефона определенного человека.
Третий атрибут: критерий поиска, или условие поиска. Это то условие, которому должно удовлетворять значение ключа поиска в искомой записи. Например, если вы ищете телефон Сидорова, то критерий поиска заключается в совпадении фамилии Сидоров с фамилией, указанной в очередной записи в книжке.
Заметим, что ключей поиска может быть несколько, тогда и критерий поиска будет сложным, учитывающим значения сразу нескольких ключей. Например, если в справочнике имеется несколько записей с фамилией Сидоров, но у них разные имена, то составной критерий поиска будет включать два условия: ФАМИЛИЯ — Сидоров, ИМЯ — Владимир.
Как при «ручном» поиске, так и при автоматизированном важнейшей задачей является сокращение времени поиска. Оно зависит от двух обстоятельств:
1) как организован набор данных в информационном хранилище (в словаре, в справочнике, на дисках компьютера и пр.);
2) каким алгоритмом поиска пользуется человек или компьютер.
Организация набора данных
Относительно первого пункта могут быть две ситуации: либо данные никак не организованы (такую ситуацию иногда называют «кучей»), либо данные структурированы.
Под словами «данные структурированы» понимается наличие какой-то упорядоченности данных в их хранилище: в словаре, в расписании, в компьютерной базе данных.
Важнейшее свойство всякой системы — наличие структуры. Это свойство присуще как материальным системам, так и информационным системам. Названные выше примеры хранилищ информации, а также архивы, библиотеки, каталоги, журналы успеваемости учащихся и многие другие являются системами данных с определенной структурой.
Структурированные системы данных, хранящиеся на каких-либо носителях, будем называть структурами данных.
Однако бывает и так, что хранимая информация не систематизирована. Представьте себе, что вы записывали адреса и телефоны своих знакомых в записную книжку без алфавитного индекса («лесенки» из букв по краям листов). Записи вели в порядке поступления, а не в алфавитном порядке. А теперь вам нужно найти телефон определенного человека. Что остается делать? Просматривать всю книжку подряд, пока не попадется нужная запись! Хорошо, если повезет и запись окажется в начале книжки. А если в конце? И тут вы поймете, что книжка с алфавитом гораздо удобнее.
Последовательный поиск
Ситуацию, описанную выше, назовем поиском в неструктурированном наборе. Разумный алгоритм для такого поиска остается один: последовательный перебор всех элементов множества до нахождения нужного. Конечно, можно просматривать множество в случайном порядке (методом случайного перебора), но это может оказаться еще хуже, поскольку неизбежны повторные просмотры одних и тех же элементов, что только увеличит время поиска.
Опишем алгоритм поиска методом последовательного перебора. Для описания алгоритма воспользуемся известным вам способом блок-схем (рис. 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:GAMEGAMESARCONke.exe
Здесь указан полный путь к файлу на логическом диске Е: от корневого каталога до самого файла. Имея такую подсказку, вы легко отыщете нужный файл на диске методом спуска по дереву каталогов. Каталог иерархической структуры файловой системы компьютера является многоуровневым списком указателей.

Система основных понятий

Поиск данных
Атрибуты поиска
Набор данных — вся совокупность данных, среди которых осуще­ствляется поиск Ключ поиска — поле записи, по значе­нию которого проис­ходит поиск Критерий поиска — условие, которому должно удовлетворять значение клю­ча поиска в искомой записи
Организация набора данных
Неструктуриро­ванный набор Структура данных
Линейная упорядочен­ность по ключу Блочная

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

структура

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

перебор.

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

перебор

Поиск

половинным

делением

Блочно-последова­тельный поиск. Использование индексов и списков указателей Поиск методом спуска по дереву. Использование многоуровневых спис­ков указателей
Поиск данных
Атрибуты поиска
Набор данных — вся совокупность данных, среди которых осуще­ствляется поиск Ключ поиска — поле записи, по значе­нию которого проис­ходит поиск Критерий поиска — условие, которому должно удовлетворять значение клю­ча поиска в искомой записи
Организация набора данных4
Неструктуриро­ванный набор Структура данных
Линейная упорядочен­ность по ключу Блочная

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

структура

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

перебор.

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

перебор

Поиск

половинным

делением

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

 

Популярные статьи

 

БАНКИ ДАННЫХ
ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ УПРАВЛЕНИЯ
ДОСТОИНСТВА И НЕДОСТАТКИ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ
ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ ОБРАБОТКИ ДАННЫХ
ВИДЫ ОБЕСПЕЧЕНИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ 
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ
ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ АВТОМАТИЗАЦИИ ОФИСА
КОМПЛЕКСНОЕ ТЕСТИРОВАНИЕ
КОМПОНЕНТЫ ИНФОРМАЦИОННОЙ ТЕХНОЛОГИИ АВТОМАТИЗАЦИИ ОФИСА
АВТОМАТИЗИРОВАННОЕ РАБОЧЕЕ МЕСТО СПЕЦИАЛИСТА
ЭТАПЫ РАЗВИТИЯ ИНФОРМАТИЗАЦИИ
ПОНЯТИЕ МУНИЦИПАЛЬНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ 
РЕЖИМЫ ОБРАБОТКИ ИНФОРМАЦИИ
ФУНКЦИИ АВТОМАТИЗИРОВАННОЙ ИНФОРМАЦИОННОЙ ТЕХНОЛОГИИ
МЕТОДЫ ОБЕСПЕЧЕНИЯ НАДЕЖНОСТИ ПРОГРАММНЫХ СРЕДСТВ
ПРАВИЛА ЗАЩИТЫ ОТ КОМПЬЮТЕРНЫХ ВИРУСОВ
ДОКУМЕНТАЛЬНЫЕ ИНФОРМАЦИОННЫЕ СИСТЕМЫ
ПРОТОКОЛЫ ТЕСТИРОВАНИЯ
ДЕСТРУКТИВНЫЕ ВОЗМОЖНОСТИ ВИРУСОВ
КЛАССИФИКАЦИЯ АВТОМАТИЗИРОВАННЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
КОНЦЕПТУАЛЬНАЯ, ЛОГИЧЕСКАЯ И ФИЗИЧЕСКАЯ МОДЕЛИ
КОМПЬЮТЕРНЫЕ ТЕХНОЛОГИИ ПОДГОТОВКИ ТЕКСТОВЫХ ДОКУМЕНТОВ
ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ ЭКСПЕРТНЫХ СИСТЕМ
ДИАЛОГОВЫЙ РЕЖИМ АВТОМАТИЗИРОВАННОЙ ОБРАБОТКИ ИНФОРМАЦИИ
ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ КОМПЬЮТЕРНЫХ СЕТЕЙ