Алгоритмы на линейных структурах: алгоритмы поиска

Дисциплина «Алгоритмы и структуры данных» Лекция № 7 Алгоритмы на линейных структурах: алгоритмы поиска Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Каким поиск бывает? Каким поиск бывает? • Точный (Exact String Matching Algorithm) – брутфорс-алгоритм (алгоритм грубой силы); – алгоритм Кнута, Морриса и Пратта (алгоритм КМП); – алгоритм Боуера и Мура (алгоритм БМ); • Нечёткий (Fuzzy String Matching Algorithm) – определения начала совпадения строк при допущении возможности их различия (отдаленности) не более, чем на… – расстояние Хемминга - отдалённость двух строк одинаковой длины, т.е. определение количества несовпадающих символов в соответствующих позициях, или количество замен для получения идентичной строки; – расстояние Левенштейна - сравнение строк разной длины с использованием операций удаления, вставки и замены: функция отдалённости или расстояние d определяется как количество замен, удалений или вставок, необходимых для получения из рассматриваемой строки искомого шаблона (проверка орфографии). Алгоритм прямого поиска Строка / Текст Образец / Слово Слово i i i i i i A A i i B C A B C A A B A C B A C B A D B D A B C A B D A B C A B D A B C A B D A B C A B D A B C A B A B C A B B C A B D D D Алгоритм прямого поиска i i A Строка / Текст Образец / Слово +j A Слово i i i i i i B C A B C A A B A C B A C B A D B D A B C A B D A B C A B D A B C A B D A B C A B D A B C A B A B C A B B C A B D D D Алгоритм прямого поиска Строка / Текст Образец / Слово Слово i+0 i i+1 i i+2 i i+3 i i+4 i i+5 i i i A B C A B C A A A B A C B A C B A D B D A B C A B D A B C A B D A B C A B D A B C A B D A B C A B A B C A B B C A B D D D Алгоритм прямого поиска Строка / Текст Образец / Слово Слово i+0 i i+1 i i+2 i i+3 i i+4 i i+5 i i i A B C A B C A A A B A C B A C B A D B D A B C A B D A B C A B D A B C A B D A B C A B D A B C A B A B C A B B C A B D D D Прямой поиск (псевдокод) Строка / Текст Образец / Слово Слово i+0 i i+1 i i+2 i i+3 i i+4 i i+5 i i i A B C A B C A A A B A C B A C B A D B D A B C A B D A B C A B D A B C A B D A B C A B D A B C A B A B C A B B C A B D D D Алгоритм прямого поиска i i+0 Строка / Текст Образец / Слово Слово i… ii+j i… i ii+длина_обзаца-1 i i A B C A B C A A B C A B A B A C B A C B A D B D A B C A B D A B C A B D A B C A B D A B C A B D A B C A B A B C A B D D D Алгоритм прямого поиска Строка / Текст Образец / Слово Слово i+0 i i+1 i i+2 i i+3 i i+4 i i+5 i i i A B C A B C Х A A A B A C B A C B A D B D A B C A B D A B C A B D A B C A B D A B C A B D A B C A B A B C A B B C A B D D D Алгоритм прямого поиска i Строка / Текст Образец / Слово Слово ii=i+1i i i i i i A A B C A B C A B C A B A B A C B A C B A D B D A B C A B D A B C A B D A B C A B D A B C A B D A B C A B A B C A B D D D Алгоритм прямого поиска i+0 i i… i+j i … i i A B C A B C A A B A C B A C B A D B D A B C A B D A B C A B D A B C A B D A B C A B D A B C A B A B C A B i Строка / Текст Образец / Слово Слово i i+длина_обзаца-1 i A B C A B D D D Алгоритм прямого поиска i Строка / Текст Образец / Слово Слово i i… i+0 i i+j i … i A B C A B C A A B A C B A C B A D B D A B C A B D A B C A B D A B C A B D A B C A B D A B C A B A B C A B Х i i+длина_обзаца-1 i A B C A B D D D Прямой поиск (брутфорс-алгоритм) Нечеткий поиск (на брутфорс-алгоритме) • Изменим внутренний цикл так, чтоб для каждой подстроки он находил расстояние Хемминга; Нечеткий поиск (на брутфорс-алгоритме) • Изменим внутренний цикл так, чтоб для каждой подстроки он находил расстояние Хемминга; • Введем параметр – k  (0..1), которое будет показывать максимальный процент несовпадений. Тогда формула определения начала совпадения будет такой: distance(s) <= length(s) * k. Нечеткий поиск (на брутфорс-алгоритме) • Изменим внутренний цикл так, чтоб для каждой подстроки он находил расстояние Хемминга; • Введем параметр – k  (0..1), которое будет показывать максимальный процент несовпадений. Тогда формула определения начала совпадения будет такой: distance(s) <= length(s) * k. Алгоритм Кнута-Морриса-Пратта. ПЕРВЫЙ ЭТАП АЛГОРИТМА: ПРЕФИКС-ФУНКЦИЯ. Определение. Дана строка s [0 .. n – 1](образ). Требуется вычислить для неё префикс-функцию, то есть массив чисел prefix [0 .. n – 1], где prefix[i] возвращает значение, равное максимальной длине совпадающих префикса и суффикса подстроки в образе, которая заканчивается i-м символом. Значение prefix[0] всегда равняется 0. Математически определение префикс-функции можно записать следующим образом: Например, для строки "abcabcd" префикс-функция равна: [0, 0, 0, 1, 2, 3, 0] , что означает: •у строки "a" нет префикса, совпадающего с суффиксом; •у строки "ab" нет префикса, совпадающего с суффиксом; •у строки "abc" нет префикса, совпадающего с суффиксом; •у строки "abca" префикс длины 1 совпадает с суффиксом; •у строки "abcab" префикс длины 2 совпадает с суффиксом; •у строки "abcabc" префикс длины 3 совпадает с суффиксом; •у строки "abcabcd" нет префикса, совпадающего с суффиксом. Другой пример — для строки "aabaaab" она равна: [0, 1, 0, 1, 2, 2, 3]. ПРОГРАММНЫЙ КОД ПРЕФИКС-ФУНКЦИИ Непосредственно следуя определению, можно написать такой алгоритм вычисления префикс-функции: Приведем итоговую схему алгоритма вычисления префикс-функции: - Считать значения префикс-функции prefix[i] будем по очереди: от i = 1 до i = n – 1 (prefix[0] = 0 – база, нулевой элемент всегда равен 0). - Для подсчета текущего prefix[i] определим переменную index, обозначающую длину текущего рассматриваемого образца. Изначально index = prefix[i – 1], то есть равна длине префикса вычисленной для предыдущей позиции. - Проверяем образец длины index, для чего сравниваем символы str[i] и str[index]. Если они совпадают – то prefix[i] = index + 1 и переходим к индексу i + 1, иначе уменьшаем длину index, полагая ее равной prefix[index – 1], и повторяем этот шаг. - Если дошли до длины index = 0 и не нашли совпадения, то prefix[i] = 0, после чего переходим к следующему индексу (i + 1). ПРОГРАММНЫЙ КОД ПРЕФИКС-ФУНКЦИИ Трудоемкость данного алгоритма составляет… Приведем итоговую схему алгоритма вычисления префикс-функции: - Считать значения префикс-функции prefix[i] будем по очереди: от i = 1 до i = n – 1 (prefix[0] = 0 – база, нулевой элемент всегда равен 0). - Для подсчета текущего prefix[i] определим переменную index, обозначающую длину текущего рассматриваемого образца. Изначально index = prefix[i – 1], то есть равна длине префикса вычисленной для предыдущей позиции. - Проверяем образец длины index, для чего сравниваем символы str[i] и str[index]. Если они совпадают – то prefix[i] = index + 1 и переходим к индексу i + 1, иначе уменьшаем длину index, полагая ее равной prefix[index – 1], и повторяем этот шаг. - Если дошли до длины index = 0 и не нашли совпадения, то prefix[i] = 0, после чего переходим к следующему индексу (i + 1). ПРОГРАММНЫЙ КОД ПРЕФИКС-ФУНКЦИИ Трудоемкость данного алгоритма составляет . Приведем итоговую схему алгоритма вычисления префикс-функции: - Считать значения префикс-функции prefix[i] будем по очереди: от i = 1 до i = n – 1 (prefix[0] = 0 – база, нулевой элемент всегда равен 0). - Для подсчета текущего prefix[i] определим переменную index, обозначающую длину текущего рассматриваемого образца. Изначально index = prefix[i – 1], то есть равна длине префикса вычисленной для предыдущей позиции. - Проверяем образец длины index, для чего сравниваем символы str[i] и str[index]. Если они совпадают – то prefix[i] = index + 1 и переходим к индексу i + 1, иначе уменьшаем длину index, полагая ее равной prefix[index – 1], и повторяем этот шаг. - Если дошли до длины index = 0 и не нашли совпадения, то prefix[i] = 0, после чего переходим к следующему индексу (i + 1). Описание префикс-функции. Мы построили алгоритм, который не содержит явных сравнений строк и имеет сложность . Приведем здесь итоговую схему алгоритма: - Считать значения префикс-функции prefix[i] будем по очереди: от i = 1 к i = n – 1 (prefix[0] = 0 – база). - Для подсчета текущего prefix[i] заводим переменную index, обозначающую длину текущего рассматриваемого образца. Изначально index = prefix[i – 1]. - Проверяем образец длины index, для чего сравниваем символы str[i] и str[index]. Если они совпадают – то prefix[i] = index + 1 и переходим к индексу i + 1, иначе уменьшаем длину index, полагая ее равной prefix[index – 1], повторяем этот шаг алгоритма снова. - Если дошли до длины index = 0 и не нашли совпадения, то prefix[i] = 0, после чего переходим к следующему индексу (i + 1). ВТОРОЙ ЭТАП. ПОИСК ОБРАЗА В СТРОКЕ. Второй этап представляет собой поиск образа в строке с использованием массива prefix. Программная реализация ниже: Алгоритм Кнута, Морриса и Пратта Изюминка КМП — это префикс-функция, которая формально решает совсем другую задачу, но после некоторого чудесного трюка, превращается в решение задачи поиска всех вхождений образца в строку. Рассмотрим строку:  строка  номер (позиция) символа в строке (для удобства начинаем с 1)  массив Pi длин префиксов, ключ к пониманию префикс-функции. Алгоритм Кнута, Морриса и Пратта Изюминка КМП — это префикс-функция, которая формально решает совсем другую задачу, но после некоторого чудесного трюка, превращается в решение задачи поиска всех вхождений образца в строку. Рассмотрим строку:  строка  номер (позиция) символа в строке (для удобства начинаем с 1)  массив Pi длин префиксов, ключ к пониманию префикс-функции. Возьмем символ с номером 7 (это a) и для K от 1 до 6 рассмотрим • строки-префиксы (подстрока, начинающаяся с первого индекса строки) и • суффиксы (подстрока, последний символ которой в строке в позиции 7 («наш» символ a) длины K. Алгоритм Кнута, Морриса и Пратта Изюминка КМП — это префикс-функция, которая формально решает совсем другую задачу, но после некоторого чудесного трюка, превращается в решение задачи поиска всех вхождений образца в строку. Рассмотрим строку:  строка  номер (позиция) символа в строке (для удобства начинаем с 1)  массив Pi длин префиксов, ключ к пониманию префикс-функции. Возьмем символ с номером 7 (это a) и для K от 1 до 6 рассмотрим • строки-префиксы (подстрока, начинающаяся с первого индекса строки) и • суффиксы (подстрока, последний символ которой в строке в позиции 7, (т.е. в позиции К+1 (!!!!) – это и есть «наш» символ a) длины K. Алгоритм Кнута, Морриса и Пратта  строка Возьмем символ с номером 7 (это a) и для K от 1 до 6 рассмотрим • строки-префиксы (подстрока, начинающаяся с первого индекса строки) и • суффиксы (подстрока, последний символ которой в строке в позиции 7 («наш» символ a) длины K.  номер (позиция) символа в строке (для удобства начинаем с 1)  массив Pi длин префиксов, ключ к пониманию префикс-функции. Алгоритм Кнута, Морриса и Пратта  строка Возьмем символ с номером 7 (это a) и для K от 1 до 6 рассмотрим • строки-префиксы (подстрока, начинающаяся с первого индекса строки) и • суффиксы (подстрока, последний символ которой в строке в позиции 7 («наш» символ a) длины K.  номер (позиция) символа в строке (для удобства начинаем с 1)  массив Pi длин префиксов, ключ к пониманию префикс-функции. Алгоритм Кнута, Морриса и Пратта  строка Возьмем символ с номером 7 (это a) и для K от 1 до 6 рассмотрим • строки-префиксы (подстрока, начинающаяся с первого индекса строки) и • суффиксы (подстрока, последний символ которой в строке в позиции 7 («наш» символ a) длины K.  номер (позиция) символа в строке (для удобства начинаем с 1)  массив Pi длин префиксов, ключ к пониманию префикс-функции. Алгоритм Кнута, Морриса и Пратта (1)  строка  номер (позиция) символа в строке (для удобства начинаем с 1)  массив Pi длин префиксов, ключ к пониманию префикс-функции. Алгоритм Кнута, Морриса и Пратта (2) Алгоритм Кнута, Морриса и Пратта (3) Алгоритм Кнута, Морриса и Пратта (4) Это место — ключ к эффективности КМП. Если очередные символы строки и образца не совпали, мы не двигаем образец на 1 символ и не сравниваем его со строкой с самого начала (как в примитивном поиске). Мы сдвигаем образец на несколько символов и делаем одно сравнение str[i] и obr[j]. Если не совпало — опять сдвиг образца, пока символы не совпадут или не дойдем до начала образца. Т.о. по строке поиска назад не двигаемся, только вперед (хотя и с остановками). Алгоритм Кнута, Морриса и Пратта i i i i Текст A B C A B C A A B C A B D Слово A B C A B D A B C A B D A B C A B D A B C A B D Если j определяет позицию в слове, содержащую первый несовпадающий символ (как в алгоритме прямого поиска), то величина сдвига Shift определяется как j-LenSuff-1. Значение LenSuff определяется как размер самой длинной последовательности символов слова, непосредственно предшествующих позиции j (суффикс), которая полностью совпадает с началом слова. LenSuff зависит только от слова и не зависит от текста. Для каждого j будет своя величина Shift, которую обозначим Shiftj. Вывод По сути, данный алгоритм представляет собой алгоритм прямого поиска, но с применением префикс-функции. Происходит такое же сравнение символов подстроки и строки, и при нахождении отличий, благодаря нашему массиву prefix, заполненного с помощью префикс-функции, мы избегаем бесполезных сдвигов, делая сдвиг на нужный нам символ. Сложность данного алгоритмаO(n+m), где n-длина подстроки, а m-длина строки. Спасибо за внимание!