Укажите по какой формуле определяют коэффициент сжатия файла k если объем исходного файла v0

Обновлено: 04.07.2024

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

Да-да, об этом уже была статья на Хабре, но без практической реализации. Здесь же мы сфокусируемся как на теоретической части, так и на программерской. Итак, все под кат!

Немного размышлений

В обычном текстовом файле один символ кодируется 8 битами(кодировка ASCII) или 16(кодировка Unicode). Далее будем рассматривать кодировку ASCII. Для примера возьмем строку s1 = «SUSIE SAYS IT IS EASY\n». Всего в строке 22 символа, естественно, включая пробелы и символ перехода на новую строку — '\n'. Файл, содержащий данную строку будет весить 22*8 = 176 бит. Сразу же встает вопрос: рационально ли использовать все 8 бит для кодировки 1 символа? Мы ведь используем не все символы кодировки ASCII. Даже если бы и использовали, рациональней было бы самой частой букве — S — дать самый короткий возможный код, а для самой редкой букве — T (или U, или '\n') — дать код подлиннее. В этом и заключается алгоритм Хаффмана: необходимо найти оптимальный вариант кодировки, при котором файл будет минимального веса. Вполне нормально, что у разных символов длины кода будут отличаться — на этом и основан алгоритм.

Кодирование

Ни один код не должен быть префиксом другого

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

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

Код каждого символа я разделил пробелом. По-настоящему в сжатом файле такого не будет!
Вытекает вопрос: ~~как этот салага придумал код~~ как создать таблицу кодов? Об этом пойдет речь ниже.

Построение дерева Хаффмана

Здесь приходят на выручку бинарные деревья поиска. Не волнуйтесь, здесь методы поиска, вставки и удаления не потребуются. Вот структура дерева на java:

Это не полный код, полный код будет ниже.

Вот сам алгоритм построения дерева:

Извлечь два дерева из приоритетной очереди и сделать их потомками нового узла (только что созданного узла без буквы). Частота нового узла равна сумме частот двух деревьев-потомков.
Для этого узла создать дерево с корнем в данном узле. Вставить это дерево обратно в приоритетную очередь. (Так как у дерева новая частота, то скорее всего она встанет на новое место в очереди)
Продолжать выполнение шагов 1 и 2, пока в очереди не останется одно дерево — дерево Хаффмана

Здесь символ «lf»(linefeed) обозначает переход на новую строку, «sp» (space) — это пробел.

А что дальше?

Мы получили дерево Хаффмана. Ну окей. И что с ним делать? ~~Его и за бесплатно не возьмут~~ А далее, нужно отследить все возможные пути от корня до листов дерева. Условимся обозначить ребро 0, если оно ведет к левому потомку и 1 — если к правому. Строго говоря, в данных обозначениях, код символа — это путь от корня дерева до листа, содержащего этот самый символ.

Таким макаром и получилась таблица кодов. Заметим, что если рассмотреть эту таблицу, то можно сделать вывод о «весе» каждого символа — это длина его кода. Тогда в сжатом виде исходный файл будет весить: 2 * 3 + 2*4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 бит. Вначале он весил 176 бит. Следовательно, мы уменьшили его аж в 176/65 = 2.7 раза! Но это утопия. Такой коэффициент вряд ли будет получен. Почему? Об этом пойдет речь чуть позже.

Декодирование

Ну, пожалуй, осталось самое простое — декодирование. Я думаю, многие из вас догадались, что просто создать сжатый файл без каких-либо намеков на то, как он был закодирован, нельзя — мы не сможем его декодировать! Да-да, мне было тяжело это осознать, но придется создать текстовый файл table.txt с таблицей сжатия:

Запись таблицы в виде 'символ'«код символа». Почему 01110 без символа? На самом деле он с символом, просто средства java, используемые мной при выводе в файл, символ перехода на новую строку — '\n' -конвертируют в переход на новую строку(как бы это глупо не звучало). Поэтому пустая строка сверху и есть символ для кода 01110. Для кода 00 символом является пробел в начале строки. Сразу скажу, что ~~нашему коэффициенту хана~~этот способ хранения таблицы может претендовать на самый нерациональный. Но он прост для понимания и реализации. С удовольствием выслушаю Ваши рекомендации в комментариях по поводу оптимизации.

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

Ни один код не должен являться префиксом другого

Реализация

Пришло время ~~унижать мой код~~ писать архиватор. Назовем его Compressor.

Начнем с начала. Первым делом пишем класс Node:

