Словарные коды класса LZ - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Словарные коды класса LZ. Доклад-сообщение содержит 30 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Кодирование с использованием скользящего окна Кодирование с использованием скользящего окна Рассмотрим основные этапы кодирования сообщения Х=х1х2х3х4…, которое порождается некоторым источником информации с алфавитом А.

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

Пример. Пусть алфавит источника А={а, b, с}, длина окна W=6. Необходимо закодировать исходное сообщение bababaabacabac. Пример. Пусть алфавит источника А={а, b, с}, длина окна W=6. Необходимо закодировать исходное сообщение bababaabacabac. После кодирования первых шести букв окно будет иметь вид bababa. - Далее проверяем наличие в окне буквы а. Она найдена, добавляем к ней b, ищем в окне ab. Эта пара есть в окне, добавляем букву а, ищем aba. Это слово есть в окне, добавляем букву с, ищем abac. Этого слова нет в окне, тогда кодируем aba кодовой комбинацией (1,3,3), где 1– признак того, что слово есть в «окне», 3– номер позиции в окне, с которой начинается это слово, 3– длина этого слова.

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

Кодирование последовательности bababaabacabac Кодирование последовательности bababaabacabac

Слайд 11

Описание слайда:

Кодирование с использованием адаптивного словаря Кодирование с использованием адаптивного словаря В этих словарных методах для хранения слов используется адаптивный словарь, заполняющийся в процессе кодирования. Перед началом кодирования в словарь включаются все символы алфавита источника. При кодировании сообщения Х=х1х2х3х4… сначала читаются два символа х1х2, поскольку это слово отсутствует в словаре, то передается код символа х1 (обычно это номер строки, содержащей найденный символ или слово). В свободную строку таблицы записывается слово х1х2, далее читается символ х3 и осуществляется поиск в словаре слова х2х3. Если это слово есть в словаре, то проверяется наличие слова х2х3х4 и так далее. Таким образом, слово из наибольшего количества входных символов, найденное в словаре, кодируется как номер строки, его содержащей.

Слайд 12

Описание слайда:

Пример. Пусть алфавит источника А={а, b, с}, размер словаря V=8. Необходимо закодировать исходное сообщение abababaabacabac. Пример. Пусть алфавит источника А={а, b, с}, размер словаря V=8. Необходимо закодировать исходное сообщение abababaabacabac. 1. Запишем символы алфавита А в словарь, каждому символу припишем кодовое слово длины L = log2V = log28 =3.

Слайд 13

Описание слайда:

2. Читаем первые две буквы ab, ищем слово ab в словаре. Этого слова нет, поэтому поместим слово ab в свободную 3-ю строку словаря, а букву а закодируем кодом 000. 2. Читаем первые две буквы ab, ищем слово ab в словаре. Этого слова нет, поэтому поместим слово ab в свободную 3-ю строку словаря, а букву а закодируем кодом 000.

Слайд 14

Описание слайда:

3. Далее читаем букву a и ищем в словаре слово ba. Этого слова нет, поэтому запишем в 4-ю строку словаря слово ba, букву b закодируем кодом 001. 3. Далее читаем букву a и ищем в словаре слово ba. Этого слова нет, поэтому запишем в 4-ю строку словаря слово ba, букву b закодируем кодом 001.

Слайд 15

Описание слайда:

4. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba, его нет в словаре. Запишем слово aba в 5-ю строку словаря, и закодируем ab кодом 011. 4. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba, его нет в словаре. Запишем слово aba в 5-ю строку словаря, и закодируем ab кодом 011.

Слайд 16

Описание слайда:

5. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву а, получим слово abaа, его нет в словаре. Запишем слово abaа в 6-ю строку словаря, и закодируем abа кодом 101. 5. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву а, получим слово abaа, его нет в словаре. Запишем слово abaа в 6-ю строку словаря, и закодируем abа кодом 101.

Слайд 17

Описание слайда:

Слайд 18

Описание слайда:

Если словарь заполняется до окончания кодирования, то можно записывать новые слова в словарь, начиная со строки с наибольшим номером, удаляя ранее записанные там слова. Если словарь заполняется до окончания кодирования, то можно записывать новые слова в словарь, начиная со строки с наибольшим номером, удаляя ранее записанные там слова. 7. Читаем букву а, ищем в словаре слово са. Этого слова нет в словаре, поэтому запишем слово са в 7-ю строку словаря, удалив слово abас, и закодируем букву с кодом 010.

Слайд 19

Описание слайда:

8. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву с, получим слово abaс, его нет в словаре. Запишем слово abaс в 6-ю строку словаря, и закодируем abа кодом 101. 8. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву с, получим слово abaс, его нет в словаре. Запишем слово abaс в 6-ю строку словаря, и закодируем abа кодом 101.

Слайд 20

Описание слайда:

9. Закодируем букву с кодом 010. Конец входной последовательности. 9. Закодируем букву с кодом 010. Конец входной последовательности. Таким образом, входное сообщение будет закодировано так:

Слайд 21

Описание слайда:

Алгоритм на псевдокоде Алгоритм на псевдокоде Кодирование с адаптивным словарем Обозначим: CurCode – текущий код PrevCode – предыдущий код M – массив, содержащий текущую последовательность L – длина текущей последовательности C – словарь (массив строк) S – текущая длина кода DicPos – количество последовательностей в словаре

Слайд 22

Описание слайда:

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) (конец сжатия)

Слайд 23

Описание слайда:

Рассмотрим теперь на примере ранее закодированного сообщения abababaabacabac (алфавит источника А={а, b, с}, размер словаря V=8) процесс декодирования. Закодированная последовательность имела такой вид Рассмотрим теперь на примере ранее закодированного сообщения abababaabacabac (алфавит источника А={а, b, с}, размер словаря V=8) процесс декодирования. Закодированная последовательность имела такой вид 000001011101101010101010 1. Запишем символы алфавита А в словарь, каждому символу припишем кодовое слово длины L = log2V = log28 = 3. (Процесс заполнения словаря будет таким же, как и при кодировании.) 2. Читаем первые три бита кодовой последовательности (код 000), по коду найдем в словаре букву а.

Слайд 24

Описание слайда:

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

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

Алгоритм на псевдокоде Алгоритм на псевдокоде Декодирование с адаптивным словарем Обозначим: CurCode – текущий код PrevCode – предыдущий код M – массив, содержащий текущую последовательность L – длина текущей последовательности C – словарь (массив строк) S – текущая длина кода DicPos – количество последовательностей в словаре

Слайд 29

Описание слайда:

S:=9; L:=0; DicPos:=257 DO CurCode:=Read(S) (читаем из файла S бит) IF (CurCode=256) break FI IF (C[CurCode]0) (в словаре найдена послед-ть с номером СurCode) M[L]:=C[CurCode][0] (в конец текущей последовательности приписываем первый символ найденной последовательности) L:=L+1 ELSE M[L]:=M[0]; L:=L+1 FI

Слайд 30

Описание слайда:

IF (текущая последовательность М не найдена в словаре С) IF (текущая последовательность М не найдена в словаре С) Write(C[PrevCode]) C[DicPos]:=M (добавляем текущую послед-ть в словарь) DicPos:=DicPos+1 IF (log DicPos+1)>S S:=S+1 FI M:=C[CurCode] (в текущую послед-ть заносим L=длина слова слово сномером CurCode) FI PrevCode:=CurCode OD Write(C[PrevCode])