Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Экспресс-проверка данных на возможность сжатия / 25 сообщений из 47, страница 1 из 2
  1  все
15.12.2015, 19:08
    #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:52
    #39129107
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экспресс-проверка данных на возможность сжатия
Dima TЗадача: экономить время при передаче данных по инету.А хоть при каких-нибудь данных (реально встречающихся, а не блока из миллиарда нулей) есть ли смысл сжимать эти данные?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.12.2015, 20:08
    #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:10
    #39129123
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экспресс-проверка данных на возможность сжатия
Опечатался, не Мбит, а Мбайт/сек.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.12.2015, 21:04
    #39129175
Basil A. Sidorov
Basil A. Sidorov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экспресс-проверка данных на возможность сжатия
Посмотрел умолчания DrWeb-овского ES-сервера и провёл "микроследствие" ...
Действительно, для deflate оптимальным является сжатие с уровнем 8 - заметно быстрее максимального, не сильно просаживает скорость на уже сжатых данных и может дать мизерный, но выигрыш в размере.

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

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

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

Можете улучшить вычисление оценки энтропии - надергайте несколько больше чем 256 (512 или 1024) байтов из случайных позиций в файле вместо последовательного блока.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2015, 08:16
    #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, 09:23
    #39129357
Изопропил
Изопропил
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экспресс-проверка данных на возможность сжатия
miksoftТогда можно взять где-то в середине небольшой произвольный блок, например, в 16 Кбайт, сжать его и на основе этого и принимать решение сжимать/не сжимать.

можно проверить на "жатый" формат (mpeg,jpeg,gif, tiff (c анализом компрессии) , стандартные архивы и тп)
если пожат - не тратить силы
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2015, 10:26
    #39129416
Basil A. Sidorov
Basil A. Sidorov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экспресс-проверка данных на возможность сжатия
Именно 7-zip - антипотоковый: после сжатия делается перемещение в начало файла и обновляется заголовок.
LZMA/LZMA2 (без контейнера) - не знаю.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2015, 10:41
    #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, 12:38
    #39129625
ЕвгенийВ
ЕвгенийВ
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экспресс-проверка данных на возможность сжатия
Dima T,
Можно смотреть по магическому заголовку или расширению.
1. pdf, jpeg, zip - не жать
2. txt, xml, bmp - жать, если размер > N.
Думаю в среднем будет хороший выигрыш.

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

Берутся с уровня приложения, там это файлы или содержимое переменных. content-type тоже передается, но он не формализован. Зависит от получателя.
ИМХУ не стоит сверху тащить рекомендации как доставлять. Каждый уровень должен быть максимально независим.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2015, 15:27
    #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:43
    #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:44
    #39129891
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экспресс-проверка данных на возможность сжатия
Dima TЕще минус - сильно меняется при изменении размера оцениваемых данных. Надо что-то постабильнее изобрести.
Надо ее делить на среднее в квадрате. Тогда стабильная цифра.
Результаты такие:
Файл ЗначениеZIP0.0079Шифрованный0.126CDX13.52XML7.082
Осталось статистики набрать. Сейчас прогоню по всему диску. Zip`ом степень сжатия померю и дисперсию посчитаю.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2015, 15:45
    #39129895
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экспресс-проверка данных на возможность сжатия
Dima TНадо что-то постабильнее изобрести.А если просто оценить долю 50% самых часто встречающихся символов?
(в таблицах это сумма первых 128 чисел).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2015, 16:15
    #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:18
    #39129939
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экспресс-проверка данных на возможность сжатия
Dima TТолько надо эту сумму на среднее поделить, чтобы не зависела от обработанного объема.Так объем везде фиксированный и одинаковый.
А для произвольных объемов, конечно, надо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2015, 17:26
    #39130020
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экспресс-проверка данных на возможность сжатия
Затестил. Прогнал через файловую помойку (3000 всяких файлов)
Не подходит ни один показатель. в 10-15% случаев ошибаются.
Буду делать ZIP куска.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Экспресс-проверка данных на возможность сжатия / 25 сообщений из 47, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 303ms
Закрыть
start [/forum/topic.php?fid=16&tablet=1&tid=1340847]:
 0ms
get settings:
 7ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 31ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 39ms
get tp. blocked users:
 1ms
others: 192ms
total:  303ms
x
x
Закрыть


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