ПРИМЕНЕНИЕ ПРЯМЫХ И ОБРАТНЫХ ИНДЕКСОВ В ЗАДАЧАХ ПОЛНОТЕКСТОВОГО ПОИСКА

Четвериков Григорий Григорьевич

Черкавский Сергей Викторович


Харьковский национальный университет радиоэлектроники

кафедра программного обеспечения ЭВМ

Харьков, Украина

chtvergg@kture.kharkov.ua, sergii.cherkavskyi@gmail.com


Затрачиваемые ресурсы на полнотекстовый поиск в нереляционных БД во многом зависит от количества обращений к внешней памяти, оптимизация которых обеспечивается схемой построения индекс-файла. Эта задача является обоснованием выбора такой структуры данных как Б-деревья [1]. Отличием Б-деревьев от обычных деревьев заключается в том, что в узле дерева сгруппированы несколько ключей, которые могут быть считаны за одно обращение к памяти, что позволяет уменьшить количество операций обмена на порядок. Такой принцип реализован в GIN и GIST индексах.

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

В случае прямого индекса, которым является GIST, записи отсортированы по номеру документа. Этот номер представляет собой битовую сигнатуру, в которой содержится информация о всех лексемах, присутствующих в этом документе. Следовательно, добавление нового элемента сопровождается добавлением только одной записи в индексе. Поисковый запрос, аналогично документу, преобразовывается в поисковую сигнатуру и поиск происходит ее побитовым сравнением с сигнатурами в узлах дерева. Сравниваются только единичные биты в поисковом запросе. Если имеется хотя бы одно несовпадение, то ответ отрицательный. Это позволяет эффективно отбирать “кандидатов” для последующей проверки. Битовые операции, используемые для построения и сравнения сигнатур, могут быть реализованы на аппаратном уровне с помощью АКП-структур. Данные структуры синтезированы средствами алгебры конечных предикатов [2-4].

Таким образом, тестирование характеристик работы обоих индексов при одинаковой начальной конфигурации [5] показали, что использование GIN индексов целесообразно в БД, нетребующих частого обновления, а скорость поиска является критичным показателем. GIST индексы предпочтительны в системах, где происходят частые обновления и скорость обновления играет основную роль.

ЛИТЕРАТУРА

1. Кнут, Д. Искусство программирования. [Текст] / Д. Кнут. том 3, 1998. . – 623с

2. Шабанов-Кушнаренко, Ю.П. Теория интеллект а. Математические средства. [Текст] / Ю. П. Шабанов-Кушнаренко. – Х.: Высшая шк., 1984. – 144с.

3. Шабанов-Кушнаренко, Ю.П. Приложения теории интеллекта к синтезу комбинационных схем [Текст] : АСУ и приборы автоматики / Ю. П. Шабанов-Кушнаренко, М. Ф. Бондаренко, Г.Г. Четвериков, З.Ю. Шабанова-Кушнаренко. – Х.: Высшая шк., 1980. Вып. 53. – 10-18с.

4. Четвериков, Г.Г. Концепція уніфікації методів та засобів побудови просторових багатозначних структур мовних систем. [Текст] / Г.Г.Четвериков // Науч.- техн. журн. «Бионика Интеллекта». – 2010.– №1(72).– С. 3-11.

5. Бартунов, О. Введение в полнотекстовый поиск в PostgreSQL [Электронный ресурс] / О. Бартунов, Ф. Сигаев. / Режим доступа : http://citforum.ru/database/postgres/fts/2.shtml – Загл. с экрана.