Алгоритм сжатия текстовых файлов | Статья в журнале «Молодой ученый»

Авторы: ,

Рубрика: Технические науки

Опубликовано в Молодой учёный №44 (178) ноябрь 2017 г.

Дата публикации: 05.11.2017

Статья просмотрена: 139 раз

Библиографическое описание:

Череданова Е. М., Мамченко Е. А. Алгоритм сжатия текстовых файлов // Молодой ученый. — 2017. — №44. — С. 24-26. — URL https://moluch.ru/archive/178/46279/ (дата обращения: 20.04.2019).



В статье рассматривается метод эффективного кодирования текстовой информации. В отличие от большинства существующих методов, большая эффективность кодирования и сжатия текста достигается за счет учета вероятностей положения алфавита символов на различных позициях в словах.

Растущий в настоящее время объем текстовой информации требует разработки новых эффективных и надежных методов ее кодирования, закрытия и передачи. Реализация данного требования возможна за счет уменьшения информационной избыточности передаваемых текстовых сообщений, которое может быть получено за счет их эффективного кодирования.

В общем случае, задача эффективного кодирования сводится к такой обработке передаваемых текстовых сообщений, при которой минимизируется среднее количество двоичных знаков, требующихся для кодирования одного символа сообщения. Это позволяет уменьшить общую длину передаваемого кодового сообщения и, соответственно, времени передачи по каналам связи.

Эффективное кодирование основывается на основной теореме Шеннона для каналов без шума. В теореме доказано, что сообщения, составленные из символов некоторого алфавита, можно закодировать так, что среднее число двоичных знаков на символ будет сколь угодно близко к энтропии источника этих сообщений, но не меньше этой величины.

Из теоремы следует, что при выборе каждого знака кодовой комбинации необходимо стараться, чтобы он нес максимальную информацию. Следовательно, каждый знак должен принимать значения 0 и 1 по возможности с равными вероятностями и каждый выбор должен быть независим от значений предыдущих знаков кодовой последовательности.

При отсутствии статистической взаимосвязи между символами методы построения эффективных кодов были даны впервые К.Шенноном и Н.Фано. Код строится следующим образом: символы алфавита сообщений выписываются в порядке убывания вероятностей. Записанная последовательность разделяется на две подгруппы с равными суммарными вероятностями. Всем символам верхней половины в качестве первого знака приписывается 1, а всем нижним — 0. Каждая из полученных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одному символу. При каждом разбиении к префиксам кодовых комбинаций символов одной подгруппы дописывается кодовый знак 0, к символам другой -1.

Предложенная методика Шеннона — Фано логически не замкнута, т. е. не всегда приводит к однозначному построению кода. Действительно, при разбиении на подгруппы, когда разбить на точно равные по вероятности подгруппы невозможно, имеется неопределенность, какую подгруппу сделать большей по вероятности, а какую меньшей. Таким образом, построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием а > 2 неопределенность становится еще больше.

От указанного недостатка свободна методика Д. Хаффмена, который дал однозначную, логически замкнутую методику составления эффективных кодов. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом кодовых знаков на символ.

Задача построения оптимального неравномерного кода (ОНК) основания a для некоррелированных алфавитов исходной дискретной последовательности (сообщения) m, состоящий из m символов, формулируется следующим образом:

среди всех возможных кодов основания а без разделительных знаков, которые обладают свойствами префикса, найти код, для которого величина

Аср= (1)

где Аср — средняя длина кодовой комбинации, - вероятность i-го символа алфавита, — число кодовых знаков кодовой комбинации i -го символа алфавита, минимально возможна.

Для того, что бы предложенный ОНК удовлетворял соотношению (1) необходимо выполнение условий:

  1. Если выписать символы в порядке убывания вероятности:

, (2)

где i>j, то длительность соответствующих кодовых комбинаций должна удовлетворять соотношению:

. (3)

  1. Во всяком случае, две последние, но не более чем a, кодовые комбинации, равны по длительности и отличаются значением только последнего кодового знака:

=, (4)

где 2a.

  1. Каждая возможная последовательность кодовых знаков должна либо сама быть кодовой комбинацией, либо иметь своим префиксом используемую кодовую комбинацию [1].

Простейшая статистика текстовых сообщений показывает наличие статистической взаимосвязи не только между символами, но и положением символов на определенных позициях в словах передаваемых сообщений.

