АЛГОРИТМЫ НА ПРАКТИКЕ

Создайте «текст-дифференциатор», используя самую длинную-общую-подпоследовательность.

.. проблема, применение, решение и реализация!

Проблема:

Давайте сначала посмотрим на основную проблему: пусть X и Y будут двумя произвольными строками длины u и v соответственно. Какая самая длинная общая подпоследовательность (LCS) между X и Y?

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

Учитывая две строки, мы должны найти самую длинную подпоследовательность, которая является общей для обеих этих строк.

Использование:

Прежде чем перейти к решению, давайте подумаем, где и зачем вам нужен такой поисковик с самой длинной общей подпоследовательностью? Первый и один из очень полезных случаев - «поиск генов». Мы можем сравнить 2 нити ДНК, найдя самую длинную общую подпоследовательность оснований [аденин (A), цитозин (C), гуанин (G ) или тимин (T)] между ними, что покажет нам, насколько генетически схожи две нити ДНК.

Другой важный вариант использования - найти полную противоположность LCS, т.е. поиск в чем разница между 2 текстами. Поэтому лучшее решение для этого - найти LCS и сравнить его с двумя текстами, чтобы определить разницу. Это особенно полезно в системах контроля версий, таких как Git, которые сравнивают файлы и разницу между ними между разными коммитами.

В этом руководстве / статье я буду создавать простой текстовый дифференциатор, в который вы можете вставить два разных текста и выяснить, насколько они похожи, а насколько разные. Мы будем использовать JavaScript, чтобы получить текст из входных данных, найти разницу, выделить их и показать как результат. Но сначала давайте посмотрим на решение:

Решение:

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

Рассмотрим строкиX и Y длины u и v соответственно. Пусть LCS(Xᵤ , Yᵥ) будет самой длинной общей подпоследовательностью между X (длина от 0 до символа uᵗʰ) и Y (длина от 0 до символа vᵗʰ).

Мы должны разделить проблему LCS(Xᵤ , Yᵥ) на более мелкие подзадачи. Если символ uᵗʰ в X и символ vᵗʰ в Y равны, это означает, что мы можем рассматривать этот знак равенства в ответе последней подпоследовательности. Таким образом, разбив это на меньшую проблему: LCS между X и Y для длины u и v соответственно равен единице плюс LCS X и Y для длины u-1 и v-1 (поскольку символ uᵗʰ для X и vᵗʰ символа Y равны).

LCS(Xᵤ , Yᵥ) = 1 + LCS(Xᵤ₋₁ , Yᵥ₋₁) -> (for equal characters)

Но что, если эти персонажи не равны? Затем у нас есть 2 варианта: рассмотреть символ uᵗʰ из X и игнорировать символ vᵗʰ из Y, или наоборот. Затем нам нужно будет найти, какой из этих двух вариантов дает подпоследовательность максимальной длины. Таким образом, рекурсивное уравнение сводится к:

LCS(Xᵤ , Yᵥ) = max(LCS(Xᵤ , Yᵥ₋₁), LCS(Xᵤ₋₁ , Yᵥ)) -> (for unequal characters)

Затем, когда вы видите большую рекурсивную проблему, всегда думайте об использовании динамического программирования (DP), если можете. Мы можем использовать динамическое программирование, если задача удовлетворяет 2 условиям:

  1. Оптимальная подструктура - проблема, которую можно разделить на подзадачи, оптимальные решения которых также могут составить наиболее оптимальное решение основной проблемы. Здесь мы видим, что LCS можно разделить на более мелкие подзадачи LCS, и поэтому LCS удовлетворяет этому условию.
  2. Перекрывающиеся подзадачи - некоторые подзадачи встречаются в дереве рекурсии более одного раза, т.е. мы неоднократно вычисляем ответ на одну и ту же подзадачу. LCS это тоже удовлетворяет.

Таким образом, мы можем использовать DP для хранения значений повторяющихся подзадач, так что мы вычисляем их только один раз ... следовательно, преобразуя временную сложность LCS из экспоненциальной рекурсии O(2ⁿ) (посмотрите на ветви рекурсии наихудшего случая .. каждая проблема приводит к 2 подзадачи ... итак, подсчитав все узлы в дереве, мы получаем 2ⁿ подзадачи для решения) до O(mn) для длины X и Y как m и n соответственно.

Алгоритм / Код:

Давайте использовать восходящий подход для решения LCS (можно также использовать нисходящий подход, никакого вреда в этом нет, временная сложность остается прежней ... но рекурсивный стек вызовов увеличивается, поэтому я предпочитаю восходящий подход здесь).

Используя восходящий подход, мы сначала создаем пустую матрицу из rows= length(X)+1 и cols=length(Y)+1. Вы можете спросить, почему +1? Это потому, что первая строка и столбец предназначены для пустых символов и будут заполнены нулями. Индексирование наших букв в каждом слове начнется с 1. Затем мы перебираем (i, j) для каждого элемента матрицы и заполняем его в соответствии с формулой: (пока не обращайте внимания на красные поля, просто посмотрите, как заполняется каждая строка. по одной по формуле)

Вот фрагмент кода JavaScript:

Теперь эта функция дает нам только длину LCS. Мы хотим найти настоящую строку LCS. Для этого нам нужно вернуться к нашим шагам в матрице, как показано красными полями на рисунке выше. Основная формула: если оба символа в данном индексе (i, j) равны, это означает, что мы прошли по диагонали, чтобы достичь этого значения. Таким образом, мы добавляем символ в LCS в обратном порядке и возвращаемся к (i-1,j-1).. Если символы не равны, мы возвращаемся к элементу, имеющему максимальное значение между (i,j-1) и (i-1,j), и ничего не добавляем к обратному выходному LCS. Вот фрагмент JS:

Окончательная реализация:

Все это хорошо, но теперь мы хотим увидеть это в действии 😛

Мы используем две основные области ввода текста, чтобы пользователь мог вводить текст. Затем мы добавляем прослушиватель событий на кнопку отправки. Как только пользователь нажимает кнопку «Отправить», запускается функция findDifference(text1, text2), которая получает текстовые значения из ввода и находит LCS между ними.

Теперь нам нужно отобразить один и тот же текст в другом <div> как слева, так и справа и выделить общие буквы LCS зеленым, а другие - красным. Для этого мы используем функцию highlightText(commonText, originalText)..

Последний шаг - добавить текст, возвращаемый highlightText(), в DOM.

И вуаля! Мы создали простой работающий текстовый дифференциатор, используя на практике алгоритм наиболее длинная-общая-подпоследовательность. 😁

Полный исходный код, включая HTML, CSS и JS, можно найти здесь! Вы также можете попробовать текст-diff, который я сделал здесь :)

Спасибо за прочтение! Если вы нашли статью полезной и / или забавной, хлопните в ладоши и подписывайтесь за мной! 😋

И как всегда, мы учимся вместе. Если вы обнаружите, что что-то не так или хотите что-то добавить, оставьте ответ, и я проверю. Ваше здоровье! ✨