Класс, создающий дерево Хаффмана:

Класс, облегчающий чтение из файла:

Ну, и главный класс:

Файл с инструкциями readme.txt предстоит вам написать самим :-)

Заключение

Наверное, это все что я хотел сказать. Если у вас есть что сказать по поводу ~~моей некомпетентности~~ улучшений в коде, алгоритме, вообще любой оптимизации, то смело пишите. Если я что-то недообъяснил, тоже пишите. Буду рад услышать вас в комментариях!

Да-да, я все еще здесь, ведь я не забыл про коэффициент. Для строки s1 кодировочная таблица весит 48 байт — намного больше исходного файла, да и про добавочные нули не забыли(количество добавленных нулей равно 7)=> коэффициент сжатия будет меньше единицы: 176/(65 + 48*8 + 7)=0.38. Если вы тоже это заметили, то ~~только не по лицу~~ вы молодец. Да, эта реализация будет крайне неэффективной для малых файлов. Но что же происходит с большими файлами? Размеры файла намного превышают размер кодировочной таблицы. Вот здесь-то алгоритм работает как-надо! Например, для монолога Фауста архиватор выдает реальный (не идеализированный) коэффициент, равный 1.46 — почти в полтора раза! И да, предполагалось, что файл будет на английском языке.

Выпустил upgrade: добавил GUI + изменил алгоритм обработки исходного текста так, чтобы не читать весь файл в память. Короче, кидаю ссылку на git для любознательных: сами всё увидите.

Благодарности

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

Огромное спасибо Исаеву Виталию Вячеславовичу за небходимую теоретическую поддержку.
Также, часть материала этой статьи взята из книги Роберта Лафоре «Data Structures and Algorithms in Java». Если сомневаетесь как или окуда начать свой путь в теории алгоритмов и структур данных — берите, не прогадаете.

що спільного і відмінного у створені внутрішніх та зовнішніх гіперпосилань у документі?

СРОЧНО ДО УТРА . выполнить вычисления 1428= ….10 3738=….10 fb16=….10 8a16=….10 информатика калькулятор

3. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего п … ути между пунктами В и Е, не проходящего через пункт А. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

Ограничение времени 1 секунда Ограничение памяти 256Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt Недавно Берляндские … ученые обнаружили две новые планеты: Добос и Феймос. В ходе исследования выяснилось, что на этих планетах есть жизнь, а их обитатели говорят друг с другом на неизвестных человечеству языках: добосовском и феймосовском. Ученым удалось выяснить, что в добосовском языке все слова являются последовательностями из символов, каждый из которых является заглавной латинской буквой «A» или «B». В феймосовском языке все слова являются последовательностями из символов, каждый из которых является цифрой «0» или «1». Также ученые выяснили, что переводить слова с одного языка на другой можно довольно просто: чтобы перевести слово с добосовского языка на феймосовский, надо каждый символ «A» в слове заменить на «0», а каждый символ «B» заменить на «1». Аналогично, чтобы перевести слово с феймосовского языка на добосовский, надо заменить в нем все символы «0» на «A», а все символы «1» — на «B». Например, слово «ABAAB» переводится с добосовского языка на феймосовский как «01001», а слово «11» переводится с феймосовского на добосовский как «BB». Ученые попросили вас написать автоматический переводчик с добосовского языка на феймосовский и обратно. Помогите им это сделать: напишите программу, которая переводит слово с одного языка на другой.

Ура, у королевы страны Берляндии родился первенец! Теперь эта светлая весть распространяется от города к городу с огромной скоростью. Берляндию можно … представить в виде прямоугольника с h строками и w столбцами, в каждой клетке которого располагается город. Строки пронумерованы от 1 до h, а столбцы — от 1 до w. В стране ведёт деятельность сарафанное радио, позволяющее за один день из каждого города передать новость в те города, в которые можно попасть из него ходами шахматного коня. А именно, для данного города, находящегося в центре рисунка, за один день можно передать информацию во все города, в которые ведут стрелки:

ДАЮ 15 БАЛЛОВ На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направ … лении, указанном стрелкой. Сколько существует различных путей из города А в город П, проходящих через город В?

ДАЮ 15 БАЛЛОВ На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, ука … занном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Г?

, (1)

где S – размер файла (байт)

M-ширина рисунка (точек)

N-высота рисунка (точек)

5. Определяю размер рисунка (M и N) в пикселях (Файл ->Свойства)

6. Фиксирую полученный результат

