- Алгоритм Лемпеля - Зива - Велча

Презентация "Алгоритм Лемпеля - Зива - Велча" по информатике – проект, доклад

Слайд 1
Слайд 2
Слайд 3
Слайд 4
Слайд 5
Слайд 6
Слайд 7
Слайд 8
Слайд 9
Слайд 10
Слайд 11
Слайд 12
Слайд 13
Слайд 14
Слайд 15
Слайд 16
Слайд 17
Слайд 18

Презентацию на тему "Алгоритм Лемпеля - Зива - Велча" можно скачать абсолютно бесплатно на нашем сайте. Предмет проекта: Информатика. Красочные слайды и иллюстрации помогут вам заинтересовать своих одноклассников или аудиторию. Для просмотра содержимого воспользуйтесь плеером, или если вы хотите скачать доклад - нажмите на соответствующий текст под плеером. Презентация содержит 18 слайд(ов).

Слайды презентации

Алгоритм Лемпеля — Зива — Велча
Слайд 1

Алгоритм Лемпеля — Зива — Велча

Алгори́тм Ле́мпеля — Зи́ва — Ве́лча (Lempel-Ziv-Welch, LZW). это универсальный алгоритм сжатия данных без потерь, созданный Авраамом Лемпелем, Яаковом Зивом и Терри Велчем . Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 197
Слайд 2

Алгори́тм Ле́мпеля — Зи́ва — Ве́лча (Lempel-Ziv-Welch, LZW)

это универсальный алгоритм сжатия данных без потерь, созданный Авраамом Лемпелем, Яаковом Зивом и Терри Велчем . Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных. Акроним «LZW» указывает на фамилии изобретателей алгоритма: Лемпель, Зив и Велч.

Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов —
Слайд 3

Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.

Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту
Слайд 4

Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту

Алгоритм Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы W первым символом сообщения. Найти в словаре строку W наибольшей длины, которая совпадает с последними принятыми символами. Считать очередной символ K из кодируемого сообщения. Если КОНЕЦ_СООБЩЕНИЯ,
Слайд 5

Алгоритм Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы W первым символом сообщения. Найти в словаре строку W наибольшей длины, которая совпадает с последними принятыми символами. Считать очередной символ K из кодируемого сообщения. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для W, иначе. Если фраза WK уже есть в словаре, присвоить входной фразе W значение WK и перейти к Шагу 3, иначе выдать код W, добавить WK в словарь, присвоить входной фразе W значение K и перейти к Шагу 3. Конец.

На момент своего появления алгоритм LZW давал лучший коэффициент сжатия, для большинства приложений, чем любой другой хорошо известный метод того времени. Он стал первым широко используемым на компьютерах методом сжатия данных. Алгоритм был реализован в программе compress, которая стала более или ме
Слайд 6

На момент своего появления алгоритм LZW давал лучший коэффициент сжатия, для большинства приложений, чем любой другой хорошо известный метод того времени. Он стал первым широко используемым на компьютерах методом сжатия данных. Алгоритм был реализован в программе compress, которая стала более или менее стандартной утилитой Unix-систем приблизительно в 1986 году. Несколько других популярных утилит-архиваторов также используют этот метод или близкие к нему.

Пример. Данный пример показывает алгоритм LZW в действии, показывая состояние выходных данных и словаря на каждой стадии, как при кодировании, так и при раскодировании сообщения. С тем чтобы сделать изложение проще, мы ограничимся простым алфавитом — только заглавные буквы, без знаков препинания и п
Слайд 7

Пример

Данный пример показывает алгоритм LZW в действии, показывая состояние выходных данных и словаря на каждой стадии, как при кодировании, так и при раскодировании сообщения. С тем чтобы сделать изложение проще, мы ограничимся простым алфавитом — только заглавные буквы, без знаков препинания и пробелов. Сообщение, которое нужно сжать, выглядит следующим образом:

TOBEORNOTTOBEORTOBEORNOT#. Маркер # используется для обозначения конца сообщения. Тем самым, в нашем алфавите 27 символов (26 заглавных букв от A до Z и #). Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 5 бит на символ. По мере роста
Слайд 8

