Как сжать двоичный файл

@[FENIX] · Регистрация: 09.10.2009

Студворк — интернет-сервис помощи студентам

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

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

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

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

@MLPMan · 15.01.2016, 23:57

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

@[FENIX] · 16.01.2016, 10:18 **[ТС]**

Ну пока всё не так, входную последовательность символов я просто заменил нулями и единицами, 0 и 1 стало больше, чем самих символов. Я не знаю что мне делать дальше с этим txt-файлом, содержащим 0 и 1 чтобы реально его сжать. Таблица частот символов, и само дерево Хаффмана хранится в php-переменных. Реализовывал всё на php.

@Kill100 · 16.01.2016, 13:39

Вы в файл так и писали 1 и 0?
Тогда логично что он больше. Так как вы закодировали байт битом, но записали его как код символа 0 и 1 то есть опять байтом.
Почитайте как в php писать биты в файл, скорее всего есть статьи об этом.

@[FENIX] · 16.01.2016, 14:30 **[ТС]**

Да, в файл так и писал 1 и 0. Да, как раз мне это и нужно как писать биты в файл, надеюсь что поможет, спасибо. Как только найду решение - сюда отпишусь.

@Shamil1 · 16.01.2016, 14:50

Сообщение от [FENIX]

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

Вы каждый символ меняете на несколько символов. Не удивительно, что размер становится больше.

Сообщение от [FENIX]

Я не знаю что мне делать дальше с этим txt-файлом, содержащим 0 и 1 чтобы реально его сжать.

Можно легко сжать в 8 раз, если для хранения 0/1 использовать не по байту, а по биту на каждый.

@[FENIX] · 16.01.2016, 16:20 **[ТС]**

Да, сейчас читаю как писать биты в файл, надеюсь что поможет. Потом ещё буду делать обратную задачу - по битовой последовательности восстанавливать исходный текст.

Добавлено через 1 час 21 минуту
Похоже что надо использовать функции pack() и unpack(). С pack() вроде бы разобрался, а вот с unpack() пока возникают сложности...

@Shamil1 · 16.01.2016, 17:12

C#
1
2
3
4
5
6
7
8
9
10
string str = "1100110101010101111000";
bool[] bools = str.Select(x => x == '1').ToArray();
BitArray bits = new BitArray(bools);
byte[] bytes = new byte[(bits.Length - 1) / 8 + 1];
bits.CopyTo(bytes, 0);
 
BitArray bits2 = new BitArray(bytes);
bool[] bools2 = new bool[bits2.Count];
bits2.CopyTo(bools2, 0);
string str2 = new string(bools2.Select(x => x ? '1' : '0').ToArray());

Как-то так. Но помните, что последний байт будет добит нулями до 8 битов.

@[FENIX] · 17.01.2016, 18:13 **[ТС]**

Shamil1 а у тебя нет примера на php. У меня всё на php реализовано.

