Вот я тут реализовал сжатие по Хафману, да только ОЧЕНЬ медленно получилось. Помогите оптимизировать плиз.
Коментарии к проге не сделал(сори), так что даю описания действий функций:
long filesize(int stream) - возвращает размер файла
void init_tree() - делает инициализацию дерева
void print_tree() - печатает дерево(для отладки)
void read_count_f(string fname) - читает файл который нужно закодировать и ститает количество повторений для каждого символа и запихивает их в "дерево"
void tree_build() - строит "дерево" на основании количества повторений символов
void build_encode() - вычисляет новый код для каждого символа(в большинстве случаев меньший чем 8 бит), который встречается в файле
void writebit2file(int f,int bit) - пишет бит в файл
void file_encode(string fname,string ftoname) - главная функция которая просчитывает будущий размер заархивированого файла и вызывает остальные функции.

Спасибо зарание!

З.Ы
Турбо С + дос

Присоединённый файл ( Кол-во скачиваний: 27 )
 ENCODE1.zip

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

Цитата

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

Так можно вообще проги не писать! Почти все можно найти в готовом виде.

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

dima_mak А чем ты запаковываешь. Может настройки надо проверить? Насчет оптимизации. Оптимизировать можно и самому.
Самое слабые места в любой программе это циклы умножение и деление.

я бы посоветовал не умножения цыклы оптимизировать а создание словаря, и минимальную и максимальную длину сжимаемых слов/блоков ( не ASCII )

именно это то что в уже реализованных "велосипедах" уже съедено, и переварено.
изобретать велосипед нужно в нескольких направлениях, и правильно:
1. посмотреть существует ли проблема. если нет дальше не надо идти ( т.е. попробовать велосипед самому, или ознакомиться с его ограничениями и устройством )
2. посмотреть можешь ли ты сейчас придумать своё решение, с оптимизацией для данной задачи
( т.е. иногда существуют решения даже принципиально лучшие, чем существующие до них )

3. посмотреть на уже существующие решения и сравнить ( или скомбинировать ) со своим решением ( в цене, и разных способностях и свойствах )

в конце концов, никто не будет использовать DM-Zip, если он не будет лучше: быстрее, экономнее, и удобнее чем RAR, PKZIP, infoZip, Arj или WinZip.

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

вот... мои 10 коп.




Это сообщение отредактировал(а) bilbobagginz - 1.5.2005, 16:08

bilbobagginz На счет циклов как думаешь есть разница отработать честно цикл 100 раз или сделать это за 10 раз практически не меняя алгоритм.

Цитата(AISIN @ 1.5.2005, 15:42)

dima_mak А чем ты запаковываешь. Может настройки надо проверить? Насчет оптимизации. Оптимизировать можно и самому. Самое слабые места в любой программе это циклы умножение и деление.

Что значит чем?! Своей прогой. Текстовые нормально, а все остальные получаются в 10 раз больше.

dima_mak Все остальные это типа *.exe, *bmp и т.д. А обратно распаковываются нормально? Текст и я могу сжать до двух символов и не обязательно по Хафману.

согласен, что если алгоритм реализован правильно, то нужно сделать оптимизацию уровнем ниже. но обычно цыклы оптимизируют только после того как сам принцип работы программы - правилен (алгоритм не делает ненужного ) , и есть уверенность в том что не алгоритм тормозит всё. только тогда смотрят на каком участке кода программа проводит больше времени и его оптимизируют. но если программа делает 10 раз умножение - упрись и сокращай, но умножишь 10 раз.

а в данном случае, это _вообще_не_имеет_смысла_, потому что не скорость работы программы нужно поправить, а её результат.

я сильно ошибаюсь ?




Это сообщение отредактировал(а) bilbobagginz - 2.5.2005, 09:51

Цитата(dima_mak @ 30.4.2005, 17:27)

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

Я сдесь вычитал что JPEG файлы уже сжаты с помощью дискретного косинус - преобразования. Значит программа плохо сжимает файлы которые уже оптимально сжаты до нас ?
bilbobagginz Честно говоря я еще не смотрел программу предложеную автором. Так что я не знаю насколько правелен алгоритм. А автор вроде просил оптимизировать. Значит результат работы программы его устраивал.... или я ошибаюсь? если умножение заменить сложением то будет как не странно это звучит быстрее! А сложение можно заменить сдвигом и будет еще быстрее!

Это сообщение отредактировал(а) AISIN - 2.5.2005, 10:30

Цитата

согласен, что если алгоритм реализован правильно, то нужно сделать оптимизацию уровнем ниже. но обычно цыклы оптимизируют только после того как сам принцип работы программы - правилен (алгоритм не делает ненужного ) , и есть уверенность в том что не алгоритм тормозит всё. только тогда смотрят на каком участке кода программа проводит больше времени и его оптимизируют. но если программа делает 10 раз умножение - упрись и сокращай, но умножишь 10 раз. а в данном случае, это _вообще_не_имеет_смысла_, потому что не скорость работы программы нужно поправить, а её результат. я сильно ошибаюсь ?

Ты прав.

Цитата

Я сдесь вычитал что JPEG файлы уже сжаты с помощью дискретного косинус - преобразования. Значит программа плохо сжимает файлы которые уже оптимально сжаты до нас ? bilbobagginz Честно говоря я еще не смотрел программу предложеную автором. Так что я не знаю насколько правелен алгоритм. А автор вроде просил оптимизировать. Значит результат работы программы его устраивал.... или я ошибаюсь? если умножение заменить сложением то будет как не странно это звучит быстрее! А сложение можно заменить сдвигом и будет еще быстрее!

Я скачивал другие реализации Хафмана и они чуть-чуть уменьшали размер ВСЕХ типов файлов. Я просто ступил и не проверил раньше на файлах отличных от текстовых, а когда проверил......
Вот новая версия проги(чуть чуть подправил, но не оптимизировал).

Присоединённый файл ( Кол-во скачиваний: 18 )
 new_hafman.zip