TOBEORNOTTOBEORTOBEORNOT#

Маркер # используется для обозначения конца сообщения. Тем самым, в нашем алфавите 27 символов (26 заглавных букв от A до Z и #). Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 5 бит на символ. По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 5-битные группы дают 25 = 32 возможных комбинации бит, поэтому, когда в словаре появится 33-е слово, алгоритм должен перейти к 6-битным группам. Заметим, что, поскольку используется группа из всех нулей 00000, то 33-я группа имеет код 32. Начальный словарь будет содержать:

# = 00000 A = 00001 B = 00010 C = 00011 . . . Z = 11010
Слайд 9

# = 00000 A = 00001 B = 00010 C = 00011 . . . Z = 11010

Кодирование. Без использования алгоритма LZW, при передаче сообщения, как оно есть — 25 символов по 5 бит на каждый — оно займёт 125 бит. Сравним это с тем, что получается при использовании LZW:
Слайд 10

Кодирование

Без использования алгоритма LZW, при передаче сообщения, как оно есть — 25 символов по 5 бит на каждый — оно займёт 125 бит. Сравним это с тем, что получается при использовании LZW:

Символ: Битовый код: Новая запись словаря: (на выходе) T 20 = 10100 O 15 = 01111 27: TO B 2 = 00010 28: OB E 5 = 00101 29: BE O 15 = 01111 30: EO R 18 = 10010 31: OR
Слайд 11

Символ: Битовый код: Новая запись словаря: (на выходе) T 20 = 10100 O 15 = 01111 27: TO B 2 = 00010 28: OB E 5 = 00101 29: BE O 15 = 01111 30: EO R 18 = 10010 31: OR

Общая длина = 6*5 + 11*6 = 96 бит. Таким образом, используя LZW, мы сократили сообщение на 29 бит из 125 — это почти 22 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактн
Слайд 12

Общая длина = 6*5 + 11*6 = 96 бит.

Таким образом, используя LZW, мы сократили сообщение на 29 бит из 125 — это почти 22 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно

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

Декодирование

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

Данные: На выходе: Полная Новая запись: : Частичная: 10100 = 20 T 27: T? 01111 = 15 O 27: TO 28: O? 00010 = 2 B 28: OB 29: B? 00101 = 5 E 29: BE 30: E? 01111 = 15 O 30: EO 31: O? 10010 = 18 R 31: OR 32: R?
Слайд 14

Данные: На выходе: Полная Новая запись: : Частичная: 10100 = 20 T 27: T? 01111 = 15 O 27: TO 28: O? 00010 = 2 B 28: OB 29: B? 00101 = 5 E 29: BE 30: E? 01111 = 15 O 30: EO 31: O? 10010 = 18 R 31: OR 32: R?

Единственная небольшая трудность может возникнуть, если новое слово словаря пересылается немедленно. В приведённом выше примере декодирования, когда декодер встречает первый символ, T, он знает, что слово 27 начинается с T, но чем оно заканчивается? Проиллюстрируем проблему следующим примером. Мы де
Слайд 15

Единственная небольшая трудность может возникнуть, если новое слово словаря пересылается немедленно. В приведённом выше примере декодирования, когда декодер встречает первый символ, T, он знает, что слово 27 начинается с T, но чем оно заканчивается? Проиллюстрируем проблему следующим примером. Мы декодируем сообщение ABABA:

Данные: На выходе: Новая запись: Полная: Частичная: . . . 011101 = 29 AB 46: (word) 47: AB? 101111 = 47 AB?
Слайд 16

Данные: На выходе: Новая запись: Полная: Частичная: . . . 011101 = 29 AB 46: (word) 47: AB? 101111 = 47 AB?

На первый взгляд, для декодера это неразрешимая ситуация. Мы знаем наперёд, что словом 47 должно быть ABA, но как декодер узнает об этом? Заметим, что слово 47 состоит из слова 29 плюс символ, идущий следующим. Таким образом, слово 47 заканчивается на «символ, идущий следующим». Но, поскольку это сл
Слайд 17

