Рассмотрим модель S-тег, которая предлагается
для использования при реализации семантического
поиска.
Определение. Алфавитом будем называть любое
конечное непустое множество. Элементы этого
множества называются символами данного
алфавита.
Пример. В качестве алфавита может выступать
любой алфавит естественного языка.
Пусть задан некоторый алфавит A.
Определение. Термином алфавита A будем
называть любой упорядоченный конечный непустой
набор символов алфавита A.
Пример. Слова и словосочетания выбранного
алфавита естественного языка являются терминами
этого алфавита.
Пусть задано множество терминов T алфавита A
Определение. S-тегом на множестве T будем
называть любое непустое подмножество T.
Пример. Поисковый запрос, представляющий
собой конъюнкцию слов и словосочетаний,
образованных алфавитом естественного языка A
является S-тегом на множестве T, где множество T
является множеством слов и словосочетаний
естественного языка алфавита A.
Пусть задано множество S-тегов ST.
Пусть ∀t ∈ T задано множество THS𝑡𝑡 ⊂ T.
Определение. Сужениями термина t ∈ T будем
называть множество:
𝑅𝑅𝑡𝑡 = {t} ∪ THS𝑡𝑡.
Пример. Если в качестве терминов рассматривать
слова и словосочетания, то в качестве множества
THS𝑡𝑡 рассмотрим множество синонимов и гипонимов
термина t. Тогда множество 𝑅𝑅𝑡𝑡 представляет собой
множество, состоящее из термина t, его синонимов и
гипонимов.
Определение. Классом термина t ∈ T будем
называть множество:
𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑠𝑠𝑡𝑡 = { st ∈ ST | st ⋂ 𝑅𝑅𝑡𝑡 ≠ ∅ }.
Пример. Если S-тег является поисковым
запросом, как было показано ранее, тогда 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑡𝑡
является множеством поисковых запросов, которые
включают термин t или его синонимы, гипонимы.
Определение. Сужениями S-тега st ∈ ST будем
называть множество:
𝑅𝑅𝑠𝑠𝑡𝑡 = 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑡𝑡.
t ∈ st
Рисунок 1 Отношения терминов, объектов и S-тегов
Пример. Сужениями поискового запроса st
являются более частные или эквивалентные запросы,
которые для каждого термина запроса st содержат
или этот термин или его сужение. Из определения
следует, что сам запрос является своим сужением.
Пусть задано множество объектов O.
∀st ∈ ST задано множество 𝑂𝑂𝑠𝑠𝑡𝑡 ⊂ O.
Определение. Классом S-тега st будем называть
множество:
𝐶𝐶𝑙𝑙𝑎𝑎𝑎𝑎𝑎𝑎 𝑠𝑠𝑡𝑡 = 𝑂𝑂𝑟𝑟𝑠𝑠𝑡𝑡.
rst ∈ 𝑅𝑅𝑠𝑠𝑡𝑡
Пример. В качестве примера множества объектов
O можно рассмотреть тексты книг. Из текста книги
могут быть выделены запросы, которым этот текст
является релевантным. Рассмотрим поисковый
запрос st. Множество 𝑂𝑂𝑠𝑠𝑠𝑠 является множеством
текстов, в которых выделен запрос st. Если текст
является релевантным более частному запросу по
сравнению с st, то он должен быть релевантным
запросу st. Отсюда следует, что 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑠𝑠𝑡𝑡 является
множеством релевантных запросу st текстов книг.
На Рис. 1 представлена визуализация связей
между терминами, S-тегами и объектами. Явно
указано, что объект O3 ∈ 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑆𝑆2. Кроме того,
объекты O1 ∈ 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑆𝑆2 и O2 ∈ 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑆𝑆2, так как S1 ∈
𝑅𝑅𝑆𝑆2. Объект O4 ∉ Class_S2, так как S3 ∉ R_S2. Это
следует из того, что термин T2 и термины из 𝑅𝑅𝑇𝑇2 не
включены в S-тег S3.
Под семантический поиском на базе S-тегов
будем понимать поиск текстов книг, которые
являются релевантными заданному поисковому
запросу, который является S-тегом. Поиск может
считаться семантическим, так как использует
синонимы и гипонимы, позволяющие передать
смысл текста.
Согласно приведенным примерам, задача поиска
релевантных текстов книг по заданному поисковому
запросу на естественном языке сводится к задаче
нахождения 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑠𝑠𝑡𝑡 для заданного S-тега st.
Рассмотрим решение этой задачи.
В первую очередь нужно найти 𝑅𝑅𝑠𝑠𝑡𝑡. Для этого
достаточно найти 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑡𝑡 для каждого термина S-тега
st.
Первый способ определения 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑡𝑡 требует
хранения инвертированного индекса 𝐼𝐼𝐼𝐼𝑆𝑆𝑇𝑇, где
каждому t ∈ T соответствует инвертированный
список S-тегов 𝐼𝐼𝐿𝐿𝑡𝑡: {st | t ∈ st}. В этом случае
поисковоый запрос st должен быть обогащен для
каждого своего термина t терминами из 𝑅𝑅𝑡𝑡:
𝐶𝐶𝑙𝑙𝑙𝑙𝑠𝑠𝑠𝑠𝑡𝑡 = 𝐼𝐼𝐿𝐿𝑟𝑟𝑡𝑡.
rt ∈ 𝑅𝑅𝑡𝑡
Предложенный способ требует дополнительных
затрат на получение ILrt. В случае большого
тезауруса эти затраты могут быть значительными.
Второй способ определения 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑡𝑡 требует
хранения инвертированного индекса 𝐼𝐼𝐼𝐼𝑆𝑆𝑇𝑇, где
каждому t ∈ T соответствует инвертированный
список тегов 𝐼𝐼𝐿𝐿𝑡𝑡 = 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑡𝑡. В этом случае размер 𝐼𝐼𝐼𝐼𝑆𝑆𝑇𝑇
существенно больше, но скорость поиска выше.
Для решения задачи поиска 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑠𝑠𝑡𝑡 необходимо
иметь инвертированный индекс 𝐼𝐼𝐼𝐼𝑂𝑂, где каждому st
∈ ST соответствует инвертированный список
объектов 𝐼𝐼𝐿𝐿𝑠𝑠𝑡𝑡 = 𝑂𝑂𝑠𝑠𝑡𝑡:
𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑠𝑠𝑡𝑡 = 𝐼𝐼𝐿𝐿𝑟𝑟𝑠𝑠𝑡𝑡.
rst ∈ 𝑅𝑅𝑠𝑠𝑡𝑡
Решив задачи нахождения 𝑅𝑅𝑠𝑠𝑡𝑡 и 𝐶𝐶𝑙𝑙𝑎𝑎𝑠𝑠𝑠𝑠𝑠𝑠𝑡𝑡 для S-
тега st, мы получаем решение задачи семантического
поиск текстов книг, которые являются релевантными
заданному поисковому запросу, как S-тегу.