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

ЗАДАЧИ ПОИСКА С КОРОТКИМ ОТВЕТОМ

Класс задач с коротким ответом — это совокупность задач поиска, в которых ответ на любой запрос содержит ограниченное число записей. Наиболее известными задачами из данного класса являются задача поиска идентичных объектов и задачи о близости.

Некоторые свойства задач поиска с коротким ответом

Результат, описываемый в данном разделе, относится к классу предикатных информационных графов (ПИГ) и в менее полной версии был опубликован в (24]. Напомним, что ПИГ — это такие ИГ, базовое множество которых не содержит переключателей, т. е. ИГ, в которых имеются только предикатные ребра.

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

ИД удобны и интересны тем, что структуры данных, им соответствующие, практичны и их гораздо проще реализовать на ЭВМ. Тогда как ПИГ обладают большими возможностями и охватывают более широкий класс алгоритмов. Поэтому представляет интерес выявление классов задач информационного поиска, для которых оптимальные (т. е. с минимальной сложностью) ПИГ находятся в классе ИД.

Один из таких классов приводится в данном разделе. По сути это такой класс задач поиска, в которых мера множества запросов, содержащих в ответе задачи более с элементов (где с = const), равна 0.

Дадим более строгое определение этого класса ЗИП, в случае когда с = 1.

Пусть нам даны множества запросов X, записей Y и отношение поиска р на X х У. Причем на множестве запросов задано вероятностное пространство (X, сг, Р).

Скажем, что ЗИП I = (X, V, р) обладает А-свойством, если

• для любой записи у € V имеем 0(у,р) € а и P(0(j/,p)) ф 0;

• для любых г/, у'V таких, что у Ф у' Р(0(у, р) П 0(ур)) = 0.

Если п — натуральное число, то скажем, что ЗИП I = у V, р) обладает Вп -свойством:, если для любых п + 1 записи из V пересечение теней этих записей равно пустому множеству.

Класс задач, обладающих A-свойством и Вп-свойством, и будет исследоваться в данном разделе.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы