Поиск наибольшей общей подстроки двух строк с использованием хеширования — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Время работы)
(Постановка задачи)
Строка 1: Строка 1:
 
==Постановка задачи==
 
==Постановка задачи==
Имеются строки <tex>S</tex> и <tex>T</tex> такие, что элементы этих строк  <tex>-</tex> символы из конечного алфавита <tex> \sum </tex>. Говорят, что строка <tex>Z</tex>[1 .. m] является подстрокой строки <tex>S</tex>[1 .. n], если существует такой индекс <tex>k</tex> &isin; [1 .. n - m], что для любого <tex>i</tex> &isin; [1 .. m] справедливо <tex>S[k + i] = Z[i]</tex>. Требуется найти такую строку <tex>Z</tex>, максимальной длины, что <tex>Z</tex> является и подстрокой <tex>S</tex>, и подстрокой <tex>T</tex>.
+
Имеются строки <tex>S</tex> и <tex>T</tex> такие, что элементы этих строк  <tex>-</tex> символы из конечного алфавита <tex> \sum </tex>. Говорят, что строка <tex>Z</tex>[1 .. m] является подстрокой строки <tex>S</tex>[1 .. n], если существует такой индекс <tex>k</tex> &isin; [0 .. n - m], что для любого <tex>i</tex> &isin; [1 .. m] справедливо <tex>S[k + i] = Z[i]</tex>. Требуется найти такую строку <tex>Z</tex>, максимальной длины, что <tex>Z</tex> является и подстрокой <tex>S</tex>, и подстрокой <tex>T</tex>.
 +
 
 
==Алгоритм==
 
==Алгоритм==
 
Данный алгоритм основывается на методе половинного деления. Пусть длина наибольшей общей подстроки будет <tex>x</tex>. Заметим, что у строк <tex>S</tex> и <tex>T</tex> обязательно найдется общая подстрока длины <tex>y</tex> &isin; [0 .. <tex>x</tex>], так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим функцию <tex>f</tex> : [1 .. min(len(<tex>S</tex>), len(<tex>T</tex>))] &rarr; <tex>\mathbb{Z}</tex>, которая для <tex>i</tex> из области определения равна <tex>i</tex>, если у строк <tex>S</tex> и <tex>T</tex> есть общая подстрока длины <tex>i</tex>, иначе она равна 0. Согласно замечанию, функция <tex>f</tex> должна по мере возрастания <tex>i</tex> строго монотонно возрастать до некоторого момента, а затем обращаться в 0. Таким образом на области определения у функции <tex>f</tex> достигается максимум. Собственно, этот максимум и является длиной наибольшей общей подстроки у строк <tex>S</tex> и <tex>T</tex>, так как функция <tex>f</tex> специально так определена. Таким образом требуется с помощью бинарного поиска найти максимум функции <tex>f</tex> на ее множестве определения. В ходе работы придется проверять наличие общей подстроки заданной длины. При этом предполагается использовать хэширование, чтобы улучшить асимптотику алгоритма. Делается это следующим образом: 1) у строки <tex>S</tex> хэшируем подстроки заданной длины и полученные хэши записываем в Set. 2) у строки <tex>T</tex> хэшируем подстроки заданной длины и в случае совпадения хэша с элементом Set выполняем посимвольную проверку на совпадение подстрок. Предполагается, что хэширование будет проводится так же, как и в [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|алгоритме Рабина-Карпа]].
 
Данный алгоритм основывается на методе половинного деления. Пусть длина наибольшей общей подстроки будет <tex>x</tex>. Заметим, что у строк <tex>S</tex> и <tex>T</tex> обязательно найдется общая подстрока длины <tex>y</tex> &isin; [0 .. <tex>x</tex>], так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим функцию <tex>f</tex> : [1 .. min(len(<tex>S</tex>), len(<tex>T</tex>))] &rarr; <tex>\mathbb{Z}</tex>, которая для <tex>i</tex> из области определения равна <tex>i</tex>, если у строк <tex>S</tex> и <tex>T</tex> есть общая подстрока длины <tex>i</tex>, иначе она равна 0. Согласно замечанию, функция <tex>f</tex> должна по мере возрастания <tex>i</tex> строго монотонно возрастать до некоторого момента, а затем обращаться в 0. Таким образом на области определения у функции <tex>f</tex> достигается максимум. Собственно, этот максимум и является длиной наибольшей общей подстроки у строк <tex>S</tex> и <tex>T</tex>, так как функция <tex>f</tex> специально так определена. Таким образом требуется с помощью бинарного поиска найти максимум функции <tex>f</tex> на ее множестве определения. В ходе работы придется проверять наличие общей подстроки заданной длины. При этом предполагается использовать хэширование, чтобы улучшить асимптотику алгоритма. Делается это следующим образом: 1) у строки <tex>S</tex> хэшируем подстроки заданной длины и полученные хэши записываем в Set. 2) у строки <tex>T</tex> хэшируем подстроки заданной длины и в случае совпадения хэша с элементом Set выполняем посимвольную проверку на совпадение подстрок. Предполагается, что хэширование будет проводится так же, как и в [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|алгоритме Рабина-Карпа]].
 
==Время работы==
 
