22. Основные принципы информационного поиска

При обработке информации в АИС наиболее часто выполняются операции поиска.

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

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

В случае многоаспектного поиска агумент поиска обычно представляет собой логическое выражение. Операндами формулы такого выражения являются имена полей записей и их значения.

Например, пусть требуется найти записи о студентах группы 222, имеющих средний балл 4,5. Аргумент поиска можно записать в виде формулы:

(ГРУППА = 222)˄(СР.БАЛЛ = 4.5).

Такое выражение может быть истинными или ложным. В информационном массиве выполняется поиск тех записей, для которых выражение является истинным.

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

Существует несколько типов критериев выдачи.

1. Критерий выдачи - по совпадению.

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

2. Критерий выдачи – по интервалу

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

3. Логический критерий выдачи

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

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

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

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

Решения, принятые на этом этапе, определяют скорость выполнения поиска, а, следовательно, и быстродействие всей АИС.

23.Последовательный поиск

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

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

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

Последовательный поиск в массиве из N записей требует в среднем (N+1)/2 сравнений (единица в числитиле появляется при нечетном N). В худшем случае, когда искомая запись окажется последней в массиве или ее не будет там вовсе, потребуется N сравнений.

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