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

@[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 **[ТС]**

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

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

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

	Как сжать двоичный файл 15.01.2016, 16:49. Показов 3689. Ответов 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 Сообщений: 524
	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 Сообщений: 524
	16.01.2016, 14:30 [ТС]
	Да, в файл так и писал 1 и 0. Да, как раз мне это и нужно как писать биты в файл, надеюсь что поможет, спасибо. Как только найду решение - сюда отпишусь. 0

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

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

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

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

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