Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Алгоритм сравнения файлов в сис-ме контроля версий

Автор: g-r-i-n 18.7.2007, 01:17

Добрый день.
Поискал по форуму - сабж вроде не нашел.
Мне нужно описание алгоритма сравнения двух модификаций
одного файла, т.е. основной операции таких систем как
CVS и SVN. Там используется какая-то предварительная
разметка? Как решаются проблемы, которые даже человек
не может разрешить в данном случае (а они есть)?
Описание мне нужно настолько подробное, чтобы можно
было написать свою несложную систему. Если кто знает
русскоязычные ссылки - буду очень благодарен.
Спасибо.

Автор: maxim1000 18.7.2007, 11:05

можно попробовать покопать в сторону динамического программирования
вот есть ссылочка: http://www.dcs.shef.ac.uk/~stu/com326/sym.html
правда, там на английском, зато картинка вполне неплохо отображает принцип

Автор: g-r-i-n 18.7.2007, 11:46

maxim1000, спасибо за совет. Только мне кажется должен быть какой-то готовый алгоритм конкретно под эту задачу. Придумать как подогнать динамическое программирование под разбор текста возможно, но не хочется изобретать велосипед.
У меня была, конечно, мысль взять исходники открытых продуктов в этой области, но разбираться в МИГ-29 не более эффективно, чем изобретать велик. А делиться своими ноу-хау разработчики серьезных продуктов, естественно, не хотят. Но я надеюсь, что это знание - достояние всей математики, а не только "избранных". Вопрос только - где найти этот готовый основной алгоритм?

Автор: AriX 19.7.2007, 14:08

g-r-i-n, честно говоря, не знаю, поможет или нет. Но посмотри вот этот опен-сорс проект - http://kdiff3.sourceforge.net/

Исходники на С++ есть. Скорее всего, сравнение делает один или несколько модулей, которые, можно будет подцепить к твоей программе. Там же, на сайте, есть небольшой pdf документ Abstract, который немного описывает принципы работы.

Автор: g-r-i-n 19.7.2007, 14:38

AriX, Спасибо большое. Это уже гораздо ближе. Думаю в начало лабиринта я уже попал =) +1!

Добавлено через 2 минуты и 30 секунд
maxim1000, я случайно зацепил голосование на пост, причем в минус! Это как-то можно исправить?

Автор: maxim1000 19.7.2007, 16:27

Цитата(g-r-i-n @ 19.7.2007, 14:38

)

maxim1000, я случайно зацепил голосование на пост, причем в минус! Это как-то можно исправить?

похоже, нет, но это и не сильно страшно

Автор: Pool 24.1.2008, 19:00

Доброго времени суток!

У меня такая жи задача ... сравнить 2 файла(старый и новый) CVS и вывести все новые строки из нового файла в мемо .... я вроде сам наклепал , но он почемута работает только до половины и страшно загружает пк при этом ....

Код


procedure TForm1.Button3Click(Sender: TObject);
var
 String1, String2: PAnsiChar;
 res: integer;
 i,j:integer;
 z1, z2: integer;
 is_run: boolean;
begin
Button1.Enabled:=False;
Button2.Enabled:=False;

Memo3.Lines.Add('start');
z1 := Memo1.Lines.Count;
z2 := Memo2.Lines.Count;

i := 0;
while i < z1 do
  begin
    String1 := PChar(Memo1.Lines.Strings[i]);
    //Memo3.Lines.Add(String1); Continue;
    j := 0;
    //is_run := true;
    while j < z2 do
      begin
        String2 := PChar(Memo2.Lines.Strings[j]);
        if(StrIComp(String1, String2) = 0) then
          begin
            Memo3.Lines.Add(String1);
            Memo2.Lines.Delete(j);
            Memo1.Lines.Delete(i);
            z1 := Memo1.Lines.Count;
            z2 := Memo2.Lines.Count;

            Label5.Caption:='Количество строк файла №1 = '+IntToStr(z1);
            Label6.Caption:='Количество строк файла №2 = '+IntToStr(z2);
            //j := Memo1.Lines.Count + 1;
          end;
          j := j + 1;
          Application.ProcessMessages;
      end;
      i := i + 1;
  end;

  Memo3.Lines.Add('finished');


end;

Модератор: пользуемся кнопкой "Код"

Автор: g-r-i-n 24.1.2008, 19:16

Pool: спасибо за ответ, но это другая задача. Она действительно решается в несколько строк и к CVS, в общем-то, отношения не имеет. Но то что мне нужно было - не сравнение старого файла и нового, а сравнение двух модификаций одного файла. А это уже серьезная наука, т.к. связана чуть ли не с распознаванием образов.
Я тогда нашел выход из ситуации (применять сравнение файлов не пришлось), так что тему можно продолжать разве из энтузиазма =) Спасибо всем, кто помог мне разобраться в этом вопросе!