"Научная Сеть: Алгоритмы и структуры данных"

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

В качестве хранилища метаданных мы используем свободно-распространяемую базу 
данных PostgreSQL (http://www.postgresql.org), в разработке которой авторы
принимают непосредственное участие. Выбор этой базы был обусловлен не 
только личными симпатиями, но и опытом работы под большими нагрузками в 
новостном проекте "Рамблер". Кроме того, в архитектуре PostgreSQL были заложены
прогрессивные идеи, такие как расширяемость, нашедшие развитие в коммерческих 
базах данных ( например Informix, Illustra ). Начавшись как 
научный  академический проект в Беркли и служивший "полигоном" для проверки
многих идей, в 1995 году он был передан сообществу для дальнейшего развития.
Именно архитектура PostgreSQL позволила авторам решить много проблем, связанных
с необходимостью введения новых типов данных,быстрых методов доступа 
и специализированных запросов. Авторы являются разработчиками 
обобщенного поискового дерева (GiST), входящего в ядро PostgreSQL,
которое дает возможность специалистам в конкретной области знаний создавать
специализированные типы данных и обеспечивает индексный доступ к ним не будучи
экспертами в области баз данных. Информация по GiST, исходные тексты,
ссылки на статьи и история развития доступны на страничке авторов по адресу 
http://www.sai.msu.su/~megera/postgres/gist/. 

GiST представляет собой
сбалансированное (по высоте) дерево, листья которого содержат 
пары (key, rid), где key - ключ, а rid - указатель на соответствующую запись
на странице данных. Внутренние узлы содержат пары (p,ptr), где p - это некий
предикат (используется как поисковый ключ), выполняющийся для *всех* наследных
узлов, а ptr - указатель на другой узел в дереве. Для этого дерева определены
базовые методы SEARCH, INSERT, DELETE, и интерфейс для написания  6-ти
пользовательских методов, которыми можно управлять работой этих (базовых
методов). Метод SEARCH управляется функцией Consistent,
возвращающая 'true', если узел удовлетворяет предикату, метод INSERT - 
функциями penalty, picksplit и union, которые позволяют оценить сложность
операции вставки в узел, разделить узел при переполнении и перестроить дерево
при необходимости, метод DELETE находит лист дерева, содержащий ключ,
удаляет пару (key, rid) и, если нужно, с помощью функции union подстраивает
родительские узлы. Дополнительные функции compress, decompress используются
для оптимизации хранения ключей. Реализации стандартных деревьев,
используемых в базах данных (B+-tree и R-tree), с помощью GiST доступны
в contrib директории дистрибутива PostgreSQL, начиная с версии 7.1. Интересно, 
что производительность по сравнению со встроенными деревьями 
практически не изменилась, в то время как затраты на память и построение R-tree
сильно уменьшились. Кроме того, в R-tree мы использовали новый, более 
оптимальный, алгоритм разделения узлов (C.H.Ang and T.C.Tan). 

Для работы со множествами мы разработали новый модуль intarray, 
обеспечивающий индексный доступ к целочисленным массивам. 
Это позволило
эффективно работать с метаданными, поддерживающие множественные значения.
Например, все статьи в НС рубрицируются по разделам знаний. Часто возникает
необходимость построения списка документов принадлежащих определенным
рубрикам. При этом, стандартный путь ( операторы OR,IN,EXISTS )
является неэффективным и трудно поддается оптимизации.
С помощью типа intarray задача решается следующим способом:

  create table message (mid int not null,sections int[]);

  -- create indices
  CREATE INDEX message_rdtree_idx on message using gist ( sections gist__int_ops);

  -- select some messages with section in 1 OR 2 - OVERLAP operator
  select message.mid from message where message.sections && '{1,2}';  

  -- select messages contains in sections 1 AND 2 - CONTAINS operator
  select message.mid from message where message.sections @ '{1,2}';
  -- the same, CONTAINED operator
  select message.mid from message where '{1,2}' ~ message.sections;

Эксперименты показали существенное ускорение выполнения запроса (на порядок
и более). Отметим, что в данном случае ключами являются так называемые 
наложенные сигнатуры (superimposed signatures), помещенные в RD-tree,
которое реализовано с помощью GiST. Идея использования сигнатур восходит к 
Блюмовским фильтрам (Bloom filters), которые представляют множество как 
битовый массив (изначально все биты равны 0), используя хеширование каждого 
элемента множества в некоторое число бит (соотв. биты становятся равным 1).
Для поискового запроса аналогичным образом создается битовый массив и 
сравнивается совпадение *всех* битов, имеющих значение 1. Если имеется хотя
бы одно несовпадение, то ответ *точно* отрицательный. Это позволяет эффективно
отбирать кандидатов для точной проверки, которая необходима из-за использования
хеширования (некоторые биты могут быть использованы несколько раз). 
Эти сигнатуры хранятся в RD-tree (russian doll), при этом выполнятся
условие иерархичности предикатов, необходимое для GiST. Т.е. сигнатура
родительского узла является объединением (union) всех сигнатур наследных узлов.
Битовые операции, используемые для построения и сравнения сигнатур, обычно
поддерживаются на аппаратном уровне. Компрессия массивов в битовый массив 
позволяет оптимизировать затраты на хранение. Основными характеристиками
такого подхода являются кол-во уникальных элементов, длина сигнатуры и 
кол-во бит, в которые хешируются элементы массива. 

Этот тип нашел применение во многих приложениях, например для организации
полнотекстового поиска. В виду ограниченности объема тезисов мы опишем
только идею (исходные тексты и документация доступны на сайте
http://openfts.sourceforge.net).
Рассмотрим документ как массив целых чисел, полученных хешированием
слов. Используя, тип intarray можно эффективно искать все документы, 
содержащие поисковые слова (которые также хешируются в целочисленный массив).
Полнотекстовый поиск, который реализован на уровне базы данных является,
на наш взгляд, примечательной особенностью нашей технологии, так как
имея доступ к метаданным системы, можно задавать очень сложные запросы,
например: найти все статьи, которые содержат поисковый запрос, но при этом
разрешены к публикации и относящиеся к определенным категории знаний.
При этом используются метаданные - статус статьи и рубрики, к которым она
относится. Кроме того, этот тип данных, а следовательно и поиск, поддерживают
инкрементальность, что также очень важно для информационных систем.
Практически это означает, что любой документ, попавший в нашу систему,
будет *мгновенно* доступен для поиска. Таким образом, мы имеем полнотекстовый
поиск с поддержкой метаданных системы и инкрементальности. Это сильно
отличает его от других поисковых машин, которые индексируют статические
коллекции и использующие стандартный подход обратных индексов
(для тематических поисков по внешним коллекциям документов мы используем
 подобного типа поисковую машину. Подробнее об этом в другом докладе).

Идея использования сигнатур для полнотекстового поиска и желание его полной
интеграции с базой данных привела нас к созданию нового типа данных 
txtidx, доступный как модуль contrib/tsearch. Новая версия OpenFTS,
доступная из CVS на сайте openfts.sourceforge.net, нашего полнотекстового 
поиска базируется уже на этом типе. Более подробно о модуле tsearch можно
прочитать в документации к этому модулю. Приведем лишь пример запроса:
  select title from titles where titleidx ## 'patch&gist';
Здесь таблица title содержит колонку title (тип text) и соответствующую ей
колонку titleidx (тип txtidx). Используется индекс по полю titleidx.
Запрос означает - найти все заголовки, содержащие слова 'patch' и 'gist'.
При этом операция ## означает, что будут найдены все формы слов (используется
морфология).

Любой полнотекстовый поиск нуждается в языковой поддержке. Нами были изучены
и реализованы несколько лингвистических алгоритмов. В частности, мы
реализовали поддержку стемминга 
(проект Snowball - http://snowball.sourceforge.net), который очень важен для
научного корпуса документов в виду большого кол-ва специальных терминов,
не присутствующих в словарях, морфологии, построенной на основе свободных 
словарей для широко известной программы ISpell
(http://fmg-www.cs.ucla.edu/geoff/ispell.html). 

Для поддержки иерархических данных нами был разработан модуль 
tree, который позволяет эффективно работать с деревьями. Основная идея 
заключается в том, что узел  представляется в виде пути по дереву от корня.
Путь указывается номером в каждом узле, так что запись '3.4' означает
4-го ребенка 3-го ребенка корня. Таким образом, обычные ресурсоемкие 
рекурсивные методы поиска по дереву, становятся не нужны, так как вся
информация о наследовании доступна в самом пути. Тестовые эксперименты,
которые проводились по данным DMOZ (Open Directory Project, http://dmoz.org),
показали высокую эффективность поиска. Пример запроса:

  Получить всех детей узла
  select * from dmoz where id <* '1.2.3.*.0';

При этом будет использовать индекс, построенный с помощью GiST.
Поддерживаются два типа - bitree (bit tree) и entree (enumerated tree),
отличающиеся максимальным количеством детей (не потомков !) узла, 65535 - для 
entree, и 8,16,32(по умолчанию),64 для bitree ( задается при компиляции).

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

Кратко коснемся проблемы поиска похожих документов и поиска с ошибками.
Для поиска похожих документов нами используется метод представления документа
как последовательность сигнатур (fingerprints) фрагментов текста, полученных 
при  использовании "окна" фиксированной длины. Этот метод был предложен 
Уди Манбером (Udi Manber) и показал высокую эффективность. Вычисление
похожести двух текстов производится путем нахождения 
относительной доли общих для этих текстов фингерпринтов. 
Эта методика малочувствительна к перестановке блоков, к удалению или вставке 
блоков в текст и, следовательно, позволяет обнаруживать переработанные 
тексты. Этот метод может использоваться и как способ нахождения изменчивости
документа (подробнее в другом докладе). Аналогичная методика, но с 
использованием триграм, нами была использована для нечеткого поиска
(поддержка операций над буквами insert, delete, transposition ).
Например, по запросам 'черная дыра', 'дырами черными' в списке ключевых 
найдется  'черная дыра'. Описанные методики реализованы в виде библиотек 
и интерфейсов к PostgreSQL и языку Perl.  

В заключение, авторы выражают благодарность коллективу Научной Сети за
плодотворные обсуждения, РФФИ (РФФИ 99-07-90069, РФФИ 02-07-90222),
и компании "Стек Технологии" за помощь и поддержку.