PHP.SU

Программирование на PHP, MySQL и другие веб-технологии

PHP.SU Портал

Главная

Помощь

Поиск

Поиск Яндекс Вакансии

Пользователи

Здравствуйте, Гость

( Вход · Регистрация · Правила форума )

Забыли пароль?

Сжатие файла методом Хаффмана

Форумы портала PHP.SU » PHP » Программирование на PHP » Вопросы новичков (Модераторы: OrmaJever, Саныч, Строитель)

Страниц (1): [1]

Без описания

Поиск в теме | Версия для печати

Valtasaar	Отправлено: 28 Ноября, 2015 - 14:31:46
Новичок Покинул форум Сообщений всего: 17 Дата рег-ции: Нояб. 2015 Помог: 0 раз(а)	Доброго всем! Есть желание понять алгоритм Хаффмана для сжатия данных. Начальный код: PHP: скопировать код в буфер обмена $handle = fopen($fileComUpName, 'r+'); //Цикл для создания массива символов $arrChar = array(); $i = 0; if ($handle) { while (false !== ($char = fgetc($handle))){ $arrChar[$i] = $char; $i++; } } //Количество повторений символов и сортировка по возрастанию $arrCharVal = array_count_values ($arrChar); asort($arrCharVal); //Дерево $arrTree = array(); while (count($arrCharVal) > 1) { $key1 = key($arrCharVal); $val1 = array_shift($arrCharVal); $key2 = key($arrCharVal); $val2 = array_shift($arrCharVal); $key = $key1.$key2; $val = $val1 + $val2; $arrTree[$key] = $val; $arrCharVal[$key] = $val; asort($arrCharVal); } asort($arrTree); Сначала я считал символы с файла и поместил их в массив. Затем подсчитал количество вхождений каждого символа и упорядочил по возрастанию. Далее попытался построить дерево. Складывал элементы символов с наименьшим вхождением. Результат записывал в массив, где в качестве ключа используются символы, а в качестве значения сумма вхождений. В итоге получился массив вида: Array ( [char1char2]=>value, [char1char2char3]=>value, ...................... и т. д. ) Здесь char - это символы, value - общее число вхождений. Далее, насколько я понял, нужно пройтись по упорядоченному массиву от элемента с наибольшей общей суммой вхождений до конца и параллельно присваивая символам 1 либо 0. Если я проделаю такое с этим массивом, то в результате получу символы, закодированные большИм кол-вом байт. Это нормально или я что-то делаю не так?

DeepVarvar	Отправлено: 28 Ноября, 2015 - 15:18:24
Активный участник Покинул форум Сообщений всего: 10377 Дата рег-ции: Дек. 2008 Откуда: Альфа Центавра Помог: 353 раз(а)	https://www[dot]siggraph[dot]org/educati[dot][dot][dot]an_tutorial[dot]html ----- Шта? Репозиторий?

dcc0	Отправлено: 28 Ноября, 2015 - 15:29:38
Участник Покинул форум Сообщений всего: 1043 Дата рег-ции: Июль 2014 Помог: 10 раз(а)	DeepVarvar, интересно... про декодирование только что-то не понял по ссылке. Получили мы 102 в конце... т.е. для декодирования где-то хранятся соответствия частота -> значения ??? (Отредактировано автором: 29 Ноября, 2015 - 01:27:34) ----- Март 2021. Бросил программирование

DeepVarvar	Отправлено: 28 Ноября, 2015 - 15:33:23
Активный участник Покинул форум Сообщений всего: 10377 Дата рег-ции: Дек. 2008 Откуда: Альфа Центавра Помог: 353 раз(а)	Да хз, я сильно там не интересовался. При энкодировании собирается словарь и данные. А для обратного я вообще видел сразу таблицы готовые вшитые прямо в бинарик декодера. ----- Шта? Репозиторий?

Valtasaar	Отправлено: 28 Ноября, 2015 - 16:18:47
Новичок Покинул форум Сообщений всего: 17 Дата рег-ции: Нояб. 2015 Помог: 0 раз(а)	DeepVarvar это я все понимаю. Как это все правильно реализовать на php?

DeepVarvar	Отправлено: 28 Ноября, 2015 - 21:26:21
Активный участник Покинул форум Сообщений всего: 10377 Дата рег-ции: Дек. 2008 Откуда: Альфа Центавра Помог: 353 раз(а)	Понятия не имею. Ты бы еще спросил как на пхп ОС реализовать. Хочешь хафмана -- ползи в сишечку. Хочешь сайтики -- ползи в пхп. ----- Шта? Репозиторий?

