Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Компьютеры, Программирование Компьютеры, Программирование     Программное обеспечение Программное обеспечение

Алгоритмы сжатия данных

Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение
Ручка "Помада".
Шариковая ручка в виде тюбика помады. Расцветка корпуса в ассортименте, без возможности выбора!
25 руб
Раздел: Оригинальные ручки
Браслет светоотражающий, самофиксирующийся, желтый.
Изготовлены из влагостойкого и грязестойкого материала, сохраняющего свои свойства в любых погодных условиях. Легкость крепления позволяет
66 руб
Раздел: Прочее

Курсовая работа Алгоритмы сжатия данных Содержание Введение Общие сведения Энтропия и количество информации Комбинаторная, вероятностная и алгоритмическая оценка количества информации Моделирование и кодирование Некоторые алгоритмы сжатия данных Алгоритм LZ77 Алгоритм LZ78-LZW84 Алгоритм PPM BW - преобразование и компрессор Кодирование Хаффмана Арифметическое кодирование Алгоритм арифметического кодирования Реализация алгоритма арифметического кодирования Реализация модели Доказательство правильности декодирования Приращаемая передача и получение Отрицательное переполнение Переполнение и завершение Адаптивная модель для арифметического кодирования Эффективность сжатия Заключение Список литературы Приложение 1. Программный код Приложение 2. Интерфейс программы Введение Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и на сколько та или иная информация при этом сожмется. Кроме того, им были проведены опыты по эмпирической оценке избыточности английского текста. Он предлагал людям угадывать следующую букву и оценивал вероятность правильного угадывания. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0.6 — 1.3 бита на символ. Несмотря на то, что результаты исследований Шеннона были по-настоящему востребованы лишь десятилетия спустя, трудно переоценить их значение. Первые алгоритмы сжатия были примитивными в связи с тем, что была примитивной вычислительная техника. С развитием мощностей компьютеров стали возможными все более мощные алгоритмы. Настоящим прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. До этого момента сжатие сводилось к примитив­ному кодированию символов. Словарные алгоритмы позволяли кодир­овать повторяющиеся строки символов, что позволило резко повысить степень сжатия. Важную роль сыграло изобретение примерно в это же время арифметического кодирования, позволившего воплотить в жизнь идею Шеннона об оптимальном кодировании. Следующим прорывом было изобретение в 1984 г. алгоритма РРМ. Следует отметить, что это изобретение долго оставалось незамеченным. Дело в том, что алгоритм сложен и требует больших ресурсов, в первую очередь больших объемов памяти, что было серьезной проблемой в то время. Изобретенный в том же 1984 г. алгоритм LZW был чрезвычайно популярен благодаря своей простоте, хорошей рекламе и нетребовательности к ресурсам, несмотря на относительно низкую степень сжатия. На сегодняшний день алгоритм РРМ является наилучшим алгоритмом для сжатия текстовой информации, a LZW давно уже не встраивается в новые приложения (однако широко используется в старых). Будущее алгоритмов сжатия тесно связано с будущим компью­терных технологий. Современные алгоритмы уже вплотную приблизи­лись к Шенноновской оценке 1.3 бита на символ, но ученые не видят причин, по которым компьютер не может предсказывать лучше, чем человек. Для достижения высоких степеней сжатия приходится использовать более сложные алгоритмы.

