Информационные онтологии как способ сжатия информации

Размещено на http://www.allbest.ru/

1

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Ижевский государственный технический университет имени

М. Т. Калашникова»

Кафедра «Автоматизированные системы управления»

КОНТРОЛЬНАЯ РАБОТА

по дисциплине «Математическая лингвистика»

на тему:

«Информационные онтологии как способ сжатия информации»

Выполнил:

Студент гр. Б 04-782-1 Щелыгин А.Н.

Проверил:

Старший преподаватель

кафедры АСУ Кутявина Л.Л.

Глазов 2013 г.

Содержание

Введение

1.Онтология по Груберу

2.Современное понятие компьютерной онтологии

3.Способы сжатия информации

4.Способы сжатия информации на основе компьютерной онтологии

Заключение

Литература

Введение

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

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

Термин «онтология» изначально философский, в информатике он принял самостоятельное значение. Здесь есть два существенных отличия:

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

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

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

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

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

Хотя термин «онтология» сейчас достаточно популярен в программистском сообществе, четкого его понимания еще не сложилось. Знания о том, что такое онтологии, и как их использовать при создании информационных систем, до сих пор являются чем-то эзотерическим, доступным только избранным специалистам по обработке знаний. Другое мнение состоит в том, что онтологии представляют собой нечто абстрактное, неприменимое на практике «игрушечное знание», которым занимаются в своих «отвлеченных сферах» так называемые «crazy scientists». Между тем, термин «онтология» совсем не сложен для понимания и был придуман для достижения вполне практических целей.

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

Термин "онтология" впервые появился в работе Томаса Грубера, в которой рассматривались различные аспекты взаимодействия интеллектуальных систем между собой и с человеком. Интеллектуальными системами называются программы, которые моделируют некоторые аспекты интеллектуальной деятельности человека. Конечно, любая программа занимается таким моделированием в той или иной степени, ведь именно в этом и состоит ценность компьютера для человека - компьютерная система позволяет освободить человека от выполнения какой-то однотипной деятельности. Эта деятельность может быть весьма сложной и изощренной, но она всегда однотипна: компьютерная система, созданная, например, для редактирования графики, не может быть использована для управления комбайнами во время сенокоса. В этом смысле знания, которые закладывает в программу ее создатель, всегда статичны, они не меняются. Интеллектуальная система в этом смысле более универсальна - в ней знание о том, что надо делать в процессе исполнения программы, не вшито в программу раз и навсегда, но может меняться. Если так, то эти знания необходимо передавать программе как данные, т.е. возникает необходимость их описания.

Томас Грубер рассматривал вопросы взаимодействия интеллектуальных систем между собой, а также с человеком. Идея Грубера состояла в том, чтобы позволить интеллектуальным системам обмениваться между собой заложенными в них знаниями о мирах задач. Если внутри интеллектуальной системы знания о мире могут быть закодированы как угодно, то для обмена этими знаниями с другой интеллектуальной системой необходимо предоставить описание этих знаний. Это описание должно быть в достаточной степени формальным, чтобы быть понятным другой системе, а также должен быть известен язык этого описания. Кроме того, описание должно быть понятно также и человеку. Для этого Грубер предложил описывать знания двумя способами:

1. В канонической форме, которая представляет собой описание знаний на языке логики предикатов (например, в виде фактов языка Prolog).

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

Таким образом, онтология по Груберу представляет собой описание декларативных знаний, сделанное в виде классов с отношением иерархии между ними. К этому описанию, предназначенному для чтения человеком, присоединено описание в канонической форме, которое предназначено для чтения машинами. Каждая интеллектуальная система может предоставлять несколько таких описаний, соответствующих различным областям хранящихся в ней декларативных знаний и, таким образом, выступает как хранилище библиотеки онтологий. Грубер представлял, что интеллектуальные системы будут выступать как библиотеки онтологий и свободно обмениваться онтологиями между собой. При этом библиотеке онтологий уже не обязательно быть интеллектуальной системой, достаточно просто предоставлять сервис по передаче онтологий по требованию.

1. Онтология по Грубберу

Термин "онтология" впервые появился в работе Томаса Грубера в 1993 году, в которой рассматривались различные аспекты взаимодействия интеллектуальных систем между собой и с человеком. Интеллектуальными системами называются программы, которые моделируют некоторые аспекты интеллектуальной деятельности человека. Онтология представляет собой описание декларативных знаний, предназначенное для чтения человеком и выполненное в виде классов с отношением иерархии между ними. Составление описания декларативных знаний требует большой работы и определенных навыков. Для обозначения этой работы, а также ее результата, Грубер ввел специальный термин - «концептуализация». Описание он назвал «спецификацией». Таким образом, онтология по Груберу определяется как «спецификация концептуализации».

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

2. Современное понятие компьютерной онтологии

Онтологии используются при разработке программного обеспечения как форма представления знаний о реальном мире или его части. Их применение возможно в рамках модельно-ориентированного подхода для построения платформо-независимой модели.