dcc0	Отправлено: 29 Ноября, 2015 - 01:25:13
Участник Покинул форум Сообщений всего: 1043 Дата рег-ции: Июль 2014 Помог: 10 раз(а)	Если простым языком расписать алгоритм, без терминологии, расписать конкретные шаги, то можно попробовать подобрать инструменты, которые есть в PHP. И, забегая вперёд скажу, вероятнее всего, реализация не особенно сложная, но в целом конечный код будет выглядеть тяжеловато. И, вероятно поэтому, ДипВарвар прав, стоит выбрать другой язык. (Отредактировано автором: 29 Ноября, 2015 - 01:26:32) ----- Март 2021. Бросил программирование

Valtasaar	Отправлено: 29 Ноября, 2015 - 10:44:13
Новичок Покинул форум Сообщений всего: 17 Дата рег-ции: Нояб. 2015 Помог: 0 раз(а)	Да, я все понимаю. На данный момент изучаю php. Си будет как-нить потом. Если бы данная задача стояла передо мной на Си, то проблем не было бы. Я нашел кучу примеров на Си, на паскаль, на делфи и т. д. Дело в том, что данную задачу требуется реализовать на php без всяких сторонних библиотек. В общем принцип метода я понял. Но то ли в силу своей неопытности, то ли из-за сложности задачи не могу сдвинуться с мертвой точки. Сам до конца не понимаю зачем такие задачи нужны на пхп, но если они есть, значит кто-то их использует.

DeepVarvar	Отправлено: 29 Ноября, 2015 - 11:19:17
Активный участник Покинул форум Сообщений всего: 10377 Дата рег-ции: Дек. 2008 Откуда: Альфа Центавра Помог: 353 раз(а)	Их нет. И никто их не использует. Там такой неимоверный оверхед по ресурсам, что нет абсолютно никакого смысла кроме академического. Но сам пхп уже ставит под сомнение вменяемость такого "академика". ----- Шта? Репозиторий?

Valtasaar	Отправлено: 29 Ноября, 2015 - 11:33:59
Новичок Покинул форум Сообщений всего: 17 Дата рег-ции: Нояб. 2015 Помог: 0 раз(а)	Собственно, что меня натолкнуло на поиски такого метода на пхп. Тестовое задание в одной из компаний: Спойлер (Отобразить) В качестве тестового задания необходимо сделать небольшую web-страницу, которая будет позволять загружать файл на сервер и будет давать возможность скачать его упакованную версию. Также должна быть возможность загрузить упакованный файл и получить неупакованный вариант. Обязательные требования: 1) Сжатие файла должно выполняться по алгоритму Хаффмана 2) Серверная часть должна быть реализована на PHP и без использования сторонних библиотек. 3) Должны быть соблюдены базовые меры безопасности при получении файла от пользователя 4) Клиентская часть (форма загрузки файла, блок для загрузки упакованного файла) должна быть выполнена аккуратно, с соблюдением элементарных правил верстки. (Отредактировано автором: 29 Ноября, 2015 - 11:34:19)

DeepVarvar	Отправлено: 29 Ноября, 2015 - 11:46:25
Активный участник Покинул форум Сообщений всего: 10377 Дата рег-ции: Дек. 2008 Откуда: Альфа Центавра Помог: 353 раз(а)	Я так и думал. Варианта два: 1) Потешить самомнение автора задачи. 2) Реально заниматься на работе такой хренью на пыхе. Если первый вариант еще простителен. То второй -- я б туда работать не пошел. ----- Шта? Репозиторий?

Valtasaar	Отправлено: 29 Ноября, 2015 - 11:54:57
Новичок Покинул форум Сообщений всего: 17 Дата рег-ции: Нояб. 2015 Помог: 0 раз(а)	Я думаю, что такое задание было дано для проверки общей подготовленности по программированию. На деле, конечно, вряд ли так будут заморачиваться. Ладно, буду пробовать дальше, может что получиться. (Добавление) Нашел вот такую реализацию: http://code[dot]kuederle[dot]com/huffman

Поиск в теме | Версия для печати

Страниц (1): [1]

Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)

« Вопросы новичков »

Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.