Статья :
Алгоритмы поиска в тексте

Автор(ы): Андрей Боровский
Дата: 28.01.2002

Авторы :
Андрей Боровский

Блоьшое спасибо за ценную информацию.
Мне как раз нужно поиск в тексте реализовывыть —
вы мне очень помогли.
Редко встретишь в инете толковую статью —
ваша как раз такая. Еще раз спасибо.

В статье неверно (точнее, неоптимально) описан следующий момент. В том случае, если при поиске "неусложненным" методом Бойера-Мура несовпадение встречается не на последнем символе образца, автор предлагает сдвигать образец вправо на 1 позицию, как в этом примере:

a b e c c a c b a d b a b b a d
          a b b a d

Между тем, совершенно очевидно, что т.к. символ c не встречается в образце, то можно сдвинуть образец на две позиции:

a b e c c a c b a d b a b b a d
              a b b a d

Строго говоря, если несовпадение обнаружилось на k-м справа символе образца, его нужно сдвинуть вправо на BMT[c] — k + 1 позиций, где c — символ из строки, не совпавший с символом из образца.

строки в текст.
Как это сделать, креме как тупым поиском?

а кстати... http://alglib.manual.ru/searching/bmh.php

Здравствуйте, PK Sly, Вы писали:

PS>Как это сделать, креме как тупым поиском?
переверни строку и ищи с конца любым алгоритмом

PS>>Как это сделать, креме как тупым поиском?
C>переверни строку и ищи с конца любым алгоритмом

Ну, во-первых, переворачивать не обязательно, можно искать, начиная с конца и заполняя BMT таблицу "обратным" образом.
А во-вторых, описанный алгоритм предназначен для поиска именно сторки целиком, для чего и строится эта таблица. Очень легко представть себе случаи, когда этот алгоритм пропустит подстроку всего лишь на один символ короче.

PS>Ну, во-первых, переворачивать не обязательно, можно искать, начиная с конца и заполняя BMT таблицу "обратным" образом.
PS>А во-вторых, описанный алгоритм предназначен для поиска именно сторки целиком, для чего и строится эта таблица.

PS>Очень легко представть себе случаи, когда этот алгоритм пропустит подстроку всего лишь на один символ короче.

Не вполне понял: предложеный алгоритм неверный? неоптимальный?
Если перевернуть строку и искать с конца будет найдено первое вхождение перевернутой строки в перевернутый текст. Это будет самое последнее вхождение исходной строки строки в исходный текст. Если это неверно, проссьба привести пример.

C>Не вполне понял: предложеный алгоритм неверный? неоптимальный?
C>Если перевернуть строку и искать с конца будет найдено первое вхождение перевернутой строки в перевернутый текст. Это будет самое последнее вхождение исходной строки строки в исходный текст. Если это неверно, проссьба привести пример.

Надо найти не последнее вхождение, а максимальное.
То есть, подстрока максимальной длины, начитая с начала.

Здравствуйте, PK Sly, Вы писали:

PS>Надо найти не последнее вхождение, а максимальное.
PS>То есть, подстрока максимальной длины, начитая с начала.
я неправильно понял условие.
подстрока удовлетворяет какому-либо условию еще? Если можно, с примером.

например, текст такой:

qwerkqwhgvoiuqwertyusdmnbbpcdsuy

подстрока, которую ищем такая:

qwertyuiop

частичные вхождения строки выделены курсивом, а максимальное вхождение — жирным

qwerkqwhgvoiuqwertyusdmnbbpcdsuy

Здравствуйте, PK Sly, Вы писали:


PS>частичные вхождения строки выделены курсивом, а максимальное вхождение — жирным

PS>qwerkqwhgvoiuqwertyusdmnbbpcdsuy

а... максимальное вхождение подстроки исходной строки в текст...

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

Здравствуйте, Alexander Fenster, Вы писали:

AF>В статье неверно (точнее, неоптимально) описан следующий момент....

Так все-таки "неверно" или "неоптимально"? Это ведь принципиально разные понятия.
Я взял простейший вариант БМ, со сдвигом на один символ, такой вариант, кстати,
описан в литературе, как и несколько других, на один из которых Вы сослались. Все это нкжно было чтобы по контрасту показать преимущества более оптимального, усложненного алгоритма, который и описывается дальше.
С уважением,
А. Боровский.

C>а... максимальное вхождение подстроки исходной строки в текст...

не любой подстроки, а только начиная с начала

C>можно построить, например, конечный автомат для поиска искомой строки, потом пройтись этим автоматом по входному тексту и найти самую удаленную от стартовой вершину, в которую автомат попаедет при прохождении по тексту. Этой вершине будет соответствовать путь от начальной, которому будет соответстовать самый длинный префикс строки.

ууууу... дааа.. это называется горе от ума
тупой поиск делается гораздо проще. через memchr и memcmp

Здравствуйте, PK Sly, Вы писали:

PS>не любой подстроки, а только начиная с начала
да, это он и есть. Просто неточно написал
PS>ууууу... дааа.. это называется горе от ума
PS>тупой поиск делается гораздо проще. через memchr и memcmp
Никто не говорил, что будет легко
Этот вариант — более оптимальный, чем memcmp (один раз строим автомат, один раз про ходим по строке, один раз ищем результат). Если важна простота реализации — конечно лучше memcmp %)

C>Никто не говорил, что будет легко
C>Этот вариант — более оптимальный, чем memcmp (один раз строим автомат, один раз про ходим по строке, один раз ищем результат). Если важна простота реализации — конечно лучше memcmp %)

