ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Экспресс-проверка данных на возможность сжатия
25 сообщений из 47, страница 1 из 2
  1  все
Экспресс-проверка данных на возможность сжатия
    #39129057
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Задача: экономить время при передаче данных по инету. Данные могут быть любые: от выборок из БД до архивов, от картинок JPG до BMP.

Архивирование помогает если есть чего жать, но если жать нечего, то лишняя тормозная операция. Сейчас сначала жмется, затем если пожатое больше - используется нежатое.

Поэтому хочется сделать какой-то экспресс-тест, который с максимально низкими затратами скажет стоит ли пробовать паковать.

 
Заготовка
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
enum pack_result {PR_PACK, PR_UNKNOWN, PR_NEED_PACK};

class pack_test {
	uint8_t data[256];
public:
	pack_test() {
		memset(data, 0, 256);
	}

	// Добавление блока
	void add(uint8_t* buf, size_t size) {
		for(uint8_t* i = buf + size - 1; i >= buf; i--) {
			data[*i]++;
		}
	}

	// Проверка
	pack_result check() {
		int cnt = 0;
		for(int i = 0; i < 256; i++) {
			if(data[i] > 0) cnt++;
		}
		if(cnt < 128) {
			return PR_NEED_PACK;
		} else if(cnt < 192) {
			return PR_UNKNOWN;
		} else {
			return PR_PACK;
		}
	}
};

void test_file(const char* filename) {
	FILE* file = fopen(filename, "rb");   
	if (file != NULL) { 
		printf("test %s ... ", filename);
		uint8_t buf [8 * 1024];
		pack_test pt;
		size_t read;
		while ((read = fread(buf, 1, sizeof(buf), file)) > 0) {
			pt.add(buf, read);
			if(pt.check() != PR_UNKNOWN) break;
		}
		fclose(file);
		printf("%s\n", pt.check() == PR_PACK ? "comressed" : "need pack");
	}
}


