Читайте также:
|
Актуальной является задача эффективного кодирования английского текста для сжатия текстовых документов. Для прогнозирования возможного преимущества при сжатии необходима оценка фактической энтропии английского языка с учётом межсимвольной зависимости.
Для удобства часто принимается допущение, что алфавит состоит всего лишь из 26 символов (26 букв и пробел или пунктуация). Поскольку 25=32, все 27 символов могут быть закодированы с помощью двоичного блок-кода, при котором каждое слово имеет длину 5. Однако, 27 – это меньше 32, поэтому фактическая энтропия меньше пяти битов.
Простейшая оценка энтропии английского языка (оценка нулевого порядка) основываются на допущении, что все буквы алфавита являются равно вероятными с вероятностью 1/27. Соответствующая энтропия нулевого порядка, обозначаемая H 0, поэтому равна H 0 = log27 = 4,755 бита на букву текста. Это верхний предел, поскольку, если вероятности не будут одинаковыми, энтропия уменьшится. Однако этот предел является важной точкой отсчёта.
Вероятности букв алфавита, т.е как часто они встречаются в английском тексте, различны. Более того этот показатель меняется в зависимости от типа документов.
Таблица 4 Вероятности встречаемости букв английского алфавита
| A | 0,064 | N | 0,056 |
| B | 0,014 | O | 0,056 |
| C | 0,027 | P | 0,017 |
| D | 0,035 | Q | 0,004 |
| E | 0,100 | R | 0,049 |
| F | 0,020 | S | 0,056 |
| G | 0,014 | T | 0,071 |
| H | 0,042 | U | 0,031 |
| I | 0,063 | V | 0,010 |
| J | 0,003 | W | 0,018 |
| K | 0,006 | X | 0,003 |
| L | 0,035 | Y | 0,018 |
| M | 0,020 | Z | 0,002 |
| Пробел/пунктуация | 0,166 |
Энтропия английского языка на основе вероятностей букв называется оценкой первого порядка и обозначается H 1. На основании данных, приведённых в таблице 4, можно вычислить, что H 1=4,194, что является скромным уменьшением энтропии по сравнению со случаем одинаковых значений вероятности. Исходя из этой оценки, предполагается, что код Хаффмена для алфавита будет иметь среднюю длину ближе к 4, чем к 5.
Кодирование по алгоритму Хаффмена, действительно используется в качестве метода компрессии английского текста, и, как предполагается, документы требуют приблизительно на 20% меньше памяти, чем в случае использования стандартного кода ASCII.
Если идти дальше и рассматривать частотность пар букв. Согласно расчётам вероятности пар составляют 272=729, и эти вероятности означают энтропию H 2 (на одну букву, не на одну пару), равную приблизительно 3,3.
Если далее рассматривать вероятность (частотность) троек букв, то 273=19683 троек, то получится значение энтропии H 3, которая приблизительно равна 3,1 бит. Шеннон сумел приблизительно оценить H 5 » 2,1 бит, H 8 » 1,9 бит. Аналогичные исследования для русского языка дают H 2(r)=3,52 бит; H 3(r)=3,01 бит.
Эти данные дают оценки значения средней информации на один знак при существующей зависимости рядом стоящих букв I 0, I 1, I 2 …
Сообщения (а также источники, их порождающие), в которых существуют статистические связи (корреляции) между знаками или их сочетаниями, называются сообщениями (источниками) с памятью или марковскими сообщениями (источниками)
Распространим эту мысль на бесконечное число корреляций. Тогда можно оценить предельную информацию на один знак в конкретном языке I µ, которая будет отражать минимальную неопределённость, связанную с выбором знака алфавита без учёта семантических особенностей языка. I0 вычисляется без учёта зависимости между буквами и характеризует наибольшую информацию, которая может содержаться в знаке данного алфавита. Шеннон ввёл величину, которую назвал относительной избыточностью языка:
По аналогии с величиной R, характеризующей избыточность языка, можно ввести относительную избыточность кода (Q):
Если исходное сообщение содержит I(A) информации, а закодированное - I(B), то относительная избыточность кода (Q):
где 
– средняя длина кода (кодовых слов).
В случае двоичного кодирования формула приобретает вид:
где 
– средняя длина двоичного кода (двоичных кодовых слов).
Избыточность является мерой бесполезно совершаемых альтернативных выборов при чтении текста. Эта величина показывает, какую долю лишней информации содержат тексты данного языка; лишней в том отношении, что она определяется структурой самого языка и, следовательно, может быть восстановлена без явного указания в буквенном виде.
Исследования Шеннона для английского языка дали значение I µ»1,4¸1,5 бит, что по отношению к I 0=4,755 бит создаёт избыточность около 0,68. Подобные оценки показывают, что и для других европейских языков, в том числе русского, избыточность составляет 60 – 70 %. Это означает, что в принципе возможно почти трёхкратное (!) сокращение текстов без ущерба для их содержательной стороны и выразительности. Именно избыточность языка позволяет легко восстановить текст, даже если он содержит большое число ошибок или неполон.
Алфавитное неравномерное кодирование
Двоичное неравномерное кодирование с использованием разделителей
Возможны различные варианты двоичного кодирования, однако не все они будут пригодны для практического использования – важно, чтобы закодированное сообщение могло быть однозначно декадировано, т.е. чтобы в последовательности 0 и 1, которая представляет собой многобуквенное кодированное сообщение, всегда можно было бы различить обозначения отдельных букв. Проще всего этого достичь, если коды будут разграничены разделителем – некоторой постоянной комбинацией двоичных знаков.
Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов – 000 (признак конца слова – пробел). Примем следующие правила построения кодов:
· код признака конца знака может быть включён в код буквы, поскольку не существует отдельно (т.е. коды всех букв будут заканчиваться на 00);
· коды букв не должны содержать двух и более нулей в середине (иначе они будут восприниматься как конец знака);
· код буквы (кроме пробела) всегда должен начинаться с 1;
· разделителю слов (000) всегда предшествует признак конца знака; при том реализуется последовательность 00000 (т.е. если в конце кода встречается комбинация …000 или …0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака)
Пример:
| Буква | Код | p i *103 |
| пробел | ||
| о | ||
| е | ||
| а | ||
| и |
Дата добавления: 2014-12-19; просмотров: 89 | Поможем написать вашу работу | Нарушение авторских прав |