Методы поиска информации

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

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

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

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

Запрос на поиск, поступающий в АИС, определенным образом формализуется. При этом формируется аргумент поиска.

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

Качество поиска, его эффективность определяются на этапе разработки системы и зависят от того, насколько точно и полно содержание и смысл запроса отражены в аргументе поиска, а смысл документа - в содержании полей записи.

Существуют следующие виды информационного поиска.

Поиск по совпадению. Аргумент поиска содержит наименования одного или нескольких признаков (имена полей записи) и их значения. Критерием выдачи в этом случае является прямое совпадение.

Поиск по интервалу. Аргумент поиска содержит имена одного или нескольких признаков и пределы изменения значений этих признаков. Критерием выдачи здесь является принадлежность заданному интервалу.

Поиск по выражению. Аргумент поиска представляет собой арифметическое или теоретико-множественное выражение или формулу булевой алгебры. Операндами являются имена признаков. В процессе поиска над содержимым соответствующих полей всех записей массива выполняются необходимые операции: либо вычисляются значения выражения, заданного аргументом поиска, либо выполняются теоретико-множественные операции, либо определяется истинность высказывания. Используемые при таком поиске критерии выдачи называются логическими критериями.

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

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

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

Последовательный поиск - единственно возможный в неупорядоченных неструктурированных массивах. Однако следует помнить, что при больших объемах информационных массивов этот поиск будет настолько длительным, что может оказаться совершенно непригодным.

Ускоренные методы поиска. Существенное ускорение процесса поиска возможно в упорядоченных последовательных информационных массивах. К ускоренным методам поиска относятся двоичный и блочный поиски.

Двоичный поиск, или, как его называют, бинарный или дихотомический поиск, является одним из самых быстрых. Первое обращение осуществляется к записи, расположенной в середине массива, упорядоченного по возрастанию значений ключей записей (рис. 2.7.1). После сравнения ключа записи (К) с аргументом поиска (А) определяется, к какой части массива следует обращаться дальше. Если значение ключа записи больше значения аргумента поиска, то следующее обращение осуществляется к записи, расположенной в середине первой части массива. В противном случае обращение происходит к записи, расположенной в середине второй части массива. Указанная процедура повторяется для 1/4, 1/8, 1/16 и т.д. массива до тех пор, пока не будет, найдена искомая запись или не станет пустым интервал, в котором осуществляется поиск.

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

Чтобы найти нужную запись в массиве из N записей, в среднем требуется [log₂ N] - 1 сравнений. В худшем случае понадобится [log₂ N]+1 сравнений.

Блочный поиск состоит в том, что массив, упорядоченный по возрастанию значений ключей записей, разбивается на определенное число блоков. Для поиска потребуется наименьшее время, если число блоков равно . Здесь N - общее число записей в массиве. Число записей в блоке при .

Рис. 2.7.1. Схема двоичного поиска Рис. 2.7.2. Схема блочного поиска

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

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

Для нахождения нужной записи требуется сравнений. В худшем случае понадобится 2сравнений. Худшим окажется тот случай, когда нужная запись оказывается в последнем блоке и занимает в нем первую позицию (при последовательном просмотре этого блока с конца) или последнюю позицию (при последовательном просмотре этого блока с начала). В массиве из 10000 записей при этом потребуется 199 просмотров.

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

Контрольные вопросы

1. Что понимается под сортировкой данных?

2. Приведите пример массива и проведите сортировку его элементов по возрастанию с помощью алгоритма линейного выбора?

3. Приведите пример массива и проведите сортировку его элементов по возрастанию с помощью алгоритма линейного выбора с обменом.?

4. Приведите пример массива и проведите сортировку его элементов по возрастанию с помощью алгоритма стандартного обмена (метод "пузырька")?

5. Приведите пример массива и проведите сортировку его элементов по возрастанию с помощью алгоритма метода просеивания?

6. Приведите пример массива и проведите сортировку его элементов по возрастанию с помощью алгоритма метода Шелла?

7. Составьте алгоритм двоичного поиска и посчитайте число сравнений в нем?

8. Что представляет собой сортировка строк?

9. Какие существуют виды информационного поиска?

Дата добавления: 2014-10-17