Научная литература
booksshare.net -> Добавить материал -> Физика -> Аветисян Р.Д. -> "Теоретические основы информатики" -> 16

Теоретические основы информатики - Аветисян Р.Д.

Аветисян Р.Д., Аветисян Д.О. Теоретические основы информатики — Телеком , 2003. — 170 c.
Скачать (прямая ссылка): teoriticheskieosnoviinformatiki2003.pdf
Предыдущая << 1 .. 10 11 12 13 14 15 < 16 > 17 18 19 20 21 22 .. 64 >> Следующая


P (А) = 0,49 P (D) = 0,16

P (В) = 0,17 P (E) = 0,01

P (С) = 0,17

С помощью схемы кодирования Д. Хаффмэна приходим к результату:

Буква Двоичный код А 1

В 01

С 000

т.е. к значению средней длины кодовых наборов, равному /min = 2,02 символа на букву.

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

Буква Двоичный код Буква Двоичный код

А 1 D 010

В 000 E 011

С 001

Несмотря на свою неоптимальность, схема Р. Фано тем не менее обеспечивает значения /, достаточно близкие или в точности совпадающие с /тш. В частности, легко убедиться в том, что в случае, когда

Буква Двоичный код D 0010

E 0001

40 все p(i) (і = А, В,...) можно представить как /;(/) = 2 "'< , где т, - натуральные числа, в результате кодирования по этим схемам непременно приходим к одинаковым значениям /. Более того, в этих случаях, независимо от того, используется ли схема Р. Фано или Д. Хаффмэна, число двоичных символов в коде каждой /-й буквы алфавита оказывается равным /, = -iog2 p{i) = mr т.е. среднее число двоичных символов, приходящихся на одну букву, оказывается равным

а п

I = Imin = X POVi = ~Х Pi') 'Gg. P(i). <=i I=I

Забегая вперед, отметим, что выражение, фигурирующее в правой части этого равенства, называется энтропией и имеет ключевое значение в теории информации. Это выражение остается в силе при произвольных значениях p(i), вовсе не обязательно удовлетворяющих условию p(i) = 2~"'i. Более подробно понятие энтропии мы рассмотрим чуть позже, в следующем параграфе этой главы.

Говоря об оптимальности кода Р. Хаффмэна, следует запомнить, Что здесь пока речь идет лишь о побуквенном кодировании, и поэтому в общем случае схема кодирования по Д. Хаффмэну в том виде, в каком мы ее рассматривали, также не является пределом компактного представления исходных текстов последовательностью двоичных символов. Если, вслед за отказом от постоянства длин кодовых наборов, отказаться также от побуквенного кодирования, т.е. допустить кодирование сразу нескольких букв (комбинаций букв), то в общем случае можно добиться значительно большего эффекта сжатия (компрессии) исходных текстов. Заметим при этом, что при заданных статистических характеристиках исходного текста чем длиннее комбинации букв, подвергающиеся кодированию, тем, при прочих равных условиях, большим получается эффект сжатия. Естественно, что с увеличением длины этих последовательностей растет также время, расходуемое на их кодирование, и поэтому чрезмерно сильное сжатие исходных текс тов не всегда оправдано, так как оно может быть связано с большими затратами машинного времени.

P о ПОНЯТИЕ ЭНТРОПИИ И ПРЕДЕЛЬНЫЕ

ВОЗМОЖНОСТИ ПРИ СЖАТИИ ТЕКСТОВ

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

41

ГЛАВА 1 информации" [2|. Центральным понятием этой теории является энтропия - количественная мера неопределенности, или, что го же самое, количество информации, необходимое для устранения имеющейся неопределенности.

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

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

"і =-I P(I)-Iog2/>(/), (2.3)

1=1

где под p(i) подразумевается вероятность того, что наугад взятая из текста буква окажется /-й буквой алфавита. Если к тому же имеет место p(i) = p(j) = 1//1, то формула вычисления энтропии (2.3) упрощается и принимает вид

H1 = Iog2 п. (2.3а)

Значение энтропии Hb вычисленное по формуле (2.3), устанавливает количественную меру "проблематичности" угадывания того, какой именно является наугад взятая буква, если известны все значения вероятностей р(і) (і = 1, 2,..., /г). Иными словами, это среднее количество информации, которое необходимо сообщить угадывающему, чтобы полностью ликвидировать имеющуюся у него неопределенность; количество информации, достаточное для того, чтобы он точно знал, какой именно является угадываемая буква. Формула (2.3) обладает рядом свойств, которые хорошо согласуются с интуитивными представлениями о степени "проблематичности" угадывания буквы. Так, /У, является непрерывной функцией от p(i) и при каждом фиксированном значении п достигает своего наибольшего возможного значения, когда все буквы равновероятны, т.е. когда
Предыдущая << 1 .. 10 11 12 13 14 15 < 16 > 17 18 19 20 21 22 .. 64 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed