Моделирование сжатия данных
Вероятностная модель автоматного метода сжатия, использующего статистику исходных данных. Оценка эффективности метода. Существующие способы контроля достоверности передаваемой информации между различными устройствами электронно-вычислительных машин.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 29.11.2018 |
| Размер файла | 169,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Моделирование сжатия данных
И.Р. Бережанский, А.К. Горбунов,
П.А. Зорина, С.Ф. Цаплина
Основное содержание исследования
Рассматривается вероятностная модель автоматного метода сжатия, использующего статистику исходных данных. Дается оценка эффективности метода.
Существующие способы контроля достоверности передаваемой информации между различными устройствами ЭВМ, а также способы исправления ошибок требуют введения некоторой избыточности. Здесь избыточность играет положительную роль.
С другой стороны, сообщения, передаваемые по информационным каналам, могут быть малоинформативны и содержать избыточные несущественные сведения, на хранение, кодирование и передачу которых затрачиваются дорогостоящие ресурсы ЭВМ. Избыточность в кодах сообщений может быть устранена с помощью сжатия информации.
В данной работе рассматривается аналитическая вероятностная модель автоматного метода сжатия, использующего статистику исходной информации .
Способ состоит в преобразовании исходного алфавита в алфавит кода , длина каждого слова которого равна длине первоначального слова алфавита . Преобразование выполняется следующим образом. В заданном массиве информации определяется вероятностная модель распределения источника алфавита. Символы источника делятся на две группы - . Для символов группы используется кодирование, в котором старший разряд каждого символа имеет значение, равное . Соответственно в группе . Преобразованные символы кода поступают в автомат, работа которого описывается графом . В каждом состоянии кодер предполагает тип символов. В состоянии кодер пропускает символы множества с равной вероятностью без всяких изменений. Отображенные символы в состоянии пропускаются без изменений, если , все они имеют . Если символ повторяется, то инвертируется и символ не пропускается. При длине цепочки больше двух организуется счетчик с инверсией .
Эффективность метода можно оценить через , где - количество бит, необходимое для описания исходного и сжатого массивов. Для конкретного массива можно рассчитать значение :
где - разрядность кодов символов; - количество символов в исходном и сжатом массивах. Определим среднее знание коэффициента сжатия:
где - математическое ожидание количества символов в сжатом массиве. Величину найдем, исходя из вероятностно-топологической модели кодера :
где - математическое ожидание количества слов на выходе кодера в состояниях . Величина , поскольку в состоянии сжатие не производится. Величины можно получить из выражения:
где - среднее значение длин цепей повторяющихся символов, принадлежащих множествам
Найдем выражения для определения . Процесс смены состояния автомата рассматриваемого кодера под воздействием входной последовательности слов соответствует эргодической марковской цепи. Для задания случайного процесса в виде марковской цепи достаточно знать матрицу переходных процессов . Для рассматриваемого случая матрица переходных вероятностей имеет вид:
сжатие электронный вычислительный модель вероятностная
Определим элементы матрицы . Из состояния в состояние автомат переходит, если на вход кодера поступило (константа инерции) символов из множества . Поэтому:
где - мощность множества исходного массива. Тогда на основании для имеем
Из состояния кодер может перейти либо в состояние , либо опять в . Поскольку из в кодер переходит при поступлении на его вход любого элемента из множества , то
Вероятность перехода кодера из состояния в состояние равна
Принцип работы кодера в состоянии аналогичен состоянию .
Вектор начальных вероятностей так как - исходное состояние кодера. В соответствии с теорией марковских цепей можно записать уравнение
С учетом нормирующего условия система уравнений имеет единственное решение:
где - главный минор определителя матрицы . Матричное уравнение, соответствующее рассматриваемому кодеру, имеет вид:
На основании имеем:
Обозначив вероятности появления символов из множества через , а из множества через , получим
Тогда
Таким образом, величины можно представить как функции одной переменной
Эффективность преобразователя зависит от разбиения символов на группы. Если, например, в одну группу собраны символы с наибольшей вероятностью поступления, то число переключений автомата сокращается, и эффективность преобразователя возрастает.
Для конкретного текста собирается статистика и выполняется приближенное оценивание с использованием рассмотренного вероятностного моделирования. Если сокращение не убедительное, то выполняется более точное моделирование работы автомата, представленного на .
Комплекс программ оценивания содержит также модели кодирования по Хаффману и методу совмещенных последовательностей.
Список литературы
[1]. Dishon Y. Data compaction in computer systems.computer design, April, 2007. [P.85-90].
Размещено на Allbest.ru
...Подобные документы
Классификация и основные характеристики метода сжатия данных. Вычисление коэффициентов сжатия и оценка их эффективности. Алгоритмы полиноминальных, экстраполяционных и интерполяционных методов сжатия и их сравнение. Оптимальное линейное предсказание.
курсовая работа [1,1 M], добавлен 17.03.2011Энтропия и количество информации. Комбинаторная, вероятностная и алгоритмическая оценка количества информации. Моделирование и кодирование. Некоторые алгоритмы сжатия данных. Алгоритм арифметического кодирования. Приращаемая передача и получение.
курсовая работа [325,1 K], добавлен 28.07.2009Архивация и компрессия как методы сжатия изображений. Алгоритмы сжатия данных. Вспомогательные средства, которые используются для понижения объемов файлов: изменение цветовой модели изображения, изменение разрешения растрового файла, ресемплирование.
презентация [45,3 K], добавлен 06.01.2014Система управление базами данных, реляционная модель. Принципы взаимодействия между клиентскими и серверными частями. Трехуровневая модель технологии "клиент-сервер". Фрактальные методы сжатия больших объемов данных. Анализ концепции хранилища данных.
курс лекций [265,0 K], добавлен 05.06.2009Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.
практическая работа [188,5 K], добавлен 24.04.2014Основные понятия и методы сжатия данных. Преобразование информации, хранящейся в файле, к виду, при котором уменьшается избыточность в ее представлении. Статистический и словарный способы сжатия. Программы-архиваторы, основные возможности WinRAR.
контрольная работа [27,5 K], добавлен 12.03.2011Виды неопределенностей в исходных данных систем и процессов защиты информации. Методы восстановления пропущенных значений в исходных данных. Моделирование методом экспертного построения функций, принадлежности оценки уровня риска информационной системы.
дипломная работа [735,3 K], добавлен 13.07.2011Сущность универсального метода упаковки, его преимущества и недостатки. Кодирование путем учета числа повторений. Примеры схем распаковки последовательности байтов. Алгоритмы сжатия звуковой, графической и видеоинформации. Разновидности формата МРЕG.
презентация [96,2 K], добавлен 19.05.2014Задачи обработки и хранения информации при помощи ЭВМ. Сжатие и кодирование информации в информационно-вычислительных комплексах. Метод Лавинского как простейший метод сжатия информации (числовых массивов) путем уменьшения разрядности исходного числа.
курсовая работа [66,0 K], добавлен 09.03.2009Типы сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие с минимальной избыточностью. Кодирование методом Шеннона-Фано. Проверка работы программы по сжатию файлов формата bmp и xls. Реализация на Delphi алгоритма сжатия Шеннона и Хаффмана.
курсовая работа [2,6 M], добавлен 26.01.2011Программы для создания архивов. Эффективность сжатия данных как важнейшая характеристика архиваторов. Основные методы сжатия данных. Характеристика программы для упаковки текстов и программ WinRar. Распаковка файлов, упаковка файлов и папок в общий архив.
реферат [21,0 K], добавлен 05.04.2010Обеспечение достоверности передаваемой информации применением корректирующих кодов. Код Хэмминга - алгоритм обнаружения и исправления одиночной ошибки. Использование циклических кодов при последовательной передачей между ЭВМ и внешними устройствами.
дипломная работа [123,7 K], добавлен 02.08.2009Разработка собственного алгоритма сжатия и восстановления данных с использованием возможностей языка C++ в рамках программного продукта "Архиватор". Разработка алгоритма программы, ее первый запуск и тестирование. Проверка работы архивации файлов.
курсовая работа [325,7 K], добавлен 13.10.2015Классификация ЭВМ: по принципу действия, этапам создания, назначению, размерам и функциональным возможностям. Основные виды электронно-вычислительных машин: суперЭВМ, большие ЭВМ, малые ЭВМ, МикроЭВМ, серверы.
реферат [22,8 K], добавлен 15.03.2004Общее понятие архивации. Особенности программ архиваторов. Основные методы сжатия информации. Методические основы изучения темы "Архивация данных и сжатие информации" на уроках информатики в базовом курсе. Разработка блока уроков по сжатию информации.
курсовая работа [3,0 M], добавлен 03.06.2012Особенности кодирования информации с помощью метода Хаффмана. Реализация кодера и декодера с использованием статического алгоритма Хаффмана. Структура программы, оценка ее эффективности (степени сжатия) в зависимости от типа и размера сжимаемых файлов.
курсовая работа [136,2 K], добавлен 15.06.2013Применение алгоритмов, обеспечивающих высокую степень сжатия, для увеличения скорости передачи данных по каналам связи. Особенности и методы нахождения сингулярного разложения. Разработка программы, реализующей сжатие изображения с помощью SVD-сжатия.
дипломная работа [3,3 M], добавлен 13.10.2015Типы изображений (черно-белые, полутоновые, цветные) и их форматы. Устройства, создающие цифровые изображения, и их параметры. Применение и характеристики методов сжатия изображений. Поиск по содержимому в базах данных изображений. Структуры баз данных.
презентация [360,4 K], добавлен 11.10.2013Сущность метода зонного сжатия буквенной информации. Описание классов, определяющих место хранения символов и алфавита. Реализация асимметричного алгоритма RSA. Логика построения шифра и структура ключевой информации в криптографическом алгоритме ГОСТ.
контрольная работа [3,2 M], добавлен 30.11.2013Растровые, векторные и комплексные графические форматы. Классификация графических форматов по допустимому объему данных, параметрам изображения, хранению палитры и методике сжатия. Разновидности метода Фурье. Метод преобразования Karhunen-Loeve.
курсовая работа [46,0 K], добавлен 22.12.2014
