1 / 1 / 2
Регистрация: 09.10.2009
Сообщений: 413
1

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

15.01.2016, 16:49. Показов 2915. Ответов 28
Метки нет (Все метки)

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

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

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

Например txt-файл, содержащий строку "test_string" занимает размер 11 байт, а файл, где каждый символ заменён на нули и единицы занимает 32 байта ((((
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.01.2016, 16:49
Ответы с готовыми решениями:

Как сжать exe-файл?
Как средствами делфи упаковать exe файл так же как это делает всякие upx только за своим...

Как можно сжать текстовый файл?
Всем здравствуйте. Сразу скажу - перерыл на двух языках в Интернете много чего - конкретного...

Как или чем максимально сжать файл?
Как или чем можно максимально сжать файл Program.cs (visual studio 2013)

Как выгрузить двоичный файл?
<form enctype='multipart/form-data' .... - после выгрузки работают только текстовые.

28
Кандёхаем веселее!
296 / 328 / 76
Регистрация: 02.10.2012
Сообщений: 2,175
15.01.2016, 23:57 2
Наверное, вышло больше из-за хранения метаинформации в файле: инфа о том, какой символ кодируется какой последовательностью тоже что-то весит, но если закодировать много текста, её доля будет практически незаметной.
0
1 / 1 / 2
Регистрация: 09.10.2009
Сообщений: 413
16.01.2016, 10:18  [ТС] 3
Ну пока всё не так, входную последовательность символов я просто заменил нулями и единицами, 0 и 1 стало больше, чем самих символов. Я не знаю что мне делать дальше с этим txt-файлом, содержащим 0 и 1 чтобы реально его сжать. Таблица частот символов, и само дерево Хаффмана хранится в php-переменных. Реализовывал всё на php.
0
434 / 299 / 82
Регистрация: 11.12.2010
Сообщений: 1,209
16.01.2016, 13:39 4
Вы в файл так и писали 1 и 0?
Тогда логично что он больше. Так как вы закодировали байт битом, но записали его как код символа 0 и 1 то есть опять байтом.
Почитайте как в php писать биты в файл, скорее всего есть статьи об этом.
0
1 / 1 / 2
Регистрация: 09.10.2009
Сообщений: 413
16.01.2016, 14:30  [ТС] 5
Да, в файл так и писал 1 и 0. Да, как раз мне это и нужно как писать биты в файл, надеюсь что поможет, спасибо. Как только найду решение - сюда отпишусь.
0
Модератор
Эксперт функциональных языков программирования
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,470
16.01.2016, 14:50 6
Цитата Сообщение от [FENIX] Посмотреть сообщение
Например txt-файл, содержащий строку "test_string" занимает размер 11 байт, а файл, где каждый символ заменён на нули и единицы занимает 32 байта
Вы каждый символ меняете на несколько символов. Не удивительно, что размер становится больше.

Цитата Сообщение от [FENIX] Посмотреть сообщение
Я не знаю что мне делать дальше с этим txt-файлом, содержащим 0 и 1 чтобы реально его сжать.
Можно легко сжать в 8 раз, если для хранения 0/1 использовать не по байту, а по биту на каждый.
0
1 / 1 / 2
Регистрация: 09.10.2009
Сообщений: 413
16.01.2016, 16:20  [ТС] 7
Да, сейчас читаю как писать биты в файл, надеюсь что поможет. Потом ещё буду делать обратную задачу - по битовой последовательности восстанавливать исходный текст.

Добавлено через 1 час 21 минуту
Похоже что надо использовать функции pack() и unpack(). С pack() вроде бы разобрался, а вот с unpack() пока возникают сложности...
0
Модератор
Эксперт функциональных языков программирования
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,470
16.01.2016, 17:12 8
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 битов.
0
1 / 1 / 2
Регистрация: 09.10.2009
Сообщений: 413
17.01.2016, 18:13  [ТС] 9
Shamil1 а у тебя нет примера на php. У меня всё на php реализовано.

Добавлено через 50 минут
Тут как то надо битовую арифметику применить, а как - не знаю ((
0
Модератор
Эксперт функциональных языков программирования
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,470
17.01.2016, 18:31 10
На пхп не писал никогда. Используйте битовый сдвиг.
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));
}
0
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,037
18.01.2016, 14:32 11
Цитата Сообщение от [FENIX] Посмотреть сообщение
Тут как то надо битовую арифметику применить, а как - не знаю ((
ну если на пальцах:
пусть у тебя строка s[i] из символов "0" и "1" в количестве 8 штук
заводим числовую переменную х = 0
далее по всем символам в строке S цикл:
х = (побитовый сдвиг влево на единицу в переменной Х)
х = (перевод s[i] в целое число) + Х

Добавлено через 4 минуты
может это - функция bindec ?
http://php.net/manual/ru/function.bindec.php
0
1 / 1 / 2
Регистрация: 09.10.2009
Сообщений: 413
19.01.2016, 10:56  [ТС] 12
Я пробовал использовать и битовый сдвиг, и функцию 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"
0
Модератор
Эксперт функциональных языков программирования
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,470
19.01.2016, 12:06 13
Число бит в массиве байт кратно 8. Если Вы в последний байт записали меньше 8 бит, то "лишнее" место будет занято нулями. Нужно что-то придумать, чтобы лишние нули не искажали Ваш текст.
Например, добавьте в алфавит символ "конец текста" и игнорируйте все биты после него.

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

Добавлено через 5 минут
Напишите класс с методами:
добавить бит
получить биты
добавить байты
получить байты
0
1 / 1 / 2
Регистрация: 09.10.2009
Сообщений: 413
19.01.2016, 13:06  [ТС] 14
Я не понимаю зачем это нужно? У меня те нули, которые в начале строки - они пропадают при выполнении операции битового сдвига. Как мне эти нули сохранить?

Если например входная строка=010000011011, то как мне сохранить 1-й символ? 010000011011 Операция арифметического сдвига нормально работает, но если выполнять обратную ей операцию - из десятичного числа получить двоичное, то получится 10000011011. Ноль в начале пропускается.
0
434 / 299 / 82
Регистрация: 11.12.2010
Сообщений: 1,209
19.01.2016, 13:22 15
Вам в файл надо писать
1) Таблицу символ - код
2) Длину тела
3) Само тело
Я в своё время разделял разделы структуры двумя нулевыми байтами.

PHP для этой задачи вам не подходит.
Да и C# не кайф, там приходится работать с массивом bool значений.
Ноль в начале пропускается.
И да, кто вам сказал что он теряет ноль?
Комп видит число как
00000100 00011011. Ваша задача записать реальную длину строчки.
И дополнить строку до целого байта.
0100 0001 1011 0000
И да, кто вам сказал что он теряет ноль?
0
1 / 1 / 2
Регистрация: 09.10.2009
Сообщений: 413
19.01.2016, 13:33  [ТС] 16
А JavaScript подойдёт для этого? Мне нужно для веб. Нужно чтобы пользователь мог загружать на страницу текстовый файл (*.txt), а на серверной стороне чтобы выполнялось его сжатие по алгоритму Хаффмана. Чтобы потом пользователь мог скачать упакованную версию этого файла. И наоборот, чтобы пользователь мог загружать упакованный файл, на сервере он бы обрабатывался, и выдавался бы *.txt-файл.
0
Модератор
Эксперт функциональных языков программирования
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,470
19.01.2016, 13:41 17
Цитата Сообщение от [FENIX] Посмотреть сообщение
Я не понимаю зачем это нужно?
Зачем нужен класс? Для того, чтобы, добавив два раза "111", Вы получили на выходе "11111100", а не "1100000011000000". И Вам не нужно будет хранить промежуточные результаты в виде строки - можно будет писать сразу в массив байт.
0
1471 / 826 / 140
Регистрация: 12.10.2013
Сообщений: 5,456
19.01.2016, 15:24 18
Хм.. что за хафман.. =).
Я бы просмотрел весь текст на уникальные слова, затем каждому слову присвоил число.
В итоге от уровня заумности текста будет зависит размер сжатого фаила.
В итоге будет не кодировка битов а кодировка целых слов:
“Я бы просмотрел весь текст на уникальные слова ” будет код типа: “1 2 3 4 5 6 7 8”
0
434 / 299 / 82
Регистрация: 11.12.2010
Сообщений: 1,209
19.01.2016, 15:31 19
Цитата Сообщение от Excalibur921 Посмотреть сообщение
Хм.. что за хафман.. =).
Ох... Это вам на википедию. Это алгоритм сжатия текста в основе которого идет построение дерева по частоте символов
0
1 / 1 / 2
Регистрация: 09.10.2009
Сообщений: 413
19.01.2016, 15:32  [ТС] 20
Ага, а если уникальных слов сотня, и не одна, тогда что?
0
19.01.2016, 15:32
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.01.2016, 15:32
Помогаю со студенческими работами здесь

Как прочитать двоичный файл
я ввожу команду creat создать файл noobs.dat и ввожу туда n чисел a = число, и так n раз как я...

Как сохранить двоичный файл в строку?
Всем привет, У меня такая задача. Есть некоторые двоичный файл, то есть НЕ текстовый, а...

Как считать двоичный файл в массив?
Помогите, пожалуйста, обидно спотыкаться на простейших вещах. Требуется: открыть файл в двоичном...

Текстовый файл перевести в двоичный, а потом полученный двоичный файл перевести обратно в текстовый
Всем привет. Есть такая задачка: &quot;текстовый файл перевести в двоичный, а потом полученный двоичный...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru