Как реализовать функцию сравнения?

Question

Как реализовать функцию diff, например, историю изменений вопросов переполнения стека?

Answer 1

Здесь у вас есть пример javascript реализации алгоритма diff.

На основании:

P. Heckel, методика выделения различий между файлами Comm. ACM, 21, (4), 264-268 (1978).

Сама реализация имеет две функции, одна из которых рекомендуется для использования:

diffString( String oldFile, String newFile )

Этот метод берет две строки и вычисляет различия в каждой. Окончательный результат - «новый файл», помеченный HTML (для обозначения как удаления из старого файла, так и добавления в новый файл).

Answer 2

Я бы нашел код для утилиты сравнения FreeBSD и использовал бы его в качестве основы. Нет смысла заново изобретать колеса, когда лицензия позволяет копировать такого рода.

Answer 3

Большинство алгоритмов основаны на LCS: Самая длинная общая подпоследовательность . Это не очевидно, чтобы реализовать это эффективным способом. Вы, вероятно, найдете различные реализации в сети для разных языков.

Answer 4

Если вам нужна история изменений, не изобретайте колесо, начиная с diff. Просто добавьте все в систему контроля версий и используйте ее средства сравнения и регистрации. Для простой линейной истории подойдет что-то простое, например, RCS . Или вы можете бросить в него последнюю пушку и использовать git .

Большинство утилит diff делают построчное сравнение. Переполнение стека делает пословное diff. Для этого необходимо что-то вроде wdiff . Большинство систем контроля версий позволяют вам подключать утилиту diff. Из коробки git diff --color-words замечательно приближается к тому, что здесь делается. Немного поигравшись с настройками, вы, вероятно, сможете заставить его выплевывать то, что вы можете затем превратить в симпатичную веб-страницу.

Answer 5

Полагаю, единственный способ - сравнить каждый символ, образующий 2 строки. Примерно так:

void diff(String first,String second) {
   int biggest = (first.length() > second.length()) ? first.length() : second.length();
   for(int i = 0;i &lt biggest;i++) {
      //compare each char from the longest string with each char from the shorter
      // do something with them if they're not equal
   }
}

Это всего лишь набросок того, как я это сделаю. Все зависит от того, что вы хотите сделать с данными.