Комментарии 20
Спасибо за интересный пост. Особенно актуален он сейчас, когда проходит конкурс параллельного программирования с задачей, очень похожей на решаемую в этом топике.
Отличный пост!
Думаю также стоит упомянуть и другие алгоритмы, например алгоритм Укконена (на базе суффиксных деревьев), который позволяет находить наибольшую общую подстроку за линейное время при линейном расходе памяти.
Самый первый алгоритм (примитивный) хорош тем, что можно использовать веса при вычислении LCS, т.е. считать, что вес совпадения может быть равен не только 1, но и 2, 3… и даже 0 (причем этот вес можно сделать даже дробным при желании). Это удобно при построчном сравнении файлов, т.к., например, пустые строки дают меньший вклад в оценку наибольшей совпадающей подпоследовательности, чем содержащие текст. Также строки большой длины имеют больший вес по сравнению с короткими строками.
Для примера:
Версия 1:
a
b
cdefghijklm
Версия 2:
cdefghijklm
a
b
При равных весах строк при сравнении LCS будет представлена строками (a, b), хотя на самом деле строка cdefghijklm содержит больше значимой информации, чем a и b вместе взятые.
В простейшем случае за вес можно взять длину строки или количество значимых символов в ней.
Для примера:
Версия 1:
a
b
cdefghijklm
Версия 2:
cdefghijklm
a
b
При равных весах строк при сравнении LCS будет представлена строками (a, b), хотя на самом деле строка cdefghijklm содержит больше значимой информации, чем a и b вместе взятые.
В простейшем случае за вес можно взять длину строки или количество значимых символов в ней.
Если очень хочется, то можно реализовать работу с весами и в алгоритме Ханта-Шуманского, перебирая индексы из matchlist в порядке уменьшения веса.
И да, повторю мысль, с реальной жизнью первый алгоритм не совместим, скачайте приложенный код и попробуйте сами.
Я применял и первый алгоритм вполне успешно, см. далее мой комментарий про разделение файлов на участки :)
Что-то мне подсказывает, что вы говорите про второй алгоритм
Поверьте мне, именно про тупой железобетонно-деревянно-неэффективный первый алгоритм с огромной матрицей :) (с предварительным эмпирическим подразбиением файлов). Собственно найти саму LCS это лишь малая часть сравнения. У меня была задача для измененных фрагментов (участков, где нет ни одного равного абзаца) показать точные изменения в тексте абзацев. А для этого нужно было сначала найти оптимальное сопоставление измененных абзацев на основе степени их схожести. Я как раз собирался сначала написать про LCS в продолжение к моему первому топику, но вы меня опередили :) Видимо теперь придется писать сразу уже про схожесть и поиск оптимального соответствия :)
Обойти ограничения первого алгоритма по времени вычислений и требуемому объему памяти можно, например, предварительно разбив файл на отдельные сравнительно небольшие участки для поиска LCS (например, содержащие не более 5000 строк). Матрицу из 5000*5000*4 байта(Integer) = 100 МБ еще как-то можно упихнуть в память). Конечно, найденная последовательность не будет самой оптимальной с математической точки зрения, но для сравнения файлов вполне годится.
Для разделения файлов на участки можно использовать какой-нибудь эмпирический подход.
Например:
1) Определить очередную теоретическую точку разделения в файлах А и Б. Эта точка находится на выбранном удалении от предыдущих найденных точек разделения. Например, 5000 строк.
2) На относительно небольшом расстоянии по отношению к размеру участка (например, 100 строк) от теоретической точки разделения найти наиболее показательные элементы (например, 10 самых длинных строк). Взять очередную найденную показательную строку (по убыванию показательности) и попытаться найти ее во втором файле на бОльшем расстоянии по сравнению с участком поиска показательных элементов в файле А, но меньшем размера участка разделения (например, 25%-50% от участка разделения, т.е. 1200-2500 строк).
3) Если соответствующая строка в файле Б найдена, то можно дополнительно подстраховаться, что мы не ошиблись, сравнив несколько строк, соседствующих c выбранной строкой (они тоже должны совпадать).
4) Если соответствующая строка в документе Б не найдена, то можно взять следующую показательную строку и попытаться выполнить шаги 2-4 для нее.
5) Если для всех показательных строк так и не получилось найти соответствие в документе Б, можно сравнение на основе точного соответствия заменить на сравнение на основе похожести («дистанции») между строками, но при этом длину участка поиска в документе Б нужно сократить.
6) Если точки разделения уточнить по схожим строкам не удалось, значит нам не повезло, вынуждены принять теоретические точки разделения за фактические.
Для найденных отдельных участков ищем LCS независимо любым из перечисленных выше алгоритмов.
Для разделения файлов на участки можно использовать какой-нибудь эмпирический подход.
Например:
1) Определить очередную теоретическую точку разделения в файлах А и Б. Эта точка находится на выбранном удалении от предыдущих найденных точек разделения. Например, 5000 строк.
2) На относительно небольшом расстоянии по отношению к размеру участка (например, 100 строк) от теоретической точки разделения найти наиболее показательные элементы (например, 10 самых длинных строк). Взять очередную найденную показательную строку (по убыванию показательности) и попытаться найти ее во втором файле на бОльшем расстоянии по сравнению с участком поиска показательных элементов в файле А, но меньшем размера участка разделения (например, 25%-50% от участка разделения, т.е. 1200-2500 строк).
3) Если соответствующая строка в файле Б найдена, то можно дополнительно подстраховаться, что мы не ошиблись, сравнив несколько строк, соседствующих c выбранной строкой (они тоже должны совпадать).
4) Если соответствующая строка в документе Б не найдена, то можно взять следующую показательную строку и попытаться выполнить шаги 2-4 для нее.
5) Если для всех показательных строк так и не получилось найти соответствие в документе Б, можно сравнение на основе точного соответствия заменить на сравнение на основе похожести («дистанции») между строками, но при этом длину участка поиска в документе Б нужно сократить.
6) Если точки разделения уточнить по схожим строкам не удалось, значит нам не повезло, вынуждены принять теоретические точки разделения за фактические.
Для найденных отдельных участков ищем LCS независимо любым из перечисленных выше алгоритмов.
Алгоритм динамического программирования можно распараллелить. Точнее, самую длинную его часть — построение матрицы. Для этого заметим, что для того, чтобы вычислить значение x[i][j], нужно знать только x[i-1][j-1], x[i][j-1], x[i-1][j]. Для начала вычислим первую строку и первый столбец матрицы. Потом вычислим левый верхний блок матрицы, например X[1:10][1:10]. После этого можем вычислять блоки X[1:10][10:20] и X[10:20][1:10]. Эти блоки можно вычислять параллельно. Дальше — больше блоков. Так можно задействовать несколько ядер процессора при использовании, например, библиотеки multiprocessing если речь идет о Питоне.
Если я ничего не путаю, то представленный тут алгоритм (который динамический за О(N*M)) — это алгоритм Нудельмана-Вунша.
Я думаю это стоит отметить в статье, потому что скорее всего этот алгоритм многие знают, и вы сэкономите им чуть-чуть времени =)
Я думаю это стоит отметить в статье, потому что скорее всего этот алгоритм многие знают, и вы сэкономите им чуть-чуть времени =)
Неделя капитанских алгоритмов?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Нахождение максимальной общей подпоследовательности