Имеется некий большой storage - т.е. файл состоящий из однотипных блоков. Есть его старая версия и новая, в которой часть блоков была удалена, часть блоков изменена и было добавлено несколько новых, общих изменений - 5-10% Необходимо на основе старого файла + некий патч с инфой сгенерить новый, так чтобы этот патч был по возможности небольшым. Как лучше организовать поиск неизменившихся частей (понятно надеюсь для чего)? Формат блоков этого хранилища неизвестен (или непринципиален), так что работать надо просто как с бинарными файлами. В настоящий момент имеется реализация на основе мощного LZ-подобного алгоритма - оригинальный файл "сжимается", заполняя словарь фраз, потом новый файл продолжает зажиматься с этим словарем (типа solid сжатие). Результат приемлимый - остается процентов 10 от оригинала, но не устраивает ресурсожерство - уже при размере окна в 16 мб, словать получается в сотню мегов, или приходится несколько раз его очищать и как следствие поиск заметно ухудшается. Хочется какой-нибудь другой подход с примерно тем-же КПД.

Забавно. Наверняка меня запинают, но что если использовать какую-нибудь сортировку, MMF-функции и какой-нибудь хешик для определения блока. Т.е. в сортировке сравнивать не блоки побайтно, а хеши блоков...
Или я вообще безнадежен :)

Запинаем! Моя же внятно сказала что понятие блоков чисто виртуальное, и с файлами работать надо как с потоком байт. Собсно вопрос и заключался в том как грамотно разбить этот поток на блоки чтоб выкинуть те что были в старом файле. Вот.

Алгоритм с хешем очень даже годится!
Можно взять из старого файла блоки небольшой длины(например которая меньше чем у 90% блоков), со сдвигом на 1 байт, посчитать для них хеш( можно просто проксорить двойные слова). Если хеш состоит из 2^n бит то все блоки разбиваотся на 2^n групп. Создаем массив из 2^n элементов. Каждый элемент является началом списка или массива адресов блоков с данным хешем. В одной группе будет в среднем filesize/2^n элементов. Затем читаем новый файл и также считаем для него хеши. После чего новый блок сравниваем с блоками в исходном файле и пытаемся выбрать наиболее длинный совпадающий участок. Если длина совпадающего участка невелика то сдвигаемся на 1 байт, а байты для пропущенного участка включаем в патч. В противном случае записываем смещение и длину в исходном файле. Если мы будем использовать n-битный хеш, то количество памяти которое на потребуется будет следующим: 2^n*4-для массива списков и filesize*8 для элементов списков, плюс длина старого файла и длина нового файла. Если списки заменить массивами то памяти для них потребуется 2^n*8+filesize*4. filesize - длина старого файла. Блок из нового файла придется в среднем сравнить с filesize/2^n блоками из старого файла. Если таблица с адресами блоков не будет помещатся в оперативную память то это не страшно, главное чтобы исходный файл поместился.

Сильно не бейте по голове :)))

=====================================
Пусть у нас есть файл A
и файл Б

Процедура генерирования файла с инфой.

Сравниваются потоки байт (слов, двойных слов) из A и B
Как только находится место различия, запоминается его смещение,
Это значит, что закончился 1 блок и начался другой -ой

Будем называть это место, местом границы БЛОКОВ.

Далее сравнение продолжается.

1. Если значительная часть байт после ГРАНИЦЫ (например минимум 4K) не изменилась,
то мы сбрасываем старую ГРАНИЦУ, ставим новую, а старую записываем в INF файл как ИСКЛЮЧЕНИЕ.

(Это уже вопрос о формате.. Но скажу сразу, у меня алгоритм генерирования INF и формат его завязаны.)

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

* Ещё, снова представим ситуацию, когда мы вдруг обнаружили границу блока.
Вот в этот момент, мы не просто сравниваем потоки данных, а и просчитываем плотность изменения.
Чтобы всё было быстро, плотность изменения не считается, а считается количество ИЗМЕНЁННЫХ байт.
Это делается для того, чтобы оценить с каким блоком мы имеем дело.
Если процент невилик, то - это скорее всего изменённый блок
Иначе -- новый.

*+
Кроме того, алгоритм должен учитывать возможность смещения блока.
То есть, когда вставляется новый блок.
Итак, этот случай происходит тогда, когда наш Алгоритм обнаруживает НОВЫЙ БЛОК.
В этом случае, он пока не выкидывает старый блок данных, а вместо этого
подсматривает на соседний блок (и если он был признан новым), пытается выяснит, равен ли этот
соседний НОВЫЙ блок старому БЛОКУ?
Если да, то это значит, что ТЕКУЩИЙ БЛОК -- это НОВЫЙ вставленный блок,
при чём программа может чётко сказать, куда он вставлен!!!!

(смещение)

Алгоритм так же делает попытку найти старый блок в следующем блоке, если только он не равен
Следующиму блоку в новом файле.

==========================================================
Теперь немного фантазии.

итак, давайте разобъём всё это на

1. MainStream() -- основной поток
2. SetBlockRange() -- установить границы блока
3. SetBlockStatus() -- установить статус блока
4. CheckBlockOld() -- проверить на наличие старого блока
5. GetCEl() -- получить текущий элемент потока
6. GetPrevOldBlock -- взять смещение предыдущего старого блока!!!
7. GetCOldDelBlock -- взять смещенее старого удалённого блока (предположительно)
8. GetCurrentOffset() -- текущее смещение
9. AnalizeStream() -- Анализ потока, и выход по событию
10. ....???

==========================================================
MainStream(pold,pnew)
{

EL_STREAM cold = 0; // текущие элементы потока
EL_STREAM cnew = 0;

OFFSET CurrentOffset = 0;
OFFSET StartBlock = 0;
OFFSET EndBlock = 0;

// Флаги состояния
int state = 0;

// Количество несовпадений
int ndiff = 0;

StartBlock = GetCurrentOffset();

cold = GetCEL(pold);
cnew = GetCEL(pnew);

while(cold == cnew)
{
cold = GetCEL(pold);
cnew = GetCEL(pnew);
}

// 1. Встретили различие
// Возможно это есть ГРАНИЦА Блока, а может и нет.
EndBlock = GetCurrentOffset();

// Анализ потока и выход, из анали, если на протяжении EVENT_MAX_EQU_SIZE не встречено
// различие
// Эта процедура
// интересно анализирует поток, о неё далее.
state = AnalizeStream(EVENT_MAX_EQU_SIZE);
// state = EVENT_EOF -- если конец :))
// state = EVENT_MAX_EQU_SIZE - если небыло различий..
// state = EVENT_MAX_FOUND_BLOCK -- если был был ПРЕДПОЛОЖИТЕЛЬНОЙ найден текущий блок.
// state =

И так далее....
(потом допишу... :(()

}//end MainStream(pold,pnew)


//////////////////////////////////////////////////////////О процедуре AnalizeStream(event)

Она не просто сравнивает старый поток и новый поток

Вот пример потока данных

= одинаковые байты блока
* - разные

[==========================================] - old
[*******====*====*====*=========*==========] - new
       ^ начало блока (он смещён в памяти)

Итак, процедура не просто сравнивает _СООТВЕТСТВУЮЩИЕ БАЙТЫ потока
Она ищет так называемый ПРИЗНАК начала БЛОКА.

Очень интересная вещь.

Итак для этого, я попробую объяснить что происходит внутри анализа:

1. Сравниваем части потока
2. Если равны -- дальше
3. Иначе увеличиваем счётчик несовпадений.

Когда объём проанализированных байт равен SIZE_START_BLOCK
функция останавливается, и СМОТРИТ, насколько этот кусок потока СОВПАЛ!!!
Если процент совпадения МАЛ, то она ставит ШТРАФНОЙ БАЛ этому куску данных
и считает, что ЕСТЬ ВЕРОЯТНОСТЬ, что блок в НОВОМ ФАЙЛЕ был смещён, а тот кусок данных --
это НОВЫЙ всттавленный БЛОК.

Поэтому ДАЛЬШЕ сравнение происходит не только с соотвествующими байтами из потока СТАРОГО файла и НОВОГО
а так же
---------------
СРАВНИВАЕТСЯ КУСОК НАЧАЛА БЛОКА ИЗ СТАРОГО ФАЙЛА И ТЕКУЩЕГО НОВОГО
Это можно сделать при помощи вычисления простейшего хеша --
сумма байт.
Если разность сум относительно (критерий) близка к нулю, значит С ВЕРОЯТНОСТЬЮ XX
блок был смещён.
Я приведу этот АЛГОРИТМ ОТДЕЛЬНО. (Он заслуживает рамки и отдельного COMPO)
---------------

Подробнее

Например есть у вас поток

010100111100101101000010101010100100101
И
111101110101001111001011010000101010101
^ - начало блока старого

Вопрос -- как найти СТАРЫЙ БЛОК В НОВОМ ПОТОКЕ?
%))))

Если ДУМАТЬ, что НАЧАЛО БЛОКА НЕ МОЖЕТ БЫТЬ ИСКАЖЕНО, то даже тогда ЭТО ОЧЕНЬ КРАСИВАЯ ЗАДАЧА
(Копирайт мой!!!! руки проч :)))))

А вот представте что есть ВЕРОЯТНОСТЬ, что БЛОК ИСКАЖЁН??? (ИЗМЕНён)

Вот вот.. (это типа нобелевская премия по IA %))))

Нужно найти его начало :))) в новом потоке.

1. Сравниваем первый байт блока старого с текущей позицией в новом потоке
Если неравно, увеличиваем счётчик штрафа и сбрасываем счётчик последовательности исовпадений
2. Иначе, увеличиваем счётчик последовательности совпадений
и анализируем следующий байт.

ЕСЛИ СЧЁТЧИК ПОСЛЕДОВАТЕЛЬНОСТИ РАВЕН 0, то КИДАЕМ АНАЛИЗ, и НАЧИНАЕМ ЕГО
С начала СТАРОГО БЛОКА, и с того места ОБНУЛИЛСЯ СЧЁТЧИК.

Этот алгоритм даст сбой во многих ситуациях.. где различие будет большим..
НО!!!
НО он достаточно БЫСТР!!!

Ещё немного об этой процедуре.
Она не анализирует до бесконечности..
Думаю, её стоит остановить на N байт.. (1M байт может)
если ничего не нашла, и ниодно условие не выполнилось..

====================================================================== ==============

Теперь остался вопрос (уже более лёгкий на порядок) какой формат у INF файла, и как в него
это запихнуть...

Но это потом...
Сперва я должен понять, что мой вариант чего то стоит.. :)))

А я в том сомневаюсь!!!
//////////////////////////////////////////////////////////

Edmond
Проблемка, я то расчитывал, что БЛОКИ не могут перемешиваться :(((
Так что этот алгоритм годится только ДЛЯ НЕПЕРЕМЕШАННЫХ БЛОКОВ.
Хотя я не пойму, разьве вирусы могут перемешывать??? ИХ???

ОК, так что вариант 2 будет позже

Edmond
А мой алгоритм обламывается на файле с большим количеством коротких одинаковых последовательностей. На нем он будет так тормозить что никакие индикаторы прогресса не помогут 8( И пока ничего лучшего чем считать кучу логарифмов в голову не приходит. Хотя еще не ясно поможет ли это.

Black_mirror
Пока я вижу ОДИН ВЫХОД.
Совместить создание словаря С Архитектурой ИНФ файла...
Короче.
Ай да :))
До застра ещё долго.

Слушай.

LZ смотрит на следующую последовательность байт, минимальную по длине, что бы она еще не была в словаре; и кодирует ее кодом той, которая была чуть раньше, плюс последний символ (каким они отличаются) - расширяет словарь; записывает в выходной поток этот новый ключ. все.

Ну во первых можно с созданием словаря похимичить.

Как? Вопрос :)))
(Может РАР выдумаю :))))

Я думаю как то скрестить создание словаря и моим алгоритмом.

Ведь у него один недостаток -- НЕВОЗМОЖНОСТЬ учитывать смешения блоков.
А в принципе он позваляет записать в INF файл ТОЛЬКО РАЗНОСТНУЮ ИНФОРМАЦИЮ.

Это его плюс.

Я теперь думаю, как же учесть ЭТО СМЕШИВАНИЕ!!!

> Хотя я не пойму, разьве вирусы могут перемешывать???

А при чем тут вирусы? Об них никто и не заикался :)

> Может РАР выдумаю.

А чего тут выдумывать? Это обычный быстрый LZ с большим (4мб) окном + узелки дожимаются арифметическим кодированием (PPM) + виртуальная машина с набором оптимизирующих фильтров.

LZ собсно всем устраивает кром гигантских запросов на память. Скорость - 2-3 мин. на 4 мб файлы на P4-2.8GHz

А чего тут выдумывать? Это обычный быстрый LZ с большим (4мб) окном + узелки дожимаются арифметическим кодированием (PPM) + виртуальная машина с набором оптимизирующих фильтров.

Ну так я именно поэтому и пошутил.. :))
Что мол алгоритм RAR повторю нечайно %)))

Теоретически можно использовать следующий алгоритм:
Считываем старый файл в буфер. Создаем массив указателей на каждый байт буфера. Считаем что эти указатели есть указатели на строки. Каждая строка идет до конца буфера. Сортируем этот массив. А затем считываем новый файл и тоже рассматриваем его как строку. Ищем в отсортированном массиве эту строку бинарным поиском. В качестве результата берем максимально совпадающую элемент. Если длина совпадения мала, например меньше 8, то сдвигаем указатель на 1 байт. Иначе в патч записываем смещение и длину области в старом файле и сдвигаемся дальше. Если мы пропускали байты, то перед этим нужно записать их количество а также их значения в патч.
Этот алгоритм позволяет найти наилучшие совпадения, но проблема в том, как сравнивать две строки. Например если файл состоит из циклически повторяющихся байт, то время сравнения элементов будут пропорционально длине файла. Вообщем его нельзя использовать на малоинформативных файлах 8( Хотя если блоки файла состоят из случайных чисел то алгорит их быстро найдет.
Есть какие-нибудь идеи как повысить информативность файла?

Создаем массив указателей на каждый байт буфера

Ты, скорее всего, оговорился :( Это ж получается DWORD указывает на BYTE.

volodya
Я имел ввиду следующее:

  stdcall alloc,[file_size]
  mov [pbuf],eax
  mov ebx,eax
  add eax,[file_size]
  mov [pbuf_end],eax
  mov eax,[file_size]
  shl eax,2
  stdcall alloc,eax
  mov [ppstr],eax
  mov ecx,[file_size]
.l0:
  mov [eax],ebx
  add eax,4
  inc ebx
  loop .l0

Затем в область памяти на которую указывает pbuf мы считывает файл. ppstr - это массив указателей на строки, который нам нужно отсортировать. Каждая строка идет до pbuf_end.