Главная | Обратная связь | Поможем написать вашу работу!

Задача поиска на множестве

Задача поиска

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

[Д.Кнут Искусство программирования для ЭВМ, Сортировка и поиск]

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

Задачу поиска можно сформулировать следующим образом:

Заданы два конечных множества и . Для каждого необходимо определить ? называется исходным множеством, называется множеством запросов, а каждый элемент этого множества - запросом. Через обозначим множество непустых слов в алфавите . Любое слово из задает определенную последовательность запросов, каждый из которых применяется к элементам множества . Данная задача представляет собой пример массовой задачи, в которой многократно повторяются однотипные действия. В таком виде постановка задачи выглядит достаточно общей и нуждается в уточнении.

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

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

а) статический поиск: множество фиксировано и не изменяется в течение выполнения серии запросов. Этой задаче отвечает АТД (,НАЙТИ)

б) динамический поиск: множество может обновляться между двумя соседними запросами (разрешены операции, изменяющие множество ). Как упоминалось ранее, множество с операциями НАЙТИ, ВСТАВИТЬ, УДАЛИТЬ образует АТД «Словарь». Другими вариантами АТД являются «Непересекающиеся множества» - (, ОБЪЕДИНИТЬ, НАЙТИ) или «Очередь с приоритетами» - (, НАЙТИ, ВСТАВИТЬ, МИН, УДАЛИТЬ, СЦЕПИТЬ, РАСЦЕПИТЬ) и т.д.

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

Очевидно, сопоставление элемента с элементом из множества подразумевает существование некоторого предиката , позволяющего отождествлять (различать, сравнивать по величине) эти элементы. Предикат предполагает, что имеется определенная логическая связь между элементами и , причем при вычислении значения предиката может быть использована только определенная часть информации, которая хранится в элементах множеств и . Совокупность параметров элементов множества , которые непосредственно участвуют в вычислении предиката, называется ключом. Ключ представляет совокупность полей элементов множества , позволяющих идентифицировать каждый элемент множества. Без ограничения общности, в дальнейшем, предполагается уникальность ключа[2]. Поскольку в решении задачи поиска важны именно ключевые параметры, можно абстрагироваться от остальных параметров[3] и без ограничения общности считать все параметры, описывающие элементы множества ключевыми. Значение предиката должно информировать об успешности поиска. Формула, описывающий предикат, может иметь достаточно сложную структуру. Поскольку сложность вычисления предиката мало зависит от структуры множества мы ограничимся, в дальнейшем, предикатами, которые характеризуют совпадение/несовпадение () ключей или предикатами, которые дают сравнительную информацию о величине ключа (<,=, >)
Ввиду того, что последовательность запросов предполагает многократное обращение к одним и тем же данным, то возникает проблема организации данных для ускорения процедуры поиска. Процесс создания таких структур носит название предобработки данных. И хотя предобработка может занимать определенное количество времени, время, затраченное на создание структуры, с лихвой окупается при многократном повторении запросов. Типичным примером предобработки данных может служить сортировка. Построение эффективного алгоритма сводится к нахождению «хороших» структур данных, которые бы обеспечили хорошую скорость поиска. Безусловно, созданные структуры должны поддерживаться при изменении состава данных.

Задача поиска на множестве

В дальнейшем, задачу поиска будем описывать тройками . Если элементы множества расположены в памяти компьютера в некотором адресном пространстве, то наиболее напрашивающимся подходом к поиску представляется подбор функции , позволяющей преобразовывать пространство ключей в адресное пространство. Однако в общем случае нахождение хорошей функции представляет непростую задачу, и подобные задачи имеют решение в частных случаях, когда число ключей относительно невелико. Такой подход, названный поиском с использованием индексации по ключам, рассмотрен в [3]. В случае, когда множество значений ключей заранее неизвестно или велико, приходится использовать другие модели поиска, и устанавливать связи между значением ключа и адресом другими методами. Рассмотрим различные подходы к решению задачи поиска в зависимости от имеющейся информации о множестве :

Последовательный поиск: Предположим, что нет никакой информации, о структуре множества . Любая процедура поиска предполагает сравнение элемента с элементами множества . Результатом сравнения может быть совпадение элементов, которое означает, что поиск завершен удачно, или отрицательный ответ, который предполагает, что процедура поиска должна быть продолжена. Конечно, значение предиката дает определенную информацию о свойствах элемента . Поскольку в последующем нет возможности использовать эту информацию в случае продолжения поиска, необходимо просматривать в некотором порядке (вообще говоря, случайном) все элементы множества , пока соответствующий элемент не будет найден, или не будет достигнут конец последовательности. В этом случае, естественной структурой данных для представления элементов множества является последовательная структура данных. Ниже представлена функция, которая выполняет поиск элемента с заданным значением ключа в символьном массиве определенной длины:

function Seq_Search(A: DataArray; count:integer; key:DataKey):integer;

var j:integer;

begin

j:=1;

while (j<=count) and (key<>A[j]) j:=j+1;

if j>count then Seq_Search:=0

else Seq_Search:=j;

end; { конец последовательного поиска }

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