Однако существовавшее одно время предубеждение, что сложные алгоритмы с более высокой степенью сжатия всегда более медленны, несостоятельно. Так, существуют крайне быстрые реализации алгоритмов РРМ для текстовой информации и SPIH для графики, имеющие очень высокую степень сжатия. Таким образом, будущее за новыми алгоритмами с высокими требованиями к ресурсам и все более и более высокой степенью сжатия. Устаревают не только алгоритмы, но и типы информации, на которые они ориентированы. Так, на смену графике с малым числом цветов и неформатированному тексту пришли высококачественные изображения и электронные документы в различных форматах. Известные алгоритмы не всегда эффективны на новых типах данных. Это делает крайне актуальной проблему синтеза новых алгоритмов. Количество нужной человеку информации неуклонно растет. Объемы устройств для хранения данных и пропускная способность линий связи также растут. Однако количество информации растет быстрее. У этой проблемы есть три решения. Первое - ограничение количества информации. К сожалению, оно не всегда приемлемо. Например, для изображений это означает уменьшение разрешения, что приведет к потере мелких деталей и может сделать изображения вообще бесполезными (например, для медицинских или космических изображений). Второе — увеличение объема носителей информации и пропускной способности каналов связи. Это решение связано с материальными затратами, причем иногда весьма значительными. Третье решение - использование сжатия информации. Это решение позволяет в несколько раз сократить требования к объему устройств хранения данных и пропускной способности каналов связи без дополнительных издержек (за исключением издержек на реализацию алгоритмов сжатия). Условиями его применимости является избы­точность информации и возможность установки специального програм­много обеспечения либо аппаратуры как вблизи источника, так и вблизи приемника информации. Как правило, оба эти условия удовлетворяются. Именно благодаря необходимости использования сжатия информации методы сжатия достаточно широко распространены. Однако существуют две серьезные проблемы. Во-первых, широко используемые методы сжатия, как правило, устарели и не обеспечивают достаточной степени сжатия. В то же время они встроены в большое количество программных продуктов и библиотек и поэтому будут использоваться еще достаточно долгое время. Второй проблемой является частое применение методов сжатия, не соответствующих характеру данных. Например, для сжатия графики широко используется алгоритм LZW, ориентированный на сжатие одномерной информации, например текста. Решение этих проблем позволяет резко повысить эффективность применения алгоритмов сжатия. Таким образом, разработка и внедрение новых алгоритмов сжатия, а также правильное использование существующих позволит значительно сократить издержки на аппаратное обеспечение вычислительных систем. При реализации алгоритма арифметического кодирования использовался язык C# и визуальная среда программирования Microsof Visual S udio 2005. Язык C# имеет следующие преимущества: простота, объектная ориентированность, типовая защищенность, “сборка мусора”, поддержка совместимости версий, упрощение отладки программ.

Общие сведения Энтропия и количество информации Под энтропией в теории информации понимают меру неопределенности (например, меру неопределенности состояния некоторого объекта). Для того чтобы снять эту неопределенность, необходимо сообщить некоторое количество информации. При этом энтропия численно равна минимальному количеству информации, которую необходимо сообщить для полного снятия неопределенности. Энтропия также может быть использована в качестве оценки наилучшей возможной степени сжатия для некоторого потока событий. Здесь и далее понятие события используется как наиболее общее понятие сущности, которую необходимо сжать. Так, при сжатии потока символов под событием может пониматься появление во входном потоке того или иного символа, при сжатии графики — пикселя того или иного цвета и т.д. Комбинаторная, вероятностная и алгоритмическая оценка количества информации Наиболее простым способом оценки количества информации является комбинаторный подход. Согласно этому подходу, если переменная х может принадлежать к множеству из элементов, то энтропия переменного H(x) = log2 . Таким образом, для передачи состояния объекта достаточно I=log2 бит информации. Заметим, что количество информации может быть дробным. Разумеется, дробное количество информации невозможно сохранить на носителе или передать по каналам связи. В то же время, если необходимо передать либо сохранить большое количество блоков информации дробной длины, их всегда можно сгруппировать таким образом, чтобы полностью исключить потери (например, посредством арифметического кодирования). Основным недостатком комбинаторного подхода является его ориентированность на системы с равновероятными состояниями. В реальном мире события, как правило, не равновероятны. Вероятностный подход к оценке количества информации, учитывающий этот фактор, является наиболее широко используемым на сегодняшний день. Пусть переменная х может принимать значений хi с вероятностью р(хi). Тогда энтропия Обозначим через р(у х) условную вероятность того, что наступит событие у если событие х уже наступило. В таком случае условная энтропия для переменной Y, которая может принимать М значений yi с условными вероятностями р(уi х) будет Приведенные формулы показывают, что вне зависимости от того, как были получены вероятности наступления следующих событий, для кодирования события с вероятностью р достаточно — log2 p бит (в полном соответствии с теоремой Шеннона об оптимальном кодировании). Алгоритмический подход применим в тех случаях, когда данные обладают некоторыми закономерностями. Согласно этому подходу, если данные можно описать посредством некоторых формул либо порождающих алгоритмов, энтропия данных будет равна минимальному количеству информации, необходимой для передачи этих формул либо алгоритмов от источника информации к приемнику. Алгоритмический подход используется самостоятельно или совместно с вероятностным, например, в некоторых алгоритмах сжатия графической информации. Моделирование и кодирование Энтропия набора данных, а значит и максимально возможная степень сжатия, зависит от модели.