На первый взгляд, для декодера это неразрешимая ситуация. Мы знаем наперёд, что словом 47 должно быть ABA, но как декодер узнает об этом? Заметим, что слово 47 состоит из слова 29 плюс символ, идущий следующим. Таким образом, слово 47 заканчивается на «символ, идущий следующим». Но, поскольку это слово посылается немедленно, то оно должно начинаться с «символа, идущего следующим», и поэтому оно заканчивается тем же символом, что и начинается, в данном случае — A. Этот трюк позволяет декодеру определить, что слово 47 — это ABA. В общем случае, такая ситуация появляется, когда кодируется последовательность вида cScSc, где c — это один символ, а S — строка, причём слово cS уже есть в словаре.

На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах. На LZ78 был выдан американский патент U.S. Patent 4 464 650, принадлежащий Sperry Corporation, позднее ставшей частью Unisys Corporation. На LZW в США были выданы два патента: U.S. Patent 4 814 746, принадлежащ
Слайд 18

На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах. На LZ78 был выдан американский патент U.S. Patent 4 464 650, принадлежащий Sperry Corporation, позднее ставшей частью Unisys Corporation. На LZW в США были выданы два патента: U.S. Patent 4 814 746, принадлежащий IBM, и патент Велча U.S. Patent 4 558 302 (выдан 20 июня 1983 года), принадлежащий Sperry Corporation, позднее перешедший к Unisys Corporation. К настоящему времени сроки всех патентов истекли. Unisys, GIF и PNG[править | править вики-текст] При разработке формата GIF в CompuServe не знали о существовании патента U.S. Patent 4 558 302 . В декабре 1994 года, когда в Unisys стало известно об использовании LZW в широко используемом графическом формате, эта компания распространила информацию о своих планах по взысканию лицензионных отчислений с коммерческих программ, имеющих возможность по созданию GIF-файлов. В то время формат был уже настолько широко распространён, что большинство компаний-производителей ПО не имели другого выхода, кроме как заплатить. Эта ситуация стала одной из причин разработки графического форматаPNG (неофициальная расшифровка: «PNG’s Not GIF»), ставшего третьим по распространённости[источник не указан 2320 дней] в WWW, после GIF и JPEG. В конце августа 1999 года Unisys прервала действие безвозмездных лицензий на LZW для бесплатного и некоммерческого ПО, а также для пользователей нелицензированных программ, призвав League for Programming Freedom развернуть кампанию «сожжём все GIF’ы» и информировать публику об имеющихся альтернативах. Многие эксперты в области патентного права отмечали, что патент не распространяется на устройства, которые могут лишь разжимать LZW-данные, но не сжимать их; по этой причине популярная утилита gzip может читать .Z-файлы, но не записывать их. 20 июня 2003 года истёк срок оригинального американского патента, что означает, что Unisys не может больше собирать по нему лицензионные отчисления. Аналогичные патенты в Европе, Японии и Канаде истекли в 2004 году.

Список похожих презентаций

Алгоритм и его формальное исполнение

Алгоритм и его формальное исполнение

Что такое алгоритм? Формальные исполнители. Неформальные исполнители. Свойства алгоритма. Дискретность - Результативность – Массовость – Детерминированность ...
Алгоритм и его формальное исполнение

Алгоритм и его формальное исполнение

Кибернетика. В 1948 г. В США и Европе вышла книга Норберта Винера «Кибернетика, или Управление и связь в животном и машине». С этого момента и стали ...
Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана

Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана

Давид Хаффман (1925-1999) Давид начал свою научную карьеру студентом в Массачусетсом технологическом институте (MIT), где построил свои коды в начале ...
Алгоритм

Алгоритм

Каждый человек в повседневной жизни, во время учёбы или на работе решает огромное количество задач самой разной сложности. Некоторые из этих задач ...
Алгоритм работы с текстом

