tltshnik Nov 8 2011 at 18:01

Описание работы алгоритма Shift-OR для поиска подстроки в строке

3 min

8.1K

Algorithms*

From sandbox

+42

Comments 16

alexxz Nov 8 2011 at 18:32

Правильно ли я понимаю, что этот алгоритм ничем не лучше наивного сравнения? Если так, то для чего он нужен?

alexxz Nov 8 2011 at 18:35

Пардон, не сразу понял, что речь идёт про нечёткий поиск.

lightcaster Nov 8 2011 at 20:02

На сколько я знаю, есть два варианта алгоритма — один для четкого, другой для нечеткого поиска.

На практике работает довольно быстро. Выигрыш достигается за счет побитовых операций.

aisek Nov 9 2011 at 10:22

Что-то не совсем понятно, в чем преимущество перед префикс-функцией. Ну разве что для паттернов короче 64 символов может быть будет чуть быстрее.

susl Nov 9 2011 at 05:45

Он достаточно быстр, если искомое слово влазит в машинное слово (простите за каламбур), работаем с маленьким алфавитом (ASCII, например) и имеем большой текст в котором нужно искать.

lightcaster Nov 8 2011 at 20:03

Спасибо, хорошая статья.

agorkov Nov 8 2011 at 20:22

Не совсем понятно, как находить частичные совпадения, если Вы предлагаете хранить только два столбца. Разве при этом информация не теряется?

tltshnik Nov 9 2011 at 21:54

Не совсем понял вопроса. Например, на этой картинке:

если у нас есть только 8 столбец, то по нему мы можем определить, что на данном символе (8 в T) заканчивается совпадение первых 4 символов из P (т.к. в 4 строке стоит единица). То есть у нас совпали предыдущие 4 символа.

Или я не правильно понял, что Вы имеете ввиду?

eZyatev Nov 8 2011 at 21:00

Ув. tltshnik, ссылки на источники информации в завершающей части статьи оформляйте аккуратнее. Сайт поисковой системы, на который Вы указываете, — слишком всеобъемлющий источник.

bolk Nov 8 2011 at 21:53

Ваша ссылка вообще никуда не ведёт.

maovrn Nov 8 2011 at 22:31

Список используемой литературы:
— Библиотека им. Ленина

Удобно для дипломников. Наверняка что-нибудь найдется.

tltshnik Nov 9 2011 at 21:44

Обязательно учту при написании других постов.

YourChief Nov 9 2011 at 15:11

похоже на репост учебника по СиАОДу третьего курса. раз автор не удосужился, я накидаю ссылок: Виктор Дмитриевич Колдаев «Алгоритмы и структуры данных». я у него учился, да. алсо, автор забыл указать что для частных случаев функция сложности этого алгоритма квадратичная, поэтому его оценка сложности неверная. вычислять эти сдвиги побитово очень плохо, да и вообще есть гораздо более простой алгоритм, где просто так же передвигаем окно с шагом в 1 байт и добавляем к контрольной сумме байт, входящий в окно и вычитаем байт, покидающий окно и на каждом шаге просто сравнимаем контрольную сумму окна и образца.

YourChief Nov 9 2011 at 15:14

кому интересно — в книжке выше есть так же алгоритм кнута-морриса-пратта и другие алгоритмы поиска с гарантированным временем O(n). правда насчёт редакции книжки подсказать не могу, но наверняка в последней всё есть

YourChief Nov 9 2011 at 15:18

насчёт функции сложности прошу прощения — всё верно указано

tltshnik Nov 9 2011 at 21:43

На самом деле, бо́льшую часть информации я брал из книги, которая стоит первой в ссылках. Но изложил тему, как мне кажется, в менее формализованном виде. А про учебник, о котором Вы сказали, я слышу в первый раз.