В стандарте NTSC каждую секунду проходит 30 кадров, то есть мы имеем дело с потоком данных 33 Мбайт/с (или около 260 Мбит/с), а полнометражный (на 1,5 часа) несжатый фильм займет на диске почти 180 Гбайт! Даже понизив разрешение до убогих 352х288 (как это делается в Video CD) и ограничив себя при этом черно-белым изображением (по одному байту на пиксел), мы все равно получим поток около 20 Мбит/с и общий объем фильма примерно в 15 Гбайт, что уже требует как минимум HD DVD в качестве носителя. Известно, что к потерям цветовой информации человек гораздо менее чувствителен, чем к потерям яркостной, и первую можно частично удалить. Можно выбросить цвет, например, для каждой второй строки и каждой второй точки по горизонтали (такой способ кодирования еще обозначают как 4:2:2), получив в результате около 1,5 байт на пиксел вместо стандартных трех. Но принципиально, как видим, само по себе такое двукратное снижение потока данных проблемы не решает - оно лишь используется в совокупности с другими алгоритмами сжатия

1. Методы компрессии и сжатия изображений

2. Работа с текстом "Поучения" Владимира Мономаха в школе

3. Составление предложений в английском языке, работа с текстом

4. Работа с текстом, таблицами и графиками в программе Power Point

5. Аналитическая работа по тексту Л.С. Выготского "Проблема возраста"

6. Алгоритм сжатия исторической информации
7. Алгоритм сжатия видео: рецепторы как кодировщики
8. Алгоритмы сжатия данных

9. Сжатие речи на основе алгоритма векторного квантования

10. Информационные потоки в ЭВМ. Алгоритм работы процессора

11. Сжатие данных

12. Подбор сечения для сжатого стержня

13. Система сжатия и уплотнения каналов

14. Сжатие речевого сигнала на основе линейного предсказания

15. Системы подачи сжатого воздуха для организации респираторной защиты на производстве

16. Использование фонового изображения для замены текста

Стенд "Календарь природы". С карточками чисел, дней недели, месяцев и бланком дневника наблюдений.
Календарь природы — важный инструмент ознакомления детей с окружающим миром. Ежедневный учет явлений природы развивает у детей
546 руб
Раздел: Демонстрационные рамки, планшеты, таблички
Вертикальный накопитель, пластиковый, черный, ширина 240 мм, 4 отделения, органайзер.
Изготовлен из полистирола. Многосекционный поддон с 4 отделениями (шириной по 40 мм каждое) для бумаг формата А4 и вместительным
445 руб
Раздел: Подставки, лотки для бумаг, футляры
Глобус Луны диаметром 320 мм, с подсветкой.
Диаметр: 320 мм. Масштаб: 1:40000000. Материал подставки: пластик. Цвет подставки: черный. Мощность: 220 V, переключатель на шнуре; может
1338 руб
Раздел: Глобусы

17. Использование сжатых дисков

18. Современные методы позиционирования и сжатия звука

19. Утилиты сжатия жесткого диска

20. Работа над английскими текстами "Prices and markets", "Price and value"

21. Клиентская часть технологической среды для разработки больших экономических моделей: компоненты поддержки работы эксперта-экономиста при формировании и отладке (в расчетном режиме) структурного текста модели

22. Методы сжатия цифровой информации. Метод Лавинского
23. Работа с полноцветными, полутоновыми и бинарными изображениями
24. Работа с архивными документами. Чтение старославянских текстов

25. Задачи и виды электронной коммерции. Алгоритм работы платежной системы Rapida

26. Устойчивость сжатых стержней. Прочность при циклически изменяющихся нагрузках (напряжениях)

27. Внутренние силы и напряжения, возникающие в поперечных сечениях бруса при растяжении и сжатии

28. Производство отделочных работ

29. Штукатурные работы с основами охраны труда

30. Производство работ по возведению жилого кирпичного здания

31. Общие виды работ, выполняемых на воздушных судах

32. Принцип работы и назначение телескопа

