На входе имеем множество файлов, содержащих большие непрерывные блоки из ограниченного множества (для примера - имеем 100 образов ISO, на которых записаны треки,  вариантов которых всего 20) .
Требуется сжать эти файлы. Обычные архиваторы не могут эффективно их обработать, т.к. длина идентичных участков слишком большая для словаря.
Основная проблема в написании кода - быстрый алгоритм, выявляющий одинаковые области в разных файлах.
Простой перебор загрузит мой процессор на ближайший триллион лет. В рамки задачи это вписывается с трудом.
Интуитивно тянет в сторону буста, с какой стороны подойти не знаю.

Области в файлах выровнены? Если да, то можно вычислять свертки (например CRC32 или MD5) от блоков (в единицах выравнивания), и сравнивать их значения (обычными алгоритмами архивирования).

Если области не выровненные, то вычислять придется скользящие свертки, не уверен, что их не получится столько же, сколько было исходных данных   

модифицируй код архиватора, увеличив размер словаря

baldina, вряд ли код какого либо архиватора будет эффективно работать со словами в несколько десятков мегабайт.

xvr, области произвольные. Т.е. разные куски длиной от 30 до 100 мб из первичного набора. могут быть склеены в произвольном порядке (в произвольном количестве).
Вот, кстати, идея на счет выделения сверток. Но т.к. границы кусков изначально не известны, то кажется, возвращаемся к началу.

Может быть ответ лежит где-то в области распознавания картинок.
Например для того, чтобы найти одинаковые области в двух массивах делаем какой-то "температурный" снимок, который передает что-то вроде не точного отпечатка для разных областей. Затем сравниваем такие отпечатки и находим наиболее близкие. После можно сравнивать уже побайтно и расползаться в обе стороны, пока не будет найдено различие.
Проходим таким образом несколько раз по обоим массивам, и отсеиваем уже найденные соответствия.
В общем пока туманно.



Это сообщение отредактировал(а) semibug - 27.9.2010, 15:48

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

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

Пытаюсь нагуглить по сабжу, вероятно задач достаточно рутинная и должна быть решена ранее.