Алгоритм на псевдокоде
Частотный код
Обозначим
w – окно
W – размер окна
P – массив частот символов
Q – массив для величин Qi.
DO (i=1,…n) w[i]:=a[i] OD (заполняем окно символами алфавита)
DO (not EOF) (пока не конец входного файла)
DO (i=1,…,n) P [i]:=1 OD
DO (i=1,…,n) P [w[i]]:= P [w[i]] +1 OD (частоты встречи
символов в окне)
pr:=0
DO (i=1,…,n)
Q [i] := pr+ P [i] /2 (вычисляем суммы)
pr:=pr+ P [i]
OD
C:=Read( ) (читаем следующий символ из файла)
DO (j=1,…,n)
IF (C=a[i]) m:=j FI (определяем номер символа в алфавите)
OD
k = 1 + log2 (n+W) - ëlog2 P[m] û (длина кодового слова)
DO (j=1,…,k) (формирование кодового слова
Q [m]:=Q [m] *2 в двоичном виде)
code:= ëQ [m]û
IF (Q [m] >1) Q [m]:= Q [m] - 1 FI
OD
Write(code) (код символа – в выходной файл)
DO (i=0,…,n-1) w[i]:= w[i+1] OD
w[n]:=C (включаем в окно текущий символ)
OD
7. словарные коды класса Lz
Словарные коды класса LZ широко используются в практических задачах. На их основе реализовано множество программ-архиваторов. Эти методы также используются при сжатии изображений в модемах и других цифровых устройствах передачи и хранения информации.
Словарные методы сжатия данных позволяют эффективно кодировать источники с неизвестной или меняющейся статистикой. Важными свойствами этих методов являются высокая скорость кодирования и декодирования, а также относительно небольшая сложность реализации. Кроме того, LZ-методы обладают способностью быстро адаптироваться к изменению статистической структуры сообщений.
Словарные коды интенсивно исследуются и конструируются, начиная с 1977 года, когда появилось описание первого алгоритма, предложенного А. Лемпелом и Я. Зивом. В настоящее время существует множество методов, объединенных в класс LZ-кодов, которые представляют собой различные модификации метода Лемпела-Зива.
Общая схема кодирования, используемая в LZ-методах, заключается в следующем.При кодировании сообщение разбивается на слова переменной длины. При обработке очередного слова ведется поиск ему подобного в ранее закодированной части сообщения.Если слово найдено, то передается соответствующий ему код. Если слово не найдено, то передается специальный символ, обозначающий его отсутствие, и новое обозначение этого слова. Каждое новое слово, не встречавшееся ранее, запоминается, и ему присваивается индивидуальный код.
При декодировании по принятому коду определяется закодированное слово. В случае получения специального символа, сигнализирующего о передаче нового слова, принятое слово запоминается, и ему присваивается такой же, как и при кодировании, код. Таким образом, декодирование является однозначным, т.к. каждому слову соответствует свой собственный код.
По способу организации хранения и поиска слов словарные методы можно разделить на две большие группы:
· алгоритмы, осуществляющие поиск слов в какой-либо части ранее закодированного текста, называемой окном;
· алгоритмы, использующие адаптивный словарь, который включает ранее встретившиеся слова. Если словарь заполняется до окончания процесса кодирования, то в некоторых методах он обновляется (на место ранее встретившихся слов записываются новые), а в некоторых кодирование продолжается без обновления словаря.
Алгоритмы класса LZ отличаются размерами окна, способами кодирования слов, алгоритмами обновления словаря и т.п. Все указанные факторы влияют и на характеристики этих методов: скорость кодирования, объем требуемой памяти и степень сжатия данных, различные для разных алгоритмов. Однако в целом методы из класса LZ представляют значительный практический интерес и позволяют достаточно эффективно сжимать данные с неизвестной статистикой.
7.1 Кодирование с использованием скользящего окна
Рассмотрим основные этапы кодирования сообщения Х=х1х2х3х4…, которое порождается некоторым источником информации с алфавитом А. Пусть используется окно длины W, т.е. при кодировании символа xi исходной последовательности учитываются W предыдущих символов:
Сначала осуществляется поиск в окне символа х1. Если символ не найден, то в качестве кода передается 0 как признак того, что этого символа нет в окне и двоичное представление х1.
Если символ х1 найден, то осуществляется поиск в окне слова х1х2, начинающегося с этого символа. Если слово х1х2 есть в окне, то производится поиск слова х1х2х3 , затем х1х2х3х4 и так далее, пока не будет найдено слово, состоящее из наибольшего количества входных символов в порядке их поступления. В этом случае в качестве кода передается 1 и пара чисел (i, j), указывающая положение найденного слова в окне (i – номер позиции окна, с которой начинается это слово, j – длина этого слова, позиции в окне нумеруются справа налево). Затем окно сдвигается на j символов вправо по тексту и кодирование продолжается.
Для кодирования чисел (i, j) могут быть использованы рассмотренные ранее коды целых чисел.
Пример. Пусть алфавит источника А={а, b, с}, длина окна 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
7.2 Кодирование с использованием адаптивного словаря
В этих словарных методах для хранения слов используется адаптивный словарь, заполняющийся в процессе кодирования. Перед началом кодирования в словарь включаются все символы алфавита источника. При кодировании сообщения Х=х1х2х3х4… сначала читаются два символа х1х2, поскольку это слово отсутствует в словаре, то передается код символа х1 (обычно это номер строки, содержащей найденный символ или слово). В свободную строку таблицы записывается слово х1х2, далее читается символ х3 и осуществляется поиск в словаре слова х2х3. Если это слово есть в словаре, то проверяется наличие слова х2х3х4 и так далее. Таким образом, слово из наибольшего количества входных символов, найденное в словаре, кодируется как номер строки, его содержащей.
Пример. Пусть алфавит источника А={а, b, с}, размер словаря V=8. Необходимо закодировать исходное сообщение abababaabacabac.
1. Запишем символы алфавита А в словарь, каждому символу припишем кодовое слово длины L = élog2Vù = élog28ù =3.
| Номер строки | Слово | Код |
| a | ||
| b | ||
| c | ||
| – | ||
| – | ||
| – | ||
| – | ||
| – |
2. Читаем первые две буквы ab, ищем слово ab в словаре. Этого слова нет, поэтому поместим слово ab в свободную 3-ю строку словаря, а букву а закодируем кодом 000.
| Номер строки | Слово | Код |
| a | ||
| b | ||
| c | ||
| ab | ||
| – | ||
| – | ||
| – | ||
| – |
3. Далее читаем букву a и ищем в словаре слово ba. Этого слова нет, поэтому запишем в 4-ю строку словаря слово ba, букву b закодируем кодом 001.
| Номер строки | Слово | Код |
| a | ||
| b | ||
| c | ||
| ab | ||
| ba | ||
| – | ||
| – | ||
| – |
4. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba, его нет в словаре. Запишем слово aba в 5-ю строку словаря, и закодируем ab кодом 011.
| Номер строки | Слово | Код |
| a | ||
| b | ||
| c | ||
| ab | ||
| ba | ||
| aba | ||
| – | ||
| – |
5. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву а, получим слово abaа, его нет в словаре. Запишем слово abaа в 6-ю строку словаря, и закодируем abа кодом 101.
| Номер строки | Слово | Код |
| a | ||
| b | ||
| c | ||
| ab | ||
| ba | ||
| aba | ||
| abaа | ||
| – |
6. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву с, получим слово abaс, его нет в словаре. Запишем слово abaс в 7-ю строку словаря, и закодируем abа кодом 101. Если словарь заполняется до окончания кодирования, то можно записывать новые слова в словарь, начиная со строки с наибольшим номером, удаляя ранее записанные там слова.
| Номер строки | Слово | Код |
| a | ||
| b | ||
| c | ||
| ab | ||
| ba | ||
| aba | ||
| abaа | ||
| abaс |
7. Читаем букву а, ищем в словаре слово са. Этого слова нет в словаре, поэтому запишем слово са в 7-ю строку словаря, удалив слово abас, и закодируем букву с кодом 010.
| Номер строки | Слово | Код |
| a | ||
| b | ||
| c | ||
| ab | ||
| ba | ||
| aba | ||
| abaа | ||
| |
8. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву с, получим слово abaс, его нет в словаре. Запишем слово abaс в 6-ю строку словаря, и закодируем abа кодом 101.
| Номер строки | Слово | Код |
| a | ||
| b | ||
| c | ||
| ab | ||
| ba | ||
| aba | ||
| | ||
| са |
9. Закодируем букву с кодом 010. Конец входной последовательности.
Таким образом, входное сообщение будет закодировано так
Дата добавления: 2019-02-07; просмотров: 177;