Реферат: Метод словарного кодирования Зива-Лемпела. Дифференциальное кодирование - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Метод словарного кодирования Зива-Лемпела. Дифференциальное кодирование

Банк рефератов / Информатика, информационные технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 27 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

БЕЛОРУССКИЙ ГОСУДАРСТВЕНН ЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ К афедра РЭС Р еферат на тему: «Словарные методы кодирования. Метод Зива-Лемпела. Дифференциальное ко дирование» МИНСК, 2009 Словарные методы кодирования. Метод Зива-Лемпела Практически все словарные методы кодирования пpинадлежат семье алгоритмов из работы двух израильских ученых - Зива и Лем пела, опубликованной в 1977 году. Сущность их состоит в том, что фразы в сж и маемом тексте заменяются указателем на то место, где они в этом тексте уже pанее появлялись . Это семейство алгоритмов называется методом Зива-Лемпела и обозн а чается как LZ-сжатие . Эт от метод быстpо пpиспосабливается к стpуктуpе текста и может кодировать ко роткие фун к циональные слов а, так как они очень часто в нем появляются. Новые слова и фразы могут такж е формир о ваться из частей ра нее встреченных слов. Декодирование сжатого текста осуществляется напрямую - проис ходит простая замена указателя готовой фразой из словаря, на которую тот указ ы вает. На практике LZ-метод добивается хорошего сжатия, его ва жным свойством являе т ся оче нь быстрая работа декодера. (Когда мы г оворим о тексте, то предполаг а ем, что кодированию подвергается некоторый вектор данных с кон ечным ди с кретным алфавитом, и это не обязательно текст в буквальном смысле этого сл о ва.) Большинство словарных методов кодирования носят имя авторов идеи м е тода Зива и Лемпела, и часто считают, что все они используют один и тот же алгор итм кодирования. На самом деле разные представители этого семейства а л горитмов очень сильно р азличаются в деталях своей работы. Все словарные методы кодирования можно разбить н а две группы. Методы, пр инадлежащие к первой группе, находя в кодируемой посл е довательности цепочки символов, которые ранее уже вст речались, вместо того, чтобы повторять эти цепочки, заменяют их указател ями на предыдущие повт о ре ния. Словарь в этой группе алгоритмов в неявном виде содержится в обр а батываемых данных, сохраняются лишь указатели на встречающи еся цепочки повт о ряющихс я символов. Все методы этой группы базируются на алгоритме, разработанном и опу б ликованном, как уже отмечало сь, сравнительно недавно - в 1977 году А брах а мом Лемпелем и Якобо м Зивом, - LZ 77. Наиболее совершенным пре дставителем этой группы, включившим в себя все достижения, полученные в данном напра в лении, являе тся алгоритм LZSS , опубликованный в 1982 году Сторером и Ш и мански. Процедура кодирования в соответствии с алгоритмами этой группы и л люстрируется рис. 1. Рис. 1 Алгоритмы в торой группы в дополнение к исходному словарю исто ч ника создают словарь фра з, представляющих собой повторяющиеся комбинации символов исходного с ловаря, встречающиеся во входных да н ных. При этом размер словаря источника возрастает, и для его кодирования потр еб у ется большее число бит , но значительная часть этого словаря будет пре д ставлять собой уже не отдельные буквы, а буквосоче тания или целые слова. Когда кодер обнаруживает фразу, которая ранее уже встречалась, он замен я ет ее индексом словаря, со держащим эту фразу. При этом длина кода индекса п о лучается меньше или намного меньше длины кода фразы. Все методы этой группы базируются на алгоритме, разработанном и опублик ованном Лемпелем и Зивом в 1978 году, – LZ 78. Наиболее сове р шенным на данный момент представителем этой группы словарны х методов является алг о ри тм LZW , разработанный в 1984 году Терри Вэлчем. Идею этой группы алгоритмов можно также пояснить с помощью рис . 2. Рис. 2 Алгоритмы второй группы несколько проще в объяснен ии их работы, поэтому начнем рассмотрение принципа действия LZ -кодеров с алгоритма LZW . Рассмотрим в самом общем виде работу LZW-кодера и декодера. Процедура кодирование Процесс сжатия выглядит достаточно просто. Мы посл едовательно считываем символы входного потока (строку) и проверяем, есть ли в уже со з данной нами та блице такая строка. Если строка есть, то считываем след ующий символ, а если такой строки нет, - заносим в выходной поток код для пр едыдущей найденной строки, заносим ее в таблицу и начин а ем поиск снова. Пусть на вход кодера поступает послед овательность символов вида / WED / WE / WEE / WEB , при этом размер алфавита входных символов dim A = 255. Схема сжатия выглядит следующим образом: Входные символы В ыходной код Новые символы сло в а ря /W / 256 = /W E W 257 = WE D E 258 = ED / D 259 = D/ WE 256 260 = /WE / E 261 = E/ WEE 260 262 = /WEE /W 261 263 = E/W EB 257 264 = WEB B В результате получим выходной код /WED<256>E<260><261><257>B . Как при этом изменилась длина выходного кода в сравнении с входным ? Если для двоичного кодирования строки / WED / WE / WEE / WEB дл и ной в 15 букв и размером алфавит а dim A = 255 нам понадобилось бы 15 • log 2 255 = 15х8 = 120 бит , то для двоичного кодирования выхо дной строки кодера / WED <256> E <260> <261> <257> B длиной в 10 новых символов с алфавитом в 264 бу к вы – 10 • 9 = 90 бит. Поцедура декодирование LZW-декодер, обрабатывая входной поток закодирован ных данных, восстанавливает из него исходные данные. Так же, как и алгорит м сжатия, декодер добавляет но вые строки в словарь всякий раз, когда находит во входном потоке новый ко д. Все, что ему остается сделать, – это преобразовать входной код в в ы ходную строку символов и отдать ее на выход кодера. Схема работы LZW-декодера выглядит следующим образом: строка на входе кодера - /WED<256>E<260><261><257>B. Входные символы В ыходная строка Новые символы с лов а ря / / W W 256 = /W E E 257 = WE D D 258 = ED 256 /W 259 = D/ E E 260 = /WE 260 /WE 261 = E/ 261 E/ 262 = /WEE 257 WE 263 = E / W B B 264 = WEB Самым замечательным качеством этого способа сжатия являет ся то, что весь словарь новых символов передаетс я декодеру без собственно пер е дачи . В конце процесса декодировани я декодер имеет точно такой же словарь н о вых символов, какой в процессе кодирования был накоп лен кодером, при этом его создание б ы ло частью процесса декодирования. Работа кодера/декодера семейства LZ77 - первой опубликованной ве р сии LZ-метода - выгля дит несколько иначе. В алгоритме LZ77 указатели обозначают фразы в окне постоянно го pазмеpа, пpедшествующие позиции кода. Максимальная длина заменяемых ук а зателями подстро к определяется параметром F (обычно это от 10 до 20). Эти огранич е ния позволяют LZ77 использовать "скользящее окно" из N символов. Из них первые N-F были уже з акодированы, а последние F с оставляют упре ж дающий бу фер. При кодировании символа в первых N-F символах окна ищут самую длинную, совпадающую с этим буфером строку. Она может частично пер е крывать буфер, но не может быть самим буфером. Найденное наибольшее соответствие затем кодируется триадой [ i, j, a ] г де i есть его смещение от начала буфера, j - длина соответствия, a - пе р вый символ, не соответствующий подстроке окна. Затем окно сдвигается вправо на j +1 символ и готово к новому шагу алгоритма. Привязка определенного символа к каждому указателю гарант и рует, что кодирование будет выполняться даже в том случае, если для первого символа упpеждающего буфера не бу дет найдено соо т ветствие. Объем памяти, требуемый кодеру и деко деру, ограничивается размером окна. Количество бит, необходимое для представления смещения ( i ) в триаде, составляет [ log(N-F) ]. Количество символов ( j ), заменяемых триадой, может быть закодировано [ logF ] бит а ми. Декодирование осуществляется очень просто и быстро. При этом по д держивается тот же порядок работы с окном, что и при код ировании, но в отличие от поиска одинаковых строк он, наоборот, копирует и х из окна в с о ответствии с очередной триадой. Дифференциальное кодирование Работа дифференциального кодера основана на том ф акте, что для многих типов данных разница между соседними отсчетами отно сительно нев е лика, даже е сли сами данные имеют большие знач ения. Например, нельзя ожидать большой разницы между соседними пикселам и цифрового изобр а жения. Следующий простой пример показывает, какое преимущество м ожет дать дифференциальное кодирование (кодирование разности между со се д ними отсчетами) в сравнен ии с простым кодированием без памяти (кодир о ванием отсчетов независимо друг от друга). Просканируем 8-битовое (256-уровневое) цифровое изображение, при этом десят ь последовательных пикселов имеют уровни: 144, 147, 150, 146, 141, 142, 138, 143, 145, 142. Если закодировать эти уровни пикс ел за пикселом каким-либо кодом без памяти, использующим 8 бит на пиксел изображения, получим кодовое слово, с о держащее 80 бит. Предположим теперь, что прежде чем подвергать отсчеты изображения коди рованию, мы вычислим разности между соседними пикселами. Эта пр о цедура даст нам последовательн ость следующего вида: 144, 147, 150, 146, 141, 142, 138, 143, 145, 142. 144, 3, 3, - 4, - 5, 1, - 4, 5, 2, -3. Исходная последовательность может быть легко восстановлена из разн о стной простым суммирова нием (дискретным интегрированием): 144, 144+ 3 , 147+ 3 , 150 – 4 , 146– 5 , 141+ 1 , 142– 4 , 138+ 5, 143+ 2 , 145- 3 144, 147, 150, 146, 141, 142, 138, 143, 145, 142. Для кодирования первого числа из полученной последо вательности ра з ностей отсч етов, как и ранее, понадобится 8 бит, все ос тальные числа можно закодировать 4-бит овыми словами (один знаковый бит и 3 би та на к о дирование модуля чис ла ). Таким образом, в результате кодирования получим кодовое слово дл и ной 8 + 9*4 = 44 бита или почти вдвое более короткое, нежели при индив ид у альном кодировании отсч етов. Метод дифференциального кодирования очень широко используется в тех с лучаях, когда природа данных такова, что их соседние значения незн а чительно отличаются друг от др уга, при том, что сами значения могут быть сколь угодно большими. Это относится к звуковым сигналам, особенно к речи, изображениям, соседние пиксели которых имеют практически од и наковые яркости и цвет и т.п. В то же время этот метод со вершенно не подходит для кодирования текстов, чертежей или каких-либо ци фровых данных с независимыми соседними знач е ниями. ЛИТЕРАТУРА 1. Лидовский В.И. Теория информации. - М., « Высшая школа», 2002г. – 120с. 2. Метрология и радиоизмерения в теле коммуникационных системах. Учебник для ВУЗов. / В.И. Нефедов, В.И. Халкин, Е.В. Федоров и др. – М.: Высшая школа, 2001 г. – 383с. 3. Цапенк о М.П. Измерительные информационные системы. – М.: Энергоатом издат, 2005. - 440с. 4. Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. – 368 с. 5. Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, и спр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
На все вопросы о формировании нового украинского правительства киевские власти отвечают: «Вот приедет Байден — Байден нас рассудит».
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по информатике и информационным технологиям "Метод словарного кодирования Зива-Лемпела. Дифференциальное кодирование", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru