ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Arseny Slobodjuck                    2:5045/41.16   21 Sep 2001  05:57:44
 To : Dmitry Maslennikov
 Subject : Алгоритм создания патча
 -------------------------------------------------------------------------------- 
 

 
  Письмо было от Dmitry Maslennikov к All. И сабжект сверху приписан:
  <Алгоритм создания патча>
 
 DM> Кто-нибудь зает subj?
 DM> Вроде это частный случай задачи LCS(Hаибольшей общей
 DM> подпоследовательности).
 
 === Cut ===
 From: "Vasily Khabituev" <vasa@burnet.ru>
 To: <eugenepavlov@mail.ru>
 Date: Thu, 17 Feb 2000 01:16:33 +0800
 Subject: Тираж изменений
 
 Евгений, Привет!
 
 В ru.algorithms увидел тред про difference extractor.
 У меня была идейка, по этому поводу, и я реализовал
 ее для 16 bit protected mode dos на Pascal. Текст не сохранился,
 прекрасно работал на небольших по 100Kб файлах.
 Мой алгоритм потребляет память в квадрате от размера
 вычисляемой пары. Для средних файлов по 2-3 Мб
 требовалось 40-60 Мб RAM. В те годы это было неприемлимо,
 но сейчас думаю это нормально, если применить
 файлы проецируемые на диск.
 
 Суть:
 имеем файл OLD и NEW
 1) открываем файл OLD
 2) в памяти строится массив P [0..255, 0..255] пойнтеров на цепочки длинных
 целых
                                 массив L [0..255, 0..255] длин цепочек
 3) обнуляется весь P
 4) для каждого байта по смещению i и i+1 из OLD от 0 до Length(OLD)-2
 выполняем
     пополнение цепочки P[OLD[i],OLD[i+1]]^ значением i и инкремент
 L[OLD[i],OLD[i+1]]
 5) в результате имеем двумерный ассоциативный индекс всех случаев
    попарного соседства любого байта с любым последующим в файле OLD
    в виде смещений.
    Hапример если P[37,199]=(4445, 77789, 90790) и L[37,199]=3
    то это значит, что в файле OLD есть 3 случая следования пары байт
    ...,33,199,... И эти случаи наблюдаются по смещению 4445, 77789 и 90790
 6) Теперь используем ассоциативный индекс для поиска наиболее
   подобных цепочек (длиной от 2-х байт и более) в файле NEW.
 7) Байты по смещению j, j+1 из NEW от 0 до Length(NEW)-2
    позволяют выполнить проверку, есть ли такой же случай (или несколько)
   в OLD. Количество случаев это N=L[NEW[j],NEW[j+1]].
    8)  для NN=1 to N выполняем поиск максимальной длины совпадения
        цепочек по смещениям OLD[P[NEW[j],NEW[j+1]]^[NN]] и NEW[j].
       и выдаем на выходной файл "PATCH" сообщение
       OLD[P[NEW[j],NEW[j+1]]^[NN]] max , MaxL
       - где max - это смещение в файле OLD и MaxL - длина цитаты
 9) j=j+MaxL
 10) переход (если не конец файла NEW) на 7)
 11) выходная цепочка сообщений PATCH - это список цитат.
      каждая цитата - это 8 = 4+4 байт, т.е. смещение цитаты в OLD и ее длина
 12) стоп
 
 Алгоритм восстановления OLD+PATCH->NEW, я думаю очевиден.
 Можно разумеется дополнительно компрессировать сам PATCH.
 В итоге для пары примерно похожих .exe файлов по 300K продуцированных
 Clipper, например, по почте уходил патчик байт на 200-300. Причем не
 имеет значения разные ли размеры. Забавно, например,
 компрессировать совсем разные файлы, но общего происхождения,
 какие-нибудь DLL. видно так называемый "коэффициент цитирования".
 
 С уважением, Василий Хабитуев.
 http://www.eastsib.ru/~vasa/
 P.S. Если не в лом, отфорварди в RU.ALGORITHMS,
 у меня news-сервер дает только читать, а фидософт мне слабо установить
 === Cut ===
 
 --- Flame Master/W32 2.7.4Nov7
  * Origin: Far East Laboratory of Kibenimatics. Ebusiness branch (2:5045/41.16)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Алгоритм создания патча   Dmitry Maslennikov   20 Sep 2001 00:33:38   Алгоритм создания патча   Arseny Slobodjuck   21 Sep 2001 05:57:44