Кодирование информации как основа уменьшения объема информационного массива

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Сжатие информации - проблема, имеющая достаточно давнюю историю, гораздо более давнюю, нежели история развития вычислительной техники, которая (история) обычно шла параллельно с историей развития проблемы кодирования и шифровки информации.

Все алгоритмы сжатия оперируют входным потоком информации, минимальной единицей которой является бит, а максимальной - несколько бит, байт или несколько байт.

Целью процесса сжатия, как правило, есть получение более компактного выходного потока информационных единиц из некоторого изначально некомпактного входного потока при помощи некоторого их преобразования.

Кодировщик переделывает символ на входе в код на выходе, используя вероятности символов, которые поставляет ему моделировщик. В данной статье речь пойдет о двух самых распространенных и известных методах кодирования информации во время сжатия: кодирование Хаффмана (Huffman) и арифметическое кодирование и его разновидности.

Кодирование Хаффмана.

Этот метод кодирования появился очень давно и получил широкое распространение из-за простоты реализации и высокой скорости. Метод не требует огромных вычислительных мощностей в отличие от арифметического кодирования, производящего целочисленные умножения и деления. На заре компьютерной эры метод оказался простым в применении.

Для работы алгоритма необходимо иметь таблицу значений вероятностей различных символов, которые могут встретиться в данный момент кодирования (в данном месте обрабатываемого текста, где кодер в данный момент будет кодировать очередной символ).

На основе этой таблицы строится бинарное дерево Хаффмана следующим образом:

1. Отсортировать символы по возрастанию вероятности их появления.

2. Первые два символа в получившемся ряде объединить в один, сопоставив первому символу ноль, второму символу - единицу. Вероятности этих двух символов сложить.

3. Если в ряде остался один символ, то закончить, иначе перейти к пункту 1.

Пример построения дерева.

Предположим, что мы имеем алфавит из 8 символов. Подпрограмма, осуществляющая моделирование задает нам следующие возможные вероятности этих символов: A - 7%, B - 13%, C - 2%, D - 28%, E - 14%, F - 22%, G - 10%, H - 4%.

Сортируем символы по возрастанию вероятности: C - 2%, H - 4%, A - 7%, G - 10%, B - 13%, E - 14%, F - 22%, D - 28%.

Левые два объединяем в один: CH - 6%, A - 7%, G - 10%, B - 13%, E - 14%, F - 22%, D - 28%.

В данном случае сортировка не требуется. Заметим также, что для символа C теперь появился код 0, для H - 1. Эти символы находятся в самом низу кроны дерева Хаффмана (дерево растет вниз, т.е. крона его внизу), и к ним впоследствии будут добавлены новые узлы дерева, которые будут стоять выше. Пока же дерево выглядит следующим образом:

Рис. 1

Снова объединяем два левых символа в один: CHA - 13%, G - 10%, B - 13%, E - 14%, F - 22%, D - 28%.

После сортировки получим: G - 10%, CHA - 13%, B - 13%, E - 14%, F - 22%, D - 28%.

Дерево выглядит следующим образом:

Рис. 2

Когда мы обработаем все символы дерево примет вид:

Рис. 3

кодирование информационный бинарный

Теперь, чтобы закодировать любой символ нужно пройти от корня дерева до символа запоминая биты, определяющие направление движения. Коды символов получились следующие: A - 1111, B - 000, C - 11100, D - 01, E - 001, F - 10, G - 110, H - 11101.

Таким образом, самые вероятные символы: D и F имеют наименьшую длину кода: 2 бита, а менее вероятные символы имеют коды большей длины. Все коды уникально идентифицируют символ, т.е. из кода можно получить исходный текст в полном объеме.

Недостаток метода Хаффмана.

Основным и, возможно, единственным существенным недостатком этого метода кодирования является то, что он кодирует символы с помощью целого количества бит, что снижает степень сжатия и сводит на нет точное предсказание вероятностей, которое дают некоторые отличные современные алгоритмы моделирования.

Представим себе, что символ встречается в тексте с 99% вероятностью. Метод Хаффмана присвоит этому символу код 1, длиной в 1 бит. Имея файл размером 1 Мбайт, сжат он будет до 1 бит/байт, т.е. до 128 Кбайт, хотя сжать его можно гораздо эффективней: буквально до нескольких сот байт! Арифметическое кодирование лишено этого недостатка [1].

Арифметическое кодирование.

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

Таблица накопительных счетчиков устроена так, что частота появления N + 1 - го символа алфавита равна разности его счетчика и счетчика N - го символа. Другими словами, если мы имеем алфавит из 8 символов с частотами 7, 9, 2, 16, 22, 14, 11 и 55 соответственно, то таблица накопительных счетчиков будет следующей: 7, 16, 18, 34, 56, 70, 81, 136.

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

