Лабораторная работа
Кодирование информации
Работа выполняется на персональном компьютере с использованием языков программирования высокого уровня. Постройте программу, которая бы позволила ввести сообщение произвольной длины. Программа должна выделить буквы алфавита введенного текста, подсчитать и выдать частоту появления этих букв. Определить энтропию, приходящуюся в среднем на одну букву, длину кода при равномерном кодировании и избыточность. Программа должна обладать некоторым интерфейсом для удобства работы пользователя. Имея программу необходимо запустить ее и, пользуясь подсказками меню, ввести произвольный связный текст на русском языке. Это может быть пословица, стихотворение или произвольный текст.
Используя результаты, выданные компьютером, следует:
1) проанализировать алфавит введенного сообщения:
количество символов алфавита, значение энтропии H, длину кода Q при целочисленном кодировании, избыточность R при однобуквенном кодировании;
2) построить вручную коды Шеннона-Фано и Хаффмена (используя полученные статистические данные);
3) определить среднюю длину кода kс;
4) сравнить полученное значение kс с оптимальным H, выданным компьютером;
5) сделать необходимые выводы.
Содержание отчета
Отчет о лабораторной работе должен содержать блок схему программы. Результаты анализа при статистическом кодировании, схему построения эффективных кодов, результаты анализа и сравнения различных методов кодирования, эффективность сжатия. Листинги результатов работы программы, выводы.
5. Сжатие информации
Сжатие информации возможно при наличии избыточности в сообщении. Различают следующие виды избыточности.
Естественная избыточность связана с первичным алфавитом, а искусственная с вторичным алфавитом. Мысль, выраженная более кратко без потери информации, обуславливает семантическую избыточность. Статистическая избыточность обуславливается не равновероятностным распределением качественных признаков первичного алфавита и их взаимозависимостью.
Для сжатия информации широко используются программыупаковщики (архиваторы). Наиболее популярными являются PKZIP/PKUNZIP, ARJ, ARC, LHARC, PAK, RAR, WINRAR, WINZIP и др.
Сжатие данных применяется при резервном копировании, при хранении информации, а также при передаче в телекоммуникационных сетях. Сжатые данные будут передаваться быстрее по сети.
5.1. Основные понятия
В области сжатия информации используются следующие основные понятия и характеристики, с помощью которых можно оценить тот или иной метод сжатия.
1. Компрессор или кодер – программа, которая сжимает исходную информацию (преобразует входной несжатый файл в выходной сжатый файл). Программа, выполняющая обратное преобразование (восстановление информации), называется декомпрессором или декодером. Для объединения кодера и декодера иногда используется понятие кодек.
2. Метод неадаптивного сжатия – метод сжатия, в котором не предусмотрена возможность изменения операций, параметров и настроек в зависимости от характера сжимаемой информации. Метод, в котором предусмотрена возможность изменения операций, параметров и настроек в зависимости от сжимаемой информации, называется методом адаптивного сжатия. Если для изменения операций, параметров и настроек предварительно собирается некоторая статистика сжимаемой информации, то метод сжатия называется полуадаптивным (двухпроходное сжатие: на первом проходе выполняется анализ информации, а на втором – собственно сжатие). Метод сжатия называется локально адаптивным, если в нем предусмотрена возможность изменения параметров в зависимости от локальных особенностей входного файла.
3. Метод сжатия без потерь (метод неискажающего сжатия) позволяет восстановить сжатую информацию без искажений. Метод сжатия с потерями (метод искажающего сжатия) предусматривает искажение сжимаемой информации для получения требуемых характеристик сжатия.
4. Симметричный метод сжатия – это метод, при использовании которого кодер и декодер выполняют одни и те же действия, но в противоположных направлениях. Если либо кодер либо декодер выполняет существенно большую работу, то соответствующий метод сжатия называется асимметричным.
5. Коэффициент сжатия – величина, получающаяся в результате деления размера выходного (сжатого) файла на размер входного (несжатого) файла.
6. Фактор сжатия – величина, обратная коэффициенту сжатия.