1. Поиск

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

1. Виды информационного поиска

1. Поиск по совпадению

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

3. Поиск по интервалу

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

5. Поиск по выражению

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

2. Методы поиска

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

Метод последовательного перебора (2.а)

Заключается в последовательном просмотре информационного массива и сравнении каждого элемента массива с элементом поиска. Среднее число обращений для информационного массива длины N – N/2, в худшем случае будет осуществлено N обращений. Может применяться для неупорядоченных массивов данных.

6. Двоичный поиск (2.Б)

Текущий элемент сравнивается с аргументом поиска. Если значение аргумента поиска меньше текущего элемента, исходной считается последовательность от первого элемента до элемента с номером N/2, иначе если значение аргумента поиска больше текущего элемента – последовательность от элемента с номером N/2 до N. В целом, осуществляется последовательное деление пополам интервала поиска до тех пор, пока не будет найден искомый элемент или длина последовательности не станет равной единице.

7. Блочный поиск (2.В)

Исходная последовательность разбивается на блоки. Поиск осуществляется за два просмотра. Во время первого просмотра аргумент поиска сравнивается со значениями последних записей блоков. Если не будет получено значение, превосходящее аргумент поиска, результат поиска – отрицательный, иначе осуществляется второй просмотр, который проводится в найденном блоке в направлении от последней к первой записи в блоке. Практика показывает, что N является лучшим количеством блоков для N записей. В среднем требуетсяN сравнений, в худшем случае – 2N сравнений.

8. Поиск по двоичному дереву (2.Г)

Осуществляется в соответствии с принципами, по которым построено дерево поиска (см. п. 1.1.1). Первое обращение производится в корень. Если текущий элемент (из узла дерева, в начале – из корня) меньше аргумента, следующим будет рассматриваться правое поддерево; если текущий элемент больше аргумента, следующим будет рассматриваться левое поддерево; если при попытке осуществить переход по левой или правой обнаруживается, что ссылка отсутствует, результат поиска является отрицательным. Наименьшее число сравнений, требующееся при поиске в двоичном сбалансированном дереве, log₂N.

Хеширование (2.д)

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

9. Многоаспектный поиск с использованием инверсных массивов (2.Е)

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