Программа-минимум кандидатского экзамена по специальности 05.13.17 «Теоретические основы информатики» (стр. 16 из 29)

КОНЦЕПТУАЛЬНОЕ (ЛОГИЧЕСКОЕ) ПРЕДСТАВЛЕНИЕ

Являясь обобщенным представлением структуры данных для всех пользователей. оно чаще всего представляется более сложными иерархическими, древовидными и сетевыми структурами данных.

ВНУТРЕННЕЕ (ФИЗИЧЕСКОЕ) ПРЕДСТАВЛЕНИЕ.

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

Язык определения данных.

План БД определяется набором выражений (дефиниций), написанных на специальном языке, который называется язык определения данных (ЯОД) (data definition language).

Результатом компиляции выражений на ЯОД является набор таблиц, хранящийся в специальном файле, который называется словарь данных (data dictionary). В словаре данных хранятся метаданные, то есть данные о данных.

Разновидностью ЯОД является язык хранения и определения данных (data storage and manipulation language), на котором написаны выражения, определяющие методы доступа к данным и способ хранения структуры.

Язык манипулирования данными

это командный язык, обеспечивающий выполнение основных операций по работе с данными:

извлечение информации, хранящейся в БД;

добавление новой информации в БД;

уничтожение хранящейся в БД информации.

Часть ЯМД, отвечающая за выборку данных, называется языком запросов.

Запрос (query) - выражение, задающее поиск данных в СУБД.

В ранних СУБД поддерживалось несколько специализированных по своим функциям языков. Чаще всего выделялись два языка - язык определения схемы БД (SDL - Schema Definition Language) и язык манипулирования данными (DML - Data Manipulation Language). SDL служил главным образом для определения логической структуры БД, т.е. той структуры БД, какой она представляется пользователям. DML содержал набор операторов манипулирования данными, т.е. операторов, позволяющих заносить данные в БД, удалять, модифицировать или выбирать существующие данные. В современных СУБД обычно поддерживается единый интегрированный язык, содержащий все необходимые средства для работы с БД, начиная от ее создания, и обеспечивающий базовый пользовательский интерфейс. Стандартным языком наиболее распространенных в настоящее время реляционных СУБД является язык SQL (Structured Query Language).

Информационный поиск

процесс нахождения и выдачи определенной заранее заданными признаками информации из массивов и записей любого вида и на любых носителях

История

Термин введён Кельвином Муром в 1948 г.

Изначально информационно-поисковые системы (ИПС) использовались только для поиска научной литературы.

Широкое распространение ИПС получили с появлением сети Интернет.

Виды информационного поиска

библиографический

поиск сведений об источнике и установление его наличия в системе источников

документальный

поиск самих источников

фактографический

поиск фактических сведений (сущностей, обладающих определенными свойствами и свойств заданных сущностей)

аналитический

поиск аналитической информации

комбинированный

Виды информационного поиска

Полнотекстовый поиск

поиск по всему содержимому документа

Поиск по метаданным

поиск по атрибутам документа

(название документа, дата создания, размер, автор)

Поиск по изображению

поиск по содержанию изображения.

Виды информационного поиска

избирательный

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

ретроспективный

по разовым запросам

во всём накопленном массиве текстов

Информационно-поисковая система (ИПС)

- пакет ПО, реализующий процессы создания, актуализации, хранения документов и поиска информации в информационных базах данных

Могут выдавать только такую информацию, которая была ранее введена в них. Этим они отличаются от информационно-логических систем (могут производить логическую переработку информации с целью получения новой информации).

Виды ИПС

Тематические каталоги

Специализированный каталоги

Поисковые машины (Яндекс, Google)

Средства метапоиска (сравнение результатов работы нескольких поисковых машин)

документальные ИПС

информация о содержании документа + информация о самом документе (автор, год ...)

фактографические ИПС

Состав ИПС

Информационно-поисковая система должна включать следующие основные компоненты :

