Содержание
- 2. Общая схема кодирования в LZ-методах При кодировании сообщение разбивается на слова переменной длины. При обработке очередного
- 3. При декодировании по принятому коду определяется закодированное слово. В случае получения специального символа, сигнализирующего о передаче
- 4. По способу организации хранения и поиска слов словарные методы можно разделить на две большие группы: алгоритмы,
- 5. Алгоритмы класса LZ отличаются: размерами окна; способами кодирования слов; алгоритмами обновления словаря и т.п. Все указанные
- 6. Кодирование с использованием скользящего окна Рассмотрим основные этапы кодирования сообщения Х=х1х2х3х4…, которое порождается некоторым источником информации
- 7. Если символ х1 найден, то осуществляется поиск в окне слова х1х2, начинающегося с этого символа. Если
- 8. Пример. Пусть алфавит источника А={а, b, с}, длина окна W=6. Необходимо закодировать исходное сообщение bababaabacabac. После
- 9. - Далее окно сдвигаем на 3 символа вправо и ищем в окне букву с. Ее нет
- 10. Кодирование последовательности bababaabacabac
- 11. Кодирование с использованием адаптивного словаря В этих словарных методах для хранения слов используется адаптивный словарь, заполняющийся
- 12. Пример. Пусть алфавит источника А={а, b, с}, размер словаря V=8. Необходимо закодировать исходное сообщение abababaabacabac. 1.
- 13. 2. Читаем первые две буквы ab, ищем слово ab в словаре. Этого слова нет, поэтому поместим
- 14. 3. Далее читаем букву a и ищем в словаре слово ba. Этого слова нет, поэтому запишем
- 15. 4. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке
- 16. 5. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке
- 17. 6. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке
- 18. Если словарь заполняется до окончания кодирования, то можно записывать новые слова в словарь, начиная со строки
- 19. 8. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке
- 20. 9. Закодируем букву с кодом 010. Конец входной последовательности. Таким образом, входное сообщение будет закодировано так:
- 21. Алгоритм на псевдокоде Кодирование с адаптивным словарем Обозначим: CurCode – текущий код PrevCode – предыдущий код
- 22. S:=9; L:=0; DicPos:=257 (256+конец сжатия) DO (not EOF) CurCode:=Read( ) (читаем следующий байт из файла) M[L]:=CurCode;
- 23. Рассмотрим теперь на примере ранее закодированного сообщения abababaabacabac (алфавит источника А={а, b, с}, размер словаря V=8)
- 24. 3. Читаем следующий код 001, по коду найдем в словаре букву b. Получим новое слово ab,
- 25. 5. Читаем код 101, такого кода нет в словаре. Тогда добавляем к слову ab первую букву
- 26. 7. Читаем код 010, по коду находим в словаре букву с, добавляем букву с к предыдущему
- 27. 9. Читаем код 010, по коду находим в словаре букву с, добавляем букву с к предыдущему
- 28. Алгоритм на псевдокоде Декодирование с адаптивным словарем Обозначим: CurCode – текущий код PrevCode – предыдущий код
- 29. S:=9; L:=0; DicPos:=257 DO CurCode:=Read(S) (читаем из файла S бит) IF (CurCode=256) break FI IF (C[CurCode]
- 31. Скачать презентацию