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

Кодирование кодом «Стопка книг»

Обозначим

code – массив кодовых слов для позиции «стопки»

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

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

S – строка, содержащая исходный алфавит

l:=<длина s_in>

DO (i=1,…l)

T:=<номер символа s_in[i] в строке S>

s_out:=s_out+code[t]

stmp:=S[t]

delete(S,t,1) (преобразование

insert(stmp,S,1) строки S)

OD

6.3 Интервальный код

Интервальный код был предложен П. Элиасом в 1987 году. В нем используется окно длины W, т.е. при кодировании символа x_i исходной последовательности учитываются W предыдущих символов:

При кодировании символа x_i определяется расстояние (интервал) до его предыдущей встречи в окне длины W. Обозначим это расстояние l(x_i). Если символ есть x_i в окне, то значение l(x_i) равно номеру позиции символа в окне. Позиции в окне нумеруются справа налево. Если символа x_i нет в окне, то l(x_i) присваивается значение W+1, а x_i кодируется словом, состоящим из l(x_i) и самого символа x_i. После кодирования очередного символа окно сдвигается вправо на один символ.

Пример.Рассмотрим описание кода для исходного алфавита A={a₁,a₂,a₃,a₄}, пусть длина окна W=3. Возьмем некоторый префиксный код для записи числа l(X_i):

Пусть кодируется последовательность а₁а₁а₂а₃а₂а₂… (см. рис. 12)

1. Сначала символа а₁ нет в окне, поэтому на выход кодера передается 111 и восьмибитовый ASCII-код символа а₁ Затем окно сдвигается на одну позицию вправо.

2. При кодировании следующего символа а₁ на выход кодера передается 0, так как теперь символ а₁ находится в первой позиции окна. Далее окно снова сдвигается на одну позицию вправо.

3. Следующий символ а₂ кодируется комбинацией 111 и восьмибитовым ASCII-кодом символа а₂, так как символа а₂ нет в окне. Окно снова сдвигается на одну позицию вправо.

4. Следующий символ а₃ кодируется комбинацией 111 и восьмибитовым ASCII-кодом символа а₃ , так как символа а₃ нет в окне. Окно снова сдвигается на одну позицию вправо.

5. Следующий кодируемый символ а₂ находим во второй позиции окна и поэтому кодируем комбинацией 10. Окно снова сдвигается на одну позицию вправо.

6. И последний символ а₂ находим во первой позиции окна и поэтому кодируем комбинацией 0. Таким образом, закодированное сообщение имеет следующий вид:

Рисунок 12 Кодирование интервальным кодом

При декодировании используется такое же окно, как и при кодировании. По принятому кодовому слову можно определить, в какой позиции окна находится данный символ. Если поступает код 111, то декодер считывает следующий за ним символ. Каждая декодированная буква полностью включается в окно.

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