| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Реализация Хафмана. |
| Автор: dima_mak 22.4.2005, 19:05 |
| Вот я тут реализовал сжатие по Хафману, да только ОЧЕНЬ медленно получилось. Помогите оптимизировать плиз. Коментарии к проге не сделал(сори), так что даю описания действий функций: 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) - главная функция которая просчитывает будущий размер заархивированого файла и вызывает остальные функции. Спасибо зарание! З.Ы Турбо С + дос |
| Автор: JackYF 22.4.2005, 22:33 |
| На алголист.мануал.ру есть описания и исходники, вроде нормальные, зачем изобретать велосипед? |
| Автор: dima_mak 23.4.2005, 15:15 | ||
Так можно вообще проги не писать! Почти все можно найти в готовом виде. |
| Автор: dima_mak 30.4.2005, 17:27 |
| Ещё вопросик! Почему когда я пытаюсь запаковать НЕ текстовый файл, у меня запакованый выходит раз в 10 больше не запакованого(хотя при расчете будушего размера поидее должно получится процентов на 30 меньше). |
| Автор: AISIN 1.5.2005, 15:42 |
| dima_mak А чем ты запаковываешь. Может настройки надо проверить? Насчет оптимизации. Оптимизировать можно и самому. Самое слабые места в любой программе это циклы умножение и деление. |
| Автор: bilbobagginz 1.5.2005, 15:52 |
| я бы посоветовал не умножения цыклы оптимизировать а создание словаря, и минимальную и максимальную длину сжимаемых слов/блоков ( не ASCII ) именно это то что в уже реализованных "велосипедах" уже съедено, и переварено. изобретать велосипед нужно в нескольких направлениях, и правильно: 1. посмотреть существует ли проблема. если нет дальше не надо идти ( т.е. попробовать велосипед самому, или ознакомиться с его ограничениями и устройством ) 2. посмотреть можешь ли ты сейчас придумать своё решение, с оптимизацией для данной задачи ( т.е. иногда существуют решения даже принципиально лучшие, чем существующие до них ) 3. посмотреть на уже существующие решения и сравнить ( или скомбинировать ) со своим решением ( в цене, и разных способностях и свойствах ) в конце концов, никто не будет использовать DM-Zip, если он не будет лучше: быстрее, экономнее, и удобнее чем RAR, PKZIP, infoZip, Arj или WinZip. не думаю что упражнение реализации алгоритма Хаффмана стоит сравнивать с настоящим решением настоящей проблемы, для которого не одну диссертацию написали немало неглупых дядей и тётей, после чего ещё больше дядей и тётей оптимизировали эти решения. вот... мои 10 коп. |
| Автор: AISIN 1.5.2005, 21:01 |
| bilbobagginz На счет циклов как думаешь есть разница отработать честно цикл 100 раз или сделать это за 10 раз практически не меняя алгоритм. |
| Автор: dima_mak 1.5.2005, 21:17 | ||
Что значит чем?! Своей прогой. Текстовые нормально, а все остальные получаются в 10 раз больше.  |
| Автор: AISIN 2.5.2005, 08:50 |
| dima_mak Все остальные это типа *.exe, *bmp и т.д. А обратно распаковываются нормально? Текст и я могу сжать до двух символов и не обязательно по Хафману. |
| Автор: bilbobagginz 2.5.2005, 09:50 |
| согласен, что если алгоритм реализован правильно, то нужно сделать оптимизацию уровнем ниже. но обычно цыклы оптимизируют только после того как сам принцип работы программы - правилен (алгоритм не делает ненужного ) , и есть уверенность в том что не алгоритм тормозит всё. только тогда смотрят на каком участке кода программа проводит больше времени и его оптимизируют. но если программа делает 10 раз умножение - упрись и сокращай, но умножишь 10 раз. а в данном случае, это _вообще_не_имеет_смысла_, потому что не скорость работы программы нужно поправить, а её результат.  я сильно ошибаюсь ? |
| Автор: AISIN 2.5.2005, 10:21 | ||
Я сдесь вычитал что JPEG файлы уже сжаты с помощью дискретного косинус - преобразования. Значит программа плохо сжимает файлы которые уже оптимально сжаты до нас ? bilbobagginz Честно говоря я еще не смотрел программу предложеную автором. Так что я не знаю насколько правелен алгоритм. А автор вроде просил оптимизировать. Значит результат работы программы его устраивал.... или я ошибаюсь? если умножение заменить сложением то будет как не странно это звучит быстрее! А сложение можно заменить сдвигом и будет еще быстрее! |
| Автор: dima_mak 2.5.2005, 17:22 | ||||
Ты прав.
Я скачивал другие реализации Хафмана и они чуть-чуть уменьшали размер ВСЕХ типов файлов. Я просто ступил и не проверил раньше на файлах отличных от текстовых, а когда проверил...... Вот новая версия проги(чуть чуть подправил, но не оптимизировал). |