Алгоритм Хаффмана

@Rocky878 · Регистрация: 22.08.2018

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

Я пытался построить простой архиватор на базе алгоритма, который мог бы кодировать произвольный файл. Побитово считывал с файла и получил таблицу с 256 битов и частотой вхождения каждого бита. Построил на их базе дерево, которое оказалось довольно глубоким, и при кодировании получается файл большего размера, чем исходный. Что то не так(не так понял)? В теории написано что можно сжать произвольный файл, но примеры только на тектовых символах с алфавитом меньше 10...

@Shamil1 · 22.08.2018, 19:32

Сообщение от Rocky878

получил таблицу с 256 битов и частотой вхождения каждого бита

Битов всего 2 - 0 и 1.

@Kuzia domovenok · 24.08.2018, 19:47

Алфавит меньше 10 будет в среднем кодироваться четырьмя битами. Одной только заменой в тексте однобайтовых ASCII символов на пачки из нескольких четырёхбитных, ты одним этим сожмёшь текст в два раза, а ведь частые символы там будут занимать ещё меньше.
В какой структуре ты хранишь словарь, что он получается большим? Ты же сам говоришь, в словаре 10 символов? Вот и храни эти 10 символов только.

@assemberist · 02.09.2018, 20:09

Код в студию! Желательно весь, но если у вас алфавит составляется правильно, то можно только часть в которой идет само кодирование.

И когда у вас получен алфавит как вы записываете сжатый код в выходной файл? Читаете символ из исходного файла, находите его код в полученном алфавите и записываете без смещения?

@Rocky878 0 / 0 / 0 Регистрация: 22.08.2018 Сообщений: 1
		1
	Алгоритм Хаффмана 22.08.2018, 18:02. Показов 822. Ответов 3 Метки нет (Все метки) Я пытался построить простой архиватор на базе алгоритма, который мог бы кодировать произвольный файл. Побитово считывал с файла и получил таблицу с 256 битов и частотой вхождения каждого бита. Построил на их базе дерево, которое оказалось довольно глубоким, и при кодировании получается файл большего размера, чем исходный. Что то не так(не так понял)? В теории написано что можно сжать произвольный файл, но примеры только на тектовых символах с алфавитом меньше 10... 0

@Shamil1 Модератор 3055 / 2197 / 459 Регистрация: 26.03.2015 Сообщений: 8,482
	22.08.2018, 19:32	2
	Сообщение от Rocky878 получил таблицу с 256 битов и частотой вхождения каждого бита Битов всего 2 - 0 и 1. 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,495 Записей в блоге: 1
	24.08.2018, 19:47	3
	Алфавит меньше 10 будет в среднем кодироваться четырьмя битами. Одной только заменой в тексте однобайтовых ASCII символов на пачки из нескольких четырёхбитных, ты одним этим сожмёшь текст в два раза, а ведь частые символы там будут занимать ещё меньше. В какой структуре ты хранишь словарь, что он получается большим? Ты же сам говоришь, в словаре 10 символов? Вот и храни эти 10 символов только. 0

@assemberist 447 / 323 / 129 Регистрация: 18.07.2017 Сообщений: 1,454
	02.09.2018, 20:09	4
	Код в студию! Желательно весь, но если у вас алфавит составляется правильно, то можно только часть в которой идет само кодирование. И когда у вас получен алфавит как вы записываете сжатый код в выходной файл? Читаете символ из исходного файла, находите его код в полученном алфавите и записываете без смещения? 0