@NeoNs8 янв 2011 в 20:16

Алгоритмы поиска в строке

4 мин

197K

Алгоритмы *

Из песочницы

+46

Комментарии 38

@Brotherofken 8 янв 2011 в 20:40

у Никлауса Вирта в «Алгоритмы и структуры данных» тоже неплохо описано и примеры есть на модуле или паскале.

@Brotherofken 8 янв 2011 в 20:45

А вообще копипаста есть немного…

@NeoNs 8 янв 2011 в 20:49

Частично взято из лекций, переработал, отредактировал, вот что получилось…

@Brotherofken 8 янв 2011 в 21:20

Чего-то всёравно не хватает. Не мне указывать, но я бы добавил блок-схемы, какие-нибудь таблицы со сравнениями результатов работы алгоритмов. Можно сделать лучше. Удачи!

@NeoNs 8 янв 2011 в 21:22

Спасибо за советы, в следующий раз все учту и исправлюсь.

@Dim0FF 8 янв 2011 в 21:50

Ещё не поздно дополнить этот топик.

@Progrik 8 янв 2011 в 22:02

Поддерживаю, с краткими блоксхемами и со сравнением работы алгоритмов будет намного лучше.

@Brotherofken 8 янв 2011 в 23:14

К тому же пытался подвести. :-)

@goodman 8 янв 2011 в 21:56

Еще можно добавить что алгоритм Рабина — Карпа использует для проверки плагиата, так же что он эффективен для многострочного поиска и поиск по множество шаблонам и что нужно делать пре подготовку текста (вырезать все знаки пунктуации). Так же, что можно спокойно использовать свои хэш функции.

@mydoom 8 янв 2011 в 21:56

а Вы, случайно, не проводили тесты данных алгоритмов? недавно по информатике нужно было написать КМП и Рабина-Карпа и сравнить их с наивным алгоритмом (за квадрат), и Рабин-Карп работал в 2-10 раз хуже, чем наивный:) я грешу на медленную операцию % в питоне, но как-то это не очень похоже на правду

@f0b0s 10 мая 2012 в 21:03

Рабин-Карп на коротких образцах (меньше 20 символов) сильно проигрывает (стабильно 40 мб/с при поиске чего угодно где угодно). КМП довольно быстрый (300 мб/с при поиска «Наташа» в Войне и Мир), Бойер-Мур (300-700 мб/с), Хорспул — до 2 гб/с(!), если не синтетические тесты.

@1ex 8 янв 2011 в 22:23

А вы ничего не путаете c оценкой РК?
Я, если честно, не осилил идею РК за вашей алегброй, но предположим N = 1000, M = 10 тогда в худшем случае РК намного менее шустр чем КМП, порядка О(9910) против O(1010), то есть почти в 10 раз медленее в худшем случае, как и заметил mydoom

@ZumZoom 8 янв 2011 в 23:42

Он заметил, что РК работал в 2-10 раз хуже наивного алгоритма, не смотря на то, что асимптотически сложности равны. Читайте внимательно.

@1ex 9 янв 2011 в 00:14

Извините, что читаю невнимательно комментарии, но если сконцентророваться на статье я вижу слова для РК:

В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).

а для КМП:

Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.

и не вижу вообще нигде слов про то что то чему то асимптотически равно.

Отсюда следует вопрос, который я и задал — не напутали ли с оценкой алгоритмов?

Собственно, какова полезность алгоритма. который в худшем случае имеет квадратичную сложность по сравнению с линейной у КМП?

Рабин и Карп с бухты-барахты придумали медленный алгоритм, а преподаватели от нечего делать его преподают, так по вашему что ли?

@Laytlas 8 янв 2011 в 22:57

А где же хеширование???

@Shc 10 янв 2011 в 19:54

РК, имхо, один из частичных случаев хеширования :)

@57DeD 8 янв 2011 в 23:01

Когда я учился, те же алгоритмы объясняли по этой книжке. Мне кажется, там доходчивее…

@stas_agarkov 9 янв 2011 в 01:37

это все интересно, но в современных языках данные алгоритмы встроены

@SkazochNik 9 янв 2011 в 04:30

