Десятичная упаковка
предназначена для упаковки символьных данных, состоящих только из чисел. Вместо используемых 8 бит под символ можно вполне рационально использовать всего лишь 4 бита для десятичных и шестнадцатеричных цифр, 3 бита для восьмеричных и т.д. При подобном подходе уже ощущается сжатие минимум 1:2.
Три в одном (упаковка байта)
Даны три целых неотрицательных числа: B, G, C. Число B равно нулю или единице, число G находится в диапазоне от 0 до 7, а число C – в диапазоне от 0 до 15. Составить из них число A так, что старший бит его двоичного представления равен B, три следующих бита составляют число G, а младшие четыре бита – число C. Например, если B = 1, G = 3, C = 14, то A = 190.
Input:одна строка, содержащая три неотрицательных целых числа B, G, C через пробел.
Output: одна строка, содержащая число A.
Example:
| Input | Output |
| 1 3 14 |
Решение.
var a,b, g,c:byte;
begin
readln(b,g,c);
a:=128*b+g*16+c;
writeln(a);
end.
Компандирование
Так называется метод упаковки звука. Название происходит от английского compander, что означает comp ressing/exp and ing coder/decod er. При упаковке звука значение амплитуды звука заменяют логарифмом этого значения, округляют и упаковывают полученные значения, что позволяет сжать информацию в два раза. Действительно, при 8-ми битном кодировании звука амплитуда A не превосходит 27, значит, log2 A не превосходит 7 и может быть закодирован тремя двоичными разрядами. Еще один разряд на знак амплитуды и получается четыре разряда.
Итак, Вам предлагается реализовать следующий алгоритм. Даны два целых числа в диапазоне от –32768 до 32767 – амплитуды звука. Требуется упаковать их оба в слово – беззнаковое двухбайтовое число. При упаковке дробная часть логарифма отбрасывается, если амплитуда представлялась отрицательным числом, добавляем единицу, иначе ноль. После преобразования упаковываем в два байта. И наоборот.
Решение
function log(a:longint):byte;
var l:real;t:longint;
begin
l:=ln(a)/ln(2);
t:=trunc(l);
log:=byte(t)
end;
function sig(a:integer):byte;
begin
if a>=0 then sig:=0;
if a<0 then sig:=1;
end;
function make_byte(a:integer):byte;
var l:byte;
begin
l:=log(abs(a));
if sig(a)=1 then l:=l+128;
make_byte:=l
end;
var a1, a2:integer;
l1, l2:integer;
c:word;
begin
readln(a1,a2);
c:=(word(make_byte(a1)) shl 8);
c:=c+make_byte(a2);
writeln(c)
end.
- Относительное кодирование является кодированием с потерей качества. Оно основано на том, что последующий элемент данных отличается от предыдущего на величину, занимающую в памяти меньше места, чем сам элемент. Характерным примером является аудиосжатие ADPCM (Adaptive Differencial Pulse Code Modulation), широко применяемое в цифровой телефонии и позволяющее сжимать звуковые данные в соотношении 1:2 с практически незаметной потерей качества.
- Символьное подавление - способ сжатия информации, при котором длинные последовательности из идентичных данных заменяются более короткими.
Применение RLE
Очевидно, что кодирование RLE эффективно для данных, содержащих большое количество серий, например, для простых графических изображений, таких как иконки и графические рисунки. Однако это кодирование плохо подходит для изображений с плавным переходом тонов, таких как фотографии.
Методом кодирования длин серий могут быть сжаты произвольные файлы с двоичными данными, поскольку спецификации на форматы файлов часто включают в себя повторяющиеся байты в области выравнивания данных.
Звуковые данные, которые имеют длинные последовательные серии байт (такие как низкокачественные звуковые семплы) могут быть сжаты с помощью RLE после того, как к ним будет применено Дельта-кодирование.
Алгоритм на Паскале (Delphi) для практического занятия
function encode(s:string):string;var i,j:integer; newS:string;begin i:=1; while i <= length(s) do begin j:=i; while (s[i] = s[j+1]) do inc(j); if (j-i = 0) or (j-i = 1) or (j-i =2) then begin newS:= newS + s[i]; if (s[i]='0') then newS:=newS+'0'; inc(i); end else begin newS:= newS + inttostr(j-i+1) + s[i]; inc(i,j-i+1); end; end; result:= newS;end; function decode(s:string):string;var i,j,c:integer; newS:string; dp: string;begini:=1;while i <= length(s) do begin j:=i; while s[j] in ['0'..'9'] do inc(j); if j-i > 0 then begin dp:= copy(s,i,j-i); for c:=1 to strtoint(dp) do newS:= newS + s[j]; delete(s,i,j-i+1); end else begin newS:= newS + s[i]; inc(i); end; end; result:= newS; end;- Статистическое кодирование основано на том, что не все элементы данных встречаются с одинаковой частотой (или вероятностью). Коды выбираются так, чтобы наиболее часто встречающемуся элементу соответствовал код с наименьшей длиной, а наименее частому - с наибольшей. Кроме этого, коды подбираются таким образом, чтобы при декодировании можно было однозначно определить элемент исходных данных. При таком подходе возможно только бит-ориентированное кодирование, при котором выделяются разрешённые и запрещённые коды. Если при декодировании битовой последовательности код оказался запрещённым, то к нему необходимо добавить ещё один бит исходной последовательности и повторить операцию декодирования. Примерами такого кодирования являются алгоритмы Шеннона и Хафмана.
Кодирование Хаффмана
Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).
Симаков Александр, xander@online.ru Сыктывкарский Государственный Университет
Кафедра Прикладной Математики
13 ноября 2002 год https://www.codenet.ru/progr/alg/huffcode.php
Ошибки при передаче информации
Биты четности
Дано число i (целое без знака). Определить, сколько единиц в его двоичном представлении.
1 способ – очевидный: перевести в двоичную систему счисления (представить, например, строкой) и подсчитать количество единиц.
2 способ – в цикле пока число больше 0 смотреть последний бит числа и уменьшать число в два раза
3 способ – уменьшать число, убирая крайнюю справа единицу в двоичной записи числа
Алгоритм следующий:
cnt:=0; //cnt - счетчик единиц в i.
while (i<>0) do // цикл повторяется число раз, равное числу единиц в i.
begin
i:=(i-1) and i; //"Убираем" крайнюю справа единицу в двоичной записи числа.
cnt:=cnt+1;
end;
Пример:
110 = i
101 = i-1
100 = i and (i-1)
Уоррен, Генри, С. Алгоритмические трюки для программистов. – М.: Издательский дом «Вильямс», 2003. – 288 с.:ил.