Обсуждаются вопросы, связанные с построением пользовательских интерфейсов для навигации по статьям тезаурусов и рубрикаторов в гетерогенных информационных системах. Приводятся некоторые алгоритмы формирования этих интерфейсов с учетом привязки внешних информационных ресурсов к выбранным статьям тезаурусов и рубрикаторов. Основной акцент сделан на динамическую привязку внешних ресурсов на основе текстового поиска по наборам характеристических терминов. Описываются стенд для проведения исследований и результаты исследований на тестовых экспертных наборах данных.
Работа выполнена при поддержке гранта ведущих научных школ НШ-7214.2016.9. 1 Навигация по рубрикаторам и поиск в гетерогенных информационных системах
С развитием технологий построения гетерогенных распределенных информационных систем, включающих в себя множество различных баз данных с различной структурой и содержанием, актуальным становится вопрос поиска информации в базах данных с использованием онтологий, тезаурусов и классификационных схем, представленных в виде отдельных баз данных (БДОТК - базы данных онтологий, тезаурусов и классификаторов).
Существует множество различных способов
построения БДОТК, организации доступа к их
содержимому и реализации явных и неявных связей
между БДОТК и другими гетерогенными
информационными ресурсами. Многие из этих
способов основаны на строгих онтологических
моделях [
Настоящая работа посвящена описанию способов
поиска семантически связанной информации в
распределенных гетерогенных информационных
системах (базах данных) без использования
специализированных технологий семантического
поиска, основанных на моделях Semantic WEB [
Несмотря на привлекательность перспектив
использования технологий Semantic Web для поиска
информации [
Нашу задачу можно сформулировать и так: требуется найти все записи в некотором множестве гетерогенных баз данных, которые бы соответствовали определенной онтологической Рисунок 1 Формирование структуры записи статьи тезауруса с динамическими связями с внешними базами данных сущности (статье тезауруса, рубрике, коду рубрикатора и пр.). Для определенности ниже эту онтологическую сущность мы будем ниже называть статьей тезауруса, понимая, что на ее месте может быть и другое. В качестве решения можно рассматривать алгоритм получения результата, реализованный в виде функционирующего серверного программного модуля для некоторой информационной системы. Эта задача практически полностью эквивалентна задачи навигации по статьям тезауруса, когда для текущей статьи тезауруса отображается информация о связанных с этой статьей записях из выбранного множества в общем случае гетерогенных баз данных. При этом «привязка» связанных записей баз данных к статье тезауруса должна быть динамической, т.е. формироваться в процессе формирования представления собственно статьи тезауруса.
Итак, клиент, используя WEB-браузер может
просматривать тезаурус, перемещаясь по связанным
статьям. Каждая выбранная статья тезауруса должна
быть представлена клиенту в виде некоторой
универсальной структуры, которая может быть
однозначно интерпретирована, т.е. эта структура
должна соответствовать какой-нибудь стандартной
схеме данных, используемой для описания статей
тезауруса. Ниже везде мы будем использовать схему
данных ZThes [
На Рисунке 1 схематично представлен алгоритм работы клиента и сервера при просмотре статьи тезауруса.
Выбор клиентом статьи тезауруса порождает обращение к WEB-серверу, который в свою очередь формирует запрос к серверу баз данных, хранящему информацию о текущем тезаурусе (БД тезауруса). Этот запрос соответствует запросу на поиск записи (статьи) по ее однозначному идентификатору, в результате его выполнения должна быть получена запись БД, соответствующая требуемой статье тезауруса и содержащей полную информацию о ней.
Если клиентом был сформулирован список баз
данных, записи которых следует соотнести с
текущей статьей тезауруса, должен быть включен
механизм формирования запросов к каждой базе
данных из выбранного списка, выполнения этих
запросов на соответствующих серверах БД,
получение ответов и формирование специальных
элементов (postings) в записи статьи тезауруса,
содержащих информацию об именах баз данных и
количестве найденных записей [
<term> . . . <relation>
<termID>31.27.20</termID> Запрос к серверу внешней БД Точки доступа к БД известны? Да Нет Запрос Explain к
серверу БД Получение ответа Анализ точек доступа
для БД Формирование запроса
на количество релевантных записей Запрос на поиск к
серверу БД Получение ответа
SRU SRU SRU SRU Сервер БД (SRW/SRU) Сервер БД (SRW/SRU) Рисунок 2 Формирование и исполнение запроса к внешней базе данных <relationType>RT</relationType> <termQualifier>31.27.20</termQualifier> <termName>Биохимия вирусов</termName> <termLanguage>rus</termLanguage> </relation> <postings> <SourceDB>AB</SourceDB> <hitCount>1022</hitCount> </postings> </term> Несомненно, самым критичным блоком этого алгоритма является блок формирования запросов к серверам внешних БД (на Рисунке 1 это блок обведен пунктиром). Именно от работы этого блока зависит качество динамической привязки записей внешних БД к текущей статье тезауруса. Работа этого блока представлена на Рисунке 2.
Прежде, чем сформировать запрос к серверу внешней БД, необходимо выяснить возможности этой БД в смысле поиска информации, т.е. в терминах SRU (или Z39.50) определить поддерживаемые поисковые атрибуты и варианты их комбинаций. Если отбросить тривиальные и маловероятные конфигурации с фиксированными точками доступа, существует только один регулярный способ – предварительно выполнить запрос explain (SRU, SRW, Z39.50) и проанализировать полученную структуру на предмет выявления поддержки требуемых поисковых атрибутов.
Например, из записи Explain можно сделать вывод, что внешняя база данных поддерживает поисковые атрибуты USE (type 1) 14 (УДК) и 21 (ключевые слова), операция сравнения - «равно» (type 2 = 3), поисковые термы интерпретируются как строки или слова (type 4=1,2,108), поиск возможен как по точному совпадению (type 5=100), так и по усечению справа (type 5=1). Поэтому к этой БД мы можем обращаться с поиском «по ключевым словам» и кодам рубрикатора УДК, т.е. если текущая статья нашего тезауруса (рубрикатора) является описанием рубрики УДК, то запрос к внешней БД должен выглядеть следующим образом (RPN в синтаксисе PQF):
@attr 1=14 @attr 5=1 {term} где вместо «term» должен фигурировать код текущей рубрики. Следует заметить, что здесь запрос сформулирован с усечением справа, т.е. будут найдены все записи, коды УДК которых начинаются с символов «term». Для иерархических рубрикаторов это означает, что к текущей рубрике будут привязаны записи БД, содержащие коды УДК не только текущей, но и всех дочерних рубрик.
В случае тезауруса каждая статья идентифицируется ее заголовком, поэтому поиск во внешних БД следует выполнять по ключевым словам, причем по полному их совпадению:
@attr 1=21 {term} где вместо «term» должен фигурировать заголовок текущей статьи тезауруса.
Строго говоря, такие запросы к внешним БД возможны только тогда, когда 1. Для рубрикаторов: a. для всех внешних БД возможен поиск по
кодам текущего рубрикатора 2. Для тезаурусов: ключевым словам сгенерированы
из текущего тезауруса. a. для всех внешних БД возможен поиск по b. ключевые слова для всех внешних БД заголовков
статей Последнее условие (2b) практически никогда не выполняется, поскольку разработчики той или иной внешней отличающиеся БД могут от использовать
тезаурусы, нашего текущего, или не использовать вообще никакие, выбирая ключевые слова для записей БД в соответствии со своими правилами.
Возникает вопрос - как можно соотносить записи внешних БД с текущей статьей
тезауруса при нарушении приведенных выше условий.
Для рубрикаторов при нарушении условия 1a возможны два варианта: 1. поиск по связанным кодам
других 2. поиск по текстовым характеристикам статьи рубрикаторов рубрикатора 1.1 Поиск по связанным кодам других рубрикаторов
Поиск по связанным кодам других рубрикаторов может быть полезен, когда внешняя
база проиндексирована по этим кодам. Действительно, если внешняя БД не проиндексирована по кодам текущего рубрикатора, например, ГРНТИ, но проиндексирована по кодам УДК, наличие связи между статьей рубрикатора ГРНТИ и статьями УДК позволяет выполнить динамическую
привязку записей из внешней БД не по кодам ГРНТИ, а по кодам УДК. <Zthes> </relation> </term> </Zthes> выше.
Технически динамическая привязка записей из внешней БД осуществляется также, как описано 1.2 Поиск по текстовым характеристикам статьи рубрикатора
Если внешняя БД не проиндексирована по кодам текущего и связанных рубрикаторов, динамическая привязка ее записей к статьям текущего рубрикатора становится задачей нетривиальной.
Действительно, для того чтобы
записи из внешних БД могли быть динамически привязаны к текущей рубрике, необходимо иметь
поисковый образ документов, соответствующих этой рубрике. При этом почти очевидно, что для такого поискового образа практически бесполезна
текстовая информация, которая обычно присутствует в описании статьи рубрикатора (название, описание, названия связанных рубрик и т.п.). Тем не менее, можно придумать схему динамической привязки, основываясь, например, на векторной модели поиска и дополнительной
информации, которой должна быть дополнена каждая статья рубрикатора.
В векторной модели поиска в
качестве поискового образа выступает некоторый уникальный для каждой статьи рубрикатора
вектор, определенный в многомерном
пространстве декартовой системе координат, каждая ось которой соответствуют своему уникальному
термину фиксированного списка терминов, характеризующих данную рубрику (Q1,
Q2, ...,
Qn)
[
Если рассматривать каждую запись внешней
БД как аналогичный вектор в пространстве встречающихся в ней терминов (X1, X2, ..., Xm), то можно говорить о в из скалярном больше это произведении векторов
Q и
X. Чем скалярное произведение, тем
выше релевантность записи
X запросу
Q. Критерием отбора записей может быть выполнение условия 1
( ∙ ) ≥ , ≤ 1 Таким образом, для реализации динамической связи записей из внешних БД со статьей текущего рубрикатора, необходимо: Наличие для каждой статьи
рубрикатора уникального характеристического вектора.
Этот вектор может быть построен только в результате обработки большого количества документов, уже имеющих в результате экспертной оценки коды рубрик текущего рубрикатора. При этом для каждой рубрики должно количество
обработанных быть достаточно большим.
документов Вопрос о достаточной размерности вектора, т.е. о количестве необходимых характеристических терминов зависит от структуры рубрикатора и может быть решен в результате тестов.
Определение параметра s, характеризующего минимально допустимое значение скалярного произведения векторов при поиске может быть произведено в результате тестов.
Наличие возможности серверами БД
обрабатывать поисковые запросы, соответствующие
векторной модели поиска. Это требование как
правило выполняется для поисковых систем,
ориентированных на неструктурированную и
слабоструктурированную информацию. Серверы БД
ориентированы на булеву модель [
В качестве примера рассмотрим характеристический вектор длиной n=4 с терминами a, b, c, d: Q = (a, b, c, d)/4.
Таблица 1 Булевый запрос (& - AND, | - OR) s 1 0,5 0,25
K 0 1 2 3 1 4 a&b&c&d a | b | c | d 2 (a&b&c) | (a&b&d) | (a&c&d) | 0,75
(b&c&d) 3 (a&b) | (a&c) | (a&d) | (b&c) | (b&d)
| (d&c) при этом количество групп, объединенных операторами OR, равно количеству сочетаний из n элементов по k: !/( − )!, причем s = (n − k)/n.
Из приведенного примера видно, что 1. При заданной длине n вектора запроса Q параметр критерия отбора a принимает дискретные значения в интервале (0<s≤1) с шагом 1/n, причем s = (n − k)/n. 2. Каждый булевый запрос для фиксированного s (или k) перекрывает все запросы с большими s (меньшими k). 3. При фиксированном параметре s для поиска необходимо исполнить только один запрос, который содержит !/ ! ( − )! групп по (n-k) термов. При этом количество участвующих в запросе термов равно !/ ! ( − − 1)! . 4. Группы объединяются оператором OR (ИЛИ), термы внутри группы объединяются оператором AND (И).
Наконец, можно сделать некоторое предположение для иерархических рубрикаторов. Если нас интересует запрос для рубрики N.M.L, для которой определен характеристический вектор qNML и соответствующий частный запрос qNML, то действующим запросом для рубрики N.M.L, будет запрос вида
QLMN = QNM & qNML = qN & qNM & qNML где частные запросы qN и qNM соответствуют характеристическим векторам qN и qNM для рубрик N и N.M соответственно.
Таким образом, поиск по текстовым характеристикам статьи рубрикатора возможен и может быть реализован в соответствии с упрощенной векторной моделью поиска конвертированием векторных запросов в булеву форму. 2 Экспериментальный стенд и результаты тестирования
Для проверки качества работы описанного выше механизма поиска во внешних ресурсах по текстовым характеристикам статей рубрикаторов были использованы: 1. База данных «Рубрикатор ГРНТИ», доступ к которой предоставлялся по протоколам Z39.50 и SRU в соответствии со спецификациями Zthes на платформе
ZooSPACE. 2. Специализированная база данных (СБД), содержащая записи РЖ ВИНИТИ (Информатика, Автоматика, Вычислительные науки) с проставленными экспертами ВИНИТИ кодами ГРНТИ для групп кодов: a. 20.*.* - Информатика b. 28.*.* - Кибернетика c. 50.*.* - Автоматика и телемеханика.
Вычислительная техника. по 200 записей для каждого кода. Для упрощения обработки эта БД была загружена в СУБД PostgreSQL с активизацией функций полнотекстового поиска в полях Title, Subject,
Abstract.
3. Для числовых характеристик, описывающих
качество поиска, использовались метрики
[
Найдено Не найдено Полнота: Точность: Ошибка: Релевантный
Не релевантный a c b d = ⁄( + ) p= ⁄( + ) e = ( + )/( + + + ) F-мера: = 2 /( + ) Для каждой рубрики ГРНТИ в указанных выше группах на основании частоты встречаемости терминов в различных записях СБД и выполнения запроса к СБД по этому термину был определен ранжированный по убыванию F список слов из заголовков, ключевых слов и аннотаций для соответствующих записей СБД.
На основе этого списка для каждой рубрики ГРНТИ может быть построен наиболее эффективный 0,4 0,3 а р 0,2 е м ‐ F 0,1
0 0,7 0,6 0,5 0,4 а р е м 0 ‐,3 F 0,2 0,1
0 0,6 0,5 0,4 а р 0,3 е м ‐ F 0,2 0,1 0
F, n=6 F, n=5 F, n=4 F, n=3 F, n=6 F, n=5 F, n=4 F, n=3 F, n=5 F, n=4
F, n=3 по вышеуказанным метрикам характеристический вектор. Мы использовали критерий максимального значения F при варьировании параметров n и s. оптимальных значений n и s в таблице 4 приведены значения метрик. Таблица 3 ГРНТИ 20.23.19 Процессы информационного поиска 28.23.27 Интеллектуальные робототехнические системы 50.11.33 Оптические запоминающие
устройства Таблица 4
Термины поисковый, запрос, поиск,
документ, информационный, пользователь, обработка,
база, … робот, мобильный, движение, алгоритм,
управление, предлагаться, … оптический, дисковод, воспроизведение, носитель, диск, запись, память, … 0 0,2 0,4 0,6 0,8
1 20.23.19
Параметр s 0 0,2 0,4 0,6 0,8
1 28.23.27
Параметр s 0 0,2 0,4 0,6 0,8
1 50.11.33
Параметр s Рисунок 3 Характерная зависимость F от длины характеристического вектора (n) и параметра s для записей с разными кодами ГРНТИ.
В качестве примера приведем ранжированный список терминов для некоторых кодов ГРНТИ. Зависимость F-меры от длины характеристического вектора и параметра s представлена на рисунке 3 для трех кодов ГРНТИ. При этом для наиболее 20.23.19 5 0,8 1 0.360 0,350 0,009 0,355 28.23.27
3 0,667
1 0,508 0,707 0,009 0,591 50.11.33
3 0,667
1 0,430 0,629 0,005 0,511 Таким образом, при наличии СБД можно определить для каждой рубрики: 1. Ранжированный список терминов 2. Длину и содержание характеристического
вектора 3. Оптимальное значение параметра s (или k) На основании этой информации можно построить булевый поисковый запрос по текстовым атрибутам, который наиболее полно будет соответствовать запросу по соответствующему коду рубрикатора. При этом вероятность нахождения нужных записей в найденном таким образом множестве записей предварительно известна и равна значению p.
Например, вместо запроса по коду ГРНТИ 28.23.27 можно выполнять запрос вида (робот & мобильный) | (робот & движение) | (мобильный & движение) Результат выполнения этого запроса будет содержать нужные данные с вероятностью 0,7.
Следует заметить: 1. Описанный механизм привязки внешних ресурсов к кодам рубрикаторов хорошо работает для «грубых» рубрикаторов.
Для иерархических рубрикаторов и рубрикаторов с «родственными» рубриками качество поиска является удовлетворительным. При этом поисковые метрики сильно зависят от длины характеристических векторов и значения критерия отбора. Обе этих характеристики могут быть получены на основе анализа экспертных данных.
В заключение следует заметить, что на основе изложенных выше методов и алгоритмов в настоящее время разрабатываются программные модули для системы ZooSPACE, реализующие графические пользовательские интерфейсы для навигации по тезаурусам и рубрикаторам с привязкой информации из разнородных источников.
Thesaurus navigation and search in the distributed heterogeneous information systems
Oleg L. Zhizhimov, Saya A. Santeeva
The issues related to creation of the user interfaces for navigation through the articles of thesauruses and rubricators in heterogeneous information systems are discussed. The algorithms of formation of these interfaces taking into account a binding of external information resources to the chosen articles of thesauruses and rubricators are given. The main emphasis is placed on a dynamic binding of external resources based on text search in the sets of characteristic terms. The workbench for studies as well as the research results obtained on the testing expert data sets are described.