Добавлено через 50 минут
Тут как то надо битовую арифметику применить, а как - не знаю ((

@Shamil1 · 17.01.2016, 18:31

На пхп не писал никогда. Используйте битовый сдвиг.

C#
1
2
3
4
5
6
7
byte[] bytes = new byte[(bools.Length - 1) / 8 + 1];
for(int i = 0; i < bools.Length; i++)
{
    int k = i >> 3; // индекс байта в массиве
    int j = i - (k << 3); // индекс бита в байте
    bytes[k] = (byte)(bytes[k] | (Convert.ToByte(bools[i]) << j));
}

@wingblack · 18.01.2016, 14:32

Сообщение от [FENIX]

Тут как то надо битовую арифметику применить, а как - не знаю ((

ну если на пальцах:
пусть у тебя строка s[i] из символов "0" и "1" в количестве 8 штук
заводим числовую переменную х = 0
далее по всем символам в строке S цикл:
х = (побитовый сдвиг влево на единицу в переменной Х)
х = (перевод s[i] в целое число) + Х

Добавлено через 4 минуты
может это - функция bindec ?
http://php.net/manual/ru/function.bindec.php

@[FENIX] · 19.01.2016, 10:56 **[ТС]**

Я пробовал использовать и битовый сдвиг, и функцию bindec. Вот например у меня есть строка:

PHP
1
2
3
4
5
6
7
8
9
$sym="010000011011";//Так я закодировал слово "kymap", k="01", y="000", m="001", a="10", p="11"
 
$x=0;//Числовая переменная
for($i=0; $i<strlen($sym); $i++)
{
    $x=($x<<1);//Побитовый сдвиг влево на единицу
    $x=(int)$sym[$i]+$x;
    echo "<br/>".$x;//вывод, для отладки
}

В итоге получается что переменная $x=1051. В общем то в десятичный вид переводит нормально. И функция bindec() возвращает тоже 1051. Но проблема в том, что я потом обратно десятичное число не смогу преобразовать в 010000011011. У меня 0 в старшем разряде пропадает ((. В общем пропадают все те нули, которые стоят в начале исходной строки.

Добавлено через 12 минут
Я левому узлу давал "0", а правому "1". Сейчас исправил. Если в дереве давать левому узлу "1", а правому "0", тогда тоже бывают ситуации, когда в начале строки нули появляются (((. Пока так решение и не нашёл.

Добавлено через 1 час 48 минут
Ещё и декодировать не получается. Наверно метод обхода дерева Хаффмана для декодирования неверно составил, народ, гляньте пожалуйста:

//Метод получения символа из бинарного кода

PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    function getMessage($root, $code, $pos)
    {
        $msg="";
        echo "<br/> code=".$code." pos=".$pos." msg=".$msg;
        if($root!=null)
        {
            if($code[$pos]=="1")
            {
                
                $this->getMessage($root->getLeft(), $code, $pos+1);
                $msg=$msg.$this->getMessage($root->getLeft(), $code, $pos+1);
            }
            else
            {
                
                $this->getMessage($root->getRight(), $code, $pos+1);
                $msg=$msg.$this->getMessage($root->getRight(), $code,$pos+1);
            }
        }
        
        return $msg;
    }

И сам вызов:

PHP
1
$Tree->getMessage($Tree->getRoot(),$sym, 0);

$sym="101111100100"; Функция должна вернуть "kymap"

@Shamil1 · 19.01.2016, 12:06

Число бит в массиве байт кратно 8. Если Вы в последний байт записали меньше 8 бит, то "лишнее" место будет занято нулями. Нужно что-то придумать, чтобы лишние нули не искажали Ваш текст.
Например, добавьте в алфавит символ "конец текста" и игнорируйте все биты после него.

И определите строго, как (в каком порядке) Вы храните биты в байтовом массиве. Я предлагаю естественный порядок: байты сначала младшие (первые), биты сначала старшие (первые). Но Вы выбирайте тот порядок, который удобен Вам.

Добавлено через 5 минут
Напишите класс с методами:
добавить бит
получить биты
добавить байты
получить байты

@[FENIX] · 19.01.2016, 13:06 **[ТС]**

Я не понимаю зачем это нужно? У меня те нули, которые в начале строки - они пропадают при выполнении операции битового сдвига. Как мне эти нули сохранить?

Если например входная строка=010000011011, то как мне сохранить 1-й символ? 010000011011 Операция арифметического сдвига нормально работает, но если выполнять обратную ей операцию - из десятичного числа получить двоичное, то получится 10000011011. Ноль в начале пропускается.

@Kill100 · 19.01.2016, 13:22

Вам в файл надо писать
1) Таблицу символ - код
2) Длину тела
3) Само тело
Я в своё время разделял разделы структуры двумя нулевыми байтами.

PHP для этой задачи вам не подходит.
Да и C# не кайф, там приходится работать с массивом bool значений.

Ноль в начале пропускается.

И да, кто вам сказал что он теряет ноль?
Комп видит число как
00000100 00011011. Ваша задача записать реальную длину строчки.
И дополнить строку до целого байта.
0100 0001 1011 0000
И да, кто вам сказал что он теряет ноль?

@[FENIX] · 19.01.2016, 13:33 **[ТС]**

А JavaScript подойдёт для этого? Мне нужно для веб. Нужно чтобы пользователь мог загружать на страницу текстовый файл (*.txt), а на серверной стороне чтобы выполнялось его сжатие по алгоритму Хаффмана. Чтобы потом пользователь мог скачать упакованную версию этого файла. И наоборот, чтобы пользователь мог загружать упакованный файл, на сервере он бы обрабатывался, и выдавался бы *.txt-файл.

@Shamil1 · 19.01.2016, 13:41

Сообщение от [FENIX]

Я не понимаю зачем это нужно?

Зачем нужен класс? Для того, чтобы, добавив два раза "111", Вы получили на выходе "11111100", а не "1100000011000000". И Вам не нужно будет хранить промежуточные результаты в виде строки - можно будет писать сразу в массив байт.

@Excalibur921 · 19.01.2016, 15:24

Хм.. что за хафман.. =).
Я бы просмотрел весь текст на уникальные слова, затем каждому слову присвоил число.
В итоге от уровня заумности текста будет зависит размер сжатого фаила.
В итоге будет не кодировка битов а кодировка целых слов:
“Я бы просмотрел весь текст на уникальные слова ” будет код типа: “1 2 3 4 5 6 7 8”

@Kill100 · 19.01.2016, 15:31

Сообщение от Excalibur921

Хм.. что за хафман.. =).

Ох... Это вам на википедию. Это алгоритм сжатия текста в основе которого идет построение дерева по частоте символов

@[FENIX] · 19.01.2016, 15:32 **[ТС]**

Ага, а если уникальных слов сотня, и не одна, тогда что?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@[FENIX] 4 / 4 / 2 Регистрация: 09.10.2009 Сообщений: 539

	Как сжать двоичный файл 15.01.2016, 16:49. Показов 3762. Ответов 28 Метки нет (Все метки) Всем привет народ. Вот такой вопрос. По Алгоритму Хаффмана я закодировал входную строку (текст). Получил 0 и 1. Построил таблицу частот символов, и само дерево Хаффмана. Потом записываю эти 0 и 1 в txt-файл, НО размер txt-файла, содержащего 0 и 1 превышает размер файла с исходным текстом. В общем я реализовал только кодирование по алгоритму Хаффмана, получил нули и единицы. Мне в конечном итоге нужно получить из исходного текстового файла - его упакованную версию (само собой с меньшим размером). Потом уже буду из упакованной версии файла восстанавливать исходную строку символов. Помогите, в какую сторону копать? Например txt-файл, содержащий строку "test_string" занимает размер 11 байт, а файл, где каждый символ заменён на нули и единицы занимает 32 байта (((( 0

@MLPMan Кандёхаем веселее! 296 / 330 / 76 Регистрация: 02.10.2012 Сообщений: 2,175
	15.01.2016, 23:57
	Наверное, вышло больше из-за хранения метаинформации в файле: инфа о том, какой символ кодируется какой последовательностью тоже что-то весит, но если закодировать много текста, её доля будет практически незаметной. 0

@[FENIX] 4 / 4 / 2 Регистрация: 09.10.2009 Сообщений: 539
	16.01.2016, 10:18 [ТС]
	Ну пока всё не так, входную последовательность символов я просто заменил нулями и единицами, 0 и 1 стало больше, чем самих символов. Я не знаю что мне делать дальше с этим txt-файлом, содержащим 0 и 1 чтобы реально его сжать. Таблица частот символов, и само дерево Хаффмана хранится в php-переменных. Реализовывал всё на php. 0

@Kill100 434 / 299 / 82 Регистрация: 11.12.2010 Сообщений: 1,209
	16.01.2016, 13:39
	Вы в файл так и писали 1 и 0? Тогда логично что он больше. Так как вы закодировали байт битом, но записали его как код символа 0 и 1 то есть опять байтом. Почитайте как в php писать биты в файл, скорее всего есть статьи об этом. 0

@[FENIX] 4 / 4 / 2 Регистрация: 09.10.2009 Сообщений: 539
	16.01.2016, 14:30 [ТС]
	Да, в файл так и писал 1 и 0. Да, как раз мне это и нужно как писать биты в файл, надеюсь что поможет, спасибо. Как только найду решение - сюда отпишусь. 0

@[FENIX] 4 / 4 / 2 Регистрация: 09.10.2009 Сообщений: 539
	16.01.2016, 16:20 [ТС]
	Да, сейчас читаю как писать биты в файл, надеюсь что поможет. Потом ещё буду делать обратную задачу - по битовой последовательности восстанавливать исходный текст. Добавлено через 1 час 21 минуту Похоже что надо использовать функции pack() и unpack(). С pack() вроде бы разобрался, а вот с unpack() пока возникают сложности... 0

@[FENIX] 4 / 4 / 2 Регистрация: 09.10.2009 Сообщений: 539
	17.01.2016, 18:13 [ТС]
	Shamil1 а у тебя нет примера на php. У меня всё на php реализовано. Добавлено через 50 минут Тут как то надо битовую арифметику применить, а как - не знаю (( 0

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,878
	19.01.2016, 12:06
	Число бит в массиве байт кратно 8. Если Вы в последний байт записали меньше 8 бит, то "лишнее" место будет занято нулями. Нужно что-то придумать, чтобы лишние нули не искажали Ваш текст. Например, добавьте в алфавит символ "конец текста" и игнорируйте все биты после него. И определите строго, как (в каком порядке) Вы храните биты в байтовом массиве. Я предлагаю естественный порядок: байты сначала младшие (первые), биты сначала старшие (первые). Но Вы выбирайте тот порядок, который удобен Вам. Добавлено через 5 минут Напишите класс с методами: добавить бит получить биты добавить байты получить байты 0

@[FENIX] 4 / 4 / 2 Регистрация: 09.10.2009 Сообщений: 539
	19.01.2016, 13:06 [ТС]
	Я не понимаю зачем это нужно? У меня те нули, которые в начале строки - они пропадают при выполнении операции битового сдвига. Как мне эти нули сохранить? Если например входная строка=010000011011, то как мне сохранить 1-й символ? 010000011011 Операция арифметического сдвига нормально работает, но если выполнять обратную ей операцию - из десятичного числа получить двоичное, то получится 10000011011. Ноль в начале пропускается. 0

@[FENIX] 4 / 4 / 2 Регистрация: 09.10.2009 Сообщений: 539
	19.01.2016, 13:33 [ТС]
	А JavaScript подойдёт для этого? Мне нужно для веб. Нужно чтобы пользователь мог загружать на страницу текстовый файл (.txt), а на серверной стороне чтобы выполнялось его сжатие по алгоритму Хаффмана. Чтобы потом пользователь мог скачать упакованную версию этого файла. И наоборот, чтобы пользователь мог загружать упакованный файл, на сервере он бы обрабатывался, и выдавался бы .txt-файл. 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	19.01.2016, 15:24
	Хм.. что за хафман.. =). Я бы просмотрел весь текст на уникальные слова, затем каждому слову присвоил число. В итоге от уровня заумности текста будет зависит размер сжатого фаила. В итоге будет не кодировка битов а кодировка целых слов: “Я бы просмотрел весь текст на уникальные слова ” будет код типа: “1 2 3 4 5 6 7 8” 0

@[FENIX] 4 / 4 / 2 Регистрация: 09.10.2009 Сообщений: 539
	19.01.2016, 15:32 [ТС]
	Ага, а если уникальных слов сотня, и не одна, тогда что? 0