Как сжать двоичный файл. , Алгоритм Хаффмана

Всем привет народ. Вот такой вопрос.
По Алгоритму Хаффмана я закодировал входную строку (текст). Получил 0 и 1. Построил таблицу частот символов, и само дерево Хаффмана. Потом записываю эти 0 и 1 в txt-файл, НО размер txt-файла, содержащего 0 и 1 превышает размер файла с исходным текстом.

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

Потом уже буду из упакованной версии файла восстанавливать исходную строку символов.
Помогите, в какую сторону копать?

Например txt-файл, содержащий строку "test_string" занимает размер 11 байт, а файл, где каждый символ заменён на нули и единицы занимает 32 байта ((((
Реализовывал всё на PHP.

Нули и единицы должны содержаться в отдельных битах. В PHP это возможно? Работа с битами есть?

Сообщение отредактировано: MBo - 15.01.16, 14:27

Цитата [FENIX] @ 15.01.16, 13:55

Помогите, в какую сторону копать?

Упаковать нули и 1 в непрерывную последовательность и записывать получающиеся байты.
Но при кодировании двоичного файла читать вики:

Цитата вики

Классический алгоритм Хаффмана имеет ряд существенных недостатков. Во-первых, для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования. Во-вторых, избыточность кодирования обращается в ноль лишь в тех случаях, когда вероятности кодируемых символов являются обратными степенями числа 2. В-третьих, для источника с энтропией, не превышающей 1 (например, для двоичного источника), непосредственное применение кода Хаффмана бессмысленно.

MBo а вот я и не знаю есть ли в PHP такая возможность ((

Славян можешь подсказать, как в PHP можно реализовать упаковку нулей и единиц в непрерывную последовательность? Или хотя бы ссылку дать

Цитата [FENIX] @ 15.01.16, 15:24

Славян можешь подсказать, как в PHP можно реализовать упаковку нулей и единиц в непрерывную последовательность?

Да просто числа умножать нацело на степени двойки и проводить побитовую операцию ИЛИ. Т.к. я ничего про PHP не знаю, то тут я вам явно не тонкий помощник; только какие-то общие соображения могу подсказать.

http://php.net/manual/ru/language.operators.bitwise.php

Цитата [FENIX] @ 15.01.16, 13:55

Реализовывал всё на PHP.

Это курсач или просто для интереса? В PHP есть свои библиотеки сжатия, есличо.

Это не курсач, но сделать надо, сжатие надо обязательно сделать по алгоритму Хаффмана, а что используют готовые бибиотеки я ж не знаю