поспорим что memchr + memcmp будет быстрее, чем автомат?

Здравствуйте, PK Sly, Вы писали:

PS>поспорим что memchr + memcmp будет быстрее, чем автомат?
Спорить не буду, потому что не знаю специфики входных данных.
Автомат быстрее, чем memchr + memcmp, на длинных текстах (если memchr + memcmp будут использоваться самым простым методом: перебором всех смещений в тексте по очереди и нахождение длины префикса искомой строки, совпадающего при смещении)

например, если текст это

qweqweqweqwe...[big]...qwerty

а строка — qwerty
то в моем понимании, тупое использование memcmp + memchr будет обрабатывать символы примерно так:

qwe
w
e
qwe
w
e
...
qwerty
w
e
r
t
y

Есил строки для поиска маленькие и их много, то конечно большая часть времени будет уходить на построение автомата
если строка одна и текстов много или текст длинный — автомат быстрее
Если строка по длине сравнима с текстом — вот тут

PS>>поспорим что memchr + memcmp будет быстрее, чем автомат?
C>Спорить не буду, потому что не знаю специфики входных данных.

данные — обычный текст. любой. текстовый
HTML, XML, plain text или что угодно

C>Автомат быстрее, чем memchr + memcmp, на длинных текстах (если memchr + memcmp будут использоваться самым простым методом: перебором всех смещений в тексте по очереди и нахождение длины префикса искомой строки, совпадающего при смещении)

C>например, если текст это
C>

C>qweqweqweqwe...[big]...qwerty

C>а строка — qwerty
C>то в моем понимании, тупое использование memcmp + memchr будет обрабатывать символы примерно так:

C>

C>qwe
C>w
C>e
C>qwe
C>w
C>e
C>...
C>qwerty
C>w
C>e
C>r
C>t
C>y

ладно. а автомат как быдет тействовать?
Будет делать тоже самое, но на каждую букву ещё лезть в таблицу?

C>Есил строки для поиска маленькие и их много, то конечно большая часть времени будет уходить на построение автомата
C>если строка одна и текстов много или текст длинный — автомат быстрее
C>Если строка по длине сравнима с текстом — вот тут

Да хоть маленькие, хоть большие. Не могу для данной задачи придумать, где тут можно использовать автомат.

Здравствуйте, PK Sly, Вы писали:

PS>данные — обычный текст. любой. текстовый
PS>HTML, XML, plain text или что угодно

PS>автомат как быдет тействовать?
PS>Будет делать тоже самое, но на каждую букву ещё лезть в таблицу?
автомат для каждый буквы будет один раз лезть в таблицу (одно обращение к симоблу строки и к таблице) и на основнии символа на входе и текущего состояния, выбирать новое состояние. Таким образом, проход автоматом по любой строке по
времени пропорционально длине строки
Проход по строке с помощью memchr + memcmp так, как он был описан, в некоторых случаях будет по нескольку раз обращаться к одной и той же букве в исходной строке (в том примере — примерно по два раза). Можно сконструировать такие входные тексты, на которых memcmp + memchr будет работать по времени пропорциорционально k * длину строки

непример, строка xxxxxxxxy и тектст
xxxxxxxxxxxxxxxxxxxxxxx...[big]...xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy

C>автомат для каждый буквы будет один раз лезть в таблицу (одно обращение к симоблу строки и к таблице) и на основнии символа на входе и текущего состояния, выбирать новое состояние. Таким образом, проход автоматом по любой строке по
C>времени пропорционально длине строки

если бы одна буква всегда была только в одном вхождении..
а вот как быть автомату с такой строкой:
abcabcabcde и строкой поиска abcde
выделенная буква входит в две подпоследовательности: одна начинается с нулевой позиции, другая — с третьей.

похоже, что одним проходом тут не обойтись.

да и ещё вопрос, как автоматически и за разумное время сгенерить автомат. как бы не оказалось, что это время будет сравнимо с временем поиска

Здравствуйте, PK Sly, Вы писали:

PS>если бы одна буква всегда была только в одном вхождении..
PS>а вот как быть автомату с такой строкой:
PS>abcabcabcde и строкой поиска abcde
PS>выделенная буква входит в две подпоследовательности: одна начинается с нулевой позиции, другая — с третьей.
PS>похоже, что одним проходом тут не обойтись.

можно обойтись. Всегда. Главное построить автомат.
Для этого примера функция переходов будет такой

p(0,a) = 1
p(1,b) = 2
p(2,c) = 3
p(3,d) = 4
p(4,e) = 5

начальное состояние — 0
все остальные переходы — в начальное состояние (т.е. p(2,a) -> 0, p(5,z) -> 0 и т. п.)
пробег автомата по приведенной в примере строке

abcabcabcde
012012012345

Это тривиальный пример. Функция переходов может быть не столь простой, если строка имеет повторяющуюся структуру (например, abcabc). Но скорость прохода по строке в результате не изменится.

PS>да и ещё вопрос, как автоматически и за разумное время сгенерить автомат. как бы не оказалось, что это время
будет сравнимо с временем поиска

про то, как строится автомат, написано, например, в книге "Алгоритмы: простоение и анализ"
там также, говорится, что для строки длины m автомат можно прострить за O(m*E), где E — количество символов в алфавите (в нашем случае — 256), а m — длина образца, и приводится тупой алгоритм, работающий за O(m^3*E), что для небольших строк тоже приемлемо..