Беда такая, необходимо подробное описание алгоритмов поиска совпадений в строке. Посмотрел у Кнута, но у него описываются алгоритмы единичного поиска, в то время как мне надо оптимизировать поиск многих альтернатив. Сейчас смотрю, что есть у Ахо и Хопкрофта, но возможно кто-то уже сталкивался и знает необходимые документы. Здесь на форуме видел пару топиков, но указания на литературу и вних нет. Ниже я привожу кусочек своего черновика, если кто видел, где есть подробное описание, и особенно ОЦЕНКА подобных вещей с указанием граблей, пожалуйста, пожалейте моё время, подскажите. По возможности с указанием страниц или глав, а то просматривать сотни страниц тоже удовольствие сомнительное. 524372841__attach.txt
брр. аттач не смотрел, но тебе нужен алгоритм Бойера-Мура. Погугли, что ли Upd: ааа, сорри. неправильно тебя понял. но все равно алгоритм БМ весьма легко дорабатывается до того, что тебе нужно.
Да, похоже на правду. Правда опять же, подход для одного вхождения, а мне бы алгоритм вычисления множества символов для поиска некоторого множесва строк с учетом длин искомых строк и частот появления символов в строке, в которой ищем. Но за это тоже спасибо, буду углубляться.
Посмотрел у Кнута, но у него описываются алгоритмы единичного поиска, в то время как мне надо оптимизировать поиск многих альтернатив. Я не очень понял формулировку. Т.е. тебе надо прогнать много паттернов против какого-то блока текста?
>>Я не очень понял формулировку. Т.е. тебе надо прогнать много паттернов против какого-то блока текста? Типа того, но не по одиночке на блок, а первое(или все) совпадение любого из вариантов. Regex движок хочу, соптимизированный до безобразия. Там из аттача понятно. А за ссылки спасибо, сердечко надеюсь вывезло P.S. хорошая книжечка. Вникаю.
В общем случае regex движок тебе круче того, что сделано в pcre и движке перла, соптимизировать удасться вряд ли Однако мне попадалась на глаза статейка (правда, там только зубодробительные мат. выкладки), что можно построить regex на галстуке Патриции Патриция - patricia trie. Описана у Сэджвика, да и у Кнута тоже. Может быть, перепишу свою вторую часть упаковщиков и добавлю туда примерчик на патрицию...
>>В общем случае regex движок тебе круче того, что сделано в pcre и движке перла, соптимизировать удасться вряд ли Это как посмотреть. Во первых асм, во вторых "а попробовать?"
