Курсовая работа на тему Исследование архитектур информационно-поисковых систем НИР 1

ОГЛАВЛЕНИЕ


ВВЕДЕНИЕ 2
1 ПОСТАНОВКА ЗАДАЧИ И ОБЗОР АНАЛОГОВ 5
1.1 РАСШИРЕННЫЕ СЕМАНТИЧЕСКИЕ СЕТИ И. П. КУЗНЕЦОВА 5
1.2 НЕОДНОРОДНЫЕ СЕМАНТИЧЕСКИЕ СЕТИ Г. С. ОСИПОВА 8
1.3 ОБОБЩЕННАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ О ПРЕДМЕТНОЙ ОБЛАСТИ А. И. БАШМАКОВА 10
1.4 НЕЧЕТКИЕ СЕМАНТИЧЕСКИЕ СЕТИ И. А. ПЕРМИНОВА 14
2 ОПИСАНИЕ МОДЕЛИ СЕМАНТИЧЕСКОЙ СЕТИ 18
3 РАЗРАБОТКА АЛГОРИТМОВ ПОИСКА В СЕМАНТИЧЕСКОЙ СЕТИ 22
3.1 РАССТОЯНИЕ ЛЕВЕШТЕЙНА 23
3.2 РАССТОЯНИЕ ДАМЕРАУ-ЛЕВЕНШТЕЙНА 24
3.3 АЛГОРИТМЫ НЕЧЕТКОГО ПОИСКА БЕЗ ИНДЕКСАЦИИ (ОНЛАЙН) 25
3.4 АЛГОРИТМЫ НЕЧЕТКОГО ПОИСКА С ИНДЕКСАЦИЕЙ (ОФФЛАЙН) 28
3.5 АЛГОРИТМ РАСШИРЕНИЯ ВЫБОРКИ 29
3.6 МЕТОД N-ГРАММ 31
3.7 ХЕШИРОВАНИЕ ПО СИГНАТУРЕ 33
3.8 BK-ДЕРЕВЬЯ 35
3.9 ТЕСТИРОВАНИЕ 36
3.10 ОРГАНИЗАЦИЯ ПОИСКА В СЕТИ 38
ЗАКЛЮЧЕНИЕ 40
ЛИТЕРАТУРА 44


ВВЕДЕНИЕ
Семантические модели данных представляют собой средство представления структуры предметной области. Такие модели имеют много общего с иерархическими и сетевыми моделями данных, они могут использоваться как средство построения структуры соответствующих баз данных [1].
Семантические модели должны отвечать следующим требованиям:
• обеспечить интегрированное представление о предметной области;
• понятийный аппарат модели должен быть понятен как специалисту предметной области, так и администратору БД;
• модель должна содержать информацию, достаточную для дальнейшего проектирования ЭИС.
Семантические модели данных используют общий набор понятий и отличаются конструкциями, применяемыми для их выражения, полнотой отражения понятий в модели, удобством использования при разработке ЭИС. Как эталон семантической полноты рассматривается естественный язык, а для формализации языковых конструкций в моделях применяется аппарат математической лингвистики [1].
Рассмотрим конструкции естественного языка, декомпозиция которых невозможна без утраты смысла, т. е. высказывания. Структура высказываний оказывается достаточной для выражения закономерностей, присутствующих в предметной области и ЭИС.
Элементами высказываний служат атомарные факты. Способ представления атомарного факта состоит в указании объектов, их взаимодействий и свойств, которые описывают событие, соответствующее атомарному факту, а также указании времени наступления этого события.
Объекты могут быть атомарными и составными. Атомарный объект - это любой объект, разложение которого на другие объекты в рамках данной предметной области не производится. Составные объекты содержат так или иначе организованные множества объектов. Рекурсивно применяя это определение, можно получить произвольную структуру объектов и фактов и рассматривать ее как составной объект. Информация о том, что объект имеет некоторое свойство или несколько объектов взаимосвязаны, представляется в виде высказывания об объекте (или группе объектов).
Существуют правила вывода новых свойств и связей из ранее определенных свойств и связей. Конъюнкция двух свойств является новым свойством. Свойства могут образовывать комбинации и наследоваться через связи [1,2].
Объект может существовать независимо от того, определены или нет свойства и связи, относящиеся к этому объекту. Обязательное свойство, необходимое для определения существующего объекта, - это время его появления и время его исчезновения (как элемента информационных потребностей пользователей ЭИС).
Вступление человечества в XXI век требует перехода к новой стратегии развития общества на основе знаний и высокоэффективных технологий. Соответственно обеспечение эффективности системы образования – одна из важнейших задач. По признанию специалистов в XXI веке в образовании станут решающими именно информационные технологии. Важнейшей составляющей процесса обучения является методически правильное и обоснованное применение современных информационных технологий в учебном процессе. Главная способность компьютера заключается, несомненно, в его пригодности для автоматизированного обучения, интеллектуального управления процессом обучения [2].
С позиций теории управления учебный процесс рассматривается как сложная система, где в роли объекта управления выступает учащийся со своими индивидуальными особенностями. В настоящее время стратегической линией исследования, разработки и внедрения образовательных информационных технологий является их интеллектуализация на основе моделей знаний учебного материала и моделей учебного процесса. Однако общепризнанных моделей и конструктивной теории решения этой проблемы в настоящее время нет, что и определяет актуальность проводимой работы [1].
Для обеспечения информатизации учебного процесса необходимо разработать структуры представления знаний, алгоритмы для решения возникающих противоречий, алгоритмы поиска в семантической сети.
Семантические сети – наиболее мощная модель для представления знаний о предметной области, одно из важнейших направлений искусственного интеллекта. В общем случае под семантической сетью понимается выражение