При последовательном поиске в среднем проверяются n/2 элементов множества . В лучшем случае будет проверяться только один элемент, а в худшем - будут проверяться все n элементов. Следовательно, временная сложность алгоритма для поиска одного элемента из в худшем и среднем случае равна [14,т.3], где - число элементов множества .

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

Двоичный поиск. Процедура последовательного поиска исходит из того, что информация, полученная на предыдущих шагах алгоритма, теряется и не используется в дальнейшем. Предположим, что на элементах множества задан линейный порядок и предикат может возвращать значения «меньше», «равно» и «больше»[4]. Поскольку отношение частичного порядка “ ” обладает свойством транзитивности, то элемент после выполнения операции сравнения с элементом , содержит информацию о части множества , связанного с элементом отношением порядка. Эта информация при соответствующей организации множества может значительно ускорить процедуру поиска. Легче всего это утверждение можно продемонстрировать на следующем примере: Пусть последовательный поиск ведется в упорядоченном (по возрастанию элементов) множестве. В этом случае, время поиска может быть сокращено за счет того, что для проверки условия в общем случае нет необходимости просматривать все элементы из . Достаточно просмотреть только часть последовательности, состоящую из элементов, меньших , пока не встретится первый элемент, больший . Однако, несмотря на такое усовершенствование, асимптотические оценки для худшего и среднего случаев остаются линейными.

Попробуем оценить время выполнения функции поиска в худшем случае с информационной точки зрения. Поскольку значение “=” предиката означает успешное завершение поиска, то информация необходимая для продолжения поиска может быть извлечена при значениях “<” или “>”. При выполнении последовательности из операций сравнения эта информация может быть записана в виде двоичного набора , где кодирует результат -го сравнения, . Тогда из мощностных (энтропийных) соображений имеем оценку

которая и является оценкой снизу числа шагов алгоритма для худшего случая.

При построении алгоритма поиска необходимо обратить внимание, что задачу можно свести к более простым задачам (подзадачам) поиска объекта на подмножествах множества с последующим объединением результатов поиска (метод «Разделяй и властвуй»). При этом, естественно полагать, что эти подмножества не должны иметь общих элементов, поскольку для элементов, входящих в пересечение мы получим избыточное представление информации, и шаги по извлечению этой информации увеличат сложность работы алгоритма. В частности, возможные значения предиката наводят на мысль разбить множество на подмножество элементов меньших , сам элемент и подмножество элементов больших с последующим поиском в соответствующем подмножестве. Если рекурсивно повторять этот процесс, то через определенное число шагов можно получить интересующий нас ответ. Реализация такого подхода требует указания, как выбирать элемент , относительно которого строится разбиение. Рассмотрим этот вопрос подробнее. Пусть на первом шаге наш алгоритм делит множество на два подмножества и , число элементов в которых соответственно равно и , . Обозначим через - максимальное число обращений к предикату алгоритма поиска на множестве из элементов. Если по результатам сравнения необходимо продолжать поиск в множестве или в множестве , то справедливы соотношения и . Появление в оценке функции говорит о том, что оптимальная оценка (минимизирующая время работы для худшего случая) получается при выравнивании значений ее аргументов (минимизации разности ). Поэтому, с позиций оптимизации времени поиска достаточно на каждом шаге делить на примерно равные по мощности подмножества и . Таким образом, мы приходим к методу поиска делением пополам, который называется «дихотомией». Полностью алгоритм двоичного поиска может быть описан следующим образом:

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

Выбор конкретной структуры данных, обеспечивающей реализацию алгоритма двоичного поиска, зависит от АТД. Поскольку при реализации процедуры поиска необходимо быстро уметь искать медиану, то в случае АТД (,НАЙТИ) для представления множества подходит структура, обеспечивающая прямой доступ к элементам . Такой структурой данных является массив.

Предположим, что элементы множества перечислены в массиве согласно отношению линейного порядка. Рассмотрим реализацию двоичного поиска для этого случая:

function BinarySearch (A: DataArray; count:integer; key:DataKey):integer;

var low, high, med: integer;

found:boolean;

begin

low:=1; high:=count;

found:=false; // не найден

while (low<=high) and (not found) do

begin

med:=(low+high) div 2;

if key<A[med] then high:=med-1

else if key>A[med] then low:=med+1

else found:=true; // найден

end;

if found then BinarySearch:=med

else BinarySearch:=0; // не найден

end; { конец поиска }

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

При реализации такой стратегии поиска существенным образом используется линейный порядок на элементах множества . В случае отсутствия такого порядка, можно его ввести, отобразив в некоторое линейно упорядоченное множество [5] с последующей заменой поиска в поиском в . Для этого необходимо найти кодирующую биективную функцию , и вместо вычисления предиката на элементах из рассматривать предикат . Например, пусть множество представляет собой множество ортонормированных векторов в -мерном Евклидовом пространстве. Понятно, что два любых элемента из несравнимы между собой. Отобразим вектор , с единицей в -ой позиции в число . Тогда множество чисел является линейно упорядоченным и для поиска соответствующего элемента базиса можно применить стратегию двоичного поиска. Безусловно при таком подходе необходимо учитывать затраты на вычисление значений функции .

12 3 4 5 6 7 8 9 10 Следующая ⇒