- логико-семантический аппарат (информационно-поисковые языки – ИПЯ, правила индексирования, критерий выдачи);

- поисковый массив (определенное множество снабженных поисковыми образами документов);

- технические средства (приспособления и устройства;

- специалистов, взаимодействующих с системой

Состав ИПС

Подсистема ввода и регистрации документов

помещение в систему, присвоение ID

Подсистема обработки документов

формирование ПОД (поисковый образ документа)

Подсистема поиска

формирование ПОЗ (поисковый образ запроса = поисковое предписание)

отыскание ПОД документов, удовлетворяющих ПОЗ согласно критерию смыслового соответствия

Подсистема хранения

выдача найденных документов пользователю

Модели ИП

Модель ИП включает:

Формат представления документов

Формат представления запросов

Функция соответствия документа и запроса

Модели ИП

Теоретико-множественные

пример: Булева модель

Вероятностные

Алгебраические

пример: Векторная модель

Гибридные

Булевская модель

Матрица документ-термин (d, t)

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

Запрос: q = t1 И (НЕ t3)

Булевская модель: достоинства и недостатки

Достоинства:

- простая, легко понимаемая структура запроса

- простота реализации

Недостатки:

- недостаточно возможностей для описания сложных запросов

- результатов запроса либо слишком много либо слишком мало

- проблематичность при ранжировании результатов

Пока еще распространены в коммерческих ИПС.

Векторная модель

Учитывается, «насколько сильно» входит в документ каждый термин (вес термина).

tf – term frequency

idf – inversed document frequency

N – общее число документов в коллекции

Nk - количество документов в коллекции C, содержащих термин Tk

Векторная модель

Матрица документ-термин (d, t)

Запрос: q= t1 и t4 <1, 0, 0, 1, 0, 0…>

Степень соответствия – близость векторов, представляющих документ и запрос (считается по формуле скалярного произведения векторов).

Векторная модель

Достоинства:

Позволяет оценить степень соответствия документа запросу.

Обладает высокой практической эффективностью.

Удобна при ранжировании документов.

Вероятностная модель

Определяется вероятность того, что данный документ окажется интересным пользователю.

Подразумевается наличие уже существующего первоначального набора релевантных документов. Рассматривается соотношение встречаемости термов в релевантном наборе и в остальной части коллекции.

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

D = <t1, …, tn> ti - {0, 1}

Стратегии поиска

Стратегия поиска – общий план поведения системы или

пользователя для выражения и удовлетворения

информационной потребности пользователя

Примеры:

следует по возможности искать специализированную ИПС по своей теме

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

следует использовать несколько ИПС

Индекс (поисковый массив)

Индекс - система связанных между собой файлов, которая нацелена на быстрый поиск данных по запросу пользователя.

Состоит из

таблицы идентификаторов страниц

таблицы ключевых слов

таблицы заголовков

таблицы гипертекстовых связей

инвертированного списка (ключевое слово - > документы, в которых оно встречается)

прямого списка

таблицы модификации страниц (когда страница изменяется, в таблицу модификации помещается ссылка на новую страницу; когда число таких ссылок становится выше допустимого, необходима перезагрузка индекса)

Информационно-поисковые языки

ИПЯ - формализованный искусственный язык, предназначенный для индексирования документов, информационных запросов и фактов в форме, удобной для автоматического поиска.

Состоит из

- алфавита (списка элементарных символов)

- правил образования (какие комбинации элементарных символов допускаются при построении слов и выражений)

- правил интерпретации (как надлежит понимать эти слова и выражения)

Выражения на ИПЯ допускают только одно истолкование, благодаря чему возможно сравнивать ПОД и ПОЗ формально, не вникая в смысл.

Виды информационно-поисковых языков

классификации (= предкоординированные ИПЯ)

Не позволяют вести поиск по заранее не предусмотренному сочетанию признаков.

Процесс индексирования с помощью классификаций принципиально не автоматизирован.