Понедельник 
                       29.04.2024 
                     10:13
Сайт учителя информатики и ИКТ
Тарантиной Натальи Владимировны
Вы вошли как Гость| Группа "Гости" | RSS
Главная | Каталог статей | Регистрация | Вход
» Форма входа

» Меню сайта

» Новости
  • Школьная жизнь моего 5б класса.

  • » Друзья сайта
  • Сайт школы №3 г.Рыбное
  • Олимпиады по программированию
  • Олимпиады для школьников
  • Московские олимпиады для школьников
  • Издат.дом "1 сентября"
  • Информатика в школе
  • Сеть творческих учителей
  • Учительская газета

  • » Статистика

    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0

    » Сайт существует


    » Поиск

    Главная » Статьи » Интересное из области информатики » Знаменитости мира

    Сжатие информации
    Попробуйте упаковать

    Методы сжатия информации часто делят на два класса: с потерями (такие способы применяются, например, для упаковки изображений) и без потерь [1—4]. В первом случае при сжатии часть исходной информации отбрасывается либо изменяется. После таких операций полностью воспроизвести исходные данные уже не представляется возможным. Во втором случае их можно восстановить в первоначальном виде.(Разумеется, методы первой груп­пы нельзя использовать, например, для сжатия файлов программ.)

    Одна из первых — и весьма распространенных — схем сжатия без потерь реализуется с помощью алгоритма Хаффмана.

    Текстовые файлы, с которыми пользователи персональных компьютеров встречаются практически ежедневно, со стоят из алфавитно-циф­ровых символов и «невидимых» кодов управления (перевод строки, возврат каретки и т.п.). Каждый такой символ в таблице кодов ASCII представлен одним байтом, и при подобном кодировании частота, с которой символы встречаются в тексте, не учитывается. Алгоритм Хаффмана основан на довольно простом принципе: символы заменяются кодовыми последовательностями различной длины — чем чаще употребляется символ, тем короче должна быть кодовая последовательность (алгоритм Хаффмана называют еще кодированием символами переменной длины). Так, в английском тексте часто встречающимся буквам «А», «Е», «Т» можно поставить в соответствие последовательности из трех бит, а буквам «J», «Q», «Z» — последовательности из восьми бит [1]. В одних вариантах реализации алгоритма Хаффмана употребляются готовые кодовые таблицы (здесь можно вспомнить азбуку Морзе), а в других кодовая таблица строится только на основе статистического анализа информации.

    Алгоритм Лемпеля — Зива (LZ), предложенный в 1977 году, основан

    на поиске и кодировании избыточной информации. Однако тут кодируются не отдельные символы, как в алгоритме Хаффмана, а последовательности символов. На его основе потом было создано множество методов сжатия информации (LZ-алгоритмы). Программа, реализующая LZ-алго­ритм, просматривает данные и выполняет статистический анализ для построения
     своей кодовой таблицы или словаря (методы сжатия этой группы употребляются, например, в утилитах PKZIP, WinZIP, ARJ, LHARC и некоторых других программах-упаковщи­ках) [1, 3—5]. Через несколько лет появился усовершенствованный вариант алгоритма — алгоритм Лемпеля — Зива - Уэлча (LZW). В 1987 году на основе алгоритма LZW в компании CompuServe был создан формат GIF (Graphics Interchange Format — формат обмена графическими файлами) [4, 6—8]. Алгоритм RLE (Run Length Encoding—»групповое» кодирование) первоначально разрабатывался специально для хранения графической информации. Метод основан на представлении последовательности одинаковых байтов в виде двух величин.
     
     
    Одна из них равна количеству повторяющихся символов, а другая представляет собой код этого символа. Например, строка из семи букв «А», трех букв «В» и четырех букв «С» (АААААААВВВСССС) может быть записана в виде 7АЗВ4С, что дает существенное сокращение ее длины. Данный метод применяется, в частности, для сжатия файлов графического формата PCX. Усовершенствованный алгоритм RLE используется в одном из вариантов формата TIFF и в формате TGA.
    В начале 1990-х годов Объединенной группой экспертов в области фотографии (Joint Photographic Experts Group, JPEG) была предложена схема сжатия, которая впоследствии получила всеобщее признание как стандартный метод сжатия неподвижных изображений. Он получил название JPEG. В основе алгоритма лежит известная математическая операция — дискретное преобразование Фурье, с

    помощью которого на основании выбранного «коэффициента качества» определяется требуемое соотношение сжатия и потерь изображения [4, 6]. Кодирование по Хаффману вместе с RLE употребляется как составная часть алгоритма — для дополнительного сжатия изображения.

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

    Существуют и другие алгоритмы упаковки, в том числе специальные алгоритмы сжатия движущихся изображений. В 1990-м году появились первые компьютерные алгоритмы фрактального сжатия изображений [4]. В 1994 году впервые было дано описание быстро завоевывающего сейчас популярность алгоритма сжатия информации на основе преобразования Бэрроуза — Уилера (Burrows — Wheeler Transform, BWT) [5]. Еще одним перспективным направлением является сжатие на основе так называемых нейронных сетей...

    Литература

    1. Борзенко А.Е., Федоров А.Г. Мультимедиа для всех. Изд. 2-е. М.: КомпьютерПресс, 1996.

    2. Фафенбергер Б., Уолл Д. Толковый словарь по компьютерным технологиям и Internet: Пер. с англ. Изд. 6-е. Киев: Диалектика. 1996.

    3. PKZIP и PKUNZIP // Информатика, Ns 46/99.

    4. Васильев А. Сжатие изображений: вчера, сегодня, завтра // Hard'n'Soft, № 4/2001.

    5. Юкин В. Операция BWT, или Новые методы сжатия // Hard'n'Soft, №4/2001.

    6. Шниер М. Толковый словарь компьютерных технологий: Пер. с англ. Киев: ДиаСофт, 2000.

    7. Мостицкий И.Л. Новейший англо-русский толковый словарь по современной электронной технике. М.: ЛУЧШИЕ КНИГИ, 2000.

    8. Пройдаков Э.М., Теплицкий Л.А. Англо-русский толковый словарь по вычислительной технике, Интернету и программированию. Изд. 2-е, испр. и доп. М.: Издательско-торговый дом «Русская редакция», 2000.

    Категория: Знаменитости мира | Добавил: Natali (21.02.2010)
    Просмотров: 1819 | Теги: алгоритм Каффмана, сжатие информации | Рейтинг: 0.0/0
    Всего комментариев: 0
    Добавлять комментарии могут только зарегистрированные пользователи.
    [ Регистрация | Вход ]
    » Категории раздела
    Знаменитости мира [16]
    о ученых и конструкторах, внесших вклад в развитие компьютерной техники и информатики
    Это интересно! [17]
    Все, что произошло в мире в области информатики и информационных технологий
    Стихи [0]
    посвященные компьютерам и информации


    Сайт учителя информатики Тарантиной Н.В.© 2024
    Бесплатный хостинг uCoz