Дифференциальный алгоритм?[закрыто]

StackOverflow https://stackoverflow.com/questions/805626

  •  03-07-2019
  •  | 
  •  

Вопрос

Я как сумасшедший искал объяснения алгоритма сравнения, который работает и эффективен.

Самое близкое, что я получил, это эта ссылка на RFC 3284 (из нескольких сообщений в блоге Эрика Синка), в котором совершенно понятными словами описывается формат данных в котором хранятся результаты различий.Однако в нем вообще не упоминается, как программа достигнет этих результатов при выполнении сравнения.

Я пытаюсь изучить это из личного любопытства, потому что я уверен, что при реализации алгоритма сравнения должны быть компромиссы, которые иногда довольно очевидны, когда вы смотрите на различия и задаетесь вопросом: «Почему программа сравнения выбрала это в качестве изменения?» вместо этого?"...

Где я могу найти описание эффективного алгоритма, который в конечном итоге выводит VCDIFF?
Кстати, если вам удастся найти описание реального алгоритма, используемого DiffMerge от SourceGear, это будет еще лучше.

ПРИМЕЧАНИЕ:Самая длинная общая подпоследовательность, похоже, не является алгоритмом, используемым VCDIFF, похоже, они делают что-то более умное, учитывая используемый ими формат данных.

Это было полезно?

Решение

Разностный алгоритм O(ND) и его вариации это фантастическая статья, и вы можете начать с нее.Он включает в себя псевдокод и красивую визуализацию обходов графа, участвующих в выполнении сравнения.

Раздел 4 В статье вводятся некоторые усовершенствования алгоритма, которые делают его очень эффективным.

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

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

Вот страница который включает в себя немного документации, полный исходный код, и примеры алгоритма сравнения, использующего методы вышеупомянутого алгоритма.

А исходный код Кажется, что он точно следует основному алгоритму и его легко читать.

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

Удачи!

Другие советы

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

Для понимание Что касается того, как на самом деле работает этот исходный код, документы в этом пакете ссылаются на статьи, которые его вдохновили:

Базовый алгоритм описан в книге «Разностный алгоритм O(ND) и его вариации», Юджин В.Майерс, «Алгоритмика», том.1 Нет.2, 1986, с.251-266;и в «Программе сравнения файлов» Уэбб Миллер и Юджин У.Майерс, «Программное обеспечение – практика и опыт», Vol.15 Нет.11, 1985, с.1025-1040.Алгоритм был открыт независимо, как описано в «Алгоритмах приблизительного сопоставления строк», Э.Укконен, «Информация и контроль», Том.64, 1985, стр.100-118.

Чтения статей, а затем просмотра исходного кода реализации должно быть более чем достаточно, чтобы понять, как это работает.

Видеть https://github.com/google/diff-match-patch

«Библиотеки Diff Match и Patch предлагают надежные алгоритмы для выполнения операций, необходимых для синхронизации простого текста....В настоящее время доступно в Java, JavaScript, C ++, C# и Python "

Также см. wikipedia.org Страница различий и - "Брэм Коэн:Проблема с дифференциалом решена"

Я пришел сюда в поисках алгоритма сравнения, а затем сделал свою собственную реализацию.Извините, я не знаю о vcdiff.

Википедия:Из самой длинной общей подпоследовательности достаточно сделать небольшой шаг, чтобы получить результат, похожий на diff:если элемент отсутствует в подпоследовательности, но присутствует в оригинале, он должен быть удален.(Знаки «–» ниже.) Если он отсутствует в подпоследовательности, но присутствует во второй последовательности, он должен быть добавлен.(Знаки «+».)

Хорошая анимация Алгоритм LCS здесь.

Ссылка на фаст Реализация LCS Ruby здесь.

Моя медленная и простая адаптация Ruby приведена ниже. 

def lcs(xs, ys)
  if xs.count > 0 and ys.count > 0
    xe, *xb = xs
    ye, *yb = ys
    if xe == ye
      return [xe] + lcs(xb, yb)
    end
    a = lcs(xs, yb)
    b = lcs(xb, ys)
    return (a.length > b.length) ? a : b
  end
  return []
end

def find_diffs(original, modified, subsequence)
  result = []
  while subsequence.length > 0
    sfirst, *subsequence = subsequence
    while modified.length > 0
      mfirst, *modified = modified
      break if mfirst == sfirst
      result << "+#{mfirst}"
    end
    while original.length > 0
      ofirst, *original = original
      break if ofirst == sfirst
      result << "-#{ofirst}"
    end
    result << "#{sfirst}"
  end
  while modified.length > 0
    mfirst, *modified = modified
    result << "+#{mfirst}"
  end
  while original.length > 0
    ofirst, *original = original
    result << "-#{ofirst}"
  end
  return result
end

def pretty_diff(original, modified)
  subsequence = lcs(modified, original)
  diffs = find_diffs(original, modified, subsequence)

  puts 'ORIG      [' + original.join(', ') + ']'
  puts 'MODIFIED  [' + modified.join(', ') + ']'
  puts 'LCS       [' + subsequence.join(', ') + ']'
  puts 'DIFFS     [' + diffs.join(', ') + ']'
end

pretty_diff("human".scan(/./), "chimpanzee".scan(/./))
# ORIG      [h, u, m, a, n]
# MODIFIED  [c, h, i, m, p, a, n, z, e, e]
# LCS       [h, m, a, n]
# DIFFS     [+c, h, +i, -u, m, +p, a, n, +z, +e, +e]

Судя по ссылке, которую дал Эммелайх, на сайте также есть отличный обзор стратегий различий. Сайт Нила Фрейзера (одного из авторов библиотеки).

Он описывает основные стратегии и к концу статьи переходит к алгоритму Майера и некоторой теории графов.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top