Задача построения оптимального неравномерного кода основания a для некоррелированных алфавитов m с учетом положения символа на различных позициях в слове формулируется следующим образом:

среди всех возможных кодов основания а без разделительных знаков, которые обладают свойствами префикса, найти код, для которого величина

Аср= (5)

где Аср — средняя длина кодовой комбинации, - вероятность i-го символа алфавита находящегося на k-й позиции в слове, — число кодовых знаков кодовой комбинации i -го символа алфавита на k-ой позиции в слове, n- максимальная длина слова.

Что бы предложенный ОНК, удовлетворял соотношению (5) необходимо выполнение условий:

  1. Для каждой позиции символов в слове k є [1…n] если выписать символы в порядке убывания вероятностей:

, (6)

где i> j, то длительность соответствующих кодовых комбинаций должна удовлетворять соотношению:

. (7)

Для двоичного кода методика эффективного кодирования сводится к следующему. Для определенного типа информации (техническая, литературная и т. д.) заранее определяются наиболее характерные частоты появления символов алфавита текстовых сообщений на позициях в словах. По каждой позиции производится ранжирование символов по убыванию частот. В результате этого для каждой позиции получают проранжированную последовательность символов. Символы, стоящие на одинаковых местах в последовательностях (на одной строке таблицы), объединяются в группу символов одного ранга. Последовательно, каждой группе символов одного ранга, ставится в соответствие ОНК, причем, чем больше ранг группы символов (т. е. меньше частота появления), тем больше длительность сопоставляемой при кодировании символу кодовой комбинации.

Оценка эффективности

Проведем оценку эффективности кодирования предложенного и существующих методов. Эффективность использования ОНК принято оценивать с помощью коэффициента сжатия . Данный коэффициент показывает, во сколько раз уменьшается среднее число двоичных знаков на символ исходного текста при передаче ОНК по сравнению с обычными методами нестатистического кодирования (передачей равномерным двоичным кодом). Для двоичных кодов определяется отношением:

= =. (8)

Возьмем для алфавита текстовых сообщений на русском языке m = 53 (32 буквы, 10 цифр, 11 служебных знаков). Тогда для равномерного распределения частот символов алфавита печатного текста, построенное по данным [2] получим:

– для соответствующего этому распределению частот первого приближения к энтропии:

= - 4,85 дв. ед./симв.;

– информационная емкость сообщения:

= = 6 дв. ед./симв.;

– максимально достижимый выигрыш при кодировании

1,24.

Для предложенной методики эффективного кодирования с учетом распределения вероятностей символов на различных позициях в словах:

= 4,02 дв. ед./симв. и

1,49 соответственно.

Заключение

Сравнивая полученные результаты, можно сделать вывод, что использование при кодировании предложенной методики приводит к более полному сжатию информации по сравнению с методикой Хаффмена.

Наиболее эффективное использование методики возможно применительно специальной служебной переписке, обладающей меньшим значением энтропии и большей избыточностью.

Литература:

1. Новик Д. А. Эффективное кодирование. М.-Л. “Энергия”,1965 г., 236

2. Котов А. П. и др., Основы телеграфии, ВКАС, л.,1958

Основные термины (генерируются автоматически): кодовая комбинация, эффективное кодирование, символ, знак, позиция, код, слово, сообщение, оптимальный неравномерный код, предложенная методика.


Похожие статьи

QR-коды, их свойства и применение | Статья в журнале...

