8.1 Общая схема кодирования

Словарные коды класса LZ широко используются в практических задачах. На их основе реализовано множество программ-архиваторов. Эти методы также используются при сжатии изображений в модемах и других цифровых устройствах передачи и хранения информации.

Словарные методы сжатия данных позволяют эффективно кодировать источники с неизвестной или меняющейся статистикой. Важными свойствами этих методов являются высокая скорость кодирования и декодирования, а также относительно небольшая сложность реализации. Кроме того, LZ-методы обладают способностью быстро адаптироваться к изменению статистической структуры сообщений.

Словарные коды интенсивно исследуются и конструируются, начиная с 1977 года, когда появилось описание первого алгоритма, предложенного А. Лемпелом и Я. Зивом. В настоящее время существует множество методов, объединенных в класс LZ-кодов, которые представляют собой различные модификации метода Лемпела-Зива.

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

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

По способу организации хранения и поиска слов словарные методы можно разделить на две большие группы:

  • алгоритмы, осуществляющие поиск слов в какой-либо части ранее закодированного текста, называемой окном;
  • алгоритмы, использующие адаптивный словарь, который включает ранее встретившиеся слова. Если словарь заполняется до окончания процесса кодирования, то в некоторых методах он обновляется (на место ранее встретившихся слов записываются новые), а в некоторых кодирование продолжается без обновления словаря.

Алгоритмы класса LZ отличаются размерами окна, способами кодирования слов, алгоритмами обновления словаря и т.п. Все указанные факторы влияют и на характеристики этих методов: скорость кодирования, объем требуемой памяти и степень сжатия данных, различные для разных алгоритмов. Однако в целом методы из класса LZ представляют значительный практический интерес и позволяют достаточно эффективно сжимать данные с неизвестной статистикой.


8.2 Кодирование с использованием скользящего окна

Рассмотрим основные этапы кодирования сообщения , которое порождается некоторым источником информации с алфавитом A алгоритмом LZ с использованием скользящего окна.

Пусть используется окно длины W, т.е. при кодировании символа  исходной последовательности учитываются W предыдущих символов:

Сначала осуществляется поиск в окне символа . Если символ не найден, то в качестве кода передается  0  как признак того, что этого символа нет в окне и двоичное представление .

Если символ  найден, то осуществляется поиск в окне слова , начинающегося с этого символа. Если слово  есть в окне, то производится поиск слова , затем    и так далее, пока не будет найдено слово, состоящее из наибольшего количества входных символов в порядке их поступления. В этом случае в качестве кода передается 1 и пара чисел (i, j), указывающая положение найденного слова в окне (i – номер позиции окна, с которой начинается это слово, j – длина слова, позиции в окне нумеруются справа налево). Затем окно сдвигается на j символов вправо по тексту и кодирование продолжается.  Для кодирования чисел (i, j) могут быть использованы коды целых чисел.

Пример 8.2.1.  Пусть алфавит источника ,  длина окна W=6. Необходимо закодировать исходное сообщение bababaabacabac. (см. рис. 13)

После кодирования первых шести букв окно будет иметь вид bababa.

  • Далее проверяем наличие в окне буквы а. Она найдена, добавляем к ней b, ищем в окне ab. Эта пара есть в окне, добавляем букву а, ищем aba. Это слово есть в окне, добавляем букву с, ищем abac. Этого слова нет в окне, тогда кодируем aba кодовой комбинацией (1,3,3), где 1– признак того, что слово есть в «окне»,3– номер позиции в окне, с которой начинается это слово, 3– длина этого слова.
  • Далее окно сдвигаем на 3 символа вправо и  ищем в окне букву с. Ее нет в окне, поэтому кодируем  комбинацией (0, «с»), где 0– признак того, что буквы нет в окне, «с»– двоичное представление буквы. Окно сдвигаем на 1 символ вправо.
  • Ищем в окне букву а, она найдена, добавляем к ней b, ищем в окне ab. Эта пара есть в окне, добавляем букву а, ищем aba. Это слово есть в окне, добавляем букву с, ищем abac. Это слово есть в окне, тогда кодируем abaс кодовой комбинацией (1,4,4), где 1 – признак того, что слово есть в окне,4 – номер позиции в окне, с которой начинается это слово, 4 – длина этого слова.

 

Рисунок 13 Кодирование последовательности bababaabacabac


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

abaс      са

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

abaа   abaс

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

 

  1. Запишем символы алфавита А в словарь, каждому символу припишем кодовое слово длины . (Процесс заполнения словаря будет таким же, как и при кодировании.)
  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. На выход декодера передаем букву с.

 

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


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


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

Обозначим
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]