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

Кодирование с адаптивным словарем

Обозначим

CurCode – текущий код

PrevCode – предыдущий код

M – массив, содержащий текущую последовательность

L – длина текущей последовательности

C – словарь (массив строк)

S – текущая длина кода

DicPos – количество последовательностей в словаре

<Инициализация словаря символами исходного алфавита>

S:=9; L:=0; DicPos:=257 (256+конец сжатия)

DO (not EOF)

CurCode:=Read( ) (читаем следующий байт из файла)

M[L]:=CurCode; L:=L+1

IF (текущая последовательность найдена в словаре)

CurCode:=номер найденной последовательности

ELSE

C[DicPos]:=M; DicPos:=DicPos+1

IF (log(DicPos)+1)>S S:=S+1 FI (использовать соотношение п.6.1)

Write(PrevCode,S) (пишем в выходной файл S бит PrevCode)

M[0]:=CurCode; L:=1

FI

PrevCode:=CurCode

OD

Write(PrevCode,S) (сохраняем оставшийся код)

Write(256,S) (конец сжатия)

Рассмотрим теперь на примере ранее закодированного сообщения abababaabacabac (алфавит источника А={а, b, с}, размер словаря V=8) процесс декодирования. Закодированная последовательность имела такой вид

1. Запишем символы алфавита А в словарь, каждому символу припишем кодовое слово длины L = élog₂Vù = élog₂8ù = 3. (Процесс заполнения словаря будет таким же, как и при кодировании.)

2. Читаем первые три бита кодовой последовательности (код 000), по коду найдем в словаре букву а.

3. Читаем следующий код 001, по коду найдем в словаре букву b. Получим новое слово ab, которого нет в словаре, поместим слово ab в свободную 3-ю строку словаря. На выход декодера передаем букву а, букву b запоминаем.

4. Читаем код 011, по коду находим в словаре слово ab. Добавляем первую букву а к предыдущему декодированному слову b, получим слово ba, его нет в словаре. Поместим слово ba в свободную 4-ю строку словаря. На выход декодера передаем букву b, слово ab запоминаем.

5. Читаем код 101, такого кода нет в словаре. Тогда добавляем к слову ab

первую букву этой же последовательности – а, получим слово aba, его нет в словаре. Поместим слово aba в свободную 5-ю строку словаря. На выход декодера передаем слово ab, слово aba запоминаем.

6. Читаем код 101, по коду находим в словаре слово aba, добавляем первую букву a к предыдущему декодированному слову aba, получим abaa. Добавим слово abaa в словарь в свободную 6-ю строку. На выход декодера передаем слово aba , и слово aba запоминаем.

7. Читаем код 010, по коду находим в словаре букву с, добавляем букву с к предыдущему декодированному слову aba, получим abac. Добавим слово abaс в словарь в свободную 7-ю строку. На выход декодера передаем слово aba , букву с запоминаем.

8. Читаем код 101, по коду находим в словаре слово aba, добавляем первую букву а к предыдущей декодированной букве с, получим слово са.

Так как словарь заполнился до окончания декодирования, то будем записывать новые слова в словарь, начиная со строки с наибольшим номером, удаляя ранее записанные там слова. Добавим слово са в 7-ю строку словаря вместо слова abac. На выход декодера передаем букву с, слово aba запоминаем.

9. Читаем код 010, по коду находим в словаре букву с, добавляем букву с к предыдущему декодированному слову aba, получим abac. Добавим слово abac в 6-ю строку словаря вместо слова abaа. На выход декодера передаем слово aba, букву с запоминаем.

10. На выход декодера передаем букву с.

В результате декодирования получим исходное сообщение