Поиск идентичных объектов

В данном разделе мы будем рассматривать задачу поиска идентичных объектов, которая в том или ином виде встречается во всех информационных системах и базах данных. Задача поиска идентичных объектов состоит в поиске в информационном массиве объекта, идентичного объекту-запросу.

Для задачи поиска идентичных объектов в рамках АДВмодели (алгебраическое дерево вычислений) [66] справедлива логарифмическая теоретико-информационная нижняя оценка сложности для худшего случая [70]. Поэтому считается, что бинарный поиск является оптимальным по порядку для задачи поиска идентичных объектов, и это как бы закрывает проблему, но несмотря на это имеется много работ, посвященных исследованию алгоритмов поиска идентичных объектов в худшем случае [7, 71]. Связано это, во-первых, с проблемой поддержки сбалансированности бинарного дерева при операциях вставки и удаления, а во-вторых, с тем, что бинарный поиск хорош только тогда, когда целиком вся библиотека помещается во внутренней памяти (внутренний поиск [23]), если же библиотека вся или частично расположена на внешних носителях (внешний поиск [23]), то эффективность бинарного поиска сразу падает. Также много работ, посвященных изучению алгоритмов поиска идентичных объектов, имеющих хорошие временные характеристики в среднем [17, 77, 80]. Связаны они в основном с методом хеширования, на котором мы остановимся чуть подробнее.

Хеширование предполагает наличие хеш-функции. Хешфункция h (y) определена на множестве записей X и переводит его в множество {1, ттг}, где т — параметр хеш-функции.

Обычно используется два основных метода хеширования. Первый — предложенный А. Думи [77] и называемый методом цепочек, предполагает наличие га списков. Тогда для поступившего запроса х (он же запись) вычисляется значение хешфункции h (x)y и если оно равно г, то просматривается г-ый список и в нем ищется запись х. Если это поиск с занесением, то в случае неудачного поиска запись х добавляется к г-ому списку.

Второй метод хеширования предложен А. П. Ершовым [17] и называется открытой адресацией. Он предполагает наличие закольцованного массива для т записей и наличие понятия пустой записи. После этого для поступившего запроса х вычисляется значение хеш-функции /i (x), и если оно равно г, то просматривается с г-ой позиции массив записей пока запись х будет найдена или пока не встретится пустая запись. Если это поиск с занесением, то в случае неудачного поиска на место встреченной пустой записи помещается запись х.

Методы хеширования хороши тем, что при удачном выборе хеш-функции, равномерно рассеивающей поступающие записи, время поиска в среднем будет очень малым. Вместе с тем Д. Кнут [23, стр. 641−642) усматривает три основных недостатка метода хеширования.

• а) После неудачного поиска мы знаем лишь то, что нужной записи нет, тогда как с помощью бинарного поиска мы обнаруживаем ближайших соседей ненайденной записи, что часто бывает важно во многих приложениях.
• б) Часто довольно трудно распределить память под хеш-таблицу. Если выделить слишком мало, то она может переполниться, и потребуется тягостное «рехеширование «. Если выделить слишком много, то это расточительно.
• в) «Наконец, при использовании методов хеширования нужно свято верить в теорию вероятностей, ибо они эффективны лишь в среднем, а худший случай просто ужасен!» — цитата из Д. Кнута [23, стр. 642]. Поэтому они не всегда подходят для работы в реальном масштабе времени, например, для управления движением транспорта, поскольку на карту постелены человеческие жизни. Алгоритмы, использующие сбалансированные деревья, гораздо безопаснее, ведь они имеют гарантированную верхнюю границу времени поиска.

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

Опишем формально задачу поиска идентичных объектов.

Пусть нам дано множество Х_у на котором задано отношение линейного порядка X, то есть такое бинарное отношение на X х X, которое для любых х_уу_у z 6 X удовлетворяет условиям.

Рассмотрим следующий тип задач поиска Sid = {X_yX_ypid)_y где отношение поиска pid есть отношение идентичности, то есть.

Тип Sid будем называть типом поиска идентичных объектов.