Принцип кодирования.

Для кодирования символов необходимо разбить полуинтервал [0; 1] на части. Каждая часть символизирует частоту повторения символа таким образом, что отношение длины интервала символа к длине всего интервала численно равно величине вероятности. Для примера возьмем алфавит из четырех символов с частотами: 23, 16, 82 и 5. Разделим интервал в соответствии с вероятностями этих символов на четыре подинтервала: [0, 0.1825], [0.1825, 0.3095], [0.3095, 0.9604] и [0.9604, 1]. Ширина третьего интервала самая большая т.к. третий символ наиболее вероятен.

Для кодирования задаются два числа - левый и правый края текущей области в интервале, которые сначала имеют значения 0 и 1 соответственно. При кодировании текущая область интервала сужается с каждым новым закодированным символом следующим образом:

Li = Li - 1 + Rng i - 1 * li

Hi = Hi - 1 - Rngi - 1 * (1 - hi)

Здесь L и H - границы текущей области интервала на соответствующем шаге, Rng - ширина текущей области на том же шаге, l и h - соответственно нижняя и верхняя границы интервала кодируемого символа.

Когда кодирование всех символов сообщения будет закончено числа L и H нужно записать в выходной поток, они и будут закодированным сообщением. Замечу, что оба числа записывать необязательно: для декодирования достаточно записать число, принадлежащее этому интервалу. Запись сообщения производится тем количеством бит, которое необходимо для представления числа с получившейся точностью, т.о. чем больше сообщение, тем с большей точностью необходимо записывать эти числа, увеличивая длину выходного сообщения.

Реализация кодирования.

Операции с дробными числами в реализации на компьютере не совсем удобны, да и длина дробного числа ограничена четырьмя или восемью байтами. Для кодирования используют целые числа, а умножение заменяют последовательным умножением и делением, чтобы не вызвать переполнение разрядной сетки.

Также в компьютерной реализации арифметического кодирования применяют масштабирование текущего интервала, путем его расширения, если длина интервала становится меньше какого-либо значения. Расширение основано на наблюдении, что начиная с какого-то закодированного символа ширина интервала изменяется незначительно и уже не может выйти за определенные рамки.

Например, если обе границы текущего интервала (верхняя и нижняя) находятся в меньшей [0, 0.5] половине единичного интервала, то они уже никак не смогут попасть в верхнюю, так как интервал может сужаться только внутрь. В данном случае можно записать в выходной поток первый, уже известный бит числа, которое должно быть сформировано на выходе и расширить интервал, растянув нижнюю половину интервала в два раза. Далее с растянутым интервалом работают как с начальным [2].

Range - кодирование.

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

Быстрое кодирование.

Быстрое кодирование обладает недостатком, присущим алгоритму Хаффмана, но позволяет не производить сортировку таблицы символов по частоте их встречаемости. Быстрота достигнута путем замены умножения битовыми сдвигами, т.е. в данном случае используется только умножение и деление на степень двойки.

Ширина интервала в данном случае округляется в большую сторону до ближайшей степени двойки, из-за чего становится возможным значительно ускорить алгоритм, но плата в данном случае - снижение степени сжатия из-за потери точности, в некоторых случаях очень существенной. Этот алгоритм следует рассматривать как альтернативу алгоритму Хаффмана.

Метод Хаффмана широко используется, но постепенно вытесняется арифметическим сжатием. Свою роль в этом сыграло то, что закончились сроки действия патентов, ограничивающих использование арифметического сжатия. Кроме того, алгоритм Хаффмана не является оптимальным. Он приближает относительные частоты появления символа в потоке частотами, представляющими собой отрицательные степени двойки, в то время как арифметическое сжатие дает лучшую степень приближения частоты.

Список литературы

1. Винокуров И.В. Классификация и кодирование информации.

2. Елинова Г.Г. Информационные технологии в профессиональной деятельности: краткий курс лекций. Оренбург ГОУ ОГУ, 2004. - 39 с.

3. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ XXI ВЕКА Абхалимова Р.С., Шарафутдинов А.Г. Экономика и социум. 2014. № 2-5 (11). С. 234-236.

4. ОСОБЕННОСТИ ФУНКЦИОНИРОВАНИЯ ЛИЧНЫХ ПОДСОБНЫХ ХОЗЯЙСТВ В РЕГИОНАЛЬНЫХ АГРАРНЫХ КЛАСТЕРАХ

5. Шарафутдинов А.Г.В сборнике: Актуальные вопросы экономико-статистического исследования и информационных технологий сборник научных статей: посвящается 40-летию создания кафедры "Статистики и информационных систем в экономике". МСХ РФ, Башкирский государственный аграрный университет. Уфа, 2011. С. 129-131.

Размещено на Allbest.ru