Подобное кодирование не реализуется практически, поскольку с ростом длины сообщения становится недопустимо большой трудоёмкость построения кода. К тому же при таком кодировании невозможно по частям отправить сообщение, что важно для непрерывных процессов передачи информации.
Существует несколько методов сжатия информации, имеющих свои достоинства и недостатки.
Например, методы Шеннона-Фэно, Хаффмена и арифметическое кодирование в общем случае являются статистическими методами, словарные алгоритмы — более практическими, преимущество которых перед статистическими обосновано тем, что они позволяют кодировать последовательности символов разной длины. Также можно применять для таких последовательностей неадаптивные статистические алгоритмы, однако при этом их реализация станет более трудоёмкой.
Алгоритм LZ77, опубликованный в 1977 г., разработан израильскими математиками Якобом Зивом (Ziv) и Авраамом Лемпелом (Lempel). Во многих программах сжатия данных применяется та или иная модификация LZ77.
Причина популярности алгоритмов LZ определяется их исключительной простотой и высокой эффективностью сжатия.
Основная идея LZ77 заключается в том, что второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на её первое вхождение. Уже просмотренную часть сообщения LZ77 использует в качестве словаря, и чтобы добиться сжатия, он старается заменить следующий фрагмент сообщения на указатель в содержимое словаря.
В 1982 г. Сторером (Storer) и Шиманским (Szimanski) на базе LZ77 был разработан алгоритм LZSS, отличающийся от LZ77 производимыми кодами. Код состоит из пары: смещение и длина, такими же как и для LZ77. В LZSS окно сдвигается ровно на длину найденной подстроки или на 1, если не найдено вхождение подстроки из буфера в словарь.
LZ77 и LZSS обладают следующими очевидными недостатками: невозможностью кодирования подстрок, отстоящих друг от друга на расстоянии, большем длины словаря; длина подстроки, которую можно закодировать, ограничена размером буфера.
В 1978 г. авторами LZ77 был разработан алгоритм LZ78, лишённый названных недостатков. Ключевым для размера получаемых кодов является размер словаря во фразах, потому что каждый код при кодировании по методу LZ78 содержит номер фразы в словаре. Из последнего следует, что эти коды имеют постоянную длину.
В 1984 г. Уэлчем (Welch) путём модификации LZ78 был создан алгоритм LZW. Как и в случае с LZ78 для LZW ключевым для размера получаемых кодов является размер словаря во фразах: LZW-коды имеют постоянную длину, равную округлённому в большую сторону двоичному логарифму размера словаря.
2.5 Вероятностный подход к измерению информации Формулу для вычисления количества информации, учитывающую неодинаковую вероятность событий, предложил К. Шеннон в 1948 году. Количественная зависимость между вероятностью события р и количеством информации в сообщении о нём x выражается формулой:
. (13)
Качественную связь между вероятностью события и количеством информации в сообщении об этом событии можно выразить следующим образом: чем меньше вероятность некоторого события, тем больше информации содержит сообщение об этом событии.
Рассмотрю ситуацию. В коробке имеется 60 шаров. Из них 40 белых и 20 чёрных. Очевидно, вероятность того, что при вытаскивании «не глядя» попадётся белый шар больше, чем вероятность попадания чёрного. Можно сделать заключение о вероятности события, которые интуитивно понятны. Проведу количественную оценку вероятности для каждой ситуации. Обозначу pч — вероятность попадания при вытаскивании чёрного шара, рб — вероятность попадания белого шара. Тогда: рч=20/60=0,3; рб=40/60=0,7.
Замечу, что вероятность попадания белого шара в 2,3 раза больше, чем чёрного. Делаю вывод: если N — это общее число возможных исходов какого-то процесса (вытаскивание шара), и из них интересующее нас событие (вытаскивание белого шара) может произойти K раз, то вероятность этого события равна K/N. Вероятность выражается в долях единицы. Вероятность достоверного события равна 1 (из 60 белых шаров вытащен белый шар). Вероятность невозможного события равна нулю (из 60 белых шаров вытащен чёрный шар).
Количественная зависимость между вероятностью события р и количеством информации в сообщении о нём x выражается формулой (13). В задаче о шарах количество информации в сообщении о попадании белого шара и чёрного шара получится:
(14)
Рассмотрю некоторый алфавит из m символов:
(15)
и вероятность выбора из этого алфавита какой-то i-й буквы для описания (кодирования) некоторого состояния объекта. Каждый такой выбор уменьшит степень неопределённости в сведениях об объекте и, следовательно, увеличит количество информации о нём. Для определения среднего значения количества информации, приходящейся в данном случае на один символ алфавита, применяется формула (2). В случае равновероятных выборов p=1/m. Подставляя это значение в исходное равенство, получаю:
. (16)
Рассмотрю следующий пример. Пусть при бросании несимметричной четырёхгранной пирамидки вероятности выпадения граней будут следующими: p1=½, p2=¼, p3=1/8, p4=1/8, тогда количество информации, получаемое после броска, можно рассчитать по формуле:
(17)
Для симметричной четырёхгранной пирамидки количество информации будет: H=log24=2(бит).
Для симметричной пирамидки количество информации будет больше, чем для несимметричной пирамидки. Максимальное значение количества информации достигается для равновероятных событий.
Таким образом, основным понятием теории информации является количество информации, которое определяется посредством процесса измерения как и в случае измерений физических величин. При этом для информации введена своя единица измерений — бит. Важнейшими процессами при обработке информации являются кодирование, обеспечивающее возможность компьютерной обработки информации, и сжатие — важный аспект оперативной передачи данных и экономного хранения.
Заключение
По результатам проделанной работы можно сделать следующие выводы. Теория информации имеет достаточно тесную связь с такими разделами математики как математическая статистика, теория вероятностей и прикладная алгебра, предоставляющими для неё математическую основу, являясь другой стороны математическим фундаментом теории связи. Информация — это то, что обычно устраняет или уменьшает создающуюся где-либо неопределённость, именно так её представляют математики, физики и специалисты по системам связи.
Существенные достижения в области теории информации в последнее время немного расширили понятия информация, сжатие информации, измерение информации, кодирование, прогресс в котором позволил создавать для телефонных каналов модемы, практически сблизившие скорость передачи информации к их пропускной способности. Достаточно эффективные и универсальные алгоритмы сжатия данных сегодня широко используются для сжатия компьютерных файлов. Теория информации остается активно развивающейся сферой деятельности, генерирующей в нынешний информационный век новые концепции и подходы в исследование, проектирование, анализ и развитие систем передачи информации и разнообразных компьютерных систем.
Математическое понятие информации тесно связано с её измерением. В теории информации принят так называемый энтропийный подход, который устанавливает ценность и значимость информации, содержащейся в сообщении для его конкретного получателя.
Главной задачей теории информации было и остаётся обнаружение математических закономерностей, которые управляют системами, разработанными для связи или манипулирования информацией.
Список литературы
Анфилатов В. С. Системный анализ в управлении: Учебное пособие. — М.: Финансы и статистика, 2003. — 368 с.
Бородакий Ю.В., Лободинский Ю. Г. Информационные технологии. методы, процессы, системы. — М.: Радио и связь, 2002. — 456 с.
Винер Н. Кибернетика, или управление и связь в животном и машине. — 2-е издание. — М.: Наука, 1983. — 344 с.
Высшая математика для экономистов: Учебник для вузов. / Под ред. Н. Ш. Кремера. — 2-е изд., перераб. и доп. — М.: ЮНИТИ-ДАНА, 2004. — 471 с.
Гиляревский Р. С. Основы информатики: Курс лекций. — М.: Экзамен, 2003. — 320 с.
Дмитриев В. И. Прикладная теория информации: Учебное пособие. — М.: Высшая школа, 1989. — 320 с.
Информатика и математика для юристов: Учебное пособие для вузов. / Под ред. Х. А. Андриашина. — М: ЮНИТИ-ДАНА, 2001. — 463 с.
Лидовский В. В. Теория информации: Учебное пособие. — М.: Спутник+, 2004. — 111 с.
Мазур М. Качественная теория информации. — Перевод с польского О. И. Лочмеля. — М.: Мир, 1974. — 239 с.
Пирс Дж. Символы, сигналы, шумы. Закономерности и процессы передачи информации. — М.: Мир, 1967. — 332 с.
Экономическая информатика: Учебник. / Под ред. В. П. Косарева. — М.: Финансы и статистика, 2002. — 592 с.
Глушков В. М. Мышление и кибернетика. // Вопросы философии. — 1963. — №
1. — С. 10−24.
Колмогоров А. Н. Три подхода к определению понятия «количество информации». // Проблемы передачи информации.
— 1965. — Т. 1. Вып. 1. -
С. 25−38.
Чугайнова А. Информатика. — [Электронный ресурс]: статья, Энциклопедия «Кругосвет», 2008
Режим доступа:
http://www.krugosvet.ru, свободный.
Янковский С. Концепции общей теории информации. — [Электронный ресурс]: электронная книга, МОО «Наука и техника», 1997;2008
Режим доступа:
http://www.n-t.ru, свободный.
Лидовский В. В. Теория информации: Учебное пособие. — М.: Спутник+, 2004. — 111 с. — С. 4.
Мазур М. Качественная теория информации. — М.: Мир, 1974. — 239 с. — С. 5.
Высшая математика для экономистов: Учебник для вузов. / Под ред. Н. Ш. Кремера. -
2-е изд., перераб. и доп. — М.: ЮНИТИ, 2004. -
471 с. — С. 7.
Пирс Дж. Символы, сигналы, шумы. Закономерности и процессы передачи информации. — М.: Мир, 1967. — 332 с.
Экономическая информатика: Учебник. / Под ред. В. П. Косарева. — М.: Финансы и статистика, 2002.
— 592 с. — С. 18.
Глушков В. М. Мышление и кибернетика. // Вопросы философии.
— 1963. — № 1.
— С. 10−24.
Колмогоров А. Н. Три подхода к определению понятия «количество информации». //
Проблемы передачи информации. — 1965. — Т. 1. Вып.
1. — С. 25−38.
Винер Н. Кибернетика, или управление и связь в животном и машине. — 2-е издание. -
М.: Наука, 1983. — 344 с. — С. 201.
Янковский С. Концепции общей теории информации. — [Электронный ресурс]: электронная книга, МОО «Наука и техника», 1997;2008
Режим доступа:
http://www.n-t.ru, свободный.
Чугайнова А. Информатика. — [Электронный ресурс]: статья, Энциклопедия «Кругосвет», 2008
Режим доступа:
http://www.krugosvet.ru, свободный.
Дмитриев В. И. Прикладная теория информации: Учебное пособие. — М.: Высшая школа, 1989. — 320 с. — С. 18.
Бородакий Ю.В., Лободинский Ю. Г. Информационные технологии. методы, процессы, системы. — М.: Радио и связь, 2002. — 456 с. — С. 142.
Бородакий Ю.В., Лободинский Ю. Г. Указ. соч. — С. 144.
Информатика и математика для юристов: Учебное пособие для вузов. / Под ред. Х. А. Андриашина. — М: ЮНИТИ-ДАНА, 2001. — 463 с.
Анфилатов В. С. Системный анализ в управлении: Учебное пособие. — М.: Финансы и статистика, 2003. — 368 с. — С. 205.
Лидовский В. В. Указ. соч. — С. 22.
Гиляревский Р. С. Основы информатики: Курс лекций. — М.: Экзамен, 2003. — 320 с. — С. 25.
Источник информации
Информационный объект
Передатчик
Устройство приёма
Получатель
Источник помех
Приёмник информации
ПеС
ПрС
ЛС
