Имеется набор файлов, размером около 100 мегабайт, требуется сжать их как можно лучше, учитывая особенности их содержимого. А именно, все эти файлы склеены в разном порядке из одних и тех же файлов, размером около 20 мегабайт.
Представляется возможным сжать файлы в архив, до размера, немного превышающего сумму исходных файлов, из которых были склеены большие файлы.
Архиватор WinRar не дал такого сжатия.
Есть ли готовые решения для компрессии данных подобного рода.

ИМХО готового не будет - слишком вилика повторяющаяся подпоследовательность. 

Да.
http://ru.wikipedia.org/wiki/PAQ

Lzma SDK.
http://www.7-zip.org/sdk.html

semibug, 
тут программистский форум вроде, а ты про готовое %)
напиши код который будет искать эти самые исходные файлы, и сжимать это все
результат запакуй rar-ом

Это сообщение отредактировал(а) GoldFinch - 7.7.2009, 18:09

andrew_121, протестировал в разных форматах - результат не удовлетворительный.

GoldFinch, а как же повторное использование кода? ))
На край действительно придется писать, а пока есть надежда одной командной строкой задачу решить.

Что тестил? Как тестил? Сообщи условия/результаты.

andrew_121, севен зипом,  и вариациями формата PAQ.
Общий итого таков, что они "не видят" что файлы состоят из одинаковых кусков, видимо по тому, что как написал Sartorius, куски слишком большие.
Это видно по сравнению размеров архивов - в один упаковывается один исходный файл, в другой два исходных файла. Во втором случае размер примерно в два раза больше. Не смотря что оба файла состоят из одинаковых, но склеенных по разному кусков.

Попробую детектить повторяющиеся блоки программно. Хороших идей пока нет, поиск "в лоб" ( простой перебор ) очень медленный.

semibug, в теории, можно создать iso-образ с повторяющимися файлами, которые пишутся в образ один раз и его уже "утоптать" архиватором.

Добавлено через 4 минуты и 56 секунд
хотя, и без упаковки должен получиться меньший размер

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

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

Это сообщение отредактировал(а) zim22 - 8.7.2009, 21:44

Было бы слишком просто)) Файлы я не контролирую (это коллекция образов для прошивки специфического оборудования).
Т.е. работать приходиться с уже склеенными файлами. 

хочу заметить, что с этого надо было начинать.


Добавлено через 3 минуты и 23 секунды

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

Это сообщение отредактировал(а) mes - 9.7.2009, 00:32

mes, Некоторая исходная информация имеется, и в конкретно моем случае можно построить адаптированные под известные размеры и разделители внутри файла алгоритмы. Но все таки хочется иметь "общий" алгоритм, на входе у которого только набор файлов и ничего больше.
Роюсь на эту тему в инете, пока хорошего мало. Линейный перебор с построением словаря, способного вмещать фрагменты до нескольких мегабайт, слишком медленный. 
Смотрю в сторону параллельных вычислений с использованием графических процессоров или FPGA.
Обобщенно представляю так - устройство (возьмем к примеру FPGA) получает образец размером в 1 мегабайт, и размещает их в регистрах. Далее отправляем потоком другую последовательность, например поток в 100 мегабайт. Он поступает на сдвиговые регистры, кол-во которых соответствует кол-ву регистров образца. Теперь отдельная схема сравнивает содержимое всех регистров начиная с первого (все сравнения происходят одновременно). Отдельная схема выдает результат сравнения (кол-во совпавших бит от начала последовательности). Таким образом пропускаем всю последовательность и за один такт сразу сравниваем часть потока с образцом большого размера.
Оставшаяся работа выполняется уже на стороне PC.

semibug как это относится к С++????

т.е к примеру  мы имеем 1000 файлов кусков по 20 мегабайт и один архив, состоящий из 5 -10 кусков в произвольном порядке и ничего лишнего в своем теле не имеет.
задача определить из каких кусков состоит архив. так ?

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



Это сообщение отредактировал(а) mes - 9.7.2009, 02:58

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

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


это хуже, но Вы так и не сказали, какую гарантированную информацию о составе файла мы имеем, например диапaзон разброса размеров файлов постоянен ?
Если нам ничего неизвестно, то лучше общего архива не придумаешь - то есть тот же самый zip/rar.



Это сообщение отредактировал(а) mes - 9.7.2009, 13:07