Это не отменяет необходимости знать их работу и применение.

@stas_agarkov 9 янв 2011 в 12:23

в большинстве практических задач таки отменяет :)

@AlexErofeev 9 янв 2011 в 12:50

Можно поинтересоваться, в каких?

@stas_agarkov 9 янв 2011 в 13:24

методы substring substr contains есть в python, java…

@AlexErofeev 9 янв 2011 в 14:23

    for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j] ==
                         target[k]; j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }

это фрагмент метода indexOf класса String из jre.
Какие из данных алгоритмов, кроме алгоритма прямого поиска, встроены в современных языках программирования?

@stas_agarkov 9 янв 2011 в 14:47

афигеть
а я думал там КМП…
вот это они лоханулись конечно…

@AlexErofeev 9 янв 2011 в 14:54

КМП требует дополнительной памяти для хранения вычисленной префикс-функции образца. Видимо, поэтому он и не вошел в стандартные библиотеки.

@ivanrt 9 янв 2011 в 23:24

КМП — подготовка к поиску занимает какое-то время. Выделение памяти. Как правило поисковые строки короткие с минимумом самоповторений. Линейное сравнение использует SIMD-инструкции. Строки влезают в кэш L1 — повторное сравнение быстрое. Так что на практике КМП выигрывает в специфических условиях.

@stas_agarkov 10 янв 2011 в 00:02

ну функция могла бы выбирать в зависимости от длины стро и т.п. нужный алгоритм
вот memset же использует sse2
а если в процессоре нет sse2 очевидно что memset не упадет :)

@ivanrt 10 янв 2011 в 00:58

В зависимости от архитектуры проще — можно выбрать при запуске программы. В зависимости от длины — замедление потенциально видимое на очень коротких строках.

@wishope 9 янв 2011 в 06:16

Думаю, нужно еще рассмотреть алгоритм Ахо-Корасика и Укконена — там, где применяется бор. В интернете очень сложно найти их хорошее описание с доказательством работы.

@TEHEK 9 янв 2011 в 06:50

В описании алгоритма Кнутта-Морриса-Пратта отстутсвует упоминание о префикс-функции (которая вычисляет, насколько нужно сдвинуть курсор поиска). Контр-пример для вашего описания:

ABABABCABABAB
ABABC

@GMile 9 янв 2011 в 11:17

Пожалуй, имеет смысл упомянуть об http://volnitsky.com/project/str_search/. Автор утверждает, что создал самый быстрый среди существующих алгоритм поиска подстроки в строке.

НЛО прилетело и опубликовало эту надпись здесь

@saymanski 9 янв 2011 в 18:31

blog.phusion.nl/2010/12/06/efficient-substring-searching/

@Astlee 9 янв 2011 в 14:22

Большой список алгоритмов поиска подстроки algolist.ru/search/esearch/index.php

@romanoza 9 янв 2011 в 18:56

<картинка про жпег и пнг />

@Nyarlathotep 10 янв 2011 в 09:52

Есть же метод поиска подстроки в строке при помощи конечного автомата.
Там, безусловно, тратится время и память на построение непосредственно автомата, если мне не изменяет память надо М*М операций (М — длина искомой строки), после чего поиск происходит линейно.
Т.е. общая сложность, если не считать дополнительные расходы по памяти, получается М*М + N.

Вроде регэкспы работают именно так?

Как я помню, это очень выгодный вариант поиска в двух случаях:

1. М << N.
2. Он легко адаптируется к поиску К подстрок в строке N, почти без дополнительных телодвижений (усложняется лишь этап построения автомата).

Поправьте, если я не прав, могу написать подробнее, если кому-то интересно.

Самому пришлось как-то искать порядка 50ти фиксированных и известных заранее подстрок в большом потоке, и именно это решение для меня оказалось оптимальным, т.к. однажды просчитав автомат я его сохранил для дальнейшего использования.

@Rustam 27 янв 2011 в 18:38

еще наверное актуально написать про Z-функцию

НЛО прилетело и опубликовало эту надпись здесь

Зарегистрируйтесь на Хабре, чтобы оставить комментарий