Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ
Посмотреть оригинал

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

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

Как уже говорилось, для задачи поиска идентичных объектов (как и для задачи о близости) в рамках АДВ-модели справедлива логарифмическая теоретико-информационная нижняя оценка сложности для худшего случая [121]. Поэтому считается, что бинарный поиск является оптимальным по порядку для задачи поиска идентичных объектов, и это как бы закрывает проблему, но несмотря на это имеется много работ, посвященных исследованию алгоритмов поиска идентичных объектов в худшем случае [3, 10, 111, 122, 146, 167, 198]. Связано это, во-первых, с проблемой поддержки сбалансированности бинарного дерева при операциях вставки и удаления, а во-вторых, с тем, что бинарный поиск хорош только тогда, когда целиком вся библиотека помещается во внутренней памяти (внутренний поиск [56]), если же библиотека вся или частично расположена на внешних носителях (внешний поиск [56]), то эффективность бинарного поиска сразу падает. Также много работ, посвященных изучению алгоритмов поиска идентичных объектов, имеющих хорошие временные характеристики в среднем [50, 124, 143, 168, 174, 184, 186, 188, 190, 199, 210]. Связаны они в основном с методом хеширования, на котором мы остановимся чуть подробнее.

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

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

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

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

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

б) Часто довольно трудно распределить память под хеш-таблицу. Если выделить слишком мало, то она может переполниться, и потребуется тягостное “рехеширование”. Если выделить слишком много, то это расточительно.

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

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

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

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

• рефлексивности х < х

• транзитивности (х < у) & (у < z) -Ь (х ?< z)

• антисимметричности (х ?< у) & (у ?< х) —» = у);

• связности (х < у) V ^ х).

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

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

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы