бинарный diff для нескольких файлов

yroslavasako

Не найдя готового решения в H&S решил мигрировать топик сюда. Хочу написать сабж, в какую сторону стоит копать, к каким алгоритмам присмотреться?
Некоторая формализация: есть n массивов бинарных данных с побайтовым доступом. Они все имеют общие элементы. Каждый из этих массивов необходимо представить как конкатенацию некоторых других подмассивов меньшей длинны. Необходимо сформировать набор таких подмассивов и таблиц их вхождения, чтобы за минимальную суммарную длину получить возможность воспроизвести все n исходных массивов.
Пусть $[math]$M_i, i \in [1..n]$[/math]$ - исходные массивы данных; $[math]$W_i, i \in [1..w]$[/math]$ - набор кодирующих элементов - бинарных массивов данных, условно назовём их словами; $[math]$C_i, i \in [1..n]$[/math]$ - правила кодирования каждого из массивов через последовательность слов. Они представляют собой последовательность индексов слов $[math]$C_i = \bigoplus_{k=1}^z x_k$ где $1 \le x_k \le w, \forall k$[/math]$ . Под значком $[math]$\bigoplus$[/math]$ я подразумевал конкатенацию значений. Таким образом $[math]$C_i$[/math]$ кодирует запись $[math]$M_i$[/math]$ массива через набор известных слов. $[math]$M_i = \bigoplus_{k=1}^z W_{C_{i_k}}$[/math]$
Понятное дело, недостаточно минимизировать суммарные размеры слов, иначе задача решалась тривиально введением алфавита в качестве множества слов, значит минимизировать нужно целевую функцию, учитывающую как размер словаря, так и длину кодирующих последовательностей. $[math]$F = {\sum_{i=1}^w |W_i|} + {k*\sum_{i=1}^n |C_i| }$[/math]$ , где под операцией $[math]$|X|$[/math]$ понимается взятие длины последовательности X. $[math]$k$[/math]$ - некоторый параметр, влияющий на степень фрагментации решения, чем больше этот параметр, тем более крупные фрагменты $[math]$W_i$[/math]$ будут получаться. По предварительным прикидкам стоит брать $[math]$k \in [2..4]$[/math]$ .
Я хочу не столько сократить размер файлов, храня их общие части и разницу, сколько выделить похожие и отличающиеся элементы. Поэтому вношу дополнительное условие, которое не сразу ясно из постановки задачи в общих словах.
$[math]Если $\exists u,v: x_u \in C_i, x_v \in C_j, i \ne j, x_v = x_u$, то для $\forall k \in [1..n] \exists p: x_p \in C_k, x_p = x_u = x_v$[/math]$
Иными словами, я хочу найти общие куски, значит кусок, присутствующий хотя бы в двух массивах, должен присутствовать и в остальных
Судя по всему в полном объёме решение задачи может занять достаточно много времени, было бы целесообразно учитывать и время работы алгоритма и прочие затраченные ресурсы. Тут важно отметить, что мне решение задачи в моём случае не критично к потраченному времени, поскольку используется не для производственных целей вроде бекапа, а для анализа данных.
С условием вроде понятно отписался, кто какой вариант решения предложит?

valodyr

Полностью текст не читал, Нидлман-Вунш не подойдёт?

yroslavasako

в чистом виде - нет. Только в качестве помощи при генерации идей. Спасибо за ссылку.

Vlad77

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

lubanj

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

(я о поиске наибольшей общей подстроки у N строк)

Оставить комментарий