такого кода достаточно велика и зависит от того, в каком виде информацию в него хотят закодировать.Максимальное число символов, которое можно внести в QR-код (версия 40, 177x177

Ключевые слова. информация, QR-код, кодирование и чтение QR-кодов, маркетинг.

Алгоритм Хаффмана для передачи большого объема информации...

Кодирование — это преобразование сообщений в сигнал, т. е. Для кодирования текстовой информации я изучила алгоритм Хаффмана.

По кодовому дереву присваиваем каждому символу бинарный код.

Алгоритмы помехоустойчивого кодирования и их аппаратная...

Кодирование и декодирование кодов Рида — Соломона является довольно сложной задачей.

В работы были исследованы некоторые методы кодирования для повышения надежности хранения информации, а именно: циклический избыточный код (CRC код), код...

Методы сжатия изображений | Статья в журнале «Молодой ученый»

Нетрудно увидеть, что присвоение кодовых слов с меньшим числом битов более вероятным значениям яркости, и наоборот, более длинных кодовых слов менее вероятным

На третьей и последней стадии кодер символов создает равномерный или неравномерный код.

Культурные коды в вербальном тексте | Статья в журнале...

Ключевые слова: лингвокультурный код, вербальный текст, фрейм, культурный сценарий, моделирование.

По Д. И. Дубровскому [1, с. 130], в арсенале кодов, которыми пользуется субъект, один является «внутренним», близким и родным для него.

Защитное кодирование оптических дисков и цифровых внешних...

Сигнал от микросенсора является кодом для входа в массивы информации, размещенные в

Автору настоящей публикации представляется наиболее оптимальным применение

Предлагаемая методика, в которой измерение импеданса производится с помощью...

Использование логических блоков Дьенеша в интеллектуальном...

Для проверки того, насколько хорошо дети освоили свойства геометрических фигур, вводится специальный код, графически изображающий данные свойства.

Развивать логическое мышление, умение кодировать блоки с помощью знаковсимволов включая знак «не».

Опорный конспект как один из способов представления учебной...

Это могут быть знаки-символы для обозначения ключевых или часто повторяющихся слов.

- использование схем и кодов при построении опорного конспекта позволяет упрощать сложные разделы, понятия, концепции изучаемых дисциплин

Дальнейшее развитие комплексных технологий защитного...

Метод кодирования оптических дисков накопителей памяти и устройство для реализации указанного метода.

В предложенной технологии кодирующее покрытие может служить основанием для персонального секретного кода или шифра, чего...

Похожие статьи

QR-коды, их свойства и применение | Статья в журнале...

такого кода достаточно велика и зависит от того, в каком виде информацию в него хотят закодировать.Максимальное число символов, которое можно внести в QR-код (версия 40, 177x177

Ключевые слова. информация, QR-код, кодирование и чтение QR-кодов, маркетинг.

Алгоритм Хаффмана для передачи большого объема информации...

Кодирование — это преобразование сообщений в сигнал, т. е. Для кодирования текстовой информации я изучила алгоритм Хаффмана.

По кодовому дереву присваиваем каждому символу бинарный код.

Алгоритмы помехоустойчивого кодирования и их аппаратная...

Кодирование и декодирование кодов Рида — Соломона является довольно сложной задачей.

В работы были исследованы некоторые методы кодирования для повышения надежности хранения информации, а именно: циклический избыточный код (CRC код), код...

Методы сжатия изображений | Статья в журнале «Молодой ученый»

Нетрудно увидеть, что присвоение кодовых слов с меньшим числом битов более вероятным значениям яркости, и наоборот, более длинных кодовых слов менее вероятным

На третьей и последней стадии кодер символов создает равномерный или неравномерный код.

Культурные коды в вербальном тексте | Статья в журнале...

Ключевые слова: лингвокультурный код, вербальный текст, фрейм, культурный сценарий, моделирование.

По Д. И. Дубровскому [1, с. 130], в арсенале кодов, которыми пользуется субъект, один является «внутренним», близким и родным для него.

Защитное кодирование оптических дисков и цифровых внешних...

Сигнал от микросенсора является кодом для входа в массивы информации, размещенные в

Автору настоящей публикации представляется наиболее оптимальным применение

Предлагаемая методика, в которой измерение импеданса производится с помощью...

Использование логических блоков Дьенеша в интеллектуальном...

Для проверки того, насколько хорошо дети освоили свойства геометрических фигур, вводится специальный код, графически изображающий данные свойства.

Развивать логическое мышление, умение кодировать блоки с помощью знаковсимволов включая знак «не».

Опорный конспект как один из способов представления учебной...

Это могут быть знаки-символы для обозначения ключевых или часто повторяющихся слов.

- использование схем и кодов при построении опорного конспекта позволяет упрощать сложные разделы, понятия, концепции изучаемых дисциплин

Дальнейшее развитие комплексных технологий защитного...

Метод кодирования оптических дисков накопителей памяти и устройство для реализации указанного метода.

В предложенной технологии кодирующее покрытие может служить основанием для персонального секретного кода или шифра, чего...

Задать вопрос