Теория информации |
Конспект лекций |
8. СЛОВАРНЫЕ КОДЫ КЛАССА LZ
8.3 Кодирование с использованием адаптивного словаря
В этих словарных методах для хранения слов используется адаптивный словарь, заполняющийся в процессе кодирования. Перед началом кодирования в словарь включаются все символы алфавита источника. При кодировании сообщения сначала читаются два символа
, поскольку это слово отсутствует в словаре, то передается код символа
(обычно это номер строки, содержащей найденный символ или слово). В свободную строку таблицы записывается слово
, далее читается символ
и осуществляется поиск в словаре слова
. Если это слово есть в словаре, то проверяется наличие слова
и т. д. Таким образом, слово из наибольшего количества входных символов, найденное в словаре, кодируется как номер строки его содержащей.
Пример 8.3.1. Пусть алфавит источника , размер словаря V. Необходимо закодировать исходное сообщение abababaabacabac.
1. Запишем символы алфавита A в словарь, каждому символу припишем кодовое слово длины
.
Номер строки |
Слово |
Код |
0 |
a |
000 |
1 |
b |
001 |
2 |
c |
010 |
3 |
– |
|
4 |
– |
|
5 |
– |
|
6 |
– |
|
7 |
– |
|
2. Читаем первые две буквы ab, ищем слово ab в словаре. Этого слова нет, поэтому поместим слово ab в свободную 3-ю строку словаря, а букву а закодируем кодом 000.
Номер строки |
Слово |
Код |
0 |
a |
000 |
1 |
b |
001 |
2 |
c |
010 |
3 |
ab |
011 |
4 |
– |
|
5 |
– |
|
6 |
– |
|
7 |
– |
|
3. Далее читаем букву a и ищем в словаре слово ba. Этого слова нет, поэтому запишем в 4-ю строку словаря слово ba, букву b закодируем кодом 001.
Номер строки |
Слово |
Код |
0 |
a |
000 |
1 |
b |
001 |
2 |
c |
010 |
3 |
ab |
011 |
4 |
ba |
100 |
5 |
– |
|
6 |
– |
|
7 |
– |
|
4. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba, его нет в словаре. Запишем слово aba в 5-ю строку словаря, и закодируем ab кодом 011.
Номер строки |
Слово |
Код |
0 |
a |
000 |
1 |
b |
001 |
2 |
c |
010 |
3 |
ab |
011 |
4 |
ba |
100 |
5 |
aba |
011 |
6 |
– |
|
7 |
– |
|
5. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву а, получим слово abaа, его нет в словаре. Запишем слово abaа в 6-ю строку словаря, и закодируем abа кодом 101.
Номер строки |
Слово |
Код |
0 |
a |
000 |
1 |
b |
001 |
2 |
c |
010 |
3 |
ab |
011 |
4 |
ba |
100 |
5 |
aba |
011 |
6 |
abaа |
101 |
7 |
– |
|
6. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву с, получим слово abaс, его нет в словаре. Запишем слово abaс в 7-ю строку словаря, и закодируем abа кодом 101. Если словарь заполняется до окончания кодирования, то можно записывать новые слова в словарь, начиная со строки с наибольшим номером, удаляя ранее записанные там слова.
Номер строки |
Слово |
Код |
0 |
a |
000 |
1 |
b |
001 |
2 |
c |
010 |
3 |
ab |
011 |
4 |
ba |
100 |
5 |
aba |
101 |
6 |
abaа |
110 |
7 |
abaс |
111 |
7. Читаем букву а, ищем в словаре слово са. Этого слова нет в словаре, поэтому запишем слово са в 7-ю строку словаря, удалив слово abас, и закодируем букву с кодом 010.
Номер строки |
Слово |
Код |
0 |
a |
000 |
1 |
b |
001 |
2 |
c |
010 |
3 |
ab |
011 |
4 |
ba |
100 |
5 |
aba |
101 |
6 |
abaа |
110 |
7 |
|
111 |
8. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву с, получим слово abaс, его нет в словаре. Запишем слово abaс в 6-ю строку словаря, и закодируем abа кодом 101.
Номер строки |
Слово |
Код |
0 |
a |
000 |
1 |
b |
001 |
2 |
c |
010 |
3 |
ab |
011 |
4 |
ba |
100 |
5 |
aba |
101 |
6 |
|
110 |
7 |
са |
111 |
9. Закодируем букву с кодом 010. Конец входной последовательности.
Таким образом, входное сообщение будет закодировано так
Алгоритм на псевдокоде
Кодирование с адаптивным словарем
Обозначим
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) (конец сжатия)
Пример 8.3.2 Рассмотрим теперь на примере ранее закодированного сообщения abababaabacabac (алфавит источника , размер словаря V=8) процесс декодирования. Закодированная последовательность имела такой вид
000001011101101010101010
В результате декодирования получим исходное сообщение
Алгоритм на псевдокоде
Декодирование с адаптивным словарем
Обозначим
CurCode – текущий код
PrevCode – предыдущий код
M – массив, содержащий текущую последовательность
L – длина текущей последовательности
C – словарь (массив строк)
S – текущая длина кода
DicPos – количество последовательностей в словаре
<Инициализация словаря символами исходного алфавита>
S:=9; L:=0; DicPos:=257
DO
CurCode:=Read(S) (читаем из файла S бит)
IF (CurCode=256) break FI
IF (C[CurCode]<>0) (в словаре найдена послед-ть с номером CurCode)
M[L]:=C[CurCode][0] (в конец текущей последовательности
приписываем первый символ найденной последовательности)
L:=L+1
ELSE M[L]:=M[0]; L:=L+1
FI
IF (текущая последовательность М не найдена в словаре С)
Write(C[PrevCode])
C[DicPos]:=M (добавляем текущую послед-ть в словарь)
DicPos:=DicPos+1
IF (log DicPos+1)>S S:=S+1 FI (использовать соотношение п.6.1)
M:=C[CurCode] (в текущую послед-ть заносим слово
L=длина слова с номером CurCode)
FI
PrevCode:=CurCode
OD
Write(C[PrevCode]