Коляска-трость Everflo "Simple blue".
Коляска-трость - идеальный вариант для путешествий и поездок в общественном транспорте. Характеристики: - Стальная рама. - Одно положение
1300 руб
Раздел: Коляски-трость
Фляжка сувенирная "На здоровье!", 270 мл.
Фляжка сувенирная. Объём: 270 мл. Материал: металл.
408 руб
Раздел: Фляжки сувенирные
Настольная игра "Баскетбол".
Настольная игра «Баскетбол» развивает моторику и быстроту реакции. Размер игры: 37х19х18 см. Возраст: 3+.
1171 руб
Раздел: Настольный баскетбол, бильярд, боулинг

33. Генетические алгоритмы

34. How "DNA" testing works Анализ "ДНК" как проверяющие работы)

35. Контрольная работа по физиологии

36. Воспитательная работа в вооруженных силах и ее влияние на психику воина в боевой деятельности

37. Спасательные и неотложные аварийно-восстановительные работы

38. Организация и проведение спасательных работ в чрезвычайных ситуациях
39. Применение ЭВМ для повышения эффективности работы штаба ГО РАТАП
40. Спасательные и неотложные аварийно-восстановительные работы в очагах поражения

41. Итоги работы портов: Одесса, Ильичёвск, Николаев, Мариуполь и Херсон за 2003 год

42. Буровые работы

43. Совершенствование организации работы отдела контроля за поступлением налогов с физических лиц

44. Исключительные права на средства индивидуализации товаров, работ, услуг и их производителей

45. Контрольная работа по всеобщей истории государства и права

46. Реферат о Пугачеве

47. Контрольная работа по муниципальному праву Вариант 2

48. Контрольная работа по Римскому праву

Полотенце вафельное "Райский уголок", банное, пляжное, 100х150 см.
Вафельное полотенце "Райский уголок". Легкое и практичное полотенце удобно использовать на пляже, в бане и в бассейне.
304 руб
Раздел: Большие, ширина свыше 40 см
Глобус Земли, физико-политический, с подсветкой, 320 мм.
Глобус Земли физико-политический, с подсветкой, работает от сети. Диаметр: 320 мм. На пластиковой подставке. Рельефный. Цвет подставки
1159 руб
Раздел: Глобусы
Коробка подарочная "Штамп".
Коробка подарочная. Материал: мелованный, ламинированный, негофрированный картон плотностью 1100 г/м2. Отделка: полноцветный декоративный
302 руб
Раздел: Коробки

49. Прием и порядок переведения работника на другую работу

50. Трудовой договор (контракт) в системе трудовых правоотношений и кадровая работа на предприятиях

51. Особенности рассмотрения в судах трудовых споров о восстановлении на работе

52. Контрольная работа по экологическому праву

53. How "DNA" testing works Анализ "ДНК" как проверяющие работы)

54. Контрольная работа по Английскому языку
55. Переводческая эквивалентность в текстах газетно-информационных материалов
56. Устойчивые словесные комплексы в (немецком) публицистическом тексте

57. Принципы работы редактора над статьями в энциклопедическом издании (на примере детских энциклопедий издательства "Дорлинг Киндерсли")

58. Сравнительный анализ портретов Ф.И Шаляпина. Работы Б.М Кустодиева и К.А Коровина

59. Культурологическая проблематика в работе Л.Н.Гумилева "Этногенез и биосфера Земли"

60. Кровоточащие и плачущие изображения с точки зрения современного естествознания

61. Сатирическое изображение русской действительности 30х годов в романе "Мастер и Маргарита"

62. Судьба деревни в изображении современных писателей (В. Распутин "Прощание с Матёрой", А. Солженицын "Матрёнин двор")

63. "Горечь" и "сладость" человеческой жизни в изображении И.Бунина и А.Куприна

64. Изображение деревни в романе Ф.А. Абрамова "Братья и сестры"

Сортер-матрешка "Волшебный куб".
Деревянный сортер-матрешка представляет собой развивающий комплекс для детишек возрастом от 3 лет. Игра состоит из 5 кубов различной
568 руб
Раздел: Сортеры, логические игрушки
Пазл-ваза "Поющие птицы в летнем саду", 160 элементов.
Ваза-пазл – это трехмерный пазл в виде вазы. Оригинальный дизайн; идеальная сцепка деталей; специальная колба для воды;
587 руб
Раздел: Прочие
Набор детской посуды "Ангел".
Набор посуды детский "Ангел". В комплекте 3 предмета: - тарелка суповая диаметром 15 см, - тарелка обеденная диаметром 17,5
397 руб
Раздел: Наборы для кормления