int main(int argc, char* argv[])
{
	test_file(....xml");
	test_file("....rar");
	system("pause");
	return 0;
}


Как я вижу: посчитать побайтно вхождение каждого значения (метод pack_test.add()), а потом как-то оценить (pack_test.check()) запаковано/незнаю/незапаковано.

Пока тупо посчитал количество употребляемых символов, на моих файлах (.rar и .xml) уже правильно сработало. Но как-то это примитивно, надо что-то посерьезнее.

PS Может я велосипед изобретаю?
...
Рейтинг: 0 / 0
15.12.2015, 19:08
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129107
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Dima TЗадача: экономить время при передаче данных по инету.А хоть при каких-нибудь данных (реально встречающихся, а не блока из миллиарда нулей) есть ли смысл сжимать эти данные?
...
Рейтинг: 0 / 0
15.12.2015, 19:52
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129122
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
miksoftDima TЗадача: экономить время при передаче данных по инету.А хоть при каких-нибудь данных (реально встречающихся, а не блока из миллиарда нулей) есть ли смысл сжимать эти данные?
xml файл размером 5 Мб жмется до 0,8 Мб. Даже при пиковой скорости 10 Мбит это 0,5 сек против 0,08 сек. За 0,42 сек его можно трижды пожать. Обычная скорость 1-2 Мбит это уже секунды.
...
Рейтинг: 0 / 0
15.12.2015, 20:08
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129123
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Опечатался, не Мбит, а Мбайт/сек.
...
Рейтинг: 0 / 0
15.12.2015, 20:10
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129175
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Посмотрел умолчания DrWeb-овского ES-сервера и провёл "микроследствие" ...
Действительно, для deflate оптимальным является сжатие с уровнем 8 - заметно быстрее максимального, не сильно просаживает скорость на уже сжатых данных и может дать мизерный, но выигрыш в размере.

P.S. Проще, imho, использовать какой-либо из "высокоскоростных" алгоритмов.
...
Рейтинг: 0 / 0
15.12.2015, 21:04
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129177
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Хотя, для "типичных" интернет-скоростей можно и классический deflate использовать - запас по производительности будет даже в однопоточном (последовательном) режиме.
...
Рейтинг: 0 / 0
15.12.2015, 21:07
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129208
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Dima T,

во первых на ум приходят lzo/lz4. Во вторых нужен специльный потоковый метод сжатия, такой что бы подстраивал степень сжатия пропускной способности канала. Типа отправляем первый блок в очередь передачи и жмём второй блок. Если передача первого завершилась то останавливаем сжатие и передаём второй блок с достигнутым сжатием.
...
Рейтинг: 0 / 0
15.12.2015, 22:11
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129209
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Подумалось, а ведь файлы в большинстве своем довольно однородны по свое длине по степени сжимаемости (за исключением краев). Тогда можно взять где-то в середине небольшой произвольный блок, например, в 16 Кбайт, сжать его и на основе этого и принимать решение сжимать/не сжимать. Блок должен быть не слишком близко к краям (т.к. начальные и конечные блоки бинарных файлов часто используются для текстовых вставок/комментариев/ресурсов и т.п.), не слишком маленьким (чтобы накладные расходы на словарь и прочее не съели экономию от сжатия) и не слишком большим (чтобы время сжатия было не накладным).
...
Рейтинг: 0 / 0
15.12.2015, 22:13
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129312
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
miksoftможно взять где-то в середине небольшой произвольный блок, например, в 16 Кбайт, сжать его и на основе этого и принимать решение сжимать/не сжимать.
Отличная мысль, так и сделаю. Спасибо.

Изначально идея была такая: посчитать повторяемость каждого байтового значения и потом как-то оценить статистическое распределение в массиве из 256 элементов. Например если это текст, то будет много пробелов, переводов строк, цифробукв, и не будет непечатных символов. Если это архив, то всех символов будет примерно одинаково. Но тут никак не учитываются повторяющиеся последовательности, которые архиваторы тоже ищут.
...
Рейтинг: 0 / 0
16.12.2015, 06:41
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129319
uid unique
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
uid unique
Участник
Dima Tmiksoftможно взять где-то в середине небольшой произвольный блок, например, в 16 Кбайт, сжать его и на основе этого и принимать решение сжимать/не сжимать.
Отличная мысль, так и сделаю. Спасибо.

Можете улучшить вычисление оценки энтропии - надергайте несколько больше чем 256 (512 или 1024) байтов из случайных позиций в файле вместо последовательного блока.
...
Рейтинг: 0 / 0
16.12.2015, 07:18
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129335
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
По поводу методов сжатия: потестил разные архиваторы
ФайлРазмер7zGzipZipRar7zGzipZipRarBMP (скан ч/б)2733744490881887501914896816.4%30.0%18.4%17.9%BMP (скан 24 бит)77424611205020010712550712417914.5%25.8%16.2%16.0%XML5087199344077988410085640552250861248.7%16.5%12.6%10.0%XML5095845563923108963378434460816211.1%21.4%15.4%11.9%XML89351857753149358.0%64.6%59.5%55.2%DBF (восновном цифры)78282462976701923164988187504111331006112.5%29.6%24.0%17.0%
7z всех сделал. Rar близко, но не рассматриваю т.к. платный.

Надо поковырять исходники 7z, вкомпилировать в свой код, чтобы DLL не таскать.
...
Рейтинг: 0 / 0
16.12.2015, 08:16
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129357
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
miksoftТогда можно взять где-то в середине небольшой произвольный блок, например, в 16 Кбайт, сжать его и на основе этого и принимать решение сжимать/не сжимать.

можно проверить на "жатый" формат (mpeg,jpeg,gif, tiff (c анализом компрессии) , стандартные архивы и тп)
если пожат - не тратить силы
...
Рейтинг: 0 / 0
16.12.2015, 09:23
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129416
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Именно 7-zip - антипотоковый: после сжатия делается перемещение в начало файла и обновляется заголовок.
LZMA/LZMA2 (без контейнера) - не знаю.
...
Рейтинг: 0 / 0
16.12.2015, 10:26
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129429
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Потестил время: победил ZIP.

Считал минимальную скорость передачи лишнего: разница в размере / разница во времени. Т.е. какая должна быть минимальная скорость канала чтобы компенсировать менее качественное сжатие.

7z тормозной, в разы медленнее ZIPа, поэтому его более качественное сжатие нейтрализуется временем. На канале от 0,2-0,3 Мб/сек ZIP быстрее по времени.

Сравнил ZIP и Gzip/Deflate (по сжатию одинаковы) ZIP тут медленнее, но не намного, чтобы ZIP проиграл надо канал от 3-5 Мб/сек
...
Рейтинг: 0 / 0
16.12.2015, 10:41
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129625
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima T,
Можно смотреть по магическому заголовку или расширению.
1. pdf, jpeg, zip - не жать
2. txt, xml, bmp - жать, если размер > N.
Думаю в среднем будет хороший выигрыш.

P. S. можно попробовать тупо жать все и посмотреть.
...
Рейтинг: 0 / 0
16.12.2015, 12:38
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129655
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ЕвгенийВDima T,
Можно смотреть по магическому заголовку или расширению.
1. pdf, jpeg, zip - не жать
2. txt, xml, bmp - жать, если размер > N.
Думаю в среднем будет хороший выигрыш.
Расширений нет. На входе кусок памяти. Разбор заголовка тоже не вариант, много их всяких бывает. Например RAR может быть без сжатия, пользуюсь иногда когда надо быстро собрать несколько мелких файлов в один.
ЕвгенийВP. S. можно попробовать тупо жать все и посмотреть.
Так и делаю, сначала жму, а потом размеры исходного и конечного сравниваю. Потому и решил немного соптимизировать.
...
Рейтинг: 0 / 0
16.12.2015, 12:58
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129787
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima TРасширений нет. На входе кусок памяти.
А откуда они берутся? Должен же быть content-type? Иначе это просто массив байт!
...
Рейтинг: 0 / 0
16.12.2015, 14:13
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129801
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ЕвгенийВDima TРасширений нет. На входе кусок памяти.
А откуда они берутся? Должен же быть content-type? Иначе это просто массив байт!
Это и есть массив байт для пакующего. Это транспорт. Его задача максимально быстро передать массив байт.

Берутся с уровня приложения, там это файлы или содержимое переменных. content-type тоже передается, но он не формализован. Зависит от получателя.
ИМХУ не стоит сверху тащить рекомендации как доставлять. Каждый уровень должен быть максимально независим.
...
Рейтинг: 0 / 0
16.12.2015, 14:28
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129872
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Не выходит из головы моя затея с экспресс-проверкой:
Вот что насчиталось:
 
То что не жмется
ZIP-архив (Дисперсия 722)
.337327325323321319317316316311310308308306305304301300299299295295292292292292291291290290290289288287287286286286285285284284284283283282281280280280280279279278278278277277276276276275275275274274273273273273270270269269269269268268268267267266266266265265264264264263263262262262262262262262261261261260260259259259258258258258257257257257256256255255255255254254254254253253253253253253253252252251251251251251251251250249249248248248247247247247247247246246246246246246246245245245244243243242241241241241241241240240240240239239239239238238237237237237237237237236236236236236235235235234234234234234233233233233233233232232231231231231231231231230230230230229228227227227226226225225224223223223223222222221220220220219219218218216215215215214210209204202197195

Шифрованый файл (жмется до 95% от исходного) (Дисперсия 8286)
.501486476473470469463463460457456453452452452451450447447443443436432430430429428424420416411408353353352350348347340337337334334334333332331330330330329328327327324324323323323322316313312303301293292290287285283283282281280280280280278278277276276272271271270270269268264263262261257257257256252252249249248247245245244243243243242242241241240240240239239237236236235235234234234234233232232231231231230229229229228228228227227226226226226224224223223221220220220219219219217217216216216212211211211210205205205204204202200200200199199199198194194194193191191191190190189189189188187186186186186185185185185183182182182181181180180179178178178177176176175172170170169168162161160157156156155154154153153152151151148148146144144143137135135134133132132130130127122116

 
То что жметсяCDX (Индексный файл, жмется до 50%) (Дисперсия 903876)
.13845653267567466361761360759958556045343941038537836832532432332232132132031931831831831831831831731731731731731731631631631631631631631631531531531531531531531431431431431331331331331331231230930930730730630630430430330330230230230130130130030029929929829829829829829729729729729729629429429329329329329229229129129129029028928928728472686766636261616161616060606060595959595959595959595959595959595959595858585858585858585858585858585858585858585858585858585857575757575757575757575757575757575756565656565656565656565656565656565655555555555555555555555555555555555555555555545454545454545454545454545454545454545454545454

XML (жмется до 15%) Дисперсия 464453
.6280420931402839282622282210210418661762158715531501138513231291126011391091107410509669429359349349349338688268107867837816696364764644133293043033002722712582452442422162001981721651631591581581571551371331171131081021021029897918784797474736563585749494847454442413834323231313028262624232121212020201919181817141414141312121212121210877754444322111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Посчитано так
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
int data[256];

void add(uint8_t* buf, size_t size) {
	for(uint8_t* i = buf + size - 1; i >= buf; i--) {
		data[*i]++;
	}
}


В таблицах массив data отсортированный для наглядности.
Посчитано по первым 65536 байтам каждого файла. Т.е. сумма всех чисел 65536.

Видно что на нежмущихся разбег значений меньше. Что-то в этом есть.
Можно попробовать стат.методами оценить разбеги. Дисперсию я посчитал. Она нелинейно связана с качеством сжатия, но у нежмущихся она на два порядка меньше.
Еще минус - сильно меняется при изменении размера оцениваемых данных. Надо что-то постабильнее изобрести.
...
Рейтинг: 0 / 0
16.12.2015, 15:27
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129889
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Смысл?
Делаем потоковое сжатие любым нересурсоёмким алгоритмом начиная от классического deflate и заканчивая ультра-скоростными, типа lzo.
Если deflate и http, то установкой Content-Coding получим автоматическую распаковку в любом более-менее кошерном http-клиенте.

P.S. Прошлым летом делал сервлет и остановился на следующем алгоритме:
1. Данные до двух килобайт вообще не пакуем;
2. Данные до тридцати двух килобайт пакуем до отправки;
В обоих случаях ставим реальный Content-Length, чтобы позволить контейнеру использовать постоянные подключения.
3. Всё, что более 32КБ - пакуем в потоке.
Передаваемые данные - "кусок памяти" известного размера (от десятков байт до десятков мегабайт).
...
Рейтинг: 0 / 0
16.12.2015, 15:43
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129891
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dima TЕще минус - сильно меняется при изменении размера оцениваемых данных. Надо что-то постабильнее изобрести.
Надо ее делить на среднее в квадрате. Тогда стабильная цифра.
Результаты такие:
Файл ЗначениеZIP0.0079Шифрованный0.126CDX13.52XML7.082
Осталось статистики набрать. Сейчас прогоню по всему диску. Zip`ом степень сжатия померю и дисперсию посчитаю.
...
Рейтинг: 0 / 0
16.12.2015, 15:44
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129895
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Dima TНадо что-то постабильнее изобрести.А если просто оценить долю 50% самых часто встречающихся символов?
(в таблицах это сумма первых 128 чисел).
...
Рейтинг: 0 / 0
16.12.2015, 15:45
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129935
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
miksoftDima TНадо что-то постабильнее изобрести.А если просто оценить долю 50% самых часто встречающихся символов?
(в таблицах это сумма первых 128 чисел).
Только надо эту сумму на среднее поделить, чтобы не зависела от обработанного объема.
Еще один изобрел: Среднее всех больше среднего. Удобно тем что сортировать не надо.
Посчитал все
Файл Сжатый Дисперсия Первые 128 Среднее > среднегоZIP100%0.00791381.09Шифрованный95%0.1261621.36CDX50%13.522272.01XML15%7.0822555.08
Затестю все показатели.
...
Рейтинг: 0 / 0
16.12.2015, 16:15
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39129939
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Dima TТолько надо эту сумму на среднее поделить, чтобы не зависела от обработанного объема.Так объем везде фиксированный и одинаковый.
А для произвольных объемов, конечно, надо.
...
Рейтинг: 0 / 0
16.12.2015, 16:18
| Ответить | Цитировать | Написать  
Экспресс-проверка данных на возможность сжатия
    #39130020
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Затестил. Прогнал через файловую помойку (3000 всяких файлов)
Не подходит ни один показатель. в 10-15% случаев ошибаются.
Буду делать ZIP куска.
...
Рейтинг: 0 / 0
16.12.2015, 17:26
| Ответить | Цитировать | Написать  
25 сообщений из 47, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Экспресс-проверка данных на возможность сжатия
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=32&tid=1340847]:
 0ms
get settings:
 6ms
get forum list:
 10ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 42ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 57ms
get tp. blocked users:
 1ms
others: 237ms
total:  367ms
созд. / загр.: 367ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]