Тренировки по алгоритмам 4.0. Лекция 2: Хеши для строк

• Лекция посвящена хэшам для строк и сравнению подстрок.  

• Математика пригодится для изучения алгоритмов.  

• План: сравнение подстрок, примеры задач, создание поисковика.  

• Сравнение полиномов: коэффициенты должны совпадать попарно.  

• Пример сравнения двух полиномов.  

• Подстановка конкретного значения x для проверки равенства полиномов.  

• Одинаковые полиномы дают одинаковый результат при подстановке x.  

• Разные полиномы могут давать одинаковый результат, что может быть ошибкой.  

• Решение: подставлять несколько значений x для уменьшения вероятности ошибки.  

• Метод быстрого вычисления полинома в точке x.  

• Использование линейного времени для вычисления.  

• Применение метода для сравнения множества полиномов.  

• Подстановка x для каждого полинома и сопоставление с числом.  

• Использование словарей для подсчета количества совпадающих чисел.  

• Хэширование как метод перевода большого множества в маленькое.  

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

• Переполнение возникает при больших степенях, что приводит к проблемам с хранением и сравнением чисел.  

• Решение: использовать остаток от деления на константу, чтобы избежать переполнения.  

• Вместо хранения длинного числа, храним остаток от деления на константу.  

• Вероятность коллизий уменьшается при использовании нескольких констант.  

• Важно брать остаток после каждой операции, чтобы избежать переполнения.  

• Строки можно рассматривать как коэффициенты полинома.  

• Для строк разной длины сопоставляем длину и значение в точке икс.  

• Сравниваем строки по паре чисел: длина и значение в точке икс.  

• Сопоставляем строке полином, где коэффициенты соответствуют буквам.  

• Сравниваем подстроки одинаковой длины, используя полином.  

• Важно учитывать, что строки и полиномы взаимосвязаны, чтобы избежать путаницы.  

• Сравнение подстрок и полиномов.  

• Коэффициенты совпадают: 1 с 1, 2 с 2, 1 с 2.  

• Можно сравнивать коэффициенты вместо подстрок.  

• Подсчет хэшей для полиномов.  

• Использование массива для хранения значений.  

• Оптимизация вычислений для линейного времени.  

• Умножение предыдущего полинома на x и прибавление очередного коэффициента.  

• Подсчет конкретных чисел за линейное время.  

• Возвращение к добыче коэффициентов конкретной подстроки.  

• Извлечение подстроки из полинома.  

• Удаление лишних коэффициентов.  

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

• Устранение лишних коэффициентов с помощью полинома.  

• Приведение степеней полиномов к одинаковым значениям.  

• Вычитание ненужных коэффициентов для получения нужного результата.  

• Сравнение хэшей для подстрок.  

• Проблемы с вычислением степеней икса.  

• Использование массива для степеней икса.  

• Вычисление по модулю для предотвращения переполнения.  

• Решение проблемы отрицательных остатков.  

• Сравнение подстрок одинаковой длины.  

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

• Решение: перенос слагаемых с минусом в другую часть.  

• Все вычисления проводятся по модулю п.  

• Чем больше п, тем меньше вероятность коллизии.  

• Современные архитектуры поддерживают 64 бита, что делает п близким к 2^64.  

• Проблема: произведение чисел, близких к п, может вызвать переполнение.  

• Икс и п должны быть взаимно простыми.  

• П не должно быть степенью икса, чтобы избежать проблем с нулями.  

• Рекомендуется использовать простые числа, такие как 10^9 + 7.  

• Для отладки удобно использовать икс = 10.  

• Это позволяет легко проверять правильность хэшей.  

• В реальной жизни икс должен быть больше размера алфавита.  

• Предпосчет включает вычисление хэшей для префиксов.  

• Используется код символа по модулю п и степени иксов.  

• Функция сравнения проверяет совпадение строк с помощью математических подсчетов.  

• Знания о сравнении подстрок применимы к разным строкам.  

• Важно, чтобы икс и п совпадали для всех сравниваемых строк.  

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

• Вырезание кусочков одинаковой длины для сравнения.  

• Два варианта: пересмотреть и запомнить или поверить на слово.  

• Задача: проверить вхождение подстроки в строку.  

• Прикладывать подстроку к каждому возможному месту.  

• Проблема: сложность O n^2k, где k - длина подстроки.  

• Решение: использование хэшей префиксов.  

• Вычисление хэшей префиксов для подстроки.  

• Перебор всех подстрок длиной k.  

• Сравнение хэшей для нахождения вхождений.  

• Возможность ложно-положительных срабатываний.  

• Решение: считать хэши по нескольким модулям.  

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

• Найти самый короткий префикс, повторяющийся бесконечно.  

• Пример: определение диаметра барабана для печати обоев.  

• Наивное решение: перебор всех длин.  

• Использование хэшей для сравнения подстрок.  

• Проблема: сложность O n^2.  

• Решение: поиск максимального префикса, совпадающего с суффиксом.  

• Сравнение суффиксов на лексикографическое меньшинство.  

• Использование бинарного поиска для нахождения совпадающих частей.  

• Определение последнего момента, когда совпадающие части перестают совпадать.  

• Научились определять, какой суффикс идет раньше.  

• Бинарный поиск полезен для решения задач по поиску подстрок.  

• Пишем поисковик для массового поиска подстрок в строке.  

• Нужно быстро находить все вхождения запроса пользователя в длинную строку.  

• Запросы короткие, но алгоритмы, работающие за O n^2, не подходят.  

• Создаем массив всех суффиксов интернета.  

• Массив суффиксов будет иметь длину порядка n^2.  

• Интернет в 1995 году был большим, поэтому нужно эффективно хранить массив.  

• Храним только исходную строку, а суффиксы характеризуем позицией начала.  

• Научились хранить суффиксы одним числом.  

• Сортировка суффиксов работает за n log n.  

• Проблема в сравнении строк, которое может занять O n^2.  

• Сравнение строк может занять много времени.  

• Нужно научиться быстро сравнивать суффиксы.  

• В предыдущей части научились сравнивать суффиксы.  

• Суффиксный массив позволяет быстро сравнивать суффиксы строк.  

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

• Общая сложность алгоритма составляет n log n.  

• Суффиксный массив можно построить за n log n.  

• Для миллиарда символов это занимает около 15 минут.  

• Массив позволяет быстро искать позиции вхождений суффиксов.  

• Для поиска используется бинарный поиск.  

• Сложность поиска составляет k log n, где k - длина образца.  

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

• Суффиксный массив позволяет быстро искать в больших строках.  

• Возможны коллизии, но они редки.  

• Применение суффиксного массива для циклических перестановок.  

• Преобразование Баррозу-Вилера позволяет восстанавливать исходные строки.  

• Применяется для создания архиваторов, таких как BZIP2.  

• Преобразование проще, чем суффиксный массив.  

• Обсуждение работы с подстроками и хэшами.  

• Использование простых чисел Мерсена для уменьшения коллизий.  

• Применение нескольких модулей и иксов для повышения надежности.  

• Хэши позволяют сравнивать строки на равенство, но не на порядок.  

• Бинарный поиск используется для нахождения максимального совпадения.  

• Сравнение суффиксов строк для определения их порядка.  

• Находим длину совпадающей части и символы после нее.  

• Определяем, что максимальная совпадающая часть имеет длину три.  

• Сравниваем символы на позициях ф один и ф два плюс длина совпадающей части.  

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

• Рассматриваем возможность обрезки суффиксного массива справа.  

• В реальной жизни алгоритмы оптимизируются для запросов длиной до 256 символов.  

• Оптимизация может ускорить процесс, но возникают проблемы с равенством суффиксов.  

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

• Суффиксный массив подходит для понимания работы алгоритмов.  

• Вопросы на этом завершены, но важно понимать, что ничего не понять — это нормально.  

• Используйте готовый рецепт для сравнения строк.  

• Следующие лекции будут менее математичными и более понятными.  

• Оставайтесь с нами, и задачи будут решаться проще.