Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ПОШУК ІДЕНТИЧНИХ ОБ'ЄКТІВ

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

Для завдання пошуку ідентичних об'єктів в рамках АДВ- моделі (алгебраїчне дерево обчислень) [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 y X y pid) y де відношення пошуку pid є ставлення ідентичності, тобто

Тип Sid будемо називати типом пошуку ідентичних об'єктів.

 
<<   ЗМІСТ   >>