Комментарии 18
Спасибо за статью. А можно сравнение производительности методов?
Пожалуйста!
Вообще, производительность методов эквивалентна. Z-функция в самом плохом случае выполняет 2|X|+2|A| сферических операций, а КМП — 3|X|+3|A|. Но наступление этих самых плохих ситуаций происходит при синтетических заготовках текста, например КМП обычно не три раза каждый символ смотрит, а полтора раза в среднем. В реальной жизни еще надо думать о каких именно операциях идет речь.
А вообще эти алгоритмы интересны не столько тем, что они особо быстрые, сколько тем, что Z-функция и преффикс-функция используются в других алгоритмах работы со строками. А самым быстрым считают Бойера-Мура и его модификации, как утверждает википедия.
Вообще, производительность методов эквивалентна. Z-функция в самом плохом случае выполняет 2|X|+2|A| сферических операций, а КМП — 3|X|+3|A|. Но наступление этих самых плохих ситуаций происходит при синтетических заготовках текста, например КМП обычно не три раза каждый символ смотрит, а полтора раза в среднем. В реальной жизни еще надо думать о каких именно операциях идет речь.
А вообще эти алгоритмы интересны не столько тем, что они особо быстрые, сколько тем, что Z-функция и преффикс-функция используются в других алгоритмах работы со строками. А самым быстрым считают Бойера-Мура и его модификации, как утверждает википедия.
На различных строках (когда искомая подстрока в начале, конце, и тд).
Оба алгоритма просматривают строки последовательно. Т.е. оба найдут первое вхождение в общем случае раньше, чем обработают всю строку. Правда КМП обнаруживает конец вхождения, а Z-функция начало. В случае длинного шаблона поиска в этом будет разница на длину X (КМП обработает на |X| символов больше), если вы это имели ввиду.
половины равны
а так статья хорошая, спасибо
а так статья хорошая, спасибо
Писал подобное на асме под дос. Тот еще секс. А нечем было заниматься в «тихий час» летом, когда в деревню к бабушке отправляли. Под рукой были x286 и книжка по асму.
Еще есть суффиксный автомат, который пишется проще суффиксного дерева и с помощью которого можно делать практически все то же самое что и помощью дерева, в том числе и находить подстроки.
1) в Решении «в лоб» по моему вы намудрили с «откатами». Вот оно решение в лоб:
а теперь попробуем реализовать алгоритм с «откатом». Получится что-то типа:
не очень тривиально, как вам кажется?
2) вычисление Z-функции и Алгоритм Кнута-Морриса-Пратта (КМП) по видимо можно записать в виде рекуррентного соотношения и вычислить при помощи динамического программирования.
Запись рекуррентного соотношения займет всего несколько строк, и заменит страницу текста с (не очень понятными) объяснениями и рисунками.
3) вопрос по термину «бор (trie)». Никогда не слышал о таком. Может быть вы имели ввиду «лес деревьев»?
for (int i=0; i<str.length-s.lenght; i++) {
if (str[i]==s[0]) {
boolean f = true;
for (int j=1; j<s.length && f; j++) {
f = str[i+j]==s[j];
}
if (f) return i;
}
}
return -1;
а теперь попробуем реализовать алгоритм с «откатом». Получится что-то типа:
int f = 0;
for (int i=0; i<str.length; i++) {
if (str[i]!=s[i-f]) {
i -= i-f; // "откат"
f = i+1;
}
else if (i-f+1==s.length) {
return f;
}
}
return -1;
не очень тривиально, как вам кажется?
2) вычисление Z-функции и Алгоритм Кнута-Морриса-Пратта (КМП) по видимо можно записать в виде рекуррентного соотношения и вычислить при помощи динамического программирования.
Запись рекуррентного соотношения займет всего несколько строк, и заменит страницу текста с (не очень понятными) объяснениями и рисунками.
3) вопрос по термину «бор (trie)». Никогда не слышал о таком. Может быть вы имели ввиду «лес деревьев»?
1) Ну хорошо, вот ваш пример который без «отката». Вот вы вошли во внутренний цикл, пощупали i+1-й символ, i+2-й, i+3-й, и тут бац! Облом. Не то. И дальше вы выходите и внутреннего и продолжаете с i+1-й позиции. И чем не откат назад? Вы же уже смотрели i+1, i+2 и т.д. символы. По логике то же самое, а код к тому месту, которое значилось как пример как делать не надо, я не писал :)
Кстати, если бы сделали break во внутреннем цикле, то вышли бы гораздо раньше, а так даже если вторая буква из пятисот не совпала, вы все-равно все пятсот шерстите.
2) Можно, но если что-то можно записать нерекурсивно, то зачем это делать рекурсией? И факториал рекурсивно считается, но зачем? Чтобы потом надеяться, что компилятор соптимизирует?
3) Это одно и то же. Бор — это лес деревьев во всех смыслах. Как ни странно, это вполне употребимый термин.
Кстати, если бы сделали break во внутреннем цикле, то вышли бы гораздо раньше, а так даже если вторая буква из пятисот не совпала, вы все-равно все пятсот шерстите.
2) Можно, но если что-то можно записать нерекурсивно, то зачем это делать рекурсией? И факториал рекурсивно считается, но зачем? Чтобы потом надеяться, что компилятор соптимизирует?
3) Это одно и то же. Бор — это лес деревьев во всех смыслах. Как ни странно, это вполне употребимый термин.
1) а) если вы считаете, что первый алгоритм, это алгоритм с «откатами», тогда у меня нет претензий.
Единственное что хочется заметить, что из этого алгоритма легко вытекает сложность О(nm): у нас два вложенных цикла, один длиной n, другой — m. А вот сложность для второго алгоритма не так тривиальна. Поэтому мне показалось. что вы говорили именно о втором алгоритме, объясняя что из-за возможных «откатов» мы получаем О(nm).
б) >>… а так даже если вторая буква из пятисот не совпала, вы все-равно все пятьсот шерстите.
Посмотрите алгоритм ещё раз внимательнее. Алгоритм выходит сразу после нахождения несовпадения. Кстати использованный прием рекомендуется для избежания break-переходов.
2) рекуррентное соотношение не имеет ничего общего с рекурсией. Числа Фибоначчи, факториал — это все рекуррентные соотношения. А обычный способ вычисления рекуррентного соотношения — это не рекурсия, а динамическое программирование.
3) хорошо, теперь буду знать, что «лес деревьев» == «бор» :)
Единственное что хочется заметить, что из этого алгоритма легко вытекает сложность О(nm): у нас два вложенных цикла, один длиной n, другой — m. А вот сложность для второго алгоритма не так тривиальна. Поэтому мне показалось. что вы говорили именно о втором алгоритме, объясняя что из-за возможных «откатов» мы получаем О(nm).
б) >>… а так даже если вторая буква из пятисот не совпала, вы все-равно все пятьсот шерстите.
Посмотрите алгоритм ещё раз внимательнее. Алгоритм выходит сразу после нахождения несовпадения. Кстати использованный прием рекомендуется для избежания break-переходов.
2) рекуррентное соотношение не имеет ничего общего с рекурсией. Числа Фибоначчи, факториал — это все рекуррентные соотношения. А обычный способ вычисления рекуррентного соотношения — это не рекурсия, а динамическое программирование.
3) хорошо, теперь буду знать, что «лес деревьев» == «бор» :)
1) a) Ну собственно так и считаю. Второй вариант совсем извращенный, хотя похоже тоже O(mn), если, конечно, он работает.
б) Да, точно. Не углядел. Кстати, а это уже аргумент за «break» — он заметнее.
2) Ну если так, то в принципе они и описаны. Динамическое программирование на рекуррентном соотношении дала бы именно такие алгоритмы. Собственно а в чем разница? Вы решаете n задачек нахождения некой функции в каждой точке. И для этого используете предыдущие результаты вычислений. В описаниях приведены правила перехода в i+1 позицию при наличии решений до 1..i позиций. Разве что само соотношение не записано, ибо условия, когда его применять, весьма муторно выписывать.
Для Z-функции получилось бы в точности то самое. Для префикс-функции возможно получился бы какой-то побочный вариант вроде «сильной префикс функции» — когда результаты «откатов» назад протаскиваются вперед чтобы не повторять откаты. Но это был бы по сути такой же КМП.
3) Если интересно, то вот здесь есть еще синонимы этой структуры. На мой взгляд «бор» — веселее. Бор — это же лес деревьев. Кроме того, более широко распространено.
б) Да, точно. Не углядел. Кстати, а это уже аргумент за «break» — он заметнее.
2) Ну если так, то в принципе они и описаны. Динамическое программирование на рекуррентном соотношении дала бы именно такие алгоритмы. Собственно а в чем разница? Вы решаете n задачек нахождения некой функции в каждой точке. И для этого используете предыдущие результаты вычислений. В описаниях приведены правила перехода в i+1 позицию при наличии решений до 1..i позиций. Разве что само соотношение не записано, ибо условия, когда его применять, весьма муторно выписывать.
Для Z-функции получилось бы в точности то самое. Для префикс-функции возможно получился бы какой-то побочный вариант вроде «сильной префикс функции» — когда результаты «откатов» назад протаскиваются вперед чтобы не повторять откаты. Но это был бы по сути такой же КМП.
3) Если интересно, то вот здесь есть еще синонимы этой структуры. На мой взгляд «бор» — веселее. Бор — это же лес деревьев. Кроме того, более широко распространено.
Перечитал текст несколько раз, все равно не понял, как вычисляется Z-функция за линейное время и почему именно так.
В википедии есть через рекуррентное соотношение, но не ясно, почему именно так.
Если не трудно, можно пару примеров?
От себя добавлю, есть еще вариант поиска через сдвигающееся окно. Это когда для строки, которую нужно найти, вычисляется некая функция (пусть для примера это будет сумма всех символов), далее вычисляется эта же функция для начала строки такой же длины. Если функции совпали, проводится посимвольное сравнение. Если нет совпадения, то «окно» сдвигается на 1 позицию: из суммы вычитается значение символа, оставшегося за границей окна, и прибавляется значение нового символа.
Правда, не знаю, зачем это может понадобится, если сложность других алгоритмов линейна :)
В википедии есть через рекуррентное соотношение, но не ясно, почему именно так.
Если не трудно, можно пару примеров?
От себя добавлю, есть еще вариант поиска через сдвигающееся окно. Это когда для строки, которую нужно найти, вычисляется некая функция (пусть для примера это будет сумма всех символов), далее вычисляется эта же функция для начала строки такой же длины. Если функции совпали, проводится посимвольное сравнение. Если нет совпадения, то «окно» сдвигается на 1 позицию: из суммы вычитается значение символа, оставшегося за границей окна, и прибавляется значение нового символа.
Правда, не знаю, зачем это может понадобится, если сложность других алгоритмов линейна :)
Окей, попробую объяснить.
Почему за линейное время в простом случае, когда для k=i-r+1 дуального i Z[k] меньше чем оставшийся Z-блок понятно — просто смотрим результат для Z[k] и вписывем в i-ю ячейку. Очевидно О(1).
Допустим Z[k] больше или равно расстоянию до конца Z-блока. Тогда мы будем проверять h+1 символов правее конца нашего самого правого Z-блока. При этом окажется, что Z[i]=Z[k]+h, что при отсчете от i-ой позиции закончится дальше, чем текущий r-тый Z-блок на h позиций. А значит r-тый мы разжалуем и возьмем за любимый Z-блок этот самый новый Z[i]. Но он будет заканчиваться на h позиций дальше, а значит для этих h позиций мы схалтурим на следующих шагах с проверкой не сравнивая больше их для других суффиксов, так как по логике подобия Z-блоков такая обработка уже совершалась. Таким образом второй тип шага для каждого символа будет проделан 1 раз. Что и дает общую сложность O(n). Да, нет гарантии что каждый шаг выполнится за O(1), но общий все-таки O(n).
Почему за линейное время в простом случае, когда для k=i-r+1 дуального i Z[k] меньше чем оставшийся Z-блок понятно — просто смотрим результат для Z[k] и вписывем в i-ю ячейку. Очевидно О(1).
Допустим Z[k] больше или равно расстоянию до конца Z-блока. Тогда мы будем проверять h+1 символов правее конца нашего самого правого Z-блока. При этом окажется, что Z[i]=Z[k]+h, что при отсчете от i-ой позиции закончится дальше, чем текущий r-тый Z-блок на h позиций. А значит r-тый мы разжалуем и возьмем за любимый Z-блок этот самый новый Z[i]. Но он будет заканчиваться на h позиций дальше, а значит для этих h позиций мы схалтурим на следующих шагах с проверкой не сравнивая больше их для других суффиксов, так как по логике подобия Z-блоков такая обработка уже совершалась. Таким образом второй тип шага для каждого символа будет проделан 1 раз. Что и дает общую сложность O(n). Да, нет гарантии что каждый шаг выполнится за O(1), но общий все-таки O(n).
Думаю ваш алгоритм может быть полезен когда вычисление хэша от набора объектов заметно дешевле их сравнения. Т.е. не для строк, а для, каких-нибудь больших и сложных объектов.
«Сдвигающееся окно» это Рабин-Карп.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск подстроки и смежные вопросы