==Время работы==
 
Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного поиска. Во-первых, хэширование подстрок строки <tex>S</tex> и запись их в Set требует O(len(<tex>S</tex>)) шагов. Во-вторых, хэширование подстрок строки <tex>T</tex> и проверка их наличия в Set требует O(len(<tex>T</tex>)). В приведенных рассужденияхпредполагается, что операции записи в Set и проверка наличия элемента в Set раюотают за амортизированную O(1). Поскольку хэшировали с помощью [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|этого]] метода, то это занимает линейное время. Значит,на каждый шаг бинарного поиска требуется O(max(len(<tex>S</tex>), len(<tex>T</tex>))) действий. На самом деле требуется несколько больше времени, поскольку совпадение хэшей не дает гарантии совпадения подстрок, однако чтобы это было справедливо с большой вероятностью, достаточно проверить совпадение лишь нескольких произвольных символов, вместо полной проверки. Тогда на это потребуется некоторое константное число операций, что маскируется с помощью O. Заметим, что всего для завершения бинарного поиска потребуется O(log(min(len(<tex>S</tex>), len(<tex>T</tex>)))) шагов. Следовательно, суммарное время работы алгоритма будет O(log(min(len(<tex>S</tex>), len(<tex>T</tex>))) * max(len(<tex>S</tex>), len(<tex>T</tex>))) действий.
 
Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного поиска. Во-первых, хэширование подстрок строки <tex>S</tex> и запись их в Set требует O(len(<tex>S</tex>)) шагов. Во-вторых, хэширование подстрок строки <tex>T</tex> и проверка их наличия в Set требует O(len(<tex>T</tex>)). В приведенных рассужденияхпредполагается, что операции записи в Set и проверка наличия элемента в Set раюотают за амортизированную O(1). Поскольку хэшировали с помощью [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|этого]] метода, то это занимает линейное время. Значит,на каждый шаг бинарного поиска требуется O(max(len(<tex>S</tex>), len(<tex>T</tex>))) действий. На самом деле требуется несколько больше времени, поскольку совпадение хэшей не дает гарантии совпадения подстрок, однако чтобы это было справедливо с большой вероятностью, достаточно проверить совпадение лишь нескольких произвольных символов, вместо полной проверки. Тогда на это потребуется некоторое константное число операций, что маскируется с помощью O. Заметим, что всего для завершения бинарного поиска потребуется O(log(min(len(<tex>S</tex>), len(<tex>T</tex>)))) шагов. Следовательно, суммарное время работы алгоритма будет O(log(min(len(<tex>S</tex>), len(<tex>T</tex>))) * max(len(<tex>S</tex>), len(<tex>T</tex>))) действий.

Версия 08:55, 15 марта 2011

Постановка задачи

Имеются строки [math]S[/math] и [math]T[/math] такие, что элементы этих строк [math]-[/math] символы из конечного алфавита [math] \sum [/math]. Говорят, что строка [math]Z[/math][1 .. m] является подстрокой строки [math]S[/math][1 .. n], если существует такой индекс [math]k[/math] ∈ [0 .. n - m], что для любого [math]i[/math] ∈ [1 .. m] справедливо [math]S[k + i] = Z[i][/math]. Требуется найти такую строку [math]Z[/math], максимальной длины, что [math]Z[/math] является и подстрокой [math]S[/math], и подстрокой [math]T[/math].

Алгоритм

Данный алгоритм основывается на методе половинного деления. Пусть длина наибольшей общей подстроки будет [math]x[/math]. Заметим, что у строк [math]S[/math] и [math]T[/math] обязательно найдется общая подстрока длины [math]y[/math] ∈ [0 .. [math]x[/math]], так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим функцию [math]f[/math] : [1 .. min(len([math]S[/math]), len([math]T[/math]))] → [math]\mathbb{Z}[/math], которая для [math]i[/math] из области определения равна [math]i[/math], если у строк [math]S[/math] и [math]T[/math] есть общая подстрока длины [math]i[/math], иначе она равна 0. Согласно замечанию, функция [math]f[/math] должна по мере возрастания [math]i[/math] строго монотонно возрастать до некоторого момента, а затем обращаться в 0. Таким образом на области определения у функции [math]f[/math] достигается максимум. Собственно, этот максимум и является длиной наибольшей общей подстроки у строк [math]S[/math] и [math]T[/math], так как функция [math]f[/math] специально так определена. Таким образом требуется с помощью бинарного поиска найти максимум функции [math]f[/math] на ее множестве определения. В ходе работы придется проверять наличие общей подстроки заданной длины. При этом предполагается использовать хэширование, чтобы улучшить асимптотику алгоритма. Делается это следующим образом: 1) у строки [math]S[/math] хэшируем подстроки заданной длины и полученные хэши записываем в Set. 2) у строки [math]T[/math] хэшируем подстроки заданной длины и в случае совпадения хэша с элементом Set выполняем посимвольную проверку на совпадение подстрок. Предполагается, что хэширование будет проводится так же, как и в алгоритме Рабина-Карпа.

Время работы

Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного поиска. Во-первых, хэширование подстрок строки [math]S[/math] и запись их в Set требует O(len([math]S[/math])) шагов. Во-вторых, хэширование подстрок строки [math]T[/math] и проверка их наличия в Set требует O(len([math]T[/math])). В приведенных рассужденияхпредполагается, что операции записи в Set и проверка наличия элемента в Set раюотают за амортизированную O(1). Поскольку хэшировали с помощью этого метода, то это занимает линейное время. Значит,на каждый шаг бинарного поиска требуется O(max(len([math]S[/math]), len([math]T[/math]))) действий. На самом деле требуется несколько больше времени, поскольку совпадение хэшей не дает гарантии совпадения подстрок, однако чтобы это было справедливо с большой вероятностью, достаточно проверить совпадение лишь нескольких произвольных символов, вместо полной проверки. Тогда на это потребуется некоторое константное число операций, что маскируется с помощью O. Заметим, что всего для завершения бинарного поиска потребуется O(log(min(len([math]S[/math]), len([math]T[/math])))) шагов. Следовательно, суммарное время работы алгоритма будет O(log(min(len([math]S[/math]), len([math]T[/math]))) * max(len([math]S[/math]), len([math]T[/math]))) действий.