Определение информации с точки зрения теории информации

владеть: инструментальными средствами обработки информации ЦЕЛЬ: Обучение принципам обработки и анализа информации знать: основные виды и процедуры обработки информации, модели и методы решения задач обработки информации генерация отчетов, поддержка принятия решений, анализ данных, обработка изображений. уметь: осуществлять математическую и информационную постановку задач по обработке информации, использовать алгоритмы обработки информации для различных приложений Учебно-методическое обеспечение дисциплины • Основная литература 1 Советов Б.Я., Дубенецкий В.А., Цехановский В.В., Шеховцов О.И. Теория информационных процессов и систем. Учебник. М.: Академия 2010. - 432 с. • Дополнительная литература 1 Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. – М.: Нолидж, 2001. – 496 с. 2 Волкова Л.А., Решетникова Е.Р. Категория:Технология обработки текстовой информации (ТОТИ). – МГУПечати, 2007. – 324 стр. Содержание 1 Модуль 1. Предметная область дисциплины МЕ №1. Определение информации с точки зрения теории информации 2 Модуль 1. Предметная область дисциплины МЕ №2. Основные алгоритмы сжатия Информация Определение Информация (от лат. “informatio” – разъяснение, изложение), первоначально – сведения, передаваемые одними людьми другим людям устным, письменным или каким-либо другим способом (например, с помощью условных сигналов, с использованием технических средств и т. д.), а также сам процесс передачи или получения этих сведений. Информатика Определение Информатика – комплексная наука об информации и информационных процессах, аппаратных и программных средствах информатизации, информационных и коммуникационных технологиях, а также социальных аспектах процесса информатизации. Передача информации Виды информации по ее форме представления графическая или изобразительная; звуковая; текстовая; числовая; видеоинформация. Виды информации Способы передачи информации: устно письменно с помощью технических средств связи Свойства информации достоверность; полнота; объективность; понятность; полезность; актуальность. Информация достоверна, если она отражает истинное положение дел; полна, если её достаточно для понимания и принятия решения; объективна, если она не зависит от чьего-либо суждения; понятна, если выражена на языке, доступном для получателя; актуальна, если она важна (существенна) для настоящего времени. Полезность информации оценивается по тем задачам, которые мы можем решить с её помощью. Клод Шеннон: Количество информации – мера уменьшения неопределенности знаний Измерение информации Содержательный подход к измерению информации Алфавитный подход Вероятностный подход к измерения информации Количество информации Определение Количество информации – это мера уменьшения неопределенности. 1 БИТ – такое кол-во информации, которое содержит сообщение, уменьшающее неопределенность знаний в два раза. БИТ– это наименьшая единица измерения информации. Единицы измерения информации 1 байт = 8 бит 1 Кб (килобайт) = 210 байт = 1024 байт 1 Мб (мегабайт) =210 Кб = 1024 Кб 1 Гб (гигабайт) = 210 Мб = 1024 Мб Формы адекватности информации 1 Синтаксическая адекватность 2 Семантическая (смысловая) адекватность 3 Прагматическая (потребительская) адекватность Синтаксическая адекватность отражает формально-структурные характеристики информации и не затрагивает ее смыслового содержания. Семантическая (смысловая) адекватность определяет степень соответствия образа объекта и самого объекта. Прагматическая (потребительская) адекватность отражает отношение информации и ее потребителя, соответствие информации цели управления, которая на ее основе реализуется. Мера количества информации 1 Синтаксическая мера информации 2 Семантическая мера информации 3 Прагматическая мера информации Синтаксическая мера информации оперирует с обезличенной информацией, не выражающей смыслового отношения к объекту. Семантическая мера информации используется для измерения смыслового содержания информации. Прагматическая мера информации определяет ее полезность, ценность для процесса управления. Пример Какое из соотношений несет в себе больше информации x = 5 или x > 3 ? Количество информации, содержащейся в X относительно Y : I(X, Y ) = X pij log2 pij pipj i,j (1) X, Y – дискретные случайные величины P(X = Xi) = pi, P(Y = Yj) = pj – законы распределения для каждой величины P(X = Xi, Y = Yj) = pij – совместный закон распределения Количество информации, содержащейся в X относительно Y : Z Z pXY (t1, t2) I(X, Y ) = pXY (t1, t2) log2 dt1dt2 R2 pX (t1)pY (t2) (2) X, Y – непрерывных случайных величин pX (t1), pY (t2), pXY (t1, t2) – плотность распределения вероятностей Очевидно, 0, i 6= j P(X = Xi, X = Xj) = (3) P(X = Xi), i = j Количество информации, содержащейся в X относительно X: I(X, X) = X pi log2 pi = −X pi log2 pi. pipi i i (4) Формула Хартли [1928 г.] I = log2 N ⇔ N = 2I , где N –число возможных равновероятных событий, I – количество информации в битах. Свойства количества информации 1 Количество информации в сообщении обратно-пропорционально вероятности появления данного сообщения. 2 Свойство аддитивности – суммарное количество информации двух источников равно сумме информации источников. 3 Для события с одним исходом количество информации равно нулю. 4 Количество информации в дискретном сообщении растет в зависимости от увеличения объема алфавита. Энтропия Определение Энтропия– это количество информации, приходящейся на одно элементарное сообщение источника, вырабатывающего статистически независимые сообщения N H = −X pi log2 pi, (5) i=1 где H – энтропия; N – количество возможных событий; pi – вероятность события. Энтропия Энтропия дискретной случайной величины Энтропия дискретной случайной величины X в теории информации определяется формулой H(X) = HX = I(X, X). (6) Пример 1. Имеются две урны, содержащие по 20 шаров – 10 белых, 5 черных и 5 красных в первой и 8 белых, 8 черных и 4 красных во второй. Из каждой урны вытаскивают по одному шару. Исход какого из этих двух опытов следует считать более неопределенным? Ответ: H1 = 1, 5 бита, H2 ≈ 1, 52 бита. Пример 2. Пусть из многолетних наблюдений за погодой известно, что для определенного города вероятность того, что 15 июня будет идти дождь, равна 0,4, а вероятность того, что в указанный день дождя не будет, равна 0,6. Пусть далее для этого же города вероятность того, что 15 ноября будет идти дождь равна 0,65, вероятность того, что 15 ноября будет идти снег, равна 0,15 и вероятность того, что 15 ноября вовсе не будет осадков, равна 0,2. Если из всех характеристик погоды интересоваться лишь вопросом о наличии и о характере осадков, то в какой из двух перечисленных дней погоду в рассматриваемом городе следует считать более неопределенной? Решение: для 15 июня: p1(дождь) = 0, 4 p1(нет осадков) = 0, 6 для 15 ноября: p2(дождь) = 0, 65 p2(снег) = 0, 15 p2(нет осадков) = 0, 2 Ответ: H1 ≈ 0, 97 бита, H2 ≈ 1, 28 бита. Энтропия сложных событий. Условная энтропия. Пусть α и β – два независимых опыта со следующими вероятностями: для событий A1, A2,..., Ak опыта α – вероятности p(A1), p(A2), dots, p(Ak) для событий B1, B2,..., Bl опыта β – вероятности p(B1), p(B2), dots, p(Bl) Правило сложения энтропий H(αβ) = H(α)+ H(β) Свойства энтропии сообщений 1 Значение функции H(p1, p2,..., pk) не меняется при любой перестановке чисел p1, p2,..., pk. 2 Функция H(p1, p2,..., pk) является непрерывной, т.е. мало меняется при малых изменениях вероятностей p1, p2,..., pk – ведь при малых изменениях вероятностей и степень неопределенности опыта должна мало изменяться. 3 Функция H(p1, p2,..., pk) удовлетворяет соотношению H(p1, p2,..., pk) = H(p1 + p2, p3,..., pk)+(p1 + p2)H . 4 Функция H(1/k, 1/k,..., 1/k) = f (k) растет с увеличением числа k. Отличие энтропии от количества информации H(X) – выражает среднюю неопределенность состояния источника и является его объективной характеристикой, она может быть вычислена априорно, т.е. до получения сообщения при наличии статистики сообщений. I(X) – определяется апостериорно, т.е. после получения сообщения. С получением информации о состоянии системы энтропия снижается. Свойства меры информации и энтропии 1 I(X, Y ) ≥ 0, I(X, Y ) = 0 ⇔ X и Y – независимы; 2 I(X, Y ) = I(Y , X); 3 HX = 0 ⇔ X – константа; 4 I(X, Y ) = HX + HY − H(X, Y ), где H(X, Y ) = −Pi,j pij log2 pij; 5 I(X, Y ) ≤ I(X, X) Содержание 1 Модуль 1. Предметная область дисциплины МЕ №1. Определение информации с точки зрения теории информации 2 Модуль 1. Предметная область дисциплины МЕ №2. Основные алгоритмы сжатия Будем называть входную последовательность данных текстом. Текст состоит из символов, полный набор которых назовем входным алфавитом. Поставим в соответствие каждому сообщению xi в соответствие код ai из некоторого алфавита A = a1, a2,..., aL. Cтоимость кодирования Определение Стоимостью кодирования будет называться величина L C(X) = X|ai| · p(xi), (7) i=1 где |a| – длина кода a в битах. Если длины всех кодов одинаковы и равны log L, то C(X) = log L. Иначе, под стоимостью кодирования понимается средняя длина кодового слова в битах (Hmax). Определение Относительная энтропия Hотн - отношение энтропии источника к максимальному значению, которое могло бы быть достигнуто при тех же символах: Hотн = H/Hmax = H/C . Определение Избыточность кодирования R равна разности между стоимостью кодирования C и энтропией H: R = C − H. Определение Относительная избыточность определяется по формуле: C − H Rотн = (1 − Hотн) · 100% = · 100% C Определение Если средняя длина кодового слова входного текста равна T, то в случае выполнения неравенства T > C мы можем говорить о том, что имеет место сжатие информации. С помощью идеального архиватора, для которого R = 0, можно определить избыточность входного текста Rt: Rt = T − H = T − C(бит) Виды избыточности Пример физической избыточности н.пр.м.р в.к.н.ть вс. гл.сн.. б.кв. ил. вы.ин.ть ка.ду. тр.ть. бу.ву, или отброс... окончан.. кажд... слов. Пример избыточности Применение в криптографии ВОТПРСТОЙПРМЕРСЖАТИЯДННЫХ Аспекты связи криптологии и сжатия информации сжатый текст труднее поддается перехвату при передаче по линии связи и его труднее обнаружить при хранении (но не следует забывать что при этом возрастает опасность распространения ошибки); сжатие информации с варьируемыми в зависимости от ключа параметрами может рассматриваться как один из нетрадиционных программных криптоалгоритмов. Применение в системах связи Протокол MNP5 фирмы Microcom, предлагавший, в среднем, двукратное сжатие отправляемых сообщений; Конец 1989 г. – протокол CCITT V42.bis, достигающий на практике 2-3-кратного повышения пропускной способности; Оригинальный алгоритм, разработанный Линчем и Миллером на основе прореживания и RLE-кодирования, позволил получить сжатие данных в 32! раза. Применение в системах хранения информации зарубежные программы PKZIP [21], ARJ [3], LHA, HA, отечественные-RAR, AIN, ACB; самораспаковывающие архиваторы и программы сжатия исполняемых файлов: PKLITE, LZEXE, DIET, EXEPACK ; системные утилиты сжатия дискового пространства на уровне отдельных секторов Stacker, DoubleSpace, SuperStor (требуется высокая скорость компрессии/декомпресии при менее жестких требованиях по избыточности); встроенные в Windows API функции LZxxx; различные программы преобразования и показа форматов видеоизображений, типа PCXVIEW, GIFVIEW, BITMAP, JPGVIEW, QuickTime. Моделирование источника информации Основные вероятностные модели: модель источника сигнала Бернулли (Сигнал порождается источником Бернулли, если очередное сообщение или код не зависит от всех предыдущих, иными словами все сообщения независимы и характеризуются только своими вероятностями) модель источника сигнала Маркова (Предполагается, что вероятность появления очередного сигнала зависит от n предыдущих сигналов) “Традиционные” методы сжатия информации Сжатие текстовой информации Перекодировка Упаковка Сжатие числовой информации Метод сжатия информации до 1/3 первоначального объема Даже Эдди нас опередил с детским хором Перекодировка Под перекодировкой мы будем понимать любое удачно выбранное представление исходной информации при котором ее легко можно восстановить обратно и которое занимает меньший физический объем на носителе. Упаковка Если путем изменения местоположения и взаимного расположения носителей информации удается сократить ее объем, то будем считать такой процесс упаковкой. Сжатие числовой информации Одним из широко известных способов сжатия последовательности цифровых данных (например результатов измерения процесса F(ti) в дискретные промежутки времени ti, i = 1 ... N) является аппроксимация. Сжатие информации в системах передачи и хранения Префикс Префикс – служебный код, предписывающий алгоритму разархивации обрабатывать следующие несколько кодов из выходного потока особым образом. RLE-кодирование Алгоритм RLE (Run Length Encoding, упаковка, кодирование длин серий) является самым быстрым, простым и понятным алгоритмом сжатия данных и при этом иногда оказывается весьма эффективным. F любой последовательности повторяющихся входных символов ставится в соответствие набор из трех выходных символов: первый-байт префикса, говорящий о том, что встретилась входная повторяющаяся последовательность, второй-байт, определяющий длину входной последовательности, третий-сам входной символ – < prefix, length, symbol > 05 05 05 05 05 05 01 01 03 03 03 03 03 03 05 03 FF FF FF FF ⇓ FF 06 05 FF 02 01 FF 06 03 FF 01 05 FF 01 03 FF 04 FF ⇓ FF 06 05 01 01 FF 06 03 05 03 FF 04 FF Сжатие информации в системах передачи и хранения Унарное кодирование Унарное кодирование основывается на том, что вероятность использования в тексте разных символов сильно различна Variable Length Integers (VLI) codes VLI-коды состоят из двух частей : сначала следует унарный код, определяющий группу чисел определенной длины, а затем само число указанной длины. F (start,step,stop), где start определяет начальную длину числа, step – приращение длины для следующей группы, stop – конечную длину. Сжатие информации в системах передачи и хранения Коды Хаффмана Код Хаффмана – наиболее эффективным кодом переменной длины, в котором ни одно слово не совпадает с началом другого (т.е. префиксный код). Теорема Пусть l1,..., lk-положительные целые числа (k > 0). Для того, чтобы существовал префиксный код, длины слов которого равны l1,..., lk, необходимо и достаточно выполнение неравенства Крафта: k X −li ≤ 1. 2 i=1 ABACCADAА ⇓ A - 00, B - 01, C - 10, D - 11 ⇓ 000100101000110000 Сжатие информации в системах передачи и хранения Дерево Хаффмана Сжатие информации в системах передачи и хранения Код Шеннона-Фано Идея этого метода – заменить часто встречающиеся символы более короткими кодами, а редко встречающиеся последовательности более длинными кодами. Таким образом, алгоритм основывается на кодах переменной длины. Для того, чтобы декомпрессор впоследствии смог раскодировать сжатую последовательность, коды Шеннона-Фано должны обладать уникальностью, то есть, не смотря на их переменную длину, каждый код уникально определяет один закодированый символ и не является префиксом любого другого кода. Пример Закодировать сообщение, используя алгоритм Шеннона-Фано: aa bbb cccc ddddd Закодированная последовательность: 111111101101101101001010101100000000000 Пример Длина кода l(i): Z Z (− log2 p(c(i))) ≤ l(i) ≤ (− log2 p(c(i)))+ 1 (8) Фиксированный алгоритм Хаффмана Идея состоит в том, чтобы пользоваться некоторым усредненным по многим текстам деревом, одинаковым для кодировщика и декодировщика. Такое дерево не надо строить и передавать вместе с текстом. Алгоритм стопки книг Каждому символу (букве) присваивается код в зависимости от его положения в алфавите – чем ближе символ к началу алфавита – тем короче код. ! Арифметическое кодирование - блочное и выходной код является уникальным для каждого из возможных входных сообщений; его нельзя разбить на коды отдельных символов. Выполним алгоритм для цепочки “aaba” Вероятностное сжатие Работает алгоритм следующим образом: имеется достаточно большая, динамически обновляющаяся таблица предсказаний, в которой для каждой возможной пары последовательных входных символов указывается предсказываемый следующий (третий) символ. Если символ предсказан правильно-генерируется код в виде однобитного префикса, равного 1. Если же не угадали –выдается код в виде префикса, равного 0 и неугаданного символа. При этом неугаданный символ замещает в таблице бывший там до этого, обеспечивая постоянное обновление статистической информации. Алгоритм LZ77. Заключается он в следующем: имеется "скользящий"(sliding) словарь V объемом |V| = 2...32. Если очередная входная строка s текста совпадает со строкой из словаря, то она заменяется на указатель ptr на эту строку вида ptr =< prefix, distance, length >, для которой prefix = 1 , после чего текущая позиция в исходном тексте pos сдвигается на length символов дальше. Под строкой подразумевается любая непрерывная последовательность символов (букв), начинающаяся с определенной позиции в словаре или в тексте, длиной |s| ≤ smax. smax обычно выбирается из диапазона 16...256 байт; в качестве словаря используются |V| байт сжимаемого текста, предшествующие текущему кодируемому символу в позиции pos. Словами в словаре выступают любые строки длины не более smax, начинающиеся в любой позиции словаря. Таким образом, в словаре всегда присутствует |V| · smax слов. Если же строки s в словаре не оказалось, генерируется код chr вида chr =< prefix, symbol >, где prefix = 0, а symbol –текущий символ исходного текста (в позиции pos). Префикс, как видно, нужен для того, чтобы отличить код ptr от кода chr. Именно префикс вносит в алгоритм кодирования LZ77 некоторую дополнительную информацию, из-за которой возможно возрастание избыточности. Вид словаря и исходного текста для алгоритма LZ77 перед началом работы а) и на 23-ем шаге б). Длины кодов Длина ptr –кода |ptr| = 1 + log2(|V|)+ log2(|smax|) (бит), Длина chr –кода |chr| = 1 + log2(|symbol|) (бит). Алгоритм LZ78-LZW84 В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позиции pos исходного текста. Так как словарь первоначально не пустой, такое слово всегда найдется; В выходной файл помещается номер найденного слова в словаре position и следующий символ из входного текста B (на котором обнаружилось различие)– < position, B >. Длина кода равна |position| + |B| = log Vmax + 8 (бит) Если словарь еще не полон, новая строка str B добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию; Указатель в исходном тексте pos смещается на |str B| = |str| + 1 байт дальше – к символу, следующему за B. Сжатие информации в системах передачи и хранения Модернизированный алгоритм LZ78-LZW84 В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позиции pos исходного текста; В выходной файл помещается номер найденного слова в словаре < position >. Длина кода равна |position| = log V (бит); Если словарь еще не полон, новая строка strB добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию; Указатель в исходном тексте pos смещается на |str| байт дальше – к символу .