65. Лексическая эквивалентность при переводе художественного текста с нидерландского языка на русский. Особенности перевода метафор. (на материале перевода отрывка из романа Анны Энквист "Тайна")

66. Особенности изображения двух миров в поэме А. Блока "Двенадцать"

67. Порождение текстов на естественном языке

68. Высший свет в изображении Л.Н. Толстого (по роману "Война и мир")

69. Роль названия в художественном тексте

70. Взаимосвязь заглавия и глубинного смысла текста в кратком художественном рассказе
71. О развитии навыков работы над полифонией
72. Начальный этап работы над музыкальным произведением

73. Реферат по научной монографии А.Н. Троицкого «Александр I и Наполеон» Москва, «Высшая школа»1994 г.

74. Работа Н.А. Бердяева "Смысл истории"

75. Программные средства и приёмы работы на компьютере

76. Принципы работы системы управления параллельными процессами в локальных сетях компьютеров

77. Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры

78. Работа маршрутизаторов в компьютерной сети

79. Распределенные алгоритмы

80. Модемы, модемные стандарты, принцип работы

Масло Mommy care для отпугивания комаров, 50 мл, арт. MC_1696.
Масло для отпугивания комаров смесь натуральных и органических масел Москитуш обладает нежным ароматом, способным притуплять обоняние
890 руб
Раздел: Крем
Поильник–непроливайка Lubby "Русские мотивы" с трубочкой, 240 мл.
Мягкая силиконовая трубочка поильника нежно соприкасается с ртом Малыша. Оптимальная длина трубочки позволяет выпить все содержимое
387 руб
Раздел: Поильники, непроливайки
Бутылочка для кормления "Avent Classic+", 260 мл (розовая, рисунок: бабочка), от 1 месяца.
Ограниченная серия - бутылочка для кормления розовая c рисунком (бабочка), серия Classic+. Зарекомендовавшая себя серия Classic была
403 руб
Раздел: Бутылочки

81. Влияние мониторов на зрение. Мониторы с электронно-лучевой трубкой (ЭЛТ) или жидкокристаллические (ЖК). Усталость глаз при работе с мониторами

82. Алгоритмы сортировки

83. Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных

84. Постановка лабораторной работы по теории графов

85. Написание игровой программы Tetris и описание алгоритма

86. Построение реалистичных изображений предметов сервировки стола (стакана, фужера, рюмки, заполненных напитками) ([Курсовая])
87. Лабораторные работы по теории и технологии информационных процессов
88. Программное сопровождение практических работ по курсу "Конструирование и проектирование одежды"

89. VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

90. Работа с каталогами (лабораторная работа)

91. Лабораторные работы

92. Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок схем на языке Turbo Pascal

93. Объектно-ориентированный подход к проектированию программного обеспечения на примере работы налоговой инспекции

94. Отчёт по созданию курсовой работы «База данных ACCESS»

95. Оптимизация плана работ по отладке программных продуктов

96. Организация внешних файлов и работа с ними

Конверт почтовый "Куда-Кому", С4 (229х324 мм), стрип, 50 штук.
Конверт выполнен из офсета, имеет клеевое нанесение типа стрип (отрывная силиконовая лента) и почтовый подсказ "Куда-Кому".
316 руб
Раздел: Прочее
Каталка-автомобиль "Sokol" (с ручкой).
Каталка-автомобиль "Sokol" рекомендуется для малышей, которые пока еще неуверенно сидят и часто падают. Эта модель каталки
2249 руб
Раздел: Каталки
Пазл "Арктика", 75 элементов.
Яркий красочный пазл познакомит ребенка с удивительным миром животных Северного полюса. Это и белые медведи, и морские котики, и белый
548 руб
Раздел: Пазлы (54-99 элементов)

97. Отчет по практической работе "Изучение MS Windows & MS Word 4 Windows 2.0"

98. Работа с таблицами в Word

99. Создание фигурного текста посредством WordArt

100. Форматирование текста


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.