Автор оригинала: Mohan Sundararaju.
1. Обзор
В этом учебнике мы изучат концепцию сопоставления шаблонов строк и как мы можем сделать это быстрее. Затем мы пройдемся по его реализации на Java.
2. Сопоставление шаблонов струнных
2.1. Определение
В строках сопоставление шаблонов является процессом проверки данной последовательности символов, называемых шаблон в последовательности символов, называемых текстовые .
Основные ожидания соответствия шаблона, когда шаблон не является регулярным выражением:
- матч должен быть точным – не частичный
- результат должен содержать все матчи, а не только первый матч
- результат должен содержать положение каждого матча в тексте
2.2. Поиск шаблона
Давайте использовать пример, чтобы понять простую проблему сопоставления шаблонов:
Pattern: NA Text: HAVANABANANA Match1: ----NA------ Match2: --------NA-- Match3: ----------NA
Мы видим, что NA происходит три раза в тексте. Чтобы получить этот результат, мы можем думать о скольжении шаблона вниз текст один символ в то время, и проверка на матч.
Тем не менее, это грубой силы подход со временем О(пат) где р является длина шаблона, и t является длина текста.
Предположим, что у нас есть несколько шаблонов для поиска. Затем сложность времени также увеличивается линейно, так как каждому шаблону потребуется отдельная итерация.
2.3. Структура данных Trie для хранения шаблонов
Мы можем улучшить время поиска, сохраняя шаблоны в структура данных trie , который известен своей быстрой повторной Trie валь предметов.
Мы знаем, что структура данных trie хранит символы строки в древо-подобной структуре. Итак, для двух строк (НА, NAB) , мы получим дерево с двумя путями:
Созданный trie позволяет сдвинуть группу шаблонов вниз по тексту и проверить совпадения всего за одну итерацию.
Обратите внимание, что мы используем $ символ для обозначения конца строки.
2.4. Структура данных Suffix Trie для хранения текста
суффикс trie , с другой стороны, это структура данных trie построен с использованием всех возможных суффиксов одной строки .
Для предыдущего примера ГАВАНАБАНАНА , мы можем построить суффикс trie:
Попытки Suffix создаются для текста и обычно делаются в рамках предварительного шага обработки. После этого поиск шаблонов можно быстро высовыть, найдя путь, соответствующий последовательности шаблонов.
Тем не менее, суффикс trie, как известно, потребляют много места, как каждый символ строки хранится в краю.
В следующем разделе мы посмотрим на улучшенную версию суффикс-три.
3. Дерево суффикса
Суффикс дерево это просто сжатый суффикс Trie . Это означает, что, соединяя края, мы можем хранить группу символов и тем самым значительно сократить пространство для хранения.
Таким образом, мы можем создать суффикс дерево для того же текста ГАВАНАБАНАНА :
Каждый путь, начинающийся от корня к листу, представляет собой суффикс строки ГАВАНАБАНАНА .
Дерево суффикса также хранит положение суффикса в листе узла . Например, BANANA$ это суффикс, начиная с седьмой позиции. Таким образом, его значение будет шесть с использованием нулевой основе номерирования. Аналогичным образом, A->БАНАНА$ это еще один суффикс, начиная с позиции пять, как мы видим на картинке выше.
Таким образом, если положить вещи в перспективе, мы можем видеть, что совпадение шаблонов происходит, когда мы можем получить путь, начинающийся от корневого узла с краями, полностью соответствующими данному шаблону .
Если путь заканчивается на листе узла, мы получаем суффикс матч. В противном случае, мы получим только подступный матч. Например, шаблон NA это суффикс ГАВАНАБАНАЗА и подразряд ХАВАЗА БАНАНА .
В следующем разделе мы увидим, как реализовать эту структуру данных в Java.
4. Структура данных
Давайте создадим структуру данных дерева суффикса. Нам нужно два класса домена.
Во-первых, нам нужна класс для представления узла дерева . Он должен хранить края дерева и его детские узлы. Кроме того, когда это узел листа, он должен хранить позиционные значения суффикса.
Итак, давайте создадим нашу Узел класс:
public class Node {
private String text;
private List children;
private int position;
public Node(String word, int position) {
this.text = word;
this.position = position;
this.children = new ArrayList<>();
}
// getters, setters, toString()
} Во-вторых, нам нужна класс для представления дерева и хранения корневого узла . Он также должен хранить полный текст, из которого генерируются суффиксы.
Следовательно, у нас есть СуффиксТри класс:
public class SuffixTree {
private static final String WORD_TERMINATION = "$";
private static final int POSITION_UNDEFINED = -1;
private Node root;
private String fullText;
public SuffixTree(String text) {
root = new Node("", POSITION_UNDEFINED);
fullText = text;
}
}5. Помощник Методы добавления данных
Прежде чем написать нашу основную логику для хранения данных, давайте добавим несколько методов помощников. Они окажутся полезными позже.
Давайте изменим наши СуффиксТри класс, чтобы добавить некоторые методы, необходимые для построения дерева.
5.1. Добавление детского узла
Во-первых, давайте метод добавитьChildNode добавить новый узел ребенка в любой родительский узел :
private void addChildNode(Node parentNode, String text, int index) {
parentNode.getChildren().add(new Node(text, index));
}5.2. Поиск самой длинной общей префикса двух струн
Во-вторых, мы напишем простой метод утилиты getLongestCommonPrefix найти самый длинный общий префикс из двух строк :
private String getLongestCommonPrefix(String str1, String str2) {
int compareLength = Math.min(str1.length(), str2.length());
for (int i = 0; i < compareLength; i++) {
if (str1.charAt(i) != str2.charAt(i)) {
return str1.substring(0, i);
}
}
return str1.substring(0, compareLength);
}5.3. Разделение узла
В-третьих, давайте метод для вырезать узел ребенка из данного родительского . В этом процессе родительский узел текстовые значение будет усечено, а право усеченная строка становится текстовые значение детского узла. Кроме того, дети родителя будут переведены в узел ребенка.
Мы можем видеть на картинке ниже, что АНА делится на А->НА. После этого новый суффикс ABANANA $ могут быть добавлены в качестве A->БАНАНА$ :
Короче говоря, это удобный метод, который пригодится при вставке нового узла:
private void splitNodeToParentAndChild(Node parentNode, String parentNewText, String childNewText) {
Node childNode = new Node(childNewText, parentNode.getPosition());
if (parentNode.getChildren().size() > 0) {
while (parentNode.getChildren().size() > 0) {
childNode.getChildren()
.add(parentNode.getChildren().remove(0));
}
}
parentNode.getChildren().add(childNode);
parentNode.setText(parentNewText);
parentNode.setPosition(POSITION_UNDEFINED);
}6. Помощник Метод для обхода
Давайте создадим логику, чтобы пересечь дерево. Мы будем использовать этот метод как для построения дерева, так и для поиска шаблонов.
6.1. Частичный матч против полного матча
Во-первых, давайте поймем концепцию частичного матча и полного матча, рассматривая дерево, населенное несколькими суффиксами:
Чтобы добавить новый суффикс АНАБАНАНА$ , мы проверяем, существует ли какой-либо узел, который может быть изменен или расширен для размещения нового значения. Для этого мы сравниваем новый текст со всеми узлами и находим, что существующий узел (А) ВАНАБАНАНА$ соответствует на первый характер. Итак, это узел, который нам нужно изменить, и этот матч можно назвать частичным совпадением.
С другой стороны, давайте рассмотрим, что мы ищем шаблон ВАН на том же дереве. Мы знаем, что это частично совпадает с (ВАН) НЕТ, ABANANA $ на первых трех символах. Если бы все четыре персонажа были совпадают, мы могли бы назвать это полным совпадением. Для поиска шаблонов необходим полный .
Таким образом, подводя итог, мы будем использовать частичный матч при построении дерева и полное совпадение при поиске шаблонов. Мы будем использовать флаг являетсяАллоуПартиалМатч указать, какой матч нам нужен в каждом конкретном случае.
6.2. Обход дерева
Теперь давайте напишем нашу логику, чтобы пересечь дерево до тех пор, как мы в состоянии соответствовать данному шаблону позиционально:
ListgetAllNodesInTraversePath(String pattern, Node startNode, boolean isAllowPartialMatch) { // ... }
Мы назовем это повторно и вернем список всех узлы мы находим на нашем пути .
Начнем с сравнения первого символа текста шаблона с текстом узла:
if (pattern.charAt(0) == nodeText.charAt(0)) {
// logic to handle remaining characters
}
Для частичного соответствия, если шаблон короче или равен по длине тексту узла, мы добавляем текущий узел в наш узлы список и остановиться здесь:
if (isAllowPartialMatch && pattern.length() <= nodeText.length()) {
nodes.add(currentNode);
return nodes;
}
Затем мы сравниваем оставшиеся символы этого текста узла с символами шаблона. Если шаблон имеет позиционные несоответствия с текстом узла, мы останавливаемся на этом. Текущий узел включен в узлы список только для частичного матча:
int compareLength = Math.min(nodeText.length(), pattern.length());
for (int j = 1; j < compareLength; j++) {
if (pattern.charAt(j) != nodeText.charAt(j)) {
if (isAllowPartialMatch) {
nodes.add(currentNode);
}
return nodes;
}
}
Если шаблон соответствует тексту узла, мы добавляем текущий узел в наш узлы список:
nodes.add(currentNode);
Но если шаблон имеет больше символов, чем текст узла, мы должны проверить узлы ребенка. Для этого мы делаем рекурсивный звонок, проходящий через текущийНоде в качестве стартового узла и оставшейся части шаблон в качестве нового шаблона. Список узлов, возвращенных с этого вызова, прикодёл к нашему узлы список, если он не пуст. В случае, если он пуст для сценария полного матча, это означает, что было несоответствие, так что, чтобы указать на это, мы добавляем нулевой пункт. И мы возвращаем узлы :
if (pattern.length() > compareLength) {
List nodes2 = getAllNodesInTraversePath(pattern.substring(compareLength), currentNode,
isAllowPartialMatch);
if (nodes2.size() > 0) {
nodes.addAll(nodes2);
} else if (!isAllowPartialMatch) {
nodes.add(null);
}
}
return nodes;Сложив все это вместе, давайте создадим getAllNodesInTraversePath :
private ListgetAllNodesInTraversePath(String pattern, Node startNode, boolean isAllowPartialMatch) { List nodes = new ArrayList<>(); for (int i = 0; i < startNode.getChildren().size(); i++) { Node currentNode = startNode.getChildren().get(i); String nodeText = currentNode.getText(); if (pattern.charAt(0) == nodeText.charAt(0)) { if (isAllowPartialMatch && pattern.length() <= nodeText.length()) { nodes.add(currentNode); return nodes; } int compareLength = Math.min(nodeText.length(), pattern.length()); for (int j = 1; j < compareLength; j++) { if (pattern.charAt(j) != nodeText.charAt(j)) { if (isAllowPartialMatch) { nodes.add(currentNode); } return nodes; } } nodes.add(currentNode); if (pattern.length() > compareLength) { List nodes2 = getAllNodesInTraversePath(pattern.substring(compareLength), currentNode, isAllowPartialMatch); if (nodes2.size() > 0) { nodes.addAll(nodes2); } else if (!isAllowPartialMatch) { nodes.add(null); } } return nodes; } } return nodes; }
7. Алгоритм
7.1. Хранение данных
Теперь мы можем написать нашу логику для хранения данных. Начнем с определения нового метода добавитьСуффикс на СуффиксТри класс:
private void addSuffix(String suffix, int position) {
// ...
}Звонящий предоставит положение суффикса.
Далее, давайте напишем логику для обработки суффикса. Во-первых, мы должны проверить, существует ли путь, соответствующий суффиксу, частично по крайней мере, позвонив нашему помощнику метод getAllNodesInTraversePath с являетсяАллоуПартиалМатч установить в качестве истинное . Если пути не существует, мы можем добавить наш суффикс в детстве к корню:
Listnodes = getAllNodesInTraversePath(pattern, root, true); if (nodes.size() == 0) { addChildNode(root, suffix, position); }
Тем не менее, если путь существует, это означает, что нам нужно изменить существующий узел . Этот узел будет последним в узлы список. Нам также необходимо выяснить, каким должен быть новый текст для этого существующего узла. Если узлы список имеет только один пункт, то мы используем суффикс . В противном случае мы исключаем общую приставку до последнего узла из суффикс чтобы получить newText :
Node lastNode = nodes.remove(nodes.size() - 1);
String newText = suffix;
if (nodes.size() > 0) {
String existingSuffixUptoLastNode = nodes.stream()
.map(a -> a.getText())
.reduce("", String::concat);
newText = newText.substring(existingSuffixUptoLastNode.length());
}Для изменения существующего узла давайте создадим новый метод продлитьНоде, которые мы будем звонить от того, где мы остановились в добавитьСуффикс метод. Этот метод имеет две ключевые обязанности. Один из них заключается в том, чтобы разбить существующий узел на родительский и детский, а другой – добавить ребенка в недавно созданный родительский узел. Мы разбиваем родительский узел только для того, чтобы сделать его общим узлом для всех его детских узлов. Итак, наш новый метод готов:
private void extendNode(Node node, String newText, int position) {
String currentText = node.getText();
String commonPrefix = getLongestCommonPrefix(currentText, newText);
if (commonPrefix != currentText) {
String parentText = currentText.substring(0, commonPrefix.length());
String childText = currentText.substring(commonPrefix.length());
splitNodeToParentAndChild(node, parentText, childText);
}
String remainingText = newText.substring(commonPrefix.length());
addChildNode(node, remainingText, position);
}Теперь мы можем вернуться к нашему методу добавления суффикса, который теперь имеет всю логику на месте:
private void addSuffix(String suffix, int position) {
List nodes = getAllNodesInTraversePath(suffix, root, true);
if (nodes.size() == 0) {
addChildNode(root, suffix, position);
} else {
Node lastNode = nodes.remove(nodes.size() - 1);
String newText = suffix;
if (nodes.size() > 0) {
String existingSuffixUptoLastNode = nodes.stream()
.map(a -> a.getText())
.reduce("", String::concat);
newText = newText.substring(existingSuffixUptoLastNode.length());
}
extendNode(lastNode, newText, position);
}
} Наконец, давайте изменим наши СуффиксТри конструктор для создания суффиксов и вызова нашего предыдущего метода добавитьСуффикс чтобы добавить их итеративно в нашу структуру данных:
public void SuffixTree(String text) {
root = new Node("", POSITION_UNDEFINED);
for (int i = 0; i < text.length(); i++) {
addSuffix(text.substring(i) + WORD_TERMINATION, i);
}
fullText = text;
}7.2. Поиск данных
Определив нашу структуру дерева суффикса для хранения данных, теперь мы можем написать логику для выполнения наших поисковых .
Начнем с добавления нового метода поискТекст на СуффиксТри класса, принимая в шаблон для поиска в качестве ввода:
public ListsearchText(String pattern) { // ... }
Далее, чтобы проверить, если шаблон существует в нашем дереве суффикса, мы называем наш метод getAllNodesInTraversePath с флагом, установленным только для точных совпадений, в отличие от добавления данных, когда мы разрешали частичные совпадения:
Listnodes = getAllNodesInTraversePath(pattern, root, false);
Затем мы получаем список узлов, которые соответствуют нашему шаблону. Последний узел в списке указывает узел, до которого шаблон точно соответствовал. Таким образом, наш следующий шаг будет получить все узлы листьев, происходящих из этого последнего соответствия узла и получить позиции, хранящиеся в этих узлов листьев.
Давайте создадим отдельный метод getPositions сделать это. Мы проверим, хранит ли данный узел окончательную часть суффикса, чтобы решить, нужно ли его значение позиции быть возвращено. И мы сделаем это повторно для каждого ребенка данного узла:
private ListgetPositions(Node node) { List positions = new ArrayList<>(); if (node.getText().endsWith(WORD_TERMINATION)) { positions.add(node.getPosition()); } for (int i = 0; i < node.getChildren().size(); i++) { positions.addAll(getPositions(node.getChildren().get(i))); } return positions; }
После того, как у нас есть набор позиций, следующим шагом является его использование для разметки шаблонов на тексте, который мы хранили в нашем дереве суффикса. Значение положения указывает, где начинается суффикс, а длина шаблона указывает, сколько символов можно компенсировать от отправной точки. Применяя эту логику, давайте создадим простой метод утилиты:
private String markPatternInText(Integer startPosition, String pattern) {
String matchingTextLHS = fullText.substring(0, startPosition);
String matchingText = fullText.substring(startPosition, startPosition + pattern.length());
String matchingTextRHS = fullText.substring(startPosition + pattern.length());
return matchingTextLHS + "[" + matchingText + "]" + matchingTextRHS;
}Теперь у нас есть наши методы поддержки готовы. Поэтому мы можем добавить их в наш метод поиска и завершить логику :
public ListsearchText(String pattern) { List result = new ArrayList<>(); List nodes = getAllNodesInTraversePath(pattern, root, false); if (nodes.size() > 0) { Node lastNode = nodes.get(nodes.size() - 1); if (lastNode != null) { List positions = getPositions(lastNode); positions = positions.stream() .sorted() .collect(Collectors.toList()); positions.forEach(m -> result.add((markPatternInText(m, pattern)))); } } return result; }
8. Тестирование
Теперь, когда у нас есть наш алгоритм на месте, давайте проверить его.
Во-первых, давайте хранить текст в нашем СуффиксТри :
SuffixTree suffixTree = new SuffixTree("havanabanana");
Далее, давайте искать действительный шаблон :
Listmatches = suffixTree.searchText("a"); matches.stream().forEach(m -> LOGGER.info(m));
Запуск кода дает нам шесть совпадений, как ожидалось:
h[a]vanabanana hav[a]nabanana havan[a]banana havanab[a]nana havanaban[a]na havanabanan[a]
Далее, давайте поиск другого действительного шаблона наб :
Listmatches = suffixTree.searchText("nab"); matches.stream().forEach(m -> LOGGER.info(m));
Запуск кода дает нам только один матч, как ожидалось:
hava[nab]anana
Наконец, давайте поиск недействительного шаблона пилить :
Listmatches = suffixTree.searchText("nag"); matches.stream().forEach(m -> LOGGER.info(m));
Запуск кода не дает нам никаких результатов. Мы видим, что матчи должны быть точными, а не частичными.
Таким образом, наш алгоритм поиска шаблонов смог удовлетворить все ожидания, которые мы изложили в начале этого учебника.
9. Сложность времени
При построении дерева суффикса для данного текста длины t , сложность времени О(т) .
Затем для поиска шаблона длины р, сложность времени O(p) . Вспомните, что для поиска грубой силы, это было О(пат) . Таким образом, поиск шаблона становится быстрее после предварительной обработки текста .
10. Заключение
В этой статье мы впервые поняли концепции трех структур данных – три, суффикс три и суффикс дерева. Затем мы увидели, как суффикс дерево может быть использовано для компактного хранения суффиксов.
Позже мы увидели, как использовать дерево суффикса для хранения данных и выполнения поиска шаблонов.
Как всегда, исходный код с тестами доступен более на GitHub .