Фундаментальные алгоритмы и структуры данных в Delphi

Потратим несколько минут, и попытаемся определить требуемый для выполнения этой задачи алгоритм. Раньше я уже пытался сделать это, что оказалось достаточно трудно. Кое-что можно упростить сразу: изменение строки можно считать удалением старой строки и вставкой новой. Мы не будем углубляться в проблемы семантики, пытаясь выяснить, насколько сильно изменилась строка. Мы всего лишь будем рассматривать все изменения в текстовом файле как набор удаленных строк и набор вставленных новых строк.

Вычисление LCS двух строк

Требуемый нам алгоритм известен под названием алгоритма определения наиболее длинной общей подпоследовательности (longest common subsequence - LCS). Вначале мы рассмотрим, как он работает применительно к строкам, а затем расширим приобретенные представления на текстовые файлы.

Уверен, что все мы играли с детскими головоломками, в которых нужно было преобразовать одно слово в другое, изменяя по одной букве. Все промежуточные варианты должны были быть также осмысленными словами. Так, преобразуя слово CAT в слово DOG, можно было бы выполнить следующие преобразования: CAT, COT, COG, DOG.

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

Предположим, что наша цель заключается в отыскании наименьшего количества изменений, требуемых для преобразования одного слова в другое. Для примера преобразуем слово BEGIN в слово FINISH. Мы видим, что нужно удалить буквы В, Е и G, а затем вставить букву F перед оставшимися буквами и буквы I, S и H после них. Как же реализовать эти действия в виде алгоритма?

Один из возможных способов предполагает просмотр подпоследовательностей букв каждого слова и выяснение наличия в них общих последовательностей. Подпоследовательность (subsequence) строки образуется за счет удаления из нее одного или более символов. Оставшиеся символы не должны переставляться. Например, четырехбуквенными подпоследовательностями для строки BEGIN являются EGIN, BGIN, BEGIN, BEIN и BEGI. Как видите, они образуются путем поочередного отбрасывания одного из символов. Трехбуквенными подпоследовательностями являются BEG, BEI, BEN, BGI, BGN, BIN, EGI, EGN, EIN и GIN. Для данного слова существует 10 двухбуквенных подпоследовательностей и пять одно-буквенных. Таким образом, для пятибуквенного слова существует всего 30 возможных подпоследовательностей, а в общем случае можно было бы показать, что для n-буквенной последовательности существует около 2(^n^) подпоследовательностей. Пока что примите это утверждение на веру.

Алгоритм с применением "грубой силы", если его можно так назвать, заключается в просмотре двух слов BEGIN и FINISH и просмотре их пятибуквенных подпоследовательностей на предмет наличия каких-либо совпадений. Такие совпадения отсутствуют, поэтому для каждого слова то же самое нужно сделать, используя четырехбуквенные подпоследовательности. Как и в предыдущем случае, ни одна из подпоследовательностей не совпадает, поэтому мы переходим к рассмотрению трехбуквенных последовательностей. Результат снова отрицателен, поэтому мы переходим к сравнению двухбуквенных подпоследовательностей. Самой длинной общей подпоследовательностью этих двух слов является IN. Исходя из этого, можно определить, какие буквы необходимо удалить, а какие вставить.

Для коротких слов, подобных приведенному примеру, описанный подход не так уж плох. Но представим, что требуется просмотреть все подпоследовательности 100-символьной строки. Как уже упоминалось, их количество составляет 2(^100^). Алгоритм с применением "грубой силы" является экспоненциальным. Количество выполняемых операций пропорционально O(2(^n^)). Даже для строк средней длины поле поиска увеличивается чрезвычайно быстро. А это влечет за собой радикальное увеличение времени, требуемого для отыскания решения. Чтобы сказанное было нагляднее, представим следующую ситуацию: предположим, что можно генерировать около биллиона подпоследовательностей в секунду.(т.е. 2(^40^)= 1 099 511 627 776, или тысячу подпоследовательностей за один такт работы процессора ПК, тактовая частота которого равна 1 ГГц). Год содержит около 2(^25^) секунд. Следовательно, для генерации всего набора подпоследовательностей для 100-символьного слова потребовалось бы 2(^35^) (34 359 738 368) лет - 11-значное число. А теперь вспомните, что 100-символьная строка - всего лишь простенький пример того, что необходимо сделать: например, найти различие между двумя вариантами 600-строчного исходного файла.

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