Алгоритм работы с текстом

К 1 (1 балл) ФОРМУЛИРОВКА ПРОБЛЕМ ИСХОДНОГО ТЕКСТА. Проблема – это объект раздумий и размышлений автора, к которым он неоднократно возвращается (см. ...
Алгоритм составления презентации

Алгоритм составления презентации

показать приемы обучения работы с программой Microsoft Office PowerPoint творческий поиск создания презентации. Цель:. Этапы создания презентации. ...
Алгоритм и его свойства

Алгоритм и его свойства

По страничкам истории... Слово «алгоритм» происходит от имени великого среднеазиатского ученого 8–9 вв. Аль-Хорезми. Из математических работ Аль-Хорезми ...
Алгоритм не роскошь, а средство достижения цели

Алгоритм не роскошь, а средство достижения цели

Краткая аннотация проекта. Алгоритмический стиль мышления развивает умение планировать свои действия при решении сложных жизненных задач, способности ...
Алгоритм и его свойства

Алгоритм и его свойства

Тема. Алгоритм и его свойства. Содержание. Алгоритм Свойства алгоритмов Способы записи алгоритмов Структуры алгоритмов Пример. Что такое алгоритм? ...
Алгоритм и его свойства

Алгоритм и его свойства

План урока. Проверка домашнего задания Новый материал «Алгоритмы» Решение задач Тестирование. Алгоритм «высеивания» простых чисел ( Решето Эратосфена). ...
Алгоритм

Алгоритм

Проверка домашнего задания. Придумать пару понятий удовлетворяющую одной из диаграмм. Последовательность действий и алгоритм. Решить простую математическую ...
Алгоритм

Алгоритм

Урок 1 Алгоритм. 1. Сначала повторим то, что мы узнали в прошлом году. Одно из основных понятий в информатике – алгоритм. Алгоритм – это задание, ...
Алгоритм и компьютерная программа

Алгоритм и компьютерная программа

Компьютерная программа – алгоритм, записанный на одном из языков программирования. управляющее устройство, механизмы, которые помогают им двигаться. ...
Алгоритм и его свойства

Алгоритм и его свойства

Цели урока:. Сформировать представление об алгоритме, свойствах алгоритма. Новые понятия: Алгоритм, дискретность, результативность, массовость, детерминированность, ...
Алгоритм как модель деятельности

Алгоритм как модель деятельности

Что такое алгоритмическая модель? Почему алгоритм можно назвать моделью и что он моделирует? Алгоритм – это понятное и точное предписание конкретному ...
Алгоритм и его свойства. Виды алгоритмов

Алгоритм и его свойства. Виды алгоритмов

Цель урока: Знакомство учащихся с темой «Алгоритм и его свойства. Виды алгоритмов» Задачи урока: Сформировать представление у учащихся о понятии алгоритма ...
Алгоритм определения искусственных объектов

Алгоритм определения искусственных объектов

АЛГОРИТМ ОПРЕДЕЛЕНИЯ ИСКУССТВЕННЫХ ОБЪЕКТОВ. Реформирование государства нужно начинать с исправления определений. Если у вещей неправильные имена ...
Алгоритм и его формальное исполнение

Алгоритм и его формальное исполнение

Алгоритм. Алгоритм – это предназначенное для конкретного исполнителя точное описание последовательности действий, направленных на решение поставленной ...
Алгоритм с ветвлением в среде программирования Turbo Pascal

Алгоритм с ветвлением в среде программирования Turbo Pascal

Цели урока: 1. Cпособствовать осознанию и осмыслению новой учебной информации; 2. Сформировать представление о принципе работы условного оператора; ...

Конспекты

Алгоритм и его исполнители

Алгоритм и его исполнители

Конспект урока по теме «Алгоритм и его исполнители». Фамилия, имя, отчество – Забелина Мария Владимировна. Место работы – Муниципальное общеобразовательное ...
Алгоритм и его свойства. Примеры алгоритмов

Алгоритм и его свойства. Примеры алгоритмов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ САРАТОВСКОЙ ОБЛАСТИ. ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ. . САРАТОВСКОЙ ОБЛАСТИ. СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ...
Алгоритм

Алгоритм

Класс: 6. Занятие рассчитано на 45 мин. Учитель информатики МКОУ «Лицей села Верхний Мамон»:. . Кравцова Елена Юрьевна. Типология урока  ...
Алгоритм – модель деятельности исполнителя алгоритмов. Исполнитель Чертежник. Управление Чертежником

Алгоритм – модель деятельности исполнителя алгоритмов. Исполнитель Чертежник. Управление Чертежником

Шандро Валентина Николаевна,. учитель информатики,. без категории,. МБОУ «СОШ №5»,. город Абакан Республика Хакасия. Методическая разработка ...
Алгоритм, способы записи алгоритма

Алгоритм, способы записи алгоритма

Конспект урока по информатике Тема урока: Алгоритм, способы записи алгоритма. Класс:. 6 класс Место в теме:. 1 урок. Цель:. изучение основных ...
Вычитание многозначных чисел. Алгоритм действий

Вычитание многозначных чисел. Алгоритм действий

Тип урока: постановка учебной задачи. Тема урока: «Вычитание многозначных чисел. Алгоритм действий». Организационный момент. . Ситуация ...
Алгоритм

Алгоритм

Учитель: Жиглатый Е.В. Класс: 9. Цель урока: Работа над понятием «алгоритм». . Задачи:. Образовательные:. - Рассмотреть проблему определения ...
Алгоритм с ветвлением

Алгоритм с ветвлением

. . ФИО (полностью). . Веревкина Вера Николаевна. . . . Место работы. . МБОУ СОШ №49. . . . . Должность. . . ...
Алгоритм

Алгоритм

Алгоритм 3 класс. (учитель начальных классов МОУ СОШ №2 г.Нефтекумска. Королёва Ирина Николаевна). Цели:. закрепить знания учащихся об основных ...
Алгоритм

Алгоритм

Тема урока:.  . "Алгоритм". Место урока в изучении раздела:.  . первый урок;.  . Форма учебной работы.  . – классно-урочная.  . Продолжительность ...

Советы как сделать хороший доклад презентации или проекта

  1. Постарайтесь вовлечь аудиторию в рассказ, настройте взаимодействие с аудиторией с помощью наводящих вопросов, игровой части, не бойтесь пошутить и искренне улыбнуться (где это уместно).
  2. Старайтесь объяснять слайд своими словами, добавлять дополнительные интересные факты, не нужно просто читать информацию со слайдов, ее аудитория может прочитать и сама.
  3. Не нужно перегружать слайды Вашего проекта текстовыми блоками, больше иллюстраций и минимум текста позволят лучше донести информацию и привлечь внимание. На слайде должна быть только ключевая информация, остальное лучше рассказать слушателям устно.
  4. Текст должен быть хорошо читаемым, иначе аудитория не сможет увидеть подаваемую информацию, будет сильно отвлекаться от рассказа, пытаясь хоть что-то разобрать, или вовсе утратит весь интерес. Для этого нужно правильно подобрать шрифт, учитывая, где и как будет происходить трансляция презентации, а также правильно подобрать сочетание фона и текста.
  5. Важно провести репетицию Вашего доклада, продумать, как Вы поздороваетесь с аудиторией, что скажете первым, как закончите презентацию. Все приходит с опытом.
  6. Правильно подберите наряд, т.к. одежда докладчика также играет большую роль в восприятии его выступления.
  7. Старайтесь говорить уверенно, плавно и связно.
  8. Старайтесь получить удовольствие от выступления, тогда Вы сможете быть более непринужденным и будете меньше волноваться.

Информация о презентации

Ваша оценка: Оцените презентацию по шкале от 1 до 5 баллов
Дата добавления:23 октября 2018
Категория:Информатика
Содержит:18 слайд(ов)
Поделись с друзьями:
Скачать презентацию
Смотреть советы по подготовке презентации