Полная версия

Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ

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


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Задачи поиска на декартовых произведениях бинарных частично-упорядоченных множеств данных

Среди задач поиска, в которых в качестве отношения поиска выступают отношения частичного порядка, наверное, наиболее распространенными являются задачи включающего поиска.

Приведем наиболее распространенную интерпретацию задачи включающего поиска.

Предположим, что мы осуществляем поиск в дескрипторных автоматизированных информационно-поисковых системах [2, 103, 106), т. е. информационный массив состоит из документов, каждый документ описывается множеством дескрипторов (ключевых слов), запрос задает некоторую совокупность дескрипторов, и необходимо перечислить в информационном массиве все документы, содержащие в своем описании все дескрипторы, входящие в запрос. Занумеруем некоторым образом множество всех дескрипторов (тезаурус). Каждому документу сопоставим запись, представляющую собой булев вектор длины, равной мощности тезауруса, в г-ой компоненте которого стоит 0 (ноль) в том и только в том случае, когда г-ый дескриптор входит в описание данного документа. Запросы будем описывать аналогичными векторами, т. е. в г-ой компоненте запроса будет стоять 0, если г-ый дескриптор входит в запрос. Теперь если в качестве отношения

ь

поиска взять отношение У, определяемое следующим соотношением

то получившаяся задача включающего поиска будет полностью соответствовать исходной. В самом деле, каждая компонента запроса должна быть не меньше соответствующей компоненты записи, или если в г-ой компоненте запроса стоит 0 (т. е. г-ый дескриптор входит в запрос), то в г-ой компоненте записи тоже должен стоять 0 (т. е. запись должна содержать г-ый дескриптор)..

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

Хотя задачи включающего поиска имеют широкое применение, исследование оценок сложности включающего поиска не проводилось.

Для этих задач удалось получить нижнюю оценку в два раза лучшую, чем мощностная нижняя оценка. Кроме того, было доказано существование задач, для которых эта нижняя оценка асимптотически не улучшаема. Эти и некоторые другие результаты приводятся в данном разделе. Эти результаты были опубликованы в работах [19, 29, 31, 35, 36, 41, 158, 159, 163).

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>