Форумы портала PHP.SU

PHP.SU

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

PHP.SU Портал

Главная

Помощь

Поиск

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

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

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

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

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

Форумы портала PHP.SU » Список сообщений, автором которых является Valtasaar

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

Найдено сообщений: 17

Valtasaar	Отправлено: 28 Ноября, 2015 - 16:18:47 • Тема: Сжатие файла методом Хаффмана • Форум: Вопросы новичков
Ответов: 11 Просмотров: 704	DeepVarvar это я все понимаю. Как это все правильно реализовать на php?

Valtasaar

Отправлено: 28 Ноября, 2015 - 14:31:46 • Тема: Сжатие файла методом Хаффмана • Форум: Вопросы новичков

Ответов: 11
Просмотров: 704

Доброго всем!

Есть желание понять алгоритм Хаффмана для сжатия данных.

Начальный код:

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. Если я проделаю такое с этим массивом, то в результате получу символы, закодированные большИм кол-вом байт. Это нормально или я что-то делаю не так?

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