Презентация на тему ""

Содержание

• 
  Слайд 1
  

  LZW: как данные сжимаются без потерь Словарный метод Алгоритм LZW — метод словарного сжатия информации. Замена кодами Он заменяет повторяющиеся последовательности символов короткими кодами. Без потерь Главное свойство: после распаковки исходные данные восстанавливаются полностью.

• 
  Слайд 2
  

  Зачем нужен алгоритм LZW При хранении и передаче данных важно уменьшить объём информации.

• 
  Слайд 3
  

  Идея словарногосжатия Исходная последовательность Содержит повторяющиеся фрагменты Заменить повторы Подставить короткие код-ссылки Создать словарь Добавить запись для повторяющегося фрагмента

• 
  Слайд 4
  

  Как формируется словарь LZW 1 Начальное состояние В начале словарь содержит все возможные исходные символы. 2 Просмотр строки Затем алгоритм просматривает строку слева направо и добавляет в словарь новые последовательности, которые встречаются во входных данных. 3 Числовые коды Каждой записи словаря соответствует числовой код.

• 
  Слайд 5
  

  Алгоритм сжатия пошагам Начать новую P Добавить/ Вывести Проверить PK Взять P и K 01 Взять P и K Взять текущую последовательность P и следующий символ K. 02 PK в словаре? Если PK уже есть в словаре, продолжить последовательность: P := PK. 03 Вывести код P Если PK отсутствует, вывести код последовательности P и добавить PK в словарь. 04 Новая последовательность Начать новую последовательность с символа K. После окончания входных данных вывести код последней последовательности.

• 
  Слайд 6
  

  Алгоритм сжатия пошагам Начать новую P Добавить/ Вывести Проверить PK Взять P и K 01 Взять P и K Взять текущую последовательность P и следующий символ K. 02 PK в словаре? Если PK уже есть в словаре, продолжить последовательность: P := PK. 03 Вывести код P Если PK отсутствует, вывести код последовательности P и добавить PK в словарь. 04 Новая последовательность Начать новую последовательность с символа K. После окончания входных данных вывести код последней последовательности.

• 
  Слайд 7
  

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

• 
  Слайд 8
  

  Особый случай придекодировании Ситуация Иногда очередной код ещё отсутствует в словаре. Причина Это происходит в ситуации, когда код обозначает последовательность вида: предыдущая последовательность + её первый символ. Решение Алгоритм может восстановить такую запись самостоятельно, поэтому декодирование остаётся однозначным.

• 
  Слайд 9
  

  Что влияет наэффективность Преимущества Сжатие без потерь Простая идея и последовательная обработка данных Не требуется хранить отдельный словарь вместе с каждым фрагментом Ограничения

• 
  Слайд 10
  

  Главный вывод и практическоезадание LZW заменяет повторяющиеся последовательности кодами, постепенно расширяя словарь. Ключевая идея алгоритма: найденный фрагмент используется повторно, а новая комбинация добавляется в словарь. Длясамостоятельного выполнения: 1 Построить таблицу Постройте таблицу словаря для строки ABABABA. 2 Обратная расшифровка Выполните обратную расшифровку полученных кодов. 3 Сравнить объём Сравните объём исходной строки и последовательности кодов.