группа strstr'ов

Werdna

Узкое место проги:
char *str -- строка
char **substrs -- массив подстрочек
требуется определить, есть ли какая-либо из подстрочек в данной строке.

 

for (i = 0; substrs[i]; i++)

{

    char *q = (strstr(str, substrs[i];

    if (q)

    {

        // some actions

    }

}

 

Как можно заоптимизировать код? Фактически, хочется получить аналог "группового strstr", но как лучше реализовать -- не знаю.
any ideas?

Ivan8209

Ты точно не пытаешься сделать getsubopt?
Может, есть ещё какие-то ограничения?
Какая используется библиотека? GNU? BSD? Ещё какая?
---
...Я работаю антинаучным аферистом...

Werdna

getsubopt

Нет. У меня задача такая: дан урл, мне надо определить, есть ли в нем "запрещенные" слова. Если есть, то, например, заменить все символы этого подслова на звездочки. Например, так.
То, что я написал -- работает, но не очень-то и быстро.

Ivan8209

Может, написать замену strstr по Бойеру---Муру?
Список слов, надеюсь, не очень часто меняется?
---
...Я работаю антинаучным аферистом...

bleyman

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

Ivan8209

"Нормальный" означает "оптимизирующий"?
Такие есть?
---
...Я работаю антинаучным аферистом...

bleyman

Бойеру---Муру

Я правильно помню, что это такое описание работы НКА в специфическом случае, придуманное в те времена, когда регексов ещё не было?

Ivan8209

Оно ещё и оптимизировано как раз под этот случай.
Почему "НКА," я только не понял.
---
...Я работаю антинаучным аферистом...

bleyman

>> "Нормальный" означает "оптимизирующий"?
Объяснись.
Ты представляешь вообще что такое конечные автоматы?

Ivan8209

И оно не для РВ, а как раз для поиска подстрок.
---
...Я работаю антинаучным аферистом...

bleyman

>> Оно ещё и оптимизировано как раз под этот случай.
Любой конечный автомат проходит строку за линейное время. Что оптимизировать-то?
>> Почему "НКА," я только не понял.
Потому что в данном конкретном случае можно легко получить 2^(количество слов) состояний ДКА. Это, наверное, не очень прикольно.

Ivan8209

Очень хорошо представляю.
БМ, в общем случае, не сравнивает со следующего знака,
неоптимизированный КА такое может делать.
---
...Я работаю антинаучным аферистом...

Ivan8209

Ты понимаешь, что 2n << 2^10 n?
Вот поэтому и надо оптимизировать.
---
...Я работаю антинаучным аферистом...

bleyman

>> БМ, в общем случае, не сравнивает со следующего знака,
А, да, точно. Ты прав.

Ivan8209

>> Почему "НКА," я только не понял.
> Потому что в данном конкретном случае можно легко получить
> 2^(количество слов) состояний ДКА.
> Это, наверное, не очень прикольно.
А можно и не получить.
Если человек захотел скорости, ему где-то придётся
пожертвовать памятью или сложностью.
Если строчки берутся из естественного языка,
число состояний очевидно будет меняться помедленнее.
---
...Я работаю антинаучным аферистом...

bleyman

Ты понимаешь, что 2n << 2^10 n?
Вот поэтому и надо оптимизировать.

Ладно, забей. Хотя мне всё равно интересно, что это ты там написал такое. Если я правильно помню, Б.-М. довольно сложные действия на каждом шаге проделывал, сложнее чем один шаг НКА, зато позволял уменьшить количество шагов до ~n/m (где m - длина искомого слова) (если очень повезёт).
В данном конкретном случае - нахождение нужных слов в урле - регексы являются лучшим возможным решением. В частности ещё и потому, что позволяют без напрягов переходить к более сложным способам задания ключевых слов. Ну и потому, что присоединяются к проекту минут за десять =)

Ivan8209

Так что будем советовать?
Делать многопроходный БМ или однопроходный офигенный КА?
Многопроходный БМ проще.
---
...Я работаю антинаучным аферистом...

bleyman

Многопроходный БМ проще.

регекс проще. И быстрее, чем многопроходный БМ. И программировать его не надо.

Ivan8209

Ты помнишь неправильно.
Лично я считаю КА довольно дорогим удовольствием.
Хотя бы потому, что если слов будет много, непонятно,
что он там скомпилирует, будет ли это всё достаточно оптимально.
---
...Я работаю антинаучным аферистом...

Ivan8209

БМ тоже программировать не надо, он точно так же берётся из Сети.
Я не очень верю в то, что КА быстрее, оптимизирующих РВ я ещё не видел.
---
...Я работаю антинаучным аферистом...

Werdna

Народ, а примерчик на КА можете подкинуть? Чтобы заботать теорию и практику.
Хочу попробовать, результат доложу.

vall

как работает КМП знаешь? (поиск одной строки КА)
берёшь все эти строки что ищешь и склеиваешь их в БОР - дерево в котором на рёбрах буквы, все слова начинаются в корне а дальше расползаются вниз по дереву.
строишь префикс функцию как в КМП для этого дерева.
и в итоге получается КМП на боре.

bleyman

Вот здесь подробнее: http://www.maz.de/parser/1/3.html
А сколько всё-таки получается вершин в ДКА для всего леса?
Кстати, насколько я помню, общий алгоритм преобразования НКА в ДКА всегда выдаёт минимальный ДКА, так что можно не заморачиваться изобретением своего алгоритма для данного конкретного случая, правда?

vall

это я туплю или ты?
вроде очевидно что не больше чем суммарное число букв в искомых строках + 1
на боре просто обратные дуги префикс функции добавляются.

Russula

погугли алгоритм Карасика
это как раз поиск нескольких подстрок в строке за линейное время

tokuchu

БМ тоже программировать не надо, он точно так же берётся из Сети.
Я не очень верю в то, что КА быстрее, оптимизирующих РВ я ещё не видел.

Если надо проверить очень много слов, то после преобразования в КА входные строки будут обрабатываться за линейное время - на каждую букву нужно будет совершать пару простейших операций. А в случае с применением многократного поиска подстроки у нас ещё будет множитель M (число проверяемых слов который может быть гораздо больше той оптимизации, которую нам даст оптимизированный БМ, пропускающий буквы. Кстати, эту оптимизацию, скорее всего, можно применить и к КА.

Maurog

мне кажется Рабин-Карп вполне подойдет
http://www.borland-academy.ru/courses/algorithms2/present/2_...

Werdna

Друзья! Всем спасибо, все оказалось крайне интересно.
Буду ботать, надо что-то писать, но пока не заботал теорию.

rosali

надо что-то писать

Не верю, что имеет смысл писать отсебятину, максимум стоит сгенерить что нибудь на ragel-е или типа того.

Werdna

погугли алгоритм Карасика

Что-то не нашел я никакого Карасика.
А вообще, как Карасик на английском пищется хоть? Fish?

margadon

сдаётся мне, он Karasick

Lina87

Корасик (Korasick и это она.
Нужно гуглить по сочетанию Aho-Korasick.