Алгоритм на псевдокоде

Кодирование интервальным кодом

Обозначим

code – массив кодовых слов для записи числа l(X_i)

s_in – строка для кодирования

s_out – результат кодирования

l:=<длина s_in>

DO (i=1,…l)

t:=0

found:=нет

DO (j=i-1,…,i-W)

t:=t+1

IF (j>0) и (s_in[i]=s_in[j])

s_out:=s_out+code[t]

found:=да

OD

FI

OD

IF (not found) s_out:=s_out+code[n]+s_in[i] FI

OD

6.4 Частотный код

В 1990 году Б. Я. Рябко предложил алгоритм кодирования, использующий алфавитный код Гилберта-Мура, и названный частотным. Частотный код относится к адаптивным методам сжатия с постоянной избыточностью. Средняя длина кодового слова для этого метода определяется только длиной окна, по которому оценивается статистика кодируемых данных, к тому же частотный код имеет достаточно высокую скорость кодирования и декодирования.

Рассмотрим алгоритм построения частотного кода для источника с алфавитом А={a₁, a₂, ..., a_n}. Пусть используется окно длины W, т.е. при кодировании символа x_i исходной последовательности учитываются W предыдущих символов:

Возьмем размер окна такой, что W=(2^r - 1)·n, где n=2^k - размер исходного алфавита, r, k - целые числа.

Порядок построения кодовой последовательности следующий:

1. Сначала оценивается число встреч в окне x_i-W...x_i-1 всех букв исходного алфавита. Обозначим эти величины через P(a_j), j=1,…,n

2. P(a_j) увеличивается на единицу и обозначается как

3. Вычисляются суммы Q_i , i=1,…,n

…

4. Для кодового слова символа а_j беретсяk знаков от двоичного разложения Q_j, где .

5. Далее окно сдвигается на один символ вправо и для кодирования следующего символа алгоритм вновь повторяется.

Пример. Пусть А={a₁, a₂, a₃, a₄}, длина окна W=4. Необходимо закодировать последовательность символов

Построим кодовое слово для символа а₃ .

1. Оценим частоты встреч в текущем "окне" всех символов алфавита:

2. Вычислим суммы Q_j :

Q₁ = 1

Q₂ = 1 + 0.5 = 1.5

Q₃ = 1 + 1 + 2 = 4

Q₄ = 1 + 1 + 4 + 1 = 7

3. Определим длину кодового слова для а₃:

k = 1 + log (4+4) - ëlog 4û = 1 + 3 - 2 = 2

4. Двоичное разложение Q₃ =100₂ , берем первые 2 знака. Таким образом, для текущего символа а₃ кодовое слово 10.