Префиксная оптимизация регулярных выражений на Java

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

    Итак проблема, есть огромный словарь городов и надо найти в тексте все эти фразы. Наивный подход заключается в склеивании по or этих слов, таким образом получается такое выражение (city1|city2|city3|...cityN). При обработке такого выражения обычный NDA движок (к которым относится большинство, в том числе JDK) будет делать по крайней мере N проверок на каждый символ в тексте, в худшем же случае(когда текущее слово отличается на последней букве от всех слов в словаре) количество проверок будет равно количеству букв в словаре.
    Это плохо, но можно сделать лучше.
    Типичное свойство языка это избыточность. В данном случае это повторяемость последовательности букв. Здесь я расскажу о самом простом способе оптимизации — префиксной оптимизации.
    Если слова начинаются с одинаковых префиксов, то вычисления будут выполнятся один раз для любого префикса. Итак мы строим Trie по нашему словарю, а затем конвертируем его в строку регулярного выражения.

    Класс описывающий дерево
    class Node {
                            char ch = START;
                            List<Node> nodes = Lists.newArrayList();
    
                            void add(String str) {
                                    if (str.length() == 0) return;
                                    char chNew = str.charAt(0);
                                    for (Node n : nodes) {
                                            if (n.ch == chNew) {
                                                    n.add(str.substring(1));
                                                    return;
                                            }
                                    }
                                    Node newNode = new Node();
                                    newNode.ch = chNew;
                                    newNode.add(str.substring(1));
                                    nodes.add(newNode);
                            }
    
                            String toRegexp() {...}
                    }
    

    Как мы видим его основной метод add проверяет есть ли первый символ среди его детей, если нет, то создает и отдает тому поддереву, которое начинается с этого символа.
    Таким образом в данной структуре любой префикс хранится только один раз(путь по дереву) и переиспользуется когда встречается в наших строках.

    Второй метод конвертирует дерево в регулярное выражение.
                            String toRegexp() {
                                    StringBuilder str = new StringBuilder();
                                    if (ch == START) {
    
                                    } else if (ch == END) {
    
                                    } else {
    //convert special characters like {}[].
                                            String newStr = escapeRegexp(String.valueOf(ch));
                                            str.append(newStr);
                                    }
                                    if (nodes.size() > 1) {
                                            str.append("(?:");
                                            for (Node n : nodes) {
                                                    str.append("");
                                                    str.append(n.toRegexp());
                                                    str.append("|");
                                            }
                                            str.setLength(str.length() - 1);
                                            str.append(')');
                                    } else if (nodes.size() == 1) {
                                            str.append(nodes.get(0).toRegexp());
                                    }
                                    return str.toString();
                            }
                    }
    


    Вот рабочий код
    public static String convertListToRegexp(final boolean useNonCapturingGroups, String... strs) {
                    Arrays.sort(strs,
                            new Comparator<String>() {
                                    public int compare(String o1, String o2) {
                                            int res = o2.length() - o1.length();
                                            if (res != 0) {
                                                    return res;
                                            }
                                            return o1.compareTo(o2);
                                    }
                            });
                    Node root = new Node();
                    for (String str : strs) {
                            root.add(str + "$");
                    }
                    return root.toRegexp();
            }
    

    и пример
    //create array of your entries
    String[] examples = new String[]{"javvva", "javggaaa", "javajava", "adsasd", "adasddsa"};
    //convert them to optimal regexp
                    String optimizedRegexp = RegExpUtils.convertListToRegexp(true, examples);
                    Assert.assertEquals("(?:ad(?:asddsa|sasd)|jav(?:ajava|ggaaa|vva))", optimizedRegexp);
    //check that it is works
                    for(String s : examples) Assert.assertTrue(s.matches(optimizedRegexp));
    
    Метки:
    Поделиться публикацией
    Похожие публикации
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 43
    • +2
      Один вопрос: А почему бы вам сразу не производить поиск по хэш-таблице/бинарному дереву (то есть брать каждое слово в тексте, и искать в этой таблице/дереву)?
      • 0
        То что вы говорите думаю будет работать медленнее.
        Отличия:
        1. хеш таблицу/дерево нельзя вставить внутрь регулярного выражения. например написать паттерн "$город в$стране"
        2. в случае бинарного дерева, практически всегда количество проверок будет log2(N), а мы можем остановится на первом символе(чаще так и будет)
        3. в случае бинарного дерева каждое сравнение делается с нуля, тут же один раз, т.е. аля динамическое программирование
        4. хеш таблица требует вычисления по всем символам проверяемой строки, а мы можем остановится на первом символе
        5. если границы слова неопределенные, совершенно непонятно как использовать хеш таблицу. в данном же случае можно использовать такие символы как .*+ и таким образом делать оптимизацию не только строк но и регулярных выражений
        • 0
          Эмм… а чем тогда автомат не нравится?
          • 0
            Хм, так это и есть минимизация автомат.
            • 0
              А, похоже я понял к чему вы. Т.е. изначальная задача стоит так: Есть набор слов. Необходимо определить, есть ли набор этих слов (или регэксп) в словаре.
              В этом смысле вашу идею понял, интересно. Но думаю, здесь получится некоторое дублирование работы. В момент разбора регулярки словарь построит из нее то же дерево/авомат.
              • 0
                Да, именно. Но насчет разбора это не совсем так. Парсер из строки в регулярное выражение ничего из вышеописанного не сделает — он не оптимизирует, он просто строит автомат как есть. Я же подготавливаю для него строку которая описывает более быстрый автомат.
                • 0
                  Может быть. Тогда, возможно, вам лучше просто построить минимальный DFA.
                  • 0
                    А это вроде как и есть DFA полученный из NFA. Понятие «Префиксная оптимизация» я придумал, возможно статью стоило назвать получение DFA в частном случае.
                    • 0
                      У вас детерминированный автомат. Но не минимальный. Вы оптимизируете только префикс.

                      Сравните для слов word, ward. Ваше дерево будет содержать 8 узлов и 7 ребер (две ветви), в то время как минимальный DFA 5 и 5 (между вторым и третьим состоянием две дуги).
                      • 0
                        Но по скорости выполнения они будут равны.
                      • 0
                        Нет, у Вас не DFA. На каждый символ входного (тестируемого) потока длины N у вас будет тратиться не O(N) операций. Точнее, всё зависит от движка регулярных выражений, но саму вашу форму DFA назвать нельзя.

                        Замечу также, что DFA регулярного выражения, которое не привязано к началу строки (нет символа ^) и которое содержит много условий «или» (символов |) будет очень большим. Это к комментарию выше.

                        Что же касается вашей оптимизации — она очень хороша для уменьшения сложности именно NFA-анализа. Сделаю предположение (не уверен, надо думать), что обычные алгоритмы получения минимального DFA сделают ваше оптимизацию ненужной (избыточность выкинется сама).
                        • 0
                          По моему все же ДНА. Определение ДНА на каждом шаге существует только один возможный переход — детерминированность. В случае Trie существует только один путь по дереву для любой строки или он отсутствует вообще. Т.е. это DFA. И затраты на каждый символ будут равны ветвистости дерева.
                          • 0
                            В случае

                            • 0
                              Раньше отправилось, извините.

                              Когда вы обнаружите несоответствие шаблону на каком-то символе, вы должны будете откатить входной поток назад. Например, пусть есть паттерн /abc/. Начинаем анализ строки abdabc. На символе d вы обнаруживаете несоответствие. Но вы не можете дальше продолжить анализ строки, вы должны вернуться назад и провести тестирование начиная от символа b. Таким образом, символы 2 и 3 (b и d) будут оттестированы дважды. Это как раз НЕ O(N).

                              Всё то, что вы говорите, работает только при привязке паттерна к началу тестируемой строки (т. е. /^abc/, а не /abc/).

                              Ахо-Корасик (ниже вы давали ссылку) решает эту проблему — насколько я помню, как раз за счёт DFA (детерминированного конечного автомата).
                              • 0
                                В Вашем примере "(?:ad(?:asddsa|sasd)|jav(?:ajava|ggaaa|vva))" проблема будет при анализе соответствия подстроке asddsa, sasd и так далее.
                                • 0
                                  В Trie откатов не происходит(мы не ищем строку а проверяем на соответствие т.е. патерн ^...$). Мой пример превращается в такое дерево.
                                  ad
                                  --asddsa
                                  --sasd
                                  jav
                                  --ajava
                                  --ggaaa
                                  --vva

                                  При обработке строки asddsa. Мы проверим первый символ первого патерна(второй не подходит так как начинается на j), второй символ на этом патерн перестанет работать т.е. как альтернатив нет. и будет всего 2 проверки символов.
                                  Т.е. в такой оптимизации никаких откатов нет так же как и альтернатив.
                                  • 0
                                    Значит, мы просто не поняли друг друга :) Извините, я Ваш код не смотрел внимательно.

                                    Но во вступлении написано «надо найти в тексте все эти фразы». Ну и дальше Вы приводите выражение (city1|city2|city3|...cityN), а не (^(city1|city2|city3|...cityN)$).

                                    Ну и в примерах тоже привязки к началу строки не видно. Хотя, может быть, это синтаксис, и тут, наоборот, нужно дописывать (.*) в начало строки, чтобы «отвязаться» от начала?
                                • 0
                                  А да согласен, все что говорю относится к привязке к началу. Но и DFA будет не O(N) если мы делаем сдвиг на символ и матчим снова… Правда как правило все двигаются по границам токенов что существенно оптимизирует процесс.
                                  • 0
                                    Не совсем с Вами согласен… DFA «по определению» будет O(N) в любом случае. На то он и детерминированный.

                                    Другое дело, что для хоть сколько-то сложных регулярок происходит state explosion, и DFA-форма начинает занимать сумасшедшие размеры в памяти. Но для этого есть свои оптимизации.
                • 0
                  если я все правильно понял:

                  1. добавление новой строки, вроде как, имеет сложность не меньше чем C*N, где N — размер слова, что в любом медленнее чем добавление в сбалансированное дерево (logN).
                  2. количество проверок для бинарного дерева logN, это точно, но ведь у вас же тоже строки должны сравниваться тем же regexp'ом на равенство. Это ведь будет не меньше чем N.

                  имхо дерево будет таки быстрее. но подход интересный.
                  • 0
                    RE 1. добавление новой строки, вроде как, имеет сложность не меньше чем C*N, где N — размер слова, что в любом медленнее чем добавление в сбалансированное дерево (logN).

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

                    RE 2. количество проверок для бинарного дерева logN, это точно, но ведь у вас же тоже строки должны сравниваться тем же regexp'ом на равенство. Это ведь будет не меньше чем N.

                    Каждая проверка в моем случае это сравнении одного символа, в случае бинарного дерева это сравнения целых строк. Сравнений может быть меньше чем N, например если первый символ не подходит для словаря то произойдет всего одна символьная проверка, в дереве же logN строковых сравнений- что значительно более трудоемко.
                  • 0
                    1. А не надо зацикливаться на регулярках :) часто нужное реализуется более простыми вещами, и более быстрыми.

                    2. А с чего вы взяли что бинарное дерево? Обычно дерево таки той ветвистости, какой словарь символов. При этом регулярка будет в разы медленнее матчить.

                    3. опять же с чего взяли что бинарное?

                    4. смотря как реализован хеш

                    5. тоже самое относится к «матчу» по деревьям и хешам, зависит от реалиации.
                    • 0
                      Если вас не устраивают теоретически аргументы проведите benchmark и убедитесь на практике.
                      • 0
                        увы у меня в проекте реализовано деревом :) при большой «маске» деревом быстрее чем любое регулярное выражение.
                    • 0
                      Так как в тегах конкретный ЯП не написан:

                      для языка Perl есть готовый модуль Regexp::Grammars, который расширяет регулярные выражения Perl (в основном в плане удобочитаемости) в котором все указанные проблемы решаемы + предоставляет удобный способ поиска по хэш таблицам.

                      Вот пример
                      • 0
                        Спасибо, узнал много нового о языке Перл.
                        Язык программирования указал в тегах и заголовке.
                  • 0
                    1. Ну а если я в словарь добавляю новое слово? Допустим читаю слова с сервера и последовательно их добавляю.

                    2. Ну по одному символу вы не определите совпадают строки или нет, все-равно же придется сканировать оставшуюся часть строки, после того как вы определили поддерево по префиксу. Просто в вашем случае это делает regexp движок.
                    • 0
                      1. добавление имеет сложность количество символов добавляемого слова и проверок происходит столько же. Мы читаем символы слова только один раз и сразу определяем куда класть.
                      2. Мы движемся по строке, это же автомат и сравниваем каждый раз по символу, до первого несовпадения.
                      Это кардинально отличается от поиска по дереву где:
                      а. на каждом шаге сравниваются две строки.
                      б. останов происходит когда доходим до узла дерева что всегда равно logN.
                      • 0
                        1. добавление длинных слов займет явно больше времени чем добавление в бинарное дерево.

                        2. опять же, если слова будут достаточно большой длинны, то работать это будет медленнее бинарного поиска.
                    • 0
                      Вот потому google re2, где конечные автоматы на ДКА так хорош.
                      • 0
                        Да, ДКА это сила, но у него другая проблема — его размеры — при компиляции он разворачивается в огромную структуру данных. Как всегда дилемма процессорного времени и памяти…
                        • 0
                          ээээ нет. неправда ваша.
                          re2 хорош тем, что хранит автомат как НКА, но идет параллельно по множеству состояний, тем самым детерменизируя его на ходу.

                          таким образом, по памяти это НКА — линейно от регулярки.
                          по времени это ДКА — линейно от текста.

                          и дополнительной памяти — не больше числа состояний.

                          там все очень и очень хорошо сделано и описана теория.
                          я аналог на JAva в качестве курсовика пишу, изучаю внутренности. Russ Cox очень большой молодец, сейчас Го с Пайком разрабатывает.
                          • 0
                            Выкладывайте в опенсорс, с удовольствием присоединюсь к проекту.
                      • 0
                        Смотрите. Допустмм этой чудо-хренью мы захотим искать в тексте название городов. Допустим, у нас есть БД с 100 000 городов. Вопрос, сколько времени будет строиться эта регулярка? Какого объема получится? Не свалится ли RE engine от такой нагрузки?

                        Что-то мне идея разбивания на слова кажется более оптимальной.
                        • 0
                          Нет, как раз в этом случае скорость все равно будет больше у такой регулярки.
                          Увы теоретически у меня не получается объяснить почему, т.е. я вроде все аргументировал, но мне не верят ) Еще последние два аргумента:
                          в википедии нет другого алгоритма поиска множества строк в тексте кроме en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm — значит он оптимальный на сегодняшний день, а это почти в точности что я описал.
                          Просто сделайте тест. Когда теория становится слишком сложной можно просто провести эксперимент.
                          • 0
                            Я уже не так уверен, но вопрос все равно спорный. Тут можно посмореть сравнение трех этих структур данных Trie(префиксная оптимизация), Hash, Tree.
                            По скорости построения, Trie самая быстрая. По скорости считывания для очень больших данных выигрывает Hash, но идеальный(когда мало коллизий) и слова очень разные — мало общих префиксов, Tree всегда хуже Trie в поиске.
                            Я все еще остаюсь при своем мнении Trie для регекспов самый быстрый способ если работать с обычным тестом где много общий префиксов. Но это мнение ИМХО, так как это не всегда верно.
                            • 0
                              а вы тестили саму эту версию? сколько она оперативы сжирает?
                              я делал нечто подобное недавно, сделал trie, потом откатил к хэшмепу, т.к. создается слишком большое количество объектов (ведь на каждую букву свой объект Node) и GC загибается (пробовал играться с разными сборщиками)
                              кстати, почему вы используете эррейлист? использовали бы хотя бы линкед лист — память не так будет тратиться.
                              ну и не совсем понятно почему вообще лист, а не мэп (поиск O(N) против O(1)) — это все я про операцию вставки
                              • 0
                                Насчет памяти не знаю, так как Pattern сериализируеться в строку. Словарь городов(около 15000) уменьшился в 1.5 раза, в сравнении с простой склейкой.
                                Скорость работы в сравнении с обычным регекспом в 100 раз быстрее, на корпусе нтмл страниц.
                                Моя структура дынных временная, так как все что она делает это создает новую строку, которая используется в дальнейших регулярных выражениях — сама структура выбрасывается и далее все зависит от движка RE.
                                Оптимальное в данном случае по скорости это массив размером 32(кол букв), где много пустых ветвей — вообще надо отказаться от указателей и перейти к индексам в массиве везде где только можно — но это уже не ява а С++ какой то ). Надо что то использовать из специальных быстрых коллекций типа bak.pcj.
                                В общем если делать просто поиск слов по словарям то лучше хеш, правда возникает вопрос границ если есть фразы длины 4,5 в словаре. Это структура удобна если пишется много регулярок из них собираются сложные и в автомат сложно вставить свой оператор.
                          • +1
                            В Emacs есть встроенная команда для такой оптимизации.
                            • 0
                              вот реализация для перла
                              search.cpan.org/~jhi/Regex-PreSuf-1.17/PreSuf.pm
                              • 0
                                в упор не понимаю почему эти пары регулярок после компиляции дают разный конечный автомат, однако на 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

                                • 0
                                  если словарь является частью большой регулярки, скорее в этом есть смысл, превратить нечто
                                  regex_part1(city1|city2|city3|...cityN)regex_part3
                                  во что-то короткое, как вы предложили.
                                  а вот для чистой проверки текста по словарю есть более эффективные алгоритмы поиска с множественным паттерном, например, автомат Aho-Corasick, Wu-Manber,…
                                  • 0
                                    Ну Aho-Corasick делает тоже самое, за исключенем того что он более оптимален по памяти и использует еще суфиксную оптимизацию.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.