Comments 44
Один вопрос: А почему бы вам сразу не производить поиск по хэш-таблице/бинарному дереву (то есть брать каждое слово в тексте, и искать в этой таблице/дереву)?
То что вы говорите думаю будет работать медленнее.
Отличия:
1. хеш таблицу/дерево нельзя вставить внутрь регулярного выражения. например написать паттерн "$город в$стране"
2. в случае бинарного дерева, практически всегда количество проверок будет log2(N), а мы можем остановится на первом символе(чаще так и будет)
3. в случае бинарного дерева каждое сравнение делается с нуля, тут же один раз, т.е. аля динамическое программирование
4. хеш таблица требует вычисления по всем символам проверяемой строки, а мы можем остановится на первом символе
5. если границы слова неопределенные, совершенно непонятно как использовать хеш таблицу. в данном же случае можно использовать такие символы как .*+ и таким образом делать оптимизацию не только строк но и регулярных выражений
Отличия:
1. хеш таблицу/дерево нельзя вставить внутрь регулярного выражения. например написать паттерн "$город в$стране"
2. в случае бинарного дерева, практически всегда количество проверок будет log2(N), а мы можем остановится на первом символе(чаще так и будет)
3. в случае бинарного дерева каждое сравнение делается с нуля, тут же один раз, т.е. аля динамическое программирование
4. хеш таблица требует вычисления по всем символам проверяемой строки, а мы можем остановится на первом символе
5. если границы слова неопределенные, совершенно непонятно как использовать хеш таблицу. в данном же случае можно использовать такие символы как .*+ и таким образом делать оптимизацию не только строк но и регулярных выражений
Эмм… а чем тогда автомат не нравится?
Хм, так это и есть минимизация автомат.
А, похоже я понял к чему вы. Т.е. изначальная задача стоит так: Есть набор слов. Необходимо определить, есть ли набор этих слов (или регэксп) в словаре.
В этом смысле вашу идею понял, интересно. Но думаю, здесь получится некоторое дублирование работы. В момент разбора регулярки словарь построит из нее то же дерево/авомат.
В этом смысле вашу идею понял, интересно. Но думаю, здесь получится некоторое дублирование работы. В момент разбора регулярки словарь построит из нее то же дерево/авомат.
Да, именно. Но насчет разбора это не совсем так. Парсер из строки в регулярное выражение ничего из вышеописанного не сделает — он не оптимизирует, он просто строит автомат как есть. Я же подготавливаю для него строку которая описывает более быстрый автомат.
Может быть. Тогда, возможно, вам лучше просто построить минимальный DFA.
А это вроде как и есть DFA полученный из NFA. Понятие «Префиксная оптимизация» я придумал, возможно статью стоило назвать получение DFA в частном случае.
У вас детерминированный автомат. Но не минимальный. Вы оптимизируете только префикс.
Сравните для слов word, ward. Ваше дерево будет содержать 8 узлов и 7 ребер (две ветви), в то время как минимальный DFA 5 и 5 (между вторым и третьим состоянием две дуги).
Сравните для слов word, ward. Ваше дерево будет содержать 8 узлов и 7 ребер (две ветви), в то время как минимальный DFA 5 и 5 (между вторым и третьим состоянием две дуги).
Нет, у Вас не DFA. На каждый символ входного (тестируемого) потока длины N у вас будет тратиться не O(N) операций. Точнее, всё зависит от движка регулярных выражений, но саму вашу форму DFA назвать нельзя.
Замечу также, что DFA регулярного выражения, которое не привязано к началу строки (нет символа ^) и которое содержит много условий «или» (символов |) будет очень большим. Это к комментарию выше.
Что же касается вашей оптимизации — она очень хороша для уменьшения сложности именно NFA-анализа. Сделаю предположение (не уверен, надо думать), что обычные алгоритмы получения минимального DFA сделают ваше оптимизацию ненужной (избыточность выкинется сама).
Замечу также, что DFA регулярного выражения, которое не привязано к началу строки (нет символа ^) и которое содержит много условий «или» (символов |) будет очень большим. Это к комментарию выше.
Что же касается вашей оптимизации — она очень хороша для уменьшения сложности именно NFA-анализа. Сделаю предположение (не уверен, надо думать), что обычные алгоритмы получения минимального DFA сделают ваше оптимизацию ненужной (избыточность выкинется сама).
По моему все же ДНА. Определение ДНА на каждом шаге существует только один возможный переход — детерминированность. В случае Trie существует только один путь по дереву для любой строки или он отсутствует вообще. Т.е. это DFA. И затраты на каждый символ будут равны ветвистости дерева.
В случае
Раньше отправилось, извините.
Когда вы обнаружите несоответствие шаблону на каком-то символе, вы должны будете откатить входной поток назад. Например, пусть есть паттерн /abc/. Начинаем анализ строки abdabc. На символе d вы обнаруживаете несоответствие. Но вы не можете дальше продолжить анализ строки, вы должны вернуться назад и провести тестирование начиная от символа b. Таким образом, символы 2 и 3 (b и d) будут оттестированы дважды. Это как раз НЕ O(N).
Всё то, что вы говорите, работает только при привязке паттерна к началу тестируемой строки (т. е. /^abc/, а не /abc/).
Ахо-Корасик (ниже вы давали ссылку) решает эту проблему — насколько я помню, как раз за счёт DFA (детерминированного конечного автомата).
Когда вы обнаружите несоответствие шаблону на каком-то символе, вы должны будете откатить входной поток назад. Например, пусть есть паттерн /abc/. Начинаем анализ строки abdabc. На символе d вы обнаруживаете несоответствие. Но вы не можете дальше продолжить анализ строки, вы должны вернуться назад и провести тестирование начиная от символа b. Таким образом, символы 2 и 3 (b и d) будут оттестированы дважды. Это как раз НЕ O(N).
Всё то, что вы говорите, работает только при привязке паттерна к началу тестируемой строки (т. е. /^abc/, а не /abc/).
Ахо-Корасик (ниже вы давали ссылку) решает эту проблему — насколько я помню, как раз за счёт DFA (детерминированного конечного автомата).
В Вашем примере "(?:ad(?:asddsa|sasd)|jav(?:ajava|ggaaa|vva))" проблема будет при анализе соответствия подстроке asddsa, sasd и так далее.
В Trie откатов не происходит(мы не ищем строку а проверяем на соответствие т.е. патерн ^...$). Мой пример превращается в такое дерево.
ad
--asddsa
--sasd
jav
--ajava
--ggaaa
--vva
При обработке строки asddsa. Мы проверим первый символ первого патерна(второй не подходит так как начинается на j), второй символ на этом патерн перестанет работать т.е. как альтернатив нет. и будет всего 2 проверки символов.
Т.е. в такой оптимизации никаких откатов нет так же как и альтернатив.
ad
--asddsa
--sasd
jav
--ajava
--ggaaa
--vva
При обработке строки asddsa. Мы проверим первый символ первого патерна(второй не подходит так как начинается на j), второй символ на этом патерн перестанет работать т.е. как альтернатив нет. и будет всего 2 проверки символов.
Т.е. в такой оптимизации никаких откатов нет так же как и альтернатив.
Значит, мы просто не поняли друг друга :) Извините, я Ваш код не смотрел внимательно.
Но во вступлении написано «надо найти в тексте все эти фразы». Ну и дальше Вы приводите выражение (city1|city2|city3|...cityN), а не (^(city1|city2|city3|...cityN)$).
Ну и в примерах тоже привязки к началу строки не видно. Хотя, может быть, это синтаксис, и тут, наоборот, нужно дописывать (.*) в начало строки, чтобы «отвязаться» от начала?
Но во вступлении написано «надо найти в тексте все эти фразы». Ну и дальше Вы приводите выражение (city1|city2|city3|...cityN), а не (^(city1|city2|city3|...cityN)$).
Ну и в примерах тоже привязки к началу строки не видно. Хотя, может быть, это синтаксис, и тут, наоборот, нужно дописывать (.*) в начало строки, чтобы «отвязаться» от начала?
А да согласен, все что говорю относится к привязке к началу. Но и DFA будет не O(N) если мы делаем сдвиг на символ и матчим снова… Правда как правило все двигаются по границам токенов что существенно оптимизирует процесс.
если я все правильно понял:
1. добавление новой строки, вроде как, имеет сложность не меньше чем C*N, где N — размер слова, что в любом медленнее чем добавление в сбалансированное дерево (logN).
2. количество проверок для бинарного дерева logN, это точно, но ведь у вас же тоже строки должны сравниваться тем же regexp'ом на равенство. Это ведь будет не меньше чем N.
имхо дерево будет таки быстрее. но подход интересный.
1. добавление новой строки, вроде как, имеет сложность не меньше чем C*N, где N — размер слова, что в любом медленнее чем добавление в сбалансированное дерево (logN).
2. количество проверок для бинарного дерева logN, это точно, но ведь у вас же тоже строки должны сравниваться тем же regexp'ом на равенство. Это ведь будет не меньше чем N.
имхо дерево будет таки быстрее. но подход интересный.
RE 1. добавление новой строки, вроде как, имеет сложность не меньше чем C*N, где N — размер слова, что в любом медленнее чем добавление в сбалансированное дерево (logN).
Скорость генерация регулярного выражения не имеет значения, так как происходит один раз для словаря, это как время компиляции. В случае же бинарного дерева, имеет значение, так как производится каждый раз при сравнении слова с паттерном.
RE 2. количество проверок для бинарного дерева logN, это точно, но ведь у вас же тоже строки должны сравниваться тем же regexp'ом на равенство. Это ведь будет не меньше чем N.
Каждая проверка в моем случае это сравнении одного символа, в случае бинарного дерева это сравнения целых строк. Сравнений может быть меньше чем N, например если первый символ не подходит для словаря то произойдет всего одна символьная проверка, в дереве же logN строковых сравнений- что значительно более трудоемко.
Скорость генерация регулярного выражения не имеет значения, так как происходит один раз для словаря, это как время компиляции. В случае же бинарного дерева, имеет значение, так как производится каждый раз при сравнении слова с паттерном.
RE 2. количество проверок для бинарного дерева logN, это точно, но ведь у вас же тоже строки должны сравниваться тем же regexp'ом на равенство. Это ведь будет не меньше чем N.
Каждая проверка в моем случае это сравнении одного символа, в случае бинарного дерева это сравнения целых строк. Сравнений может быть меньше чем N, например если первый символ не подходит для словаря то произойдет всего одна символьная проверка, в дереве же logN строковых сравнений- что значительно более трудоемко.
1. А не надо зацикливаться на регулярках :) часто нужное реализуется более простыми вещами, и более быстрыми.
2. А с чего вы взяли что бинарное дерево? Обычно дерево таки той ветвистости, какой словарь символов. При этом регулярка будет в разы медленнее матчить.
3. опять же с чего взяли что бинарное?
4. смотря как реализован хеш
5. тоже самое относится к «матчу» по деревьям и хешам, зависит от реалиации.
2. А с чего вы взяли что бинарное дерево? Обычно дерево таки той ветвистости, какой словарь символов. При этом регулярка будет в разы медленнее матчить.
3. опять же с чего взяли что бинарное?
4. смотря как реализован хеш
5. тоже самое относится к «матчу» по деревьям и хешам, зависит от реалиации.
Так как в тегах конкретный ЯП не написан:
для языка Perl есть готовый модуль Regexp::Grammars, который расширяет регулярные выражения Perl (в основном в плане удобочитаемости) в котором все указанные проблемы решаемы + предоставляет удобный способ поиска по хэш таблицам.
Вот пример
для языка Perl есть готовый модуль Regexp::Grammars, который расширяет регулярные выражения Perl (в основном в плане удобочитаемости) в котором все указанные проблемы решаемы + предоставляет удобный способ поиска по хэш таблицам.
Вот пример
1. Ну а если я в словарь добавляю новое слово? Допустим читаю слова с сервера и последовательно их добавляю.
2. Ну по одному символу вы не определите совпадают строки или нет, все-равно же придется сканировать оставшуюся часть строки, после того как вы определили поддерево по префиксу. Просто в вашем случае это делает regexp движок.
2. Ну по одному символу вы не определите совпадают строки или нет, все-равно же придется сканировать оставшуюся часть строки, после того как вы определили поддерево по префиксу. Просто в вашем случае это делает regexp движок.
1. добавление имеет сложность количество символов добавляемого слова и проверок происходит столько же. Мы читаем символы слова только один раз и сразу определяем куда класть.
2. Мы движемся по строке, это же автомат и сравниваем каждый раз по символу, до первого несовпадения.
Это кардинально отличается от поиска по дереву где:
а. на каждом шаге сравниваются две строки.
б. останов происходит когда доходим до узла дерева что всегда равно logN.
2. Мы движемся по строке, это же автомат и сравниваем каждый раз по символу, до первого несовпадения.
Это кардинально отличается от поиска по дереву где:
а. на каждом шаге сравниваются две строки.
б. останов происходит когда доходим до узла дерева что всегда равно logN.
Вот потому google re2, где конечные автоматы на ДКА так хорош.
Да, ДКА это сила, но у него другая проблема — его размеры — при компиляции он разворачивается в огромную структуру данных. Как всегда дилемма процессорного времени и памяти…
ээээ нет. неправда ваша.
re2 хорош тем, что хранит автомат как НКА, но идет параллельно по множеству состояний, тем самым детерменизируя его на ходу.
таким образом, по памяти это НКА — линейно от регулярки.
по времени это ДКА — линейно от текста.
и дополнительной памяти — не больше числа состояний.
там все очень и очень хорошо сделано и описана теория.
я аналог на JAva в качестве курсовика пишу, изучаю внутренности. Russ Cox очень большой молодец, сейчас Го с Пайком разрабатывает.
re2 хорош тем, что хранит автомат как НКА, но идет параллельно по множеству состояний, тем самым детерменизируя его на ходу.
таким образом, по памяти это НКА — линейно от регулярки.
по времени это ДКА — линейно от текста.
и дополнительной памяти — не больше числа состояний.
там все очень и очень хорошо сделано и описана теория.
я аналог на JAva в качестве курсовика пишу, изучаю внутренности. Russ Cox очень большой молодец, сейчас Го с Пайком разрабатывает.
Смотрите. Допустмм этой чудо-хренью мы захотим искать в тексте название городов. Допустим, у нас есть БД с 100 000 городов. Вопрос, сколько времени будет строиться эта регулярка? Какого объема получится? Не свалится ли RE engine от такой нагрузки?
Что-то мне идея разбивания на слова кажется более оптимальной.
Что-то мне идея разбивания на слова кажется более оптимальной.
Нет, как раз в этом случае скорость все равно будет больше у такой регулярки.
Увы теоретически у меня не получается объяснить почему, т.е. я вроде все аргументировал, но мне не верят ) Еще последние два аргумента:
в википедии нет другого алгоритма поиска множества строк в тексте кроме en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm — значит он оптимальный на сегодняшний день, а это почти в точности что я описал.
Просто сделайте тест. Когда теория становится слишком сложной можно просто провести эксперимент.
Увы теоретически у меня не получается объяснить почему, т.е. я вроде все аргументировал, но мне не верят ) Еще последние два аргумента:
в википедии нет другого алгоритма поиска множества строк в тексте кроме en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm — значит он оптимальный на сегодняшний день, а это почти в точности что я описал.
Просто сделайте тест. Когда теория становится слишком сложной можно просто провести эксперимент.
Я уже не так уверен, но вопрос все равно спорный. Тут можно посмореть сравнение трех этих структур данных Trie(префиксная оптимизация), Hash, Tree.
По скорости построения, Trie самая быстрая. По скорости считывания для очень больших данных выигрывает Hash, но идеальный(когда мало коллизий) и слова очень разные — мало общих префиксов, Tree всегда хуже Trie в поиске.
Я все еще остаюсь при своем мнении Trie для регекспов самый быстрый способ если работать с обычным тестом где много общий префиксов. Но это мнение ИМХО, так как это не всегда верно.
По скорости построения, Trie самая быстрая. По скорости считывания для очень больших данных выигрывает Hash, но идеальный(когда мало коллизий) и слова очень разные — мало общих префиксов, Tree всегда хуже Trie в поиске.
Я все еще остаюсь при своем мнении Trie для регекспов самый быстрый способ если работать с обычным тестом где много общий префиксов. Но это мнение ИМХО, так как это не всегда верно.
а вы тестили саму эту версию? сколько она оперативы сжирает?
я делал нечто подобное недавно, сделал trie, потом откатил к хэшмепу, т.к. создается слишком большое количество объектов (ведь на каждую букву свой объект Node) и GC загибается (пробовал играться с разными сборщиками)
кстати, почему вы используете эррейлист? использовали бы хотя бы линкед лист — память не так будет тратиться.
ну и не совсем понятно почему вообще лист, а не мэп (поиск O(N) против O(1)) — это все я про операцию вставки
я делал нечто подобное недавно, сделал trie, потом откатил к хэшмепу, т.к. создается слишком большое количество объектов (ведь на каждую букву свой объект Node) и GC загибается (пробовал играться с разными сборщиками)
кстати, почему вы используете эррейлист? использовали бы хотя бы линкед лист — память не так будет тратиться.
ну и не совсем понятно почему вообще лист, а не мэп (поиск O(N) против O(1)) — это все я про операцию вставки
Насчет памяти не знаю, так как Pattern сериализируеться в строку. Словарь городов(около 15000) уменьшился в 1.5 раза, в сравнении с простой склейкой.
Скорость работы в сравнении с обычным регекспом в 100 раз быстрее, на корпусе нтмл страниц.
Моя структура дынных временная, так как все что она делает это создает новую строку, которая используется в дальнейших регулярных выражениях — сама структура выбрасывается и далее все зависит от движка RE.
Оптимальное в данном случае по скорости это массив размером 32(кол букв), где много пустых ветвей — вообще надо отказаться от указателей и перейти к индексам в массиве везде где только можно — но это уже не ява а С++ какой то ). Надо что то использовать из специальных быстрых коллекций типа bak.pcj.
В общем если делать просто поиск слов по словарям то лучше хеш, правда возникает вопрос границ если есть фразы длины 4,5 в словаре. Это структура удобна если пишется много регулярок из них собираются сложные и в автомат сложно вставить свой оператор.
Скорость работы в сравнении с обычным регекспом в 100 раз быстрее, на корпусе нтмл страниц.
Моя структура дынных временная, так как все что она делает это создает новую строку, которая используется в дальнейших регулярных выражениях — сама структура выбрасывается и далее все зависит от движка RE.
Оптимальное в данном случае по скорости это массив размером 32(кол букв), где много пустых ветвей — вообще надо отказаться от указателей и перейти к индексам в массиве везде где только можно — но это уже не ява а С++ какой то ). Надо что то использовать из специальных быстрых коллекций типа bak.pcj.
В общем если делать просто поиск слов по словарям то лучше хеш, правда возникает вопрос границ если есть фразы длины 4,5 в словаре. Это структура удобна если пишется много регулярок из них собираются сложные и в автомат сложно вставить свой оператор.
В Emacs есть встроенная команда для такой оптимизации.
вот реализация для перла
search.cpan.org/~jhi/Regex-PreSuf-1.17/PreSuf.pm
search.cpan.org/~jhi/Regex-PreSuf-1.17/PreSuf.pm
в упор не понимаю почему эти пары регулярок после компиляции дают разный конечный автомат, однако на v8 результаты интересные:
txt= Array(10000).join('javada')
var re= /javajava|javggaaa|javvva|adasddsa|adsasd/ 186.77 µs
var re= /jav(?:ajava|ggaaa|vva)|ad(?:asddsa|sasd)/ 200.19 µs
var re= /adasddsa|adsasd|javajava|javggaaa|javvva/ 186.77 µs
var re= /ad(?:asddsa|sasd)|jav(?:ajava|ggaaa|vva)/ 165.77 µs
txt= Array(10000).join('javada')
var re= /javajava|javggaaa|javvva|adasddsa|adsasd/ 186.77 µs
var re= /jav(?:ajava|ggaaa|vva)|ad(?:asddsa|sasd)/ 200.19 µs
var re= /adasddsa|adsasd|javajava|javggaaa|javvva/ 186.77 µs
var re= /ad(?:asddsa|sasd)|jav(?:ajava|ggaaa|vva)/ 165.77 µs
если словарь является частью большой регулярки, скорее в этом есть смысл, превратить нечто
regex_part1(city1|city2|city3|...cityN)regex_part3
во что-то короткое, как вы предложили.
а вот для чистой проверки текста по словарю есть более эффективные алгоритмы поиска с множественным паттерном, например, автомат Aho-Corasick, Wu-Manber,…
regex_part1(city1|city2|city3|...cityN)regex_part3
во что-то короткое, как вы предложили.
а вот для чистой проверки текста по словарю есть более эффективные алгоритмы поиска с множественным паттерном, например, автомат Aho-Corasick, Wu-Manber,…
Код из статьи, портированный на js и es6:
gist.github.com/DenVdmj/1fd7da3f3ae50443cea267654fa2cfd9
codepen.io/DenVdmj/pen/dmpAL
codepen.io/DenVdmj/pen/MGNejb
gist.github.com/DenVdmj/1fd7da3f3ae50443cea267654fa2cfd9
codepen.io/DenVdmj/pen/dmpAL
codepen.io/DenVdmj/pen/MGNejb
Sign up to leave a comment.
Префиксная оптимизация регулярных выражений на Java