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

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

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

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

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

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

Источник

5 ответов

Решение

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

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

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

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

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

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

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

Удачи!

Источник

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

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

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

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

Источник

См. https://github.com/google/diff-match-patch

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

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

Источник

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

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

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

Ссылка на быструю реализацию LCS 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]
Источник

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

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

Источник
Другие вопросы по тегам