7. Сохраняю исходное изображение и назначаю тип файла 24-разрядный рисунок формата BMP

8. Повторно сохраняю исходное изображение, назначив тип файла GIF.

9. Повторно сохраняю исходное изображение, назначив тип файла JPG.

10. Определяю размер каждой сохранённой картинки в килобайтах при помощи Проводника (или щелчок ПКМ на объекте ->Свойства)

11. Определяю коэффициент сжатия каждого изображения по формуле (2)

(2)

где k – коэффициент сжатия

V_исх – исходный размер изображения (в Кб)

V_{рез –} размер изображения в результате преобразований (в Кб)

12. Полученные данные заношу в таблицу 1.

Результаты эксперимента №1

Формат файла	Размер файла (Кбайт)	Коэффициент сжатия (%)
BMP
GIF
JPG

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

14. Изображаю на полотне настоящий шедевр, используя максимум 4 цвета

15. Выполняю пункты 7–11 для созданного мною изображения. Полученные данные заношу в таблицу 2

Результаты эксперимента №2

Формат файла	Размер файла (Кбайт)	Коэффициент сжатия (%)
BMP
GIF
JPG

Тематические вопросы по главе I

1. Какой формат графических данных из рассмотренных нами наилучшим образом подходит для передачи цветного фотографического материала по каналам электронных сетей?

2. Какой формат наиболее благоприятен для передачи рисунков, имеющих малое количество цветовых оттенков?

3. Какой формат графических данных целесообразно использовать для передачи черно-белого фотоматериала по каналам электронных сетей?

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

Тематические ответы по главе I

Часть II. Исследование алгоритмов сжатия программы WinRAR

1.Для проведения эксперимента создаю папку

2. Заполняю папку произвольными файлами различного типа в объеме

3. Запускаю программу WinRAR

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

5. В окне Имя и параметры архива через кнопку Обзор выбираю папку, в которой будет находиться архив

6. В раскрывающемся списке Степень сжатия выбираю пункт Без сжатия.

7. Фиксирую время, которое займет процесс архивации.

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

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

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

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

12. Определяю коэффициент сжатия по формуле (3)

(3)

где k – коэффициент сжатия

V_исх – исходный размер изображения (в Мб)

V_{рез –} размер изображения в результате преобразований (в Мб)

13. Определяю эффективность сжатия по формуле (4)

(4)

12. Сделайте вывод о наиболее эффективном методе сжатия по критерию соотношения степени сжатия и расхода времени на операцию.

13. В программе Проводник удалите экспериментальные папки C:\Temp\Input и C:\Temp\Output.

Информатика. Базовый курс. 2-е издание/ Под ред. С.В.Симоновича. – СПб.: Питер, 2007

По теме: методические разработки, презентации и конспекты

Практические работа по архиваторам

2 практические работа.

Практические работы по архиваторам

Разработка фрагмента практической работы для учащихся 6 класса. Тема обучающей практической работы: Определение географической широты объектов

Определение географической широты объектовПрограммы: Примерная программа основного общего образования по географии "География Земли"(6-7 классы)/ сборник нормативных документов: География: Федеральный.

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

Разработка фрагмента практической работы для учащихся 7 класса.Программы: Примерная программа основного общего образования по географии "География Земли"(6-7 классы)/ сборник нормативных документов: Г.

Разработка фрагмента практической работы для учащихся 8 класса. Тема обучающей практической работы: Определение поясного и местного времени для разных пунктов России

Разработка фрагмента практической работы для учащихся 8 класса.Программы: Примерная программа основного общего образования по географии "География Земли"(6-7 классы)/ сборник нормативных документов: Г.

УЧЕТ ПСИХОФИЗИОЛОГИЧЕСКИХ ОСОБЕННОСТЕЙ УЧАЩИХСЯ В ПРАКТИЧЕСКОЙ РАБОТЕ НА УРОКАХ ТРУДА УЧЕТ ПСИХОФИЗИОЛОГИЧЕСКИХ ОСОБЕННОСТЕЙ УЧАЩИХСЯ В ПРАКТИЧЕСКОЙ РАБОТЕ НА УРОКАХ ТРУДА

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

Конспект урока по дисциплине "Информатика". Тема: "Основные режимы работы программ-архиваторов"

Архиваторы различаются возможностями и качеством сжатия.Качество сжатия зависит не только от архиватора, но и от типа сжимаемых данных.Лучше всего сжимаются простые растровые изображения. Черно-белое .