Введенное Грубером разделение спецификаций знаний на две составляющие (каноническую форму и онтологию) не очень удобно, т.к. приходится описывать одни и те же знания два раза. Современные языки описания онтологий позволяют совместить эти формы спецификаций в единое целое. Таким образом, сейчас под онтологией понимается любое описание декларативных знаний, сделанное на формальном языке и снабженное некоторой классификацией специфицируемых знаний, позволяющей человеку удобно воспринимать их. Каноническая форма не обязательно использует язык логики предикатов, могут использоваться и другие формализмы. Например, можно использовать алгебраический подход к описанию знаний, в котором факты представляются в виде термов, а различные соотношения между фактами - в виде ограничений, налагаемых на вид этих фактов, и выраженных в форме аксиом эквивалентности. Но любое такое описание должно включать в себя представление декларативных знаний в виде иерархии объектов (классов), только в этом случае это описание может считаться онтологией.

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

Для описания онтологий существуют различные языки и системы. Наиболее перспективным является визуальный подход, позволяющий специалистам рисовать онтологии, что помогает наглядно сформулировать и объяснить сущности и их взаимодействие в предметной области. Программы визуализации онтологий являются инструментом, позволяющим сделать видимыми структуры объектов предметной области.

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

Некоторые авторы используют термин «онтология» только для спецификаций знаний о мире, т.е. таких концептуализаций, целью которых является описание структуры Бытия безотносительно какой-либо инженерной задачи. Такой концептуализацией уже давно занимаются философы, и в философии термин «онтология» применяется именно в этом смысле - как спецификация знаний об окружающем мире. Программисты, однако, сталкиваются с иного рода задачами: они проводят концептуализацию с целью построения модели решаемой задачи. Таким образом, философы и программисты преследуют различные цели, когда проводят концептуализацию: первые имеют целью описание свойств окружающей реальности, а вторые строят формальную модель конкретной задачи. Для философских концептуализаций предлагается использовать термин «онтология», а для концептуализаций инженерных задач - термин «концептуальная схема». Последний термин уже используется в теории баз данных, где обозначает результат построения модели задачи. В реляционных базах данных концептуальная схема представляет собой не что иное, как схему базы данных. Термин «концептуальная схема», который предлагается использовать для обозначения спецификаций концептуализаций программных моделей, представляет собой более широкое понятие.

Для каких целей вообще может понадобиться построение онтологий в философском смысле, кроме какой-нибудь специфической задачи построения онтологии для некоторой программы философского справочника. Оказывается, спецификации такого рода необходимы для задачи слияния онтологий. Для слияния онтологий необходимо, чтобы эти онтологии были каким-то образом согласованы друг с другом: должна быть согласована терминология, выделены термины, обозначающие одни и те же классы, описываемые факты не должны противоречить друг другу. Только в этом случае можно попытаться слить две разных спецификации в одну. Здесь на помощь приходит философская онтология. Сливаемые онтологии сначала присоединяются к философской онтологии, и на основе этого присоединения происходит согласование сливаемых онтологий. Философские онтологии в абсолютном большинстве случаев описывают очень абстрактные знания, без какой-либо конкретики, поэтому их часто называют онтологиями верхнего уровня. Например, в онтологии верхнего уровня придется описать что такое материальный объект, чем он отличается от нематериального, и тому подобные вещи. Сейчас имеется довольно большое число онтологий верхнего уровня, использующих различные подходы для концептуализации Бытия.

Не существует единственного «правильного» способа или методологии разработки онтологий. Здесь мы обсуждаем общие моменты, которые нужно учитывать, и предлагаем один из возможных способов разработки онтологии. Мы описываем итеративный подход к разработке онтологии: мы начинаем с первого чернового просмотра онтологии. Затем мы проверяем и уточняем получаемую онтологию и добавляем детали. Попутно мы обсуждаем решения, касающиеся моделирования, которые должен принять разработчик, а также «за» и «против» и результаты принятия различных решений.

Во-первых, мы бы хотели выделить некоторые фундаментальные правила разработки онтологии, к которым мы будем неоднократно обращаться. Эти правила могут показаться довольно категоричными. Тем не менее, во многих случаях они могут помочь принять проектные решения.

1) Не существует единственного правильного способа моделирования предметной области - всегда существуют жизнеспособные альтернативы. Лучшее решение почти всегда зависит от предполагаемого приложения и ожидаемых расширений.

2) Разработка онтологии - это обязательно итеративный процесс.

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

То есть, знание того, для чего вы собираетесь использовать онтологию и насколько детальной или общей она будет, повлияет на многие решения, касающиеся моделирования. Среди нескольких жизнеспособных альтернатив нам нужно определить, какая поможет лучше решить поставленную задачу и будет более наглядной, более расширяемой и более простой в обслуживании. Нам также нужно помнить, что онтология - это модель реального мира и понятия в онтологии должны отражать эту реальность. После того, как мы определим начальную версию онтологии, мы можем оценить и отладить ее, используя ее в приложениях или в методах решения задач и/или обсудив ее с экспертами предметной области. В результате почти наверняка нам нужно будет пересмотреть начальную онтологию. Этот процесс итеративного проектирования, вероятно, будет продолжаться в течение всего жизненного цикла онтологии.

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

