Префиксная оптимизация регулярных выражений на 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));