Методы оптимального кодирования. Сжатие данных.
Процедуру оптимального кодирования часто называют сжатием данных. Тогда задача сжатия данных есть минимизация технических затрат на хранение или передачу информации путем оптимального кодирования. На практике используют два вида сжатия данных:
1.Сжатие без потерь - устранение избыточности информации, не связанное с ее изменением, принципиально существенным для пользователя.
2. Сжатие с потерями – устранение избыточности информации, которое приводит к безвозвратной потере некоторой доли информации, хотя это не принципиально для ее восстановления в интересах пользователя.
Сжатие без потерь наиболее применимо к числовым и текстовым данным. Применительно к вычислительной технике сжатие позволяет уменьшить количество бит информации, необходимого для хранения и передачи заданного объема этой информации, что дает возможность передавать сообщения более быстро или хранить более экономно. Такие программные средства, реализующие сжатие, называют архиваторами. Существует достаточно большое их разнообразие.
Методы сжатия данных были разработаны как математическая теория, которая до первой половины 80-х годов 20 века мало использовалась в компьютерной технике.
Методы или алгоритмы сжатия данных без потерь можно разделить на:
1.Статистические методы или алгоритмы. Например, методы Шеннона - Фано, Хаффмана и др.
Они базируются на априорной статистике (вероятностях появления букв алфавита). Это главный недостаток таких кодов, так как априорная статистика кодов заранее не известна, а, следовательно, эффективному кодированию должен предстоять так называемый частотный анализ, т.е. анализ частоты появления символов в кодовой комбинации.
2.Адаптивные методы или алгоритмы. Например, модифицированные коды Хаффмана, арифметическое кодирование и др.
Здесь распределение вероятностей символов сначала считается равномерным на заданном интервале, а потом оно меняется по мере накопления статистики.
3.Динамические методы или алгоритмы. Они являются универсальными и не нуждаются в априорной статистике. Например, метод Лемпела- Зива.
Метод кодирования Шеннона - Фано.
Буквы исходного алфавита записываются в порядке убывания их вероятностей. Это множество разбивается так, чтобы вероятности двух подмножеств были примерно равны. Все буквы верхнего подмножества в качестве первого символа кода получают 1, а буквы нижнего подмножества-0. Затем последнее подмножество снова разбивается на два подмножества с соблюдением того же условия и проводят то же самое присвоение кодовым элементам второго символа. Процесс продолжается до тех пор, пока во всех подмножествах не останется по одной букве кодового алфавита.
Пример.
Буква xi |
Вероятности pi |
Кодовая последовательность |
Длина кодового слова ni |
pini |
-pilog2pi |
|||
Номер разбиения |
||||||||
1 |
2 |
3 |
4 |
|||||
x1 |
0,25 |
1 |
1 |
|
|
2 |
0,5 |
0,5 |
x2 |
0,25 |
1 |
0 |
|
|
2 |
0,5 |
0,5 |
x3 |
0,15 |
0 |
1 |
1 |
|
3 |
0,45 |
0,4 |
x4 |
0,15 |
0 |
1 |
0 |
|
3 |
0,45 |
0,4 |
x5 |
0,05 |
0 |
0 |
1 |
1 |
4 |
0,2 |
0,2 |
x6 |
0,05 |
0 |
0 |
1 |
0 |
4 |
0,2 |
0,2 |
x7 |
0,05 |
0 |
0 |
0 |
1 |
4 |
0,2 |
0,2 |
x8 |
0,05 |
0 |
0 |
0 |
0 |
4 |
0,2 |
0,2 |
=
=
(0,25*2+0,25*2+0,15*3+0,15*3+0,05*4+0,05*4+0,05*4+0,15*4)=2,7 бит
=
- (2*0,25*log2
0,25 + 2*0,15*log2
0,15 + 4*0,05*log20,05)
= 2,7 бит
=
1
Метод Шеннона - Фано не всегда приводит к однозначному построению кода, так как при разбиении на подмножества можно сделать большей по вероятности как верхнюю, так и нижнюю часть, следовательно, такое кодирование хотя и является эффективным, но не всегда будет оптимальным.