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