Popoff
popoff.donetsk.ua
Нахождение максимальной подстроки для двух строк
Решил оптимизировать работу системы сравнения двух статей, которая используется на сайте для того, чтобы администраторы могли сравнивать две разные версии статей и видеть изменения.
Сейчас у меня реализован алгоритм Левенштейна (ru.wikipedia.org/...) со слежением, что там как менялось (то есть, не просто число вычисляется, как в оригинале, а ещё отслеживается, как это число получилось и это позволяет сказать, что и как поменялось в статьях). Сложность алгоритма - О(m*n). То есть, если в статье 1000 строк (а это не самая большая статья) и там поменяли один символ, то, чтобы это определить, нужно, грубо говоря, выполнить миллион операций. Скорость работы такая, что реально за 30 секунд успевает выполниться сравнение статей объёмом максимум 700-800 строк.
Я ввёл некоторую оптимизацию в алгоритм сравнения, которая состоит в том, что перед применением алгоритма Левенштейна удаляются начальные и конечные совпадающие строки сравниваемых статей. Результат, в общем-то очевидный. Чаще всего это хорошо помогает, но если поменять что-нибудь в самом начале и в самом конце, то снова долго сравнивается.
Предполагаемое улучшение, которое можно было бы ввести в простейшем случае - это найти наибольшую общую подстроку (например, назовём её А) среди двух строк (назовём их Y и Z), вычеркнуть эту подстроку из этих двух строк (то есть рассматриваем эти две строки как конкатенацию Y==BAC и Z==DAE, где B,C,D и E - некоторые строки) и дальше отдельно сравнивать B c D и C c E. Это простое, я считаю, логичное улучшение.
Улучшение тут состоит не только в том, что из исходные строки становятся короче из-за удаления повтояющихся последовательностей, но также и в том, что задача разбивается на две независимые подзадачи, так что эти две задачи последовательно решаются быстрее, чем если бы решалась одна общая задача. Дальше, эти две подзадачи тоже можно решать с этим же улучшением - то есть, рекурсивно, снова искать в новых строках новую наибольшую общую часть, вычеркивать, разбивать на подзадачи и т.п. Это, я считаю, тоже просто.
В PEAR есть процедуры для поиска наибольшей подстроки, но сложность реализованных там процедур равна O(m*n), то есть, только чтобы найти наибольшую подстроку, уже нужно m*n операций сделать - не считая того, что дальше ещё потом те кусочки тоже сравнивать надо.
Если представить все возможные подстроки (в данном случае интересуют только все возможные суффиксы) второй строки (ещё лучше - той, которая длиннее) в виде дерева и проверять вхождение подстроки уже с использованием дерева (то есть, если в дереве найден суффикс, для которого искомая подстрока первой строки была бы префиксом, то значит эта подстрока является общей частью этих двух строк), а не прямым перебором во второй строке, то сложность алгоритма можно было бы уменьшить до O(m*log(n)). Не считая времени на построение того дерева; вместе с простейшим двоичным деревом без всяких штук, описанных ниже, получится что-то типа O((m+n)*log(n)) - тоже, в общем-то неплохо. Сравнивая те же две статьи по 1000 строк, уже нужно будет выполнить не миллион операций, а каких-то ~20 000.
Я начал копать в сторону суффиксных деревьев (ссылка 1, ссылка 2) - они, вроде как, обещают скорость поиска наибольшей подстроки, равной О(m+n). Я, в общем-то разобрался, как те деревья строятся, но в ступор меня вогнал третий снизу абзац по первой ссылке:
Мне кажется, это не совсем так. Если, к примеру, в y будет наибольшая повторяющаяся последовательность из 3 символов (например, y=abcdebcdf, наибольшая повторяющаяся последовательность = bcd), а строка х, к примеру, будет состоять всего из 2 символов (например, ab), то предложенный ими способ вернёт те три символа из y (наибольшая повторяющаяся последовательность для строки ab#abcdebcdf$ - всё та же bcd), которых в х и впомине нету.
Хотя, конечно, может, я не уловил какой-то не сказанный явно смысл или недостаточно внимательно изучил ту статью, или ещё чего-то не так понял. Я, конечно, найду решение и сам, или, на худой конец, удовлетворюсь O((m+n)*log(n)). Но если кому-то интересно помыслить над этой задачкой и решить её со сложностью O(m+n), то я был бы рад помощи. Ну, или, может, кто-то знает другие алгоритмы.
Решил оптимизировать работу системы сравнения двух статей, которая используется на сайте для того, чтобы администраторы могли сравнивать две разные версии статей и видеть изменения.
Сейчас у меня реализован алгоритм Левенштейна (ru.wikipedia.org/...) со слежением, что там как менялось (то есть, не просто число вычисляется, как в оригинале, а ещё отслеживается, как это число получилось и это позволяет сказать, что и как поменялось в статьях). Сложность алгоритма - О(m*n). То есть, если в статье 1000 строк (а это не самая большая статья) и там поменяли один символ, то, чтобы это определить, нужно, грубо говоря, выполнить миллион операций. Скорость работы такая, что реально за 30 секунд успевает выполниться сравнение статей объёмом максимум 700-800 строк.
Я ввёл некоторую оптимизацию в алгоритм сравнения, которая состоит в том, что перед применением алгоритма Левенштейна удаляются начальные и конечные совпадающие строки сравниваемых статей. Результат, в общем-то очевидный. Чаще всего это хорошо помогает, но если поменять что-нибудь в самом начале и в самом конце, то снова долго сравнивается.
Предполагаемое улучшение, которое можно было бы ввести в простейшем случае - это найти наибольшую общую подстроку (например, назовём её А) среди двух строк (назовём их Y и Z), вычеркнуть эту подстроку из этих двух строк (то есть рассматриваем эти две строки как конкатенацию Y==BAC и Z==DAE, где B,C,D и E - некоторые строки) и дальше отдельно сравнивать B c D и C c E. Это простое, я считаю, логичное улучшение.
Улучшение тут состоит не только в том, что из исходные строки становятся короче из-за удаления повтояющихся последовательностей, но также и в том, что задача разбивается на две независимые подзадачи, так что эти две задачи последовательно решаются быстрее, чем если бы решалась одна общая задача. Дальше, эти две подзадачи тоже можно решать с этим же улучшением - то есть, рекурсивно, снова искать в новых строках новую наибольшую общую часть, вычеркивать, разбивать на подзадачи и т.п. Это, я считаю, тоже просто.
В PEAR есть процедуры для поиска наибольшей подстроки, но сложность реализованных там процедур равна O(m*n), то есть, только чтобы найти наибольшую подстроку, уже нужно m*n операций сделать - не считая того, что дальше ещё потом те кусочки тоже сравнивать надо.
Если представить все возможные подстроки (в данном случае интересуют только все возможные суффиксы) второй строки (ещё лучше - той, которая длиннее) в виде дерева и проверять вхождение подстроки уже с использованием дерева (то есть, если в дереве найден суффикс, для которого искомая подстрока первой строки была бы префиксом, то значит эта подстрока является общей частью этих двух строк), а не прямым перебором во второй строке, то сложность алгоритма можно было бы уменьшить до O(m*log(n)). Не считая времени на построение того дерева; вместе с простейшим двоичным деревом без всяких штук, описанных ниже, получится что-то типа O((m+n)*log(n)) - тоже, в общем-то неплохо. Сравнивая те же две статьи по 1000 строк, уже нужно будет выполнить не миллион операций, а каких-то ~20 000.
Я начал копать в сторону суффиксных деревьев (ссылка 1, ссылка 2) - они, вроде как, обещают скорость поиска наибольшей подстроки, равной О(m+n). Я, в общем-то разобрался, как те деревья строятся, но в ступор меня вогнал третий снизу абзац по первой ссылке:
Фактически, они предлагают найти самую большую повторяющуюся последовательность в строке x#y$ и говорят, что это - и будет наибольшая общая последовательность символов между x и y.
Мне кажется, это не совсем так. Если, к примеру, в y будет наибольшая повторяющаяся последовательность из 3 символов (например, y=abcdebcdf, наибольшая повторяющаяся последовательность = bcd), а строка х, к примеру, будет состоять всего из 2 символов (например, ab), то предложенный ими способ вернёт те три символа из y (наибольшая повторяющаяся последовательность для строки ab#abcdebcdf$ - всё та же bcd), которых в х и впомине нету.
Хотя, конечно, может, я не уловил какой-то не сказанный явно смысл или недостаточно внимательно изучил ту статью, или ещё чего-то не так понял. Я, конечно, найду решение и сам, или, на худой конец, удовлетворюсь O((m+n)*log(n)). Но если кому-то интересно помыслить над этой задачкой и решить её со сложностью O(m+n), то я был бы рад помощи. Ну, или, может, кто-то знает другие алгоритмы.
