Реализация алгоритма Хаффмана на Java

@ОчереднойДжедай · Регистрация: 18.10.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте, дорогие форумчане! В качестве темы для курсовой работы я выбрал реализацию программного средства для упаковки и распаковки данных методом Хаффмана. Программа работает - выбираешь файл, он шифруется, затем выбираешь зашифрованный файл, он расшифровывается - получаешь исходный файл. Но проблема заключается в размере файла с кодом Хаффмана.

Если файл текстовый (.txt) и содержит вполне себе обычный текст, то он прекрасно сжимается - в среднем на 30%, а то и больше ("Война и мир" прекрасно сжималась). Но вот если дело обстоит с файлами другого типа - .JPEG, .GIF, .PDF, .MP3 и т.д., то файл с кодом Хаффмана весит больше, чем изначальный файл. То есть сжатия данных как такого вообще не происходит, а выходит с точностью наоборот.

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

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

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

Однако я немного в замешательстве - насколько мне известно, алгоритм Хаффмана успешно применяется для сжатия не только текстовых данных, но и для изображений в том числе. Подскажите, пожалуйста, что необходимо сделать, чтобы дерево не было слишком глубоким? И применяется ли при сжатии НЕ текстовых данных алгоритм Хаффмана в чистом виде? Или он применяется обязательно в сочетании с другими методами сжатия? Или использование адаптивного алгоритма изменит ситуацию?

Спасибо большое!

@alecss131 · 20.03.2020, 22:49

Сообщение от ОчереднойДжедай

.JPEG, .GIF, .PDF, .MP3

Сжать уже и так сжатое? Попробуйте другие не так ужатые форматы. Из звука например wav

@ОчереднойДжедай · 20.03.2020, 22:59 **[ТС]**

Только что попробовал .wav. Не вышло - файл с кодом Хаффмана все равно больше.

@xoraxax · 20.03.2020, 23:09

примеров же много, изучай
https://github.com/topics/huff... thm?l=java

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/

@ОчереднойДжедай 0 / 0 / 0 Регистрация: 18.10.2015 Сообщений: 7

	Реализация алгоритма Хаффмана на Java 20.03.2020, 22:20. Показов 6456. Ответов 3 Метки сжатие данных, сжатие изображений, сжатие файла, Хаффмана (Все метки) Здравствуйте, дорогие форумчане! В качестве темы для курсовой работы я выбрал реализацию программного средства для упаковки и распаковки данных методом Хаффмана. Программа работает - выбираешь файл, он шифруется, затем выбираешь зашифрованный файл, он расшифровывается - получаешь исходный файл. Но проблема заключается в размере файла с кодом Хаффмана. Если файл текстовый (.txt) и содержит вполне себе обычный текст, то он прекрасно сжимается - в среднем на 30%, а то и больше ("Война и мир" прекрасно сжималась). Но вот если дело обстоит с файлами другого типа - .JPEG, .GIF, .PDF, .MP3 и т.д., то файл с кодом Хаффмана весит больше, чем изначальный файл. То есть сжатия данных как такого вообще не происходит, а выходит с точностью наоборот. Как я узнал, Алгоритм Хаффмана очень плохо работает в случае, если частота встречи символов в алфавите соответствует числам Фибоначчи. В этом случае у дерева Хаффмана достигается большая глубина (узлы становятся в ряд), по этой причине код Хаффмана может стать даже длиннее кода изначального, отсюда файл с кодом может весить больше изначального файла. Любой файл я читаю как обычную последовательность байтов. Дисперсия букв в тексте, имеющем смысл, такова, что дерево получается более-менее сбалансированным и небольшим, поэтому сжатие выполняется успешно. Но если читать картинку, музыку и т.д. как последовательность байт, то дисперсия уже намного хуже. Как я заметил, большое число байт встречается примерное одинаковое количество, а к ним в придачу какие-то ~20 байт встречаются намного чаще/реже и т.д. В общем, из-за этого дерева получается слишком глубоким и несбалансированным, а длина кодов недопустимо большой. Однако я немного в замешательстве - насколько мне известно, алгоритм Хаффмана успешно применяется для сжатия не только текстовых данных, но и для изображений в том числе. Подскажите, пожалуйста, что необходимо сделать, чтобы дерево не было слишком глубоким? И применяется ли при сжатии НЕ текстовых данных алгоритм Хаффмана в чистом виде? Или он применяется обязательно в сочетании с другими методами сжатия? Или использование адаптивного алгоритма изменит ситуацию? Спасибо большое! 0

@ОчереднойДжедай 0 / 0 / 0 Регистрация: 18.10.2015 Сообщений: 7
	20.03.2020, 22:59 [ТС]
	Только что попробовал .wav. Не вышло - файл с кодом Хаффмана все равно больше. 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	20.03.2020, 23:09
	примеров же много, изучай https://github.com/topics/huff... thm?l=java 0