Именно в Система автоматизированного проектирования(САПР) всегда существует потребность в связном представлении разнообразных видов знаний (нормативные и справочные данные, методические материалы, понятийная модель предметной области, фактическая модель предметной области, математические модели, математические методы, типовые решения, программы, ограничения, принятые проектные решения).

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

Отчёты представляют научное знание по категориям:

- показатели (системные роли, изменчивость в смысловом и признаковом пространствах, смысловая активность, ранги значимости, оценки надёжности);

- структуры отношений (сложность, однородность, смысловая разрешимость, роли в системогенезе, устойчивость);

- эталонные типы поведения, эталонные состояния, механизмы формирования эталонных и неэталонных форм поведения и состояния;

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

- системные модели состояний, жизнедеятельности, свойств открытых систем.

Эксперты играют важную роль на этапе подготовки эмпирических контекстов. Информационный, интеллектуальный, технологический и инновационный ресурсы создаются на базе таких контекстов автоматически без привлечения экспертов. Эксперты включаются в работу после того, как Аналитическое ядро сгенерирует подготовленные решения проблем. Задача экспертов сводится к освоению автоматически подготовленных решений, определению полезности и перспектив эксплуатации полученного научного знания.

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

Тезаурус скорее более закреплён за лексикой в проекции на семантику, а Онтология в её информационном употреблении - это семантика и прагматика, возможно до известной степени в проекции на язык.

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

Модель предметной области автоматизации проектирования (АП) должна включать описание проектируемого изделия, ресурсов и процесса проектирования.

Вывод: Информационные онтологии рассматривают различные аспекты взаимодействия интеллектуальных систем между собой и с человеком. Они используются при разработке программного обеспечения как форма представления знаний о реальном мире или его части. Построение онтологий сводится к построению иерархии концептов и связей между ними.

Рис.1. Пример информационной онтологии. Физические свойства.

3. Способы сжатия информации

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

Сжатие информации - это процесс преобразования информации, хранящейся в файле, к виду, при котором уменьшается избыточность в ее представлении и соответственно требуется меньший объем памяти для хранения; процесс сокращения количества битов, необходимых для хранения и передачи некоторого объема информации.

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

Основные способы сжатия: статистический и словарный.

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

При словарном способе группы последовательных символов или "фраз" заменяются кодом. Замененная фраза может быть найдена в некотором словаре. В 1977 году Лемпель и Зив предложили свою модификацию словарного метода, отличающуюся от Хаффмановского и арифметического методов в которой сжатие основано на свойстве "потока символов" иметь повторяющиеся участки. Поток символов - это исходные данные для сжатия (например текстовый файл, массив). Основная идея алгоритма Лемпеля и Зива состоит в том, что второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылкой на ее первое появление в сообщении.

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

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

Метод основан на представлении последовательности одинаковых символов в виде двух величин K и S, где K - количество повторяющихся символов, S - код этого символа. Основным недостатком данного метода является то, что он обеспечивает сжатие лишь в случае, когда в исходном файле основную часть составляют повторяющиеся символы. В противном случае сжатый файл может занимать больше места, чем исходный неуплотненный файл. Наиболее эффективно метод сжатия последовательностей одинаковых символов работает в случае двоичных файлов.

Синтетические алгоритмы. Рассмотренные выше алгоритмы в «чистом виде» на практике не применяются из-за того, что эффективность каждого из них сильно зависит от начальных условий. В связи с этим, современные средства архивации, используют более сложные алгоритмы, основанные на комбинации нескольких теоретических методов. Общим принципом в работе таких «синтетических» алгоритмов является предварительный просмотр и анализ исходных данных для индивидуальной настройки алгоритма на особенности обрабатываемого материала.

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

Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущая строка перестает соответствовать какой-нибудь фразе словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк. Новая фраза, состоящая из индекса совпадения и следующего за ним символа, прибавляется в словарь. В следующий раз, если эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает меру сжатия информации.

Алгоритм LZW построен вокруг таблицы фраз (словаря), которая заменяет строки символов сжимаемого сообщения в коды фиксированной длины. Таблица имеет так называемое свойством опережения, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже заносится в словарь. Если все части словаря полностью заполнены, кодирование перестает быть адаптивным (кодирование происходит исходя из уже существующих в словаре фраз).

Алгоритмы сжатия этой группы наиболее эффективны для текстовых данных больших объемов и малоэффективны для файлов маленьких размеров (за счет необходимости сохранение словаря).

4. Способы сжатия информации на основе компьютерной онтологии

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

Рис.2. Пример информационной онтологии. Единицы измерения.

Сжатие информации - это процесс уменьшения количества занимаемой информации на носителе. Сжатие можно сделать обратимыми, как в случае с прошлыми примерами(см. п.1), так не обратимыми. Рассмотрим просто пример сжатия информационной онтологии. Используем онтологию с рисунка 2.

онтология информатика сжатие

Рис.3 Пример сжатой информационной онтологии. Единицы измерения.

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

Вывод

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

Размещено на Allbest.ru