[алгоритмы] поиск wildcard-ов, которые соответствуют строке
маски являются классическими регулярными выражениями, значит алгоритмически можно построить один большой автомат (НКА с указателем на регулярное выражение, которому соответствует тот или иной исход. Далее перевести NFA-DFA, так мы реализуем проверку регулярного выражения.
Из более простого - да, отсортировать паттерны и ограничить перебор.
Из более простого - да, отсортировать паттерны и ограничить перебор.
А где об этом почитать, посмотреть реализации?
Можно кстати их и настоящими регулярками заменить, если юзвери осилят.
про реализацию регекспов?
вот например:
http://swtch.com/~rsc/regexp/
вот с картинками про преобразование НКА в ДКА: http://web.cecs.pdx.edu/~harry/compilers/slides/LexicalPart3...
вот еще примеры реализаций:
http://github.com/openresty/sregex
http://github.com/dhruvbird/regexp-js
вот например:
http://swtch.com/~rsc/regexp/
вот с картинками про преобразование НКА в ДКА: http://web.cecs.pdx.edu/~harry/compilers/slides/LexicalPart3...
вот еще примеры реализаций:
http://github.com/openresty/sregex
http://github.com/dhruvbird/regexp-js
А че перл уже не модно?
мм
что perl?
да, там есть такая тема как Assemble, но он не поможет в случае нескольких совпадений
если было бы достаточно одного, можно было бы решить задачу на уровне преобразований регекспов.
что perl?
да, там есть такая тема как Assemble, но он не поможет в случае нескольких совпадений
если было бы достаточно одного, можно было бы решить задачу на уровне преобразований регекспов.
Не, я про то, что ты написал. Библиотека для регулярок меня вполне устраивает java.util.regex.
Может я задачу неправильно понял, но почему нельзя просто обойтись match'ем в цикле по списку wildcard'ов?
Я имею в виду, что я в этом (НКА/ДКА) ни в зуб ногой. С чего начать курить?
можно почитать википедию или аналоги
суть идеи:
регулярному выражению (в котором есть *, ? и альтернатива (a|b соответствует НКА (недетерминированный автомат по нему можно построить ДКА (детерминированный автомат).
Детерминированный автомат принимает на вход строку и однозначно сообщает, соответствует ли строка выбранному РВ или нет, за линейное время. Соответственно, задача решается за линейное время, но один раз нужно построить специальный автомат (который имеет несколько альтернатив и знает в конце, соответствие каким шаблонам было найдено).
вот определения:
НКА http://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D0%B4...
ДКА http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%82...
алгоритм http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D1%81...,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A2%D0%BE%D0%BC%D0%BF%D1%81%D0%BE%D0%BD%D0%B0
Для явы кстати тоже есть реализация РВ: http://matt.might.net/articles/implementation-of-nfas-and-re..., можно допилить ее
суть идеи:
регулярному выражению (в котором есть *, ? и альтернатива (a|b соответствует НКА (недетерминированный автомат по нему можно построить ДКА (детерминированный автомат).
Детерминированный автомат принимает на вход строку и однозначно сообщает, соответствует ли строка выбранному РВ или нет, за линейное время. Соответственно, задача решается за линейное время, но один раз нужно построить специальный автомат (который имеет несколько альтернатив и знает в конце, соответствие каким шаблонам было найдено).
вот определения:
НКА http://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D0%B4...
ДКА http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%82...
алгоритм http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D1%81...,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A2%D0%BE%D0%BC%D0%BF%D1%81%D0%BE%D0%BD%D0%B0
Для явы кстати тоже есть реализация РВ: http://matt.might.net/articles/implementation-of-nfas-and-re..., можно допилить ее
мне кажется, что это в общем случае не будет гарантировано алгоритмически быстрее, чем просто матчить со всеми. если все регулярки "разные", то то на то и выйдет, не?
ЗЫ можно еще на ragel посмотреть - это, конечно, кодогенератор, зато оч удобный для таких целей - на крайняк можно и код сгенеренный посмотреть (в яву он, вроде, умеет)
ЗЫ можно еще на ragel посмотреть - это, конечно, кодогенератор, зато оч удобный для таких целей - на крайняк можно и код сгенеренный посмотреть (в яву он, вроде, умеет)
время матчинга зависит от длины входной строки, не от сложности автомата, а сложность построения автомата уже зависит от длины регекспов.
если, например, список РВ часто меняется и нужно перестраивать общий автомат, тут уже надо соотнести время проверки с временем перестроения, может и проще будет ходить по списку.
если, например, список РВ часто меняется и нужно перестраивать общий автомат, тут уже надо соотнести время проверки с временем перестроения, может и проще будет ходить по списку.
ну так хождение по списку же и так линейно от длины строки, т.ч. не факт что выигрыш будет - я это имел в виду
ЗЫ еще вспомнил про рагель - он умеет картинки рисовать наглядные - их смотреть удобнее чем код и можно прикинуть что и как будет
ЗЫ еще вспомнил про рагель - он умеет картинки рисовать наглядные - их смотреть удобнее чем код и можно прикинуть что и как будет
Наверняка же есть библиотеки, которые делают, что я хочу.
Пока нашёл вот такую штуку: http://httpd.apache.org/docs/current/mod/mod_rewrite.html но она на C и немного не то.
Пока нашёл вот такую штуку: http://httpd.apache.org/docs/current/mod/mod_rewrite.html но она на C и немного не то.
Это пишется студентом за день, ты его уже потратил на поиск библиотек, сзм
Уж хуже того, s/*/.*/ и склеить через |, куча регулярочных движков строит дка изкаропки
Уж хуже того, s/*/.*/ и склеить через |, куча регулярочных движков строит дка изкаропки
Вроде Trie должно подойти. Только ваилдкарды будут плодить головы по мере обхода
Ну, это мне и самому в голову пришло. Просто я не знал, что оно Trie называется.
UPD: А правильно понимаю, что Trie это частный случай FST?
UPD: А правильно понимаю, что Trie это частный случай FST?
Так напиши тогда. Делов на пару часов с тестированием
Вроде Trie должно подойти. Только ваилдкарды будут плодить головы по мере обходакак ты решил заюзать trie здесь? предположу, что думаешь ты о НКА
ps. ссылка на вики, чтобы мы говорили об одном и том же: http://en.wikipedia.org/wiki/Trie
Да, мы говорим об одном и том же. Нет, я не думаю об НКА, он слишком универсален, чтоб быть оптимальным. Trie тоже наверняка неоптимальна, но сходу выглядит быстрее
сходу выглядит быстрееможешь пояснить, как ты его планируешь использовать для решения задачи ТС?
Могу. Строим Trie. Есть 2 типа рёбер - простой переход и wildcard переход.
Бежим по термам входного слова. Каждый раз держим список голов дерева, куда дошли.
Из каждой головы осуществляем переход по рёбрам и если из неё нет wildcard выходов, то голову удаляем.
На примере ТС,
• нос*
• бе*от
• н*о*г
• ги*ам
будет следующее дерево:
Здесь сложность совпадает с НКА (и да, это также пишется с помощью него, но инструмент явно избыточный для исходной задачи но легко схлопываются тривиальные переходы.
Как-то так
Бежим по термам входного слова. Каждый раз держим список голов дерева, куда дошли.
Из каждой головы осуществляем переход по рёбрам и если из неё нет wildcard выходов, то голову удаляем.
На примере ТС,
• нос*
• бе*от
• н*о*г
• ги*ам
будет следующее дерево:
- н
- oc ->
* o
* г$ ->
- бе
* от$ ->
- ги
* ам$ ->
Здесь сложность совпадает с НКА (и да, это также пишется с помощью него, но инструмент явно избыточный для исходной задачи но легко схлопываются тривиальные переходы.
Как-то так
Есть 2 типа рёбер - простой переход и wildcard переход.ну я так и думал. это не trie, это НКА
1) у тебя циклы в тех вершинах, из которых выходит ребро с надписью * (даже если ты их не стал рисовать, то это видно из твоего алгоритма прохода)
2) для каждого узла ты можешь пойти сразу по нескольким ребрам из этого узла (максимум по двум: с конкретным символом и по *)
trie - это
1) дерево (без циклов, конечно)
2) переход идет только по одному ребру (в вики сказано, что trie можно рассматривать как ДКА)
НКА в процессе работы как раз находится сразу в нескольких узлах, это твой случай
Trie - это структура данных, префиксное дерево, оно не определяет алгоритм работы с ней.
С пунктом 2 согласен, есть отличие. И всё же это не НКА, а его упрщение.
С пунктом 2 согласен, есть отличие. И всё же это не НКА, а его упрщение.
У тебя ключи разной длины в руте.
Оставить комментарий
kill-still
Есть N wildcard-ов. На вход подаётся строка. Надо найти те, к которым подходит эта строка.Например есть:
• нос*
• бе*от
• н*о*г
• ги*ам
Пользователь вводит "носорог", ему в ответ выдаёт
• нос*
• н*о*г
wildcard-ов ~1000, позже может стать больше. Критично время выполнения.
Сразу на ум приходит простой перебор с усечением по началу и концу. Но вот думаю не будет ли быстрее поиск по n-gram-ам, или ещё как нибудь извернуться?