Алгоритмы и структуры данных. Лекция 14. Расстояние Левенштейна

• В видео обсуждается расстояние Ливенштейна, которое помогает считать расстояние между подстроками.  

• Рассматриваются два примера: классический отец и две строки.  

• Обсуждается алгоритм Вагнера-Фишера для расчета расстояния Ливенштейна.  

• Рассматривается пример с двумя строками: спейсер и спит.  

• Построение графа для представления расстояния Ливенштейна.  

• Граф состоит из узлов решетки и ребер, соответствующих операциям вставки, удаления и замены символов.  

• Проставляются веса ребер, соответствующие стоимости операций.  

• Рассматривается задача о нахождении расстояния от паттерна до строки по метрике Ливенштейна.  

• Обсуждается использование графа для решения задачи.  

• Предлагается решение, основанное на фиксации и и использовании графа для получения ответа на все запросы.  

• Обсуждается идея использования графа для получения расстояния между паттерном и подстрокой.  

• Объясняется идея использования динамического программирования для решения задачи.  

• Обсуждается идея обрезки текста и использования графа для получения ответа на все запросы.  

• В видео обсуждается определение расстояния Либинштейна между двумя строками.  

• Расстояние Либинштейна между двумя строками - это минимальное количество операций вставки, удаления и замены символов, необходимых для преобразования одной строки в другую.  

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

• В видео объясняется, как найти все подстроки с минимальным расстоянием Либинштейна.  

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

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

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

• Для этого предлагается использовать нумерацию диагоналей матрицы, на которых происходит дописывание символов к обеим строкам.  

• Если удастся быстро считать эту последовательность одинаковых строк, то можно ускорить алгоритм.  

• В видео объясняется, что расстояние Левенштейна - это математическая абстракция, которую сложно визуализировать.  

• Для определения расстояния Левенштейна необходимо найти максимальное расстояние на диагонали, где расстояние равно фиксированному числу.  

• В видео объясняется, что для поиска максимального расстояния на диагонали необходимо перебирать все клетки и выбирать ту, где расстояние равно фиксированному числу.  

• Затем выбирается самая нижняя клетка на диагонали, где расстояние равно фиксированному числу.  

• В видео обсуждаются ограничения на поиск паттернов и максимальное расстояние, которое можно допустить.  

• Также объясняется, что если считать расстояние Левенштейна минус к минус один, то невозможно сделать исправления, чтобы дополнить текст до полной строки.  

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

• Упоминается, что алгоритм учитывает максимальное значение и учитывает все возможные пути по динамике.  

• Обсуждается, как алгоритм работает с удалением символов и как это влияет на паттерн.  

• Обсуждается время работы алгоритма, которое зависит от длины текста и количества итераций.  

• Упоминается, что время работы алгоритма можно улучшить с помощью использования суффиксного дерева.  

• Обсуждается идея суффиксного дерева, которое строится на суффиксах строки и сжимает проходные вершины.  

• Упоминается, что суффиксное дерево можно построить за линейное время.  

• Утверждение о том, что суффиксное дерево можно построить из суффиксного автомата и дерева ссылок.  

• Построение дерева ссылок и определение глубин вершин.  

• Использование суффиксного автомата для определения длин ребер и глубин вершин.  

• Алгоритм состоит из трех частей: инициация, построение суффиксного дерева и расчет значений рпк.  

• Инициация включает построение собственного дерева и расчет базы для рпк.  

• Расчет значений рпк включает поиск лцп двух строк или сипи в строке.  

• Время работы алгоритма составляет O(n).