(1)
где
- множество объектов конкретной предметной области;

- множество отношений между объектами;

- тип отношений.
1 ПОСТАНОВКА ЗАДАЧИ И ОБЗОР АНАЛОГОВ
Разработку модели начнем с формулирования требований к ней со стороны рассматриваемой приметной области. В нашем случае в качестве предметной области выступает модель представления знаний о теории автоматического управления. В качестве основных требований выступают следующие [1].
Способы представления должны описывать все (в данной области) объекты, их свойства и отношения между ними.
Возможность решения возникающих противоречий.
Возможность исключения дублирования информации.
Возможность поиска в семантической сети.
Среди моделей семантических сетей, разработанных в России в последние десятилетия, наибольшую известность получили:
Расширенные семантические сети И. П. Кузнецова,
Неоднородные семантические сети Г. С. Осипова,
Обобщенная модель представления знаний о предметной области А. И. Башмакова,
Нечеткие семантические сети И. А. Перминова.
1.1 РАСШИРЕННЫЕ СЕМАНТИЧЕСКИЕ СЕТИ И. П. КУЗНЕЦОВА
При построении модели (Расширенные семантические сети И. П. Кузнецова) использованы четыре базовых принципа.
Открытый характер многих предметных областей, постоянное расширение круга решаемых в них задач. Это требует расширения функциональных возможностей модели в соответствующем направлении. Подчеркивается, что это целесообразно осуществлять не за счет трудоемкого программирования, а вводом в модель новых декларативных сведений в удобной для человека форме. Они должны автоматически преобразовываться во внутреннее представление [1].
Язык представления знаний должен быть ориентирован на автономную внутрисистемную обработку. Поэтому средства представления знаний должны быть простыми, однотипными, удовлетворять критерию однородности и должны иметь структурную основу. В наибольшей степени этим критериям удовлетворяют семантические сети.
Необходимы унифицированные методики комплексного решения задач ввода и обработки знаний, отличные от логики предикатов, недостаточной для поддержки лингвистической компоненты, организации интерфейса и т.д.
Модель должна поддерживаться соответствующими инструментальными средствами, ориентированными на расширение классов прикладных систем и на конечных пользователей [2].
В соответствии с этими принципами в предложен аппарат расширенных семантических сетей (PCC). Для устранения неоднородности обычных семантических сетей, возникающих с наличием кванторов, совокупностей объектов, связанных отношениями, отношений, связанных между собой отношениями и др., в PCC введены: вершины, соответствующие именам отношений и вершины связи, выполняющие роль «развязывающих» элементов. Вершина связи разрывает дугу сети и подсоединяется одним ребром к вершине-отношению, а другим ребром – к вершинам-объектам.
Множество вершин обозначим через D . Тогда элементарные фрагменты ( ЭФ) PCC представляются в виде:
D0(D1,D2,…,Dk/Dk+1), где D0, D1, D2,…, Dk+1
D, k > 0 (2)
Очевидно, что ЭФ представляет K -местное отношение: D0 – имя отношения; D1,…, Dk - объекты, участвующие в отношении; Dk+1 - обозначает всю совокупность объектов, участвующих в отношении, эта вершина называется с-вершиной ЭФ.
PCC = {ЭФi}, i =
(3)
РСС может представлять наборы отношений, различные ситуации, сценарии. Разные ЭФ обязаны иметь различные с-вершины, выполняющие роль обозначения своего ЭФ [2].
Формально описание РСС имеет вид:

(4)
В РСС И. П. Кузнецова имена отношений играют роль объектов и могут вступать в отношения. Этим определяется высокая однородность модели. С-вершина ЭФ Tk может входить в другие ЭФ, но не в роли с-вершины.
Множество вершин разбито на 3 подмножества D

(5)
где G - распознанные компоненты, X - нераспознанные компоненты, E - специальные вершины.

(6)
где R - имена отношений (соответствуют D0), A - объекты и их классы (понятия), t - true, f - false.
Для представления теоретико-множественных отношений вводятся вершины
. Для представления арифметических выражений - {+,-,*,:} ? R. Для представления логических конструкций -