В описанаии и реализации алгоритма WinDiff от Microsoft есть несколько неясных моментов.
Может быть кто-нибудь знает его автора или может подсказать где взять более четкое описание?
Здравствуйте, RealBobEx, Вы писали:
RBE>В описанаии и реализации алгоритма WinDiff от Microsoft есть несколько неясных моментов. RBE>Может быть кто-нибудь знает его автора или может подсказать где взять более четкое описание?
Ключевые слова: LCS — Longest Common Subsequences, SES — Shortest Edit Script.
Edit script собственно и есть описание разницы между двумя строками/файлами. Обе проблемы решаются одним и тем же способом и различаются только интерпретацией результата.
Здравствуйте, lazyden, Вы писали:
L>Здравствуйте, RealBobEx, Вы писали:
RBE>>В описанаии и реализации алгоритма WinDiff от Microsoft есть несколько неясных моментов. RBE>>Может быть кто-нибудь знает его автора или может подсказать где взять более четкое описание?
L>Ключевые слова: LCS — Longest Common Subsequences, SES — Shortest Edit Script.
L>Edit script собственно и есть описание разницы между двумя строками/файлами. Обе проблемы решаются одним и тем же способом и различаются только интерпретацией результата.
L>Ссылки: L>An O(ND) Difference Algorithm and Its Variations L>An O(NP) Sequence Comparison Algorithm L>Кладезь мудрости :)
1. Большое спасибо за ссылки
К сожалению первая не живая. Нашел его только в HTML, но там нет картинок.
Нет ли у вас скачанного этого pdf-ника?
2. Насчет ключевых слов, a также алгоримтов LCS и SES я в курсе. Реализовывал и алгоритм "грубой силы", и динамический алгоритм Вагнера-Фишера, и Хиршберга (это, как Вы понимаете, — LCS).
Вопрос возник потому что в описании реализации от Microsoft нет ничего похожего.
Привожу его текст из исходников WinDiff-а:
Как видите, в явном виде ни LCS, ни SES не вычисляется.
Однако на выходе дает перемещенные строки + все остальные измененные (но не различает редактирование от вставки, а это важно для дальнейшего разбора строки по словам).
И возникает вопрос — перспективно ли долбаться с его клоном?
/***************************************************************************
* Function: ci_compare
*
* Purpose:
*
* Compare files and build a composite list.
*
* Comments:
*
* Comparison method:
*
* 0 Break each file into lines and hash each line. Lines which
* don't match can be rapidly eliminated by comparing the hash code.
*
* Store the hash codes in a binary search tree that
* will give for each hash code the number of times that it
* occurred in each file and one of the lines where it occurred
* in each file. The tree is used to rapidly find the partner
* of a line which occurs exactly once in each file.
*
* 1 Make a section covering the whole file (for both)
* and link unique lines between these sections (i.e. link lines
* which occur exactly once in each file as they must match each other).
* These are referred to as anchor points.
*
* 2 Build section lists for both files by traversing line lists and
* making a section for each set of adjacent lines that are unmatched
* and for each set of adjacent lines that match a set of adjacent
* lines in the other file. In making a section we start from a
* known matching line and work both forwards and backwards through
* the file including lines which match, whether they are unique or not.
*
* 3 Establish links between sections that match
* and also between sections that don't match but do
* correspond (by position in file between matching sections)
*
* 4 For each section pair that don't match but do correspond,
* link up matching lines unique within that section. (i.e. do
* the whole algorithm again on just this section).
*
* There may be some lines which occur many times over in each file.
* As these occurrences are matched up, so the number left to match
* reduces, and may reach one in each file. At this point these two
* can be matched. Therefore we...
*
* Repeat steps 0-4 until no more new links are added, but (especially
* in step 0) we only bother with lines which have not yet been matched.
* This means that a line which has only one unmatched instance in each
* file gets a count of one and so is a new anchor point.
*
* Finally build a composite list from the two lists of sections.
*
***************************************************************************/
Здравствуйте, _Obelisk_, Вы писали:
_O_>Здравствуйте, lazyden, Вы писали:
L>>Ключевые слова: LCS — Longest Common Subsequences, SES — Shortest Edit Script.
_O_>Так же встречается как Minimum Edit Distance.
Minimum Edit Distance не катит, т.к. дает всего лишь стоимость наиболее короткого преобразования, а мне нужно не его, а саму последовательность содержащую,
как минимум разделение вставленных строк от просто редактированных.
Улавливаете разницу?
Здравствуйте, RealBobEx, Вы писали:
RBE>1. Большое спасибо за ссылки RBE>К сожалению первая не живая. Нашел его только в HTML, но там нет картинок. RBE>Нет ли у вас скачанного этого pdf-ника?
Есть. Правда у меня статья выкачивается без проблем.
RBE>Привожу его текст из исходников WinDiff-а: RBE>Однако на выходе дает перемещенные строки + все остальные измененные (но не различает редактирование от вставки, а это важно для дальнейшего разбора строки по словам).
это я не совсем понял...
RBE>И возникает вопрос — перспективно ли долбаться с его клоном?
не подскажу, но алгоритм выглядит как не оптимальный в смысле длинны скрипта редактирования — т.е. дает корректный скрипт, но не всегда минимальной длины. IMHO, конечно.
Здравствуйте, lazyden, Вы писали:
L>Здравствуйте, RealBobEx, Вы писали:
RBE>>1. Большое спасибо за ссылки RBE>>К сожалению первая не живая. Нашел его только в HTML, но там нет картинок. RBE>>Нет ли у вас скачанного этого pdf-ника? L>Есть. Правда у меня статья выкачивается без проблем.
Да, сегодня и у меня закачалась.
RBE>>Однако на выходе дает перемещенные строки + все остальные измененные (но не различает редактирование от вставки, а это важно для дальнейшего разбора строки по словам). L>это я не совсем понял...
Ну это просто. Редактированные строки имеют пару для дальнейшего сравнения по словам.
А вставленнные — не имеют такой пары, их НЕВОЗМОЖНО дальше разобрать по словам (да и не нужно конечно).
И вот windiff не различает этой принципиальной разницы.
Кстати, как Вы сказали — неминимальная длина редактирования (тут я не улавливаю — почему Вы в этом увернны?) — это источник ошибок.
Здравствуйте, RealBobEx, Вы писали:
RBE>Здравствуйте, lazyden, Вы писали:
L>>Здравствуйте, RealBobEx, Вы писали:
RBE>Ну это просто. Редактированные строки имеют пару для дальнейшего сравнения по словам. RBE>А вставленнные — не имеют такой пары, их НЕВОЗМОЖНО дальше разобрать по словам (да и не нужно конечно). RBE>И вот windiff не различает этой принципиальной разницы.
RBE>Кстати, как Вы сказали — неминимальная длина редактирования (тут я не улавливаю — почему Вы в этом увернны?) — это источник ошибок.
IMHO Упрощенный аналогичный алгоритм —
1.Ищем в двух секциях пару одинаковых между собой и уникальных внутри своей секции строк.
2.а. Нашли. Тогда каждая строка делит секцию на две половинки. Применяем рекурсивно алгоритм к первым половинкам, затем ко вторым.
2.б. Не нашли на одинаковых строк — это две совершенно различные секции. Где-то их сохраняем.
2.с. Есть одинаковые строки, но нет уникальных — значит существуют разные варианты их сопоставления между собой. Как обработать эту ситуацию для того чтобы получить минимальный скрипт я и не увидел в описании алгоритма (или не понял/неасилил ). В принципе для реальных файлов это должно быть очень редкой ситуацией. Даже если и есть много одинаковых строк (ну например
{
в сишном исходнике или
end
в паскалевском) то они будут окружены уникальным контекстом, который и будет выбираться шагом 2.а до тех пор пока секция не сократится. И в этой сокращенной секции end станет уникальным.
По редактированию сложнее.
Либо можно подумать над шагом 2.б — что бы "нечетко" сравнивать строки (как — не знаю ). Либо работать не с отдельными строками, а сразу с отдельными словами .
Здравствуйте, RealBobEx, Вы писали:
RBE>Minimum Edit Distance не катит, т.к. дает всего лишь стоимость наиболее короткого преобразования, а мне нужно не его, а саму последовательность содержащую, RBE>как минимум разделение вставленных строк от просто редактированных. RBE>Улавливаете разницу?
В своё время решал задачу сравнения распознанного текста с оригиналом.
Легко получить не только минимальную стоимость редактирования, но и все возможные наборы операций редактирования с
минимальной стоимостью (мне были нужны именно все лучшие преобразования)
Правда, я работал на уровне отдельной строки... Для больших текстов этот метод подходит плохо..
Здравствуйте, RealBobEx, Вы писали:
RBE>В описанаии и реализации алгоритма WinDiff от Microsoft есть несколько неясных моментов. RBE>Может быть кто-нибудь знает его автора или может подсказать где взять более четкое описание?
Конечно, это не WinDiff, но я бы хотел представить вам и остальным свое видение решения
этой задачи. Может быть кому-нибудь это будет интересно.
Для своих целей я решил реализовать это по-своему,
возможно это неэффективно, но работало хорошо: берется текстовый файл и строится
матрица равенства строк между собой, то есть каждая строка сравнивается с каждой.
Эта операция очень быстрая, поэтому сравнение производилось очень быстро.
в итоге, получается матрица такого вида(1, если строки равны, 0, если не равны):
Вот, такой алгоритм. Анализируя эту матрицу можно узнать многое о сравнении двух текстов.
Может быть этот алгоритм далёк от оптимального, но для несложного приложения его вполне хватает.
L>2.с. Есть одинаковые строки, но нет уникальных — значит существуют разные варианты их сопоставления между собой. Как обработать эту ситуацию для того чтобы получить минимальный скрипт я и не увидел в описании алгоритма (или не понял/неасилил ).
Вот именно тут алгоритм рожает ошибки. И в его реализации от Mircosoft именно это и происходит.
Т.е. фактически, он дает какой-то скрипт, но не оптимальный. Причина — в этом месте нет якорной точки. А она — основа правильности скрипта.
L> В принципе для реальных файлов это должно быть очень редкой ситуацией. Даже если и есть много одинаковых строк.....
Я не могу делать скидку на редкость ситуаци. Сами знаете кто такой юзер — он обязательно первым делом сделает именно то, чего от него не ожидали
L>По редактированию сложнее.
Да, а именно редактирование меня беспокоит больше всего.
Вобщем читая сображения тех кто откликнулся, я убедился что изначально я был прав и маяться этой фигней не стоит
Здравствуйте, Imatic, Вы писали:
I>Для своих целей я решил реализовать это по-своему, I>возможно это неэффективно, но работало хорошо: берется текстовый файл и строится I>матрица равенства строк между собой, то есть каждая строка сравнивается с каждой. I>Эта операция очень быстрая, поэтому сравнение производилось очень быстро. I>в итоге, получается матрица такого вида(1, если строки равны, 0, если не равны):
I>
I>Вот, такой алгоритм. Анализируя эту матрицу можно узнать многое о сравнении двух текстов. I>Может быть этот алгоритм далёк от оптимального, но для несложного приложения его вполне хватает.
I>Особенно не ругайте!
Никто ругать и не собирается .
Тем более, что такое решение — это первое что приходит в голову любому.
Мне тоже приходило. Оно хорошо тем что мы имеем дело с разреженной матрицей и значит можно применить любой из известных способов экономии памяти (например по Кнуту, хотя я предпочитаю в этом случае простой и эффективный класс SparseArray подробно описанный у Джефа Элджера).
Однако кажется мне, что тут потенциально есть ошибки распознавания редактирования.
Хотя я и не могу это доказать.
Например, там где Вы написали "<- здесь строка вставлена" может быть и просто редактирование.
Представьте, что есть подряд идущие опеарации вставка-редактирование-удаление-редактирование и т.п.
Вобще построение такой матрицы, это изначальная идея, которая в конце концов привела к весьма изящному алгоритму нахождение Longest Common Subsequence Вагнера — Фишера (известен под названием "динамическое программирования")
А вообще, по поводу скорости и памяти, можно сказать, что мое приложение должно быть очень быстрым и главное — обрабатывать пары файлов не меньше 10 Мб не сжирая при этом всю доступную системе память (а так делают некоторые коммерч. продукты) в разумное время, т.е. не больше чем O(m*n).
Поэтому держать живьем матрицы в памяти я не могу.
). Либо работать не с отдельными строками, а сразу с отдельными словами 
.
