Комментарии 57
Я не понимаю, почему в таблице в разделе "Переходим к трюку" на позиции 6 (там где '@') стоит 3, а на позиции 8 стоит 5 как будто там найдено совпадение. Нет ли там ошибки?
Конечно, реально редко встретишь образец длиной 100, но в олимпиадных задачах «на поиск» это обычное дело, поэтому там простой поиск часто не подходит.
Я вас огорчу. Вокруг таких реальных задач вся биоинформатика крутиться. Там масса алгоритмов разработано именно для анализа строк ДНК.
Вы меня не огорчили — я в курсе. Это популярная статья для программистов, которым просто нужен быстрый поиск. Процитирую себя: «Но те, кому действительно нужен этот алгоритм, не нуждаются в популярном изложении, имхо».Специалисты по ДНК (или по поиску вирусных сигнатур) относятся именно к тем, на кого это статься не ориентирована.
Я не пытаюсь написать статью, которая будет интересна как новичкам, так и «специалистам по глубокому бурению» (имхо, это бесполезно). Как говорил Кузьма Прутков: «И снова повторю — нельзя объять необъятное».
Я не пытаюсь написать статью, которая будет интересна как новичкам, так и «специалистам по глубокому бурению» (имхо, это бесполезно). Как говорил Кузьма Прутков: «И снова повторю — нельзя объять необъятное».
Позволю добавить, КМП примечателен отсутствием сдвига указателя чтения «назад», тем самым позволяя просматривать поток данных.
Префикс-функция, о которой велась речь в статье, выстраивает конечный автомат, по которому движется алгоритм при поиске подстроки. Это позволяет переложить такой алгоритм на ASIC/FPGA и сферу применения — intrusion detection systems, где данных много, да еще и хранить их для дальнейшего анализа не всегда возможно.
Префикс-функция, о которой велась речь в статье, выстраивает конечный автомат, по которому движется алгоритм при поиске подстроки. Это позволяет переложить такой алгоритм на ASIC/FPGA и сферу применения — intrusion detection systems, где данных много, да еще и хранить их для дальнейшего анализа не всегда возможно.
В результате расчет значений массива занимает время порядка О(длина строки).
А где доказательство?
А почему «чудо»? Потому что, он вроде как решает совсем другую задачу и это решение, после некоторого чудесного трюка, превращается в решение задачи поиска всех вхождений образца в строку.
Почему задача, которую он решает, названа "вроде как совсем другой", если это прямое обобщение исходной задачи?
Для нахождения образца ааbаа в строке ааbааbааааbааbаааb склеим образец со строкой вот так ааbаа@ааbааbааааbааbаааb и вызовем для нее префикс-функцию для заполнения массива.
… и сразу же повысим требования по памяти в несколько раз! Дополнительной памяти правильная реализация алгоритма требует O(N), где N — длина образца. Ваш же способ требует O(N+M) дополнительной памяти, где N — длина образца, M — длина текста.
Даже не заню, что Вам ответить: наверное эта статья не для Вас. Раз требования к памяти возрастают в несколько раз, то Ваши образцы в несколько раз больше строки, где они ищутся.
К сожалению, я неправильно понял Ваше замечание, а редактироване заблокировано. Можете дать ссылку, где памяти требуется O(N)?.. Во всех задачах на acmp, timus (где я использовал КМП) проблем ни с памятью ни со скоростью не было. Но все же интересно.
Там, вероятно, и вовсе нет задач где можно так запросто упереться в ограничения, особенно при работе с текстом. Но привычка совершать лишние действия может тяжело аукнуться при попытке решения какого-нибудь "гроба".
Так все-таки есть ссылка на O(N) или нет?
Я, наверное, вас не так понял. Вам ссылку на задачу надо или на алгоритм? Если второе — то вот: https://ideone.com/qmNQ39
Спасибо, завтра поизучаю.
НЛО прилетело и опубликовало эту надпись здесь
Я понял (а точнее, даже вспомнил). В случае, когда надо найти не все вхождения подстроки, а первое вхождение, память нужно выделить для хранения длин префиксов образца. А длины суффиксов строки поиска на запоминаются в массиве. Длина для текущей позиции хранится в переменной и как только она сравнивается с длиной образца (т.е. образец найден), функция прекращает работу и возвращает найденную позицию.
Нет никакой разницы нужно ли найти первое вхождение или же все вхождения. Код, предложенный вам выше, ищет все вхождения (роль @ в нем играет
'\0' на конце образца)Код выводит информацию об нахождении в cout. Получается, что он «заточен» под определенную задачу. С массивом проще — вызывающая прощедура сама решает, что делась с найдеными фрагментами и делает. Хотя можно модифицировать префикс-функцию так, чтобы ее передавала функция, обрабатывающая найденный фрагмент.
Реально мне ни разу не потребовалось экономить на выделении памяти для массива, но не исключаю, что у кого-то есть такая потребность.
Реально мне ни разу не потребовалось экономить на выделении памяти для массива, но не исключаю, что у кого-то есть такая потребность.
Возвращайте вектор позиций вхождения или вы считаете, что функция поиска подстроки должна возвращать в качестве ответа массив вычисленных префикс-функций?
В чем проблема вместо вывода в cout делать что-то еще?
Или вы имеете в виду, что в данной реализации алгоритма не хватает выделения самого алгоритма? Тогда можно сделать вот так: https://ideone.com/zn9Fe4
Или вот так: https://ideone.com/pnafkx
Или еще кучей других способов. Алгоритм от этого не изменится, это лишь оформление.
НЛО прилетело и опубликовало эту надпись здесь
На домашнем компьютере 200+ Гиг в память не затянешь, по-любому придется считывать порциями. Будет порция 20-50-100Мб особой роли не играет. 30 Гиг я читал сам и работал с программами воосстановления файлов на разделах под терабайт. Они тоже читают порциями, правда неясно, какой алгоритм используют.
Ну а если встретится задачка, где будут жесткие ограничения по памяти и скорости — так я добавил в статью процедуру prefix_find, которой нужен буфер только под образец.
Ну а если встретится задачка, где будут жесткие ограничения по памяти и скорости — так я добавил в статью процедуру prefix_find, которой нужен буфер только под образец.
В результате расчет значений массива занимает время порядка О(длина строки).
В худшем случае это S = sum(ln k, 1, n) и это не линейное время так как предел lim S/n видимо бесконечный.
А почему тогда не алгоритм Бойера-Мура, который настолько же сложно объясняется, но часто работает быстрее в несколько раз? (до N раз быстрее, где N — длина образца — хотя иногда, надо признать, может работать и медленнее, чем КМП — худшая оценка у него выше)
(Если первый символ в КМП не совпадает, мы всегда смещаемся на единицу, если последний символ в БМ не совпадает, и этого символа нет в образце — мы смещаемся сразу на длину образца! И даже если есть одинаковые символы, мы почти всегда смещаемся больше, чем на единицу).
(Если первый символ в КМП не совпадает, мы всегда смещаемся на единицу, если последний символ в БМ не совпадает, и этого символа нет в образце — мы смещаемся сразу на длину образца! И даже если есть одинаковые символы, мы почти всегда смещаемся больше, чем на единицу).
Написал бы про Байера-Мура — обязательно кто-то спросил бы «прочему не КМП — он ведь такой-разтакой»? Я захотел написать про КМП и написал. Вам нравится Баейр- Мур — так напишите! Зачем противопоставлять одно другому? Чем больше интересных/полезных статей — тем лучше.
Ок. Но я был бы признателен, если бы вы хотя бы упомянули его в вашей статье рядом с алгоритмом Ахо-Карасик.
Ну, если только упомянуть — так я внес дополнение. Вы удовлетворены? Все же это статья про алгоритм КМП, а не монография про различные методы эффективного поиска.
Спасибо большое. Я просто считаю, что всегда, описывая определённое решение, нужно указать область применимости, недостатки алгоритма и альтернативные решения.
Кстати, теперь я понимаю, почему вы не любите алгоритм Бойера-Мура — вы не считаете, что он существенно быстрее в большинстве случаев :) А, между тем, в grep используется именно Бойер-Мур, и именно из-за его более высокой скорости.
Объяснение ваше в посте про БМ некорректное. БМ тем медленнее, чем больше частичных совпадений между концом образца и текстом, а не внутри образца. Но его можно улучшить, чтобы этого замедления не было, и тогда худшая оценка будет совпадать к КМП. Получится как с быстрой сортировкой против сортировки вставками.
Поскольку редко кто в 2016м году подобные алгоритмы программирует сам вручную, я бы не рекомендовал на практике КМП, а рекомендовал БМ или Ахо-Карасика.
А для знакомства с алгоритмами рекомендовал бы Кормана вместо Хабрахабра :)
Кстати, теперь я понимаю, почему вы не любите алгоритм Бойера-Мура — вы не считаете, что он существенно быстрее в большинстве случаев :) А, между тем, в grep используется именно Бойер-Мур, и именно из-за его более высокой скорости.
Объяснение ваше в посте про БМ некорректное. БМ тем медленнее, чем больше частичных совпадений между концом образца и текстом, а не внутри образца. Но его можно улучшить, чтобы этого замедления не было, и тогда худшая оценка будет совпадать к КМП. Получится как с быстрой сортировкой против сортировки вставками.
Поскольку редко кто в 2016м году подобные алгоритмы программирует сам вручную, я бы не рекомендовал на практике КМП, а рекомендовал БМ или Ахо-Карасика.
А для знакомства с алгоритмами рекомендовал бы Кормана вместо Хабрахабра :)
Кхм, вообще-то алгоритм Ахо-Карасика решает другую задачу, его с КМП и БМ сравнимать некорректно.
Правильно, алгоритм Ахо-Корасика решает расширенную задачу, когда шаблонов много, но вы же сами ниже говорите про то, как легко КМП расширяется на несколько шаблонов. Вот вместо этого лучше как раз взять готовый алгоритм Ахо-Корасика, и заодно немного сэкономить на группировке шаблонов в готовый trie.
Вообще-то, алгоритм Ахо-Корасика — это и есть КМП, расширенный на насколько образцов :)
Хм, покажите, где я утверждаю обратное :)
но вы же сами ниже говорите про то, как легко КМП расширяется на несколько шаблонов. Вот вместо этого лучше как раз взять готовый алгоритм Ахо-Корасика
Нельзя взять алгоритм Ахо-Корасика вместо раширенного на несколько образцов КМП — потому что это один и тот же алгоритм.
Я пользовалсся Бойер-Муром, но при решении одной из задач все время выскакивал TL. В обсуждениях я прочитал, что надо использовать КМП (в строке поиска и в образце были часто повторяющиеся фрагменты и Б-М не мог быстро «скакать», как я понял из обсуждения). Почитал про КМП, запрограммировал и задача прошла «на ура», а сам КМП запал в душу. Это было давненько, с тех пор я стал использовать его и больше никогда TL не встречался (по причине медленного поиска). Наверное потому, что олимпиадные задачи не требуют чего-то более серьезного.
Потому что, как я уже писал ранее, использовать БМ без турбосдвига нельзя.
Для олимпиадных целей (цель — написать как можно проще, лишь бы попадало в требуемую асимптотику) самый простой алгоритм — это поиск с помощью хеш-функции. Особенно когда нам нужно найти только первое вхождение, тогда нам не обязательно верить, что если хеш-функции двух строк равны, то эти строки совпадают.
КМП проще хеш-функции
С использованием хешей не самый простой, и не самый быстрый, особенно при поиске одного шаблона. Вот когда шаблонов много — тогда стоит подумать об алгоритме Рабина-Карпа, например.
Да, я именно про Рабина-Карпа и говорил (забыл, что у него есть устоявшееся название). А почему не самый простой то? По объему кода сопоставим с КМП, зато идея, лежащая в его основе, гораздо проще. И при этом довольный мощный: обобщается для двумерного случая (найти за O(n*m) все вхождения заданного шаблона прямоугольника в квадратной матрице n*m), для случая множества шаблонов.
Я вам что-то сначала поверил, а теперь осознал, что не понимаю, как он обобщается на случай множества шаблонов нефиксированной длины.
Понятное дело, для олимпиад специально придумают контрпримеры, чтобы использовать алгоритм O(MN) вместо O(M+N) было нельзя. Наиболее простой контрпример — шаблон и строка из одинаковых букв («ааааа» и «аааааааааааааааа»). Нужна модификация БМ с турбосдвигом, которая работает за 2*N в худшем случае, хотя, конечно, она сложнее.
Но подумайте вот о чём. Олимпиады — это лишь тренировка навыков скоростного программирования, а не практика написания программных продуктов.
Для написания реальных программных продуктов нельзя использовать те же самые критерии, что и для олимпиад.
Поэтому лучше брать готовые алгоритмы, упакованные в библиотеки. Конечно, крайне желательно понимать, как они работают, чтобы знать их ограничения. Спасибо вам за хорошо иллюстрированный пост, я уверен, он поможет многим разобраться, что происходит. Но лучше думайте о промышленных программистах, которые будут использовать ваш пост, как руководство к действию — а нам всем потом именно их программами придётся пользоваться…
Но подумайте вот о чём. Олимпиады — это лишь тренировка навыков скоростного программирования, а не практика написания программных продуктов.
Для написания реальных программных продуктов нельзя использовать те же самые критерии, что и для олимпиад.
Поэтому лучше брать готовые алгоритмы, упакованные в библиотеки. Конечно, крайне желательно понимать, как они работают, чтобы знать их ограничения. Спасибо вам за хорошо иллюстрированный пост, я уверен, он поможет многим разобраться, что происходит. Но лучше думайте о промышленных программистах, которые будут использовать ваш пост, как руководство к действию — а нам всем потом именно их программами придётся пользоваться…
Насчет grep не знаю, а вот что используют программы типа WinHex, работающие с разделами, восстановлением файлов, когда надо прокачать десятки (а то и сотни) гигабайт данных — интересно.
Зато КМП легко расширяется для нескольких образцов — а алгоритм Бойера-Мура нет.
Да и сложность в худшем случае может сыграть злую шутку, поэтому без эвристики турбосдвига алгоритм Бойера-Мура лучше не использовать. А с этой эвристикой алгоритм становится намного сложнее КМП.
Почему в примере на С++ тип переменной длины и индексов size_t, а в примере на С — int?
А объясните неучу как формируется массив длин префиксов?
В статье про это есть, правда без доказательств и оценки асимптотики. Если очень вкратце, то пусть
1) Все (не только самый длинный) собственные префиксы, являющиеся также и суффиксами, строки
2) Рассмотрим строку
3) Из этих двух соображений возникает алгоритм нахождения
Примеры есть в статье, доказательство асимптотики в этом комментарии выше.
l(S) — это префикс-функция строки S (для удобства восприятия будет считать значением функции саму строку, а не её длину, т.е. l(ababa)=aba). Тогда:1) Все (не только самый длинный) собственные префиксы, являющиеся также и суффиксами, строки
S — это множество l(S), l(l(S)), l(l(l(S)))… (до тех пор, пока не получим пустую строку. Будем считать, что она также является подходящим префиксо-суффиксом).2) Рассмотрим строку
Sc (дописали в конец строки символ c). Пусть l(Sc)=Ac (т.к. префикс-функция является суффиксом строки, то если только это не пустая строка, то она обязана заканчиваться на с. А может быть пустой строкой). Тогда нетрудно понять, что A является префиксо-суффиксом (каким-то, не факт, что самым длинным) строки S.3) Из этих двух соображений возникает алгоритм нахождения
l(Sc). Будем последовательно перебирать все префиксо-суффиксы строки S, начиная с самого наибольшего (т.е. просто будем идти по ряду l(S), l(l(S)), l(l(l(S)))...) и проверять не будет ли это также префиксо-суффиксом для строки Sc (для этого необходимо и достаточно, чтобы символ, следующий за концом соответствующего префикса, был с).Примеры есть в статье, доказательство асимптотики в этом комментарии выше.
Случайно нет ли опечатки в «M[8]+1=5 b»?
Напишите, как изменить размер шрифта для одного абзаца.
Или как изменить шрифт внутри < source > Спасибо.
Или как изменить шрифт внутри < source > Спасибо.
Хотел дополнить статью таблицами, объясняющими КМП «на пальцах», но раз с ходу минусуют, значит не надо.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)