Schnelle Musterübereinstimmung von Zeichenfolgen mithilfe des Suffixbaums in Java

1. Übersicht

In diesem Tutorial werden wir das Konzept des Pattern Matching von Strings untersuchen und wie wir es schneller machen können. Anschließend werden wir die Implementierung in Java durchgehen.

2. Pattern Matching von Strings

2.1. Definition

In Zeichenfolgen ist der Mustervergleich der Vorgang des Überprüfens einer bestimmten Zeichenfolge, die als Muster bezeichnet wird, in einer Folge von Zeichen, die als Text bezeichnet wird .

Die grundlegenden Erwartungen an den Mustervergleich, wenn das Muster kein regulärer Ausdruck ist, sind:

  • Die Übereinstimmung sollte genau sein - nicht teilweise
  • Das Ergebnis sollte alle Übereinstimmungen enthalten - nicht nur die erste Übereinstimmung
  • Das Ergebnis sollte die Position jeder Übereinstimmung im Text enthalten

2.2. Suche nach einem Muster

Lassen Sie uns ein Beispiel verwenden, um ein einfaches Mustervergleichsproblem zu verstehen:

Pattern: NA Text: HAVANABANANA Match1: ----NA------ Match2: --------NA-- Match3: ----------NA

Wir können sehen, dass das Muster NA im Text dreimal vorkommt. Um dieses Ergebnis zu erzielen, können wir uns vorstellen, das Muster zeichenweise über den Text zu schieben und nach Übereinstimmungen zu suchen.

Dies ist jedoch ein Brute-Force-Ansatz mit der Zeitkomplexität O (p * t), wobei p die Länge des Musters und t die Länge des Textes ist.

Angenommen, wir müssen mehr als ein Muster suchen. Dann nimmt die Zeitkomplexität auch linear zu, da jedes Muster eine separate Iteration benötigt.

2.3. Versuchen Sie die Datenstruktur zum Speichern von Mustern

Wir können die Suchzeit verbessern, indem wir die Muster in einer Testdatenstruktur speichern, die für ihre schnelle Überprüfung von Elementen bekannt ist.

Wir wissen, dass eine Trie-Datenstruktur die Zeichen einer Zeichenfolge in einer baumartigen Struktur speichert. Für zwei Zeichenfolgen {NA, NAB} erhalten wir also einen Baum mit zwei Pfaden:

Wenn Sie einen Versuch erstellen, können Sie eine Gruppe von Mustern im Text nach unten schieben und in nur einer Iteration nach Übereinstimmungen suchen.

Beachten Sie, dass wir das Zeichen $ verwenden, um das Ende der Zeichenfolge anzugeben.

2.4. Suffix Trie Datenstruktur zum Speichern von Text

Ein Suffix trie ist andererseits eine Trie-Datenstruktur, die unter Verwendung aller möglichen Suffixe einer einzelnen Zeichenfolge erstellt wird .

Für das vorherige Beispiel HAVANABANANA können wir ein Suffix trie erstellen :

Suffixversuche werden für den Text erstellt und normalerweise in einem Vorverarbeitungsschritt durchgeführt. Danach kann die Suche nach Mustern schnell durchgeführt werden, indem ein Pfad gefunden wird, der der Mustersequenz entspricht.

Es ist jedoch bekannt, dass ein Suffix trie viel Platz beansprucht, da jedes Zeichen der Zeichenfolge in einer Kante gespeichert ist.

Wir werden uns im nächsten Abschnitt eine verbesserte Version des Suffix-Versuchs ansehen.

3. Suffixbaum

Ein Suffix - Baum ist einfach eine komprimierte Suffix Trie . Dies bedeutet, dass wir durch Verbinden der Kanten eine Gruppe von Zeichen speichern und dadurch den Speicherplatz erheblich reduzieren können.

So können wir einen Suffixbaum für denselben Text HAVANABANANA erstellen :

Jeder Pfad von der Wurzel bis zum Blatt repräsentiert ein Suffix der Zeichenfolge HAVANABANANA .

Ein Suffixbaum speichert auch die Position des Suffix im Blattknoten . Zum Beispiel ist BANANA $ ein Suffix ab der siebten Position. Daher ist sein Wert bei Verwendung einer auf Null basierenden Nummerierung sechs. Ebenso ist A-> BANANA $ ein weiteres Suffix ab Position fünf, wie wir im obigen Bild sehen.

Wenn wir also die Dinge relativieren, können wir sehen, dass eine Musterübereinstimmung auftritt, wenn wir in der Lage sind, einen Pfad ab dem Wurzelknoten mit Kanten zu erhalten, die vollständig mit dem gegebenen Muster positionell übereinstimmen .

Wenn der Pfad an einem Blattknoten endet, erhalten wir eine Suffixübereinstimmung. Andernfalls erhalten wir nur eine Teilzeichenfolge. Beispielsweise ist das Muster NA ein Suffix von HAVANABANA [NA] und ein Teilstring von HAVA [NA] BANANA .

Im nächsten Abschnitt erfahren Sie, wie Sie diese Datenstruktur in Java implementieren.

4. Datenstruktur

Erstellen wir eine Suffixbaum-Datenstruktur. Wir brauchen zwei Domainklassen.

Erstens benötigen wir eine Klasse, um den Baumknoten darzustellen . Es muss die Kanten des Baums und seine untergeordneten Knoten speichern. Wenn es sich um einen Blattknoten handelt, muss außerdem der Positionswert des Suffix gespeichert werden.

Erstellen wir also unsere Node- Klasse:

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() }

Zweitens benötigen wir eine Klasse, um den Baum darzustellen und den Wurzelknoten zu speichern . Außerdem muss der vollständige Text gespeichert werden, aus dem die Suffixe generiert werden.

Folglich haben wir eine SuffixTree- Klasse:

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. Hilfsmethoden zum Hinzufügen von Daten

Bevor wir unsere Kernlogik zum Speichern von Daten schreiben, fügen wir einige Hilfsmethoden hinzu. Diese werden sich später als nützlich erweisen.

Lassen Sie uns unsere SuffixTree- Klasse ändern , um einige Methoden hinzuzufügen, die zum Erstellen des Baums erforderlich sind.

5.1. Hinzufügen eines untergeordneten Knotens

Lassen Sie uns zunächst eine Methode addChildNode verwenden , um einem bestimmten übergeordneten Knoten einen neuen untergeordneten Knoten hinzuzufügen :

private void addChildNode(Node parentNode, String text, int index) { parentNode.getChildren().add(new Node(text, index)); }

5.2. Finden des längsten gemeinsamen Präfixes von zwei Zeichenfolgen

Zweitens schreiben wir eine einfache Dienstprogrammmethode getLongestCommonPrefix , um das längste gemeinsame Präfix von zwei Zeichenfolgen zu finden :

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. Knoten teilen

Drittens haben wir eine Methode, um einen untergeordneten Knoten aus einem bestimmten übergeordneten Knoten herauszuarbeiten . In diesem Verfahren wird der übergeordnete Knoten Textwert wird abgeschnitten werden, und der rechte abgeschnitten Zeichenfolge wird der Text Wert des Kindknotens. Außerdem werden die untergeordneten Elemente des übergeordneten Elements auf den untergeordneten Knoten übertragen.

Wir können dem Bild unten entnehmen, dass ANA in A-> NA aufgeteilt wird. Anschließend kann das neue Suffix ABANANA $ als A-> BANANA $ hinzugefügt werden :

In short, this is a convenience method that will come in handy when inserting a new node:

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. Helper Method for Traversal

Let's now create the logic to traverse the tree. We'll use this method for both constructing the tree and searching for patterns.

6.1. Partial Match vs. Full Match

First, let's understand the concept of a partial match and a full match by considering a tree populated with a few suffixes:

To add a new suffix ANABANANA$, we check if any node exists that can be modified or extended to accommodate the new value. For this, we compare the new text with all the nodes and find that the existing node [A]VANABANANA$ matches at first character. So, this is the node we need to modify, and this match can be called a partial match.

On the other hand, let's consider that we're searching for the pattern VANE on the same tree. We know that it partially matches with [VAN]ABANANA$ on the first three characters. If all the four characters had matched, we could call it a full match. For pattern search, a complete match is necessary.

So to summarize, we'll use a partial match when constructing the tree and a full match when searching for patterns. We'll use a flag isAllowPartialMatch to indicate the kind of match we need in each case.

6.2. Traversing the Tree

Now, let's write our logic to traverse the tree as long as we're able to match a given pattern positionally:

List getAllNodesInTraversePath(String pattern, Node startNode, boolean isAllowPartialMatch) { // ... }

We'll call this recursively and return a list of all the nodes we find in our path.

We start by comparing the first character of the pattern text with the node text:

if (pattern.charAt(0) == nodeText.charAt(0)) { // logic to handle remaining characters } 

For a partial match, if the pattern is shorter or equal in length to the node text, we add the current node to our nodes list and stop here:

if (isAllowPartialMatch && pattern.length() <= nodeText.length()) { nodes.add(currentNode); return nodes; } 

Then we compare the remaining characters of this node text with that of the pattern. If the pattern has a positional mismatch with the node text, we stop here. The current node is included in nodes list only for a partial match:

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; } } 

If the pattern matched the node text, we add the current node to our nodes list:

nodes.add(currentNode);

But if the pattern has more characters than the node text, we need to check the child nodes. For this, we make a recursive call passing the currentNode as the starting node and remaining portion of the pattern as the new pattern. The list of nodes returned from this call is appended to our nodes list if it's not empty. In case it's empty for a full match scenario, it means there was a mismatch, so to indicate this, we add a null item. And we return the nodes:

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;

Putting all this together, let's create getAllNodesInTraversePath:

private List getAllNodesInTraversePath(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) { 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. Algorithm

7.1. Storing Data

We can now write our logic to store data. Let's start by defining a new method addSuffix on the SuffixTree class:

private void addSuffix(String suffix, int position) { // ... }

The caller will provide the position of the suffix.

Next, let's write the logic to handle the suffix. First, we need to check if a path exists matching the suffix partially at least by calling our helper method getAllNodesInTraversePath with isAllowPartialMatch set as true. If no path exists, we can add our suffix as a child to the root:

List nodes = getAllNodesInTraversePath(pattern, root, true); if (nodes.size() == 0) { addChildNode(root, suffix, position); }

However, if a path exists, it means we need to modify an existing node. This node will be the last one in the nodes list. We also need to figure out what should be the new text for this existing node. If the nodes list has only one item, then we use the suffix. Otherwise, we exclude the common prefix up to the last node from the suffix to get the 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()); }

For modifying the existing node, let's create a new method extendNode, which we'll call from where we left off in addSuffix method. This method has two key responsibilities. One is to break up an existing node to parent and child, and the other is to add a child to the newly created parent node. We break up the parent node only to make it a common node for all its child nodes. So, our new method is ready:

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); }

We can now come back to our method for adding a suffix, which now has all the logic in place:

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); } }

Finally, let's modify our SuffixTree constructor to generate the suffixes and call our previous method addSuffix to add them iteratively to our data structure:

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. Searching Data

Having defined our suffix tree structure to store data, we can now write the logic for performing our search.

We begin by adding a new method searchText on the SuffixTree class, taking in the pattern to search as an input:

public List searchText(String pattern) { // ... }

Next, to check if the pattern exists in our suffix tree, we call our helper method getAllNodesInTraversePath with the flag set for exact matches only, unlike during the adding of data when we allowed partial matches:

List nodes = getAllNodesInTraversePath(pattern, root, false);

We then get the list of nodes that match our pattern. The last node in the list indicates the node up to which the pattern matched exactly. So, our next step will be to get all the leaf nodes originating from this last matching node and get the positions stored in these leaf nodes.

Let's create a separate method getPositions to do this. We'll check if the given node stores the final portion of a suffix to decide if its position value needs to be returned. And, we'll do this recursively for every child of the given node:

private List getPositions(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; }

Once we have the set of positions, the next step is to use it to mark the patterns on the text we stored in our suffix tree. The position value indicates where the suffix starts, and the length of the pattern indicates how many characters to offset from the starting point. Applying this logic, let's create a simple utility method:

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; }

Now, we have our supporting methods ready. Therefore, we can add them to our search method and complete the logic:

public List searchText(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. Testing

Now that we have our algorithm in place, let's test it.

First, let's store a text in our SuffixTree:

SuffixTree suffixTree = new SuffixTree("havanabanana"); 

Next, let's search for a valid pattern a:

List matches = suffixTree.searchText("a"); matches.stream().forEach(m -> LOGGER.info(m));

Running the code gives us six matches as expected:

h[a]vanabanana hav[a]nabanana havan[a]banana havanab[a]nana havanaban[a]na havanabanan[a]

Next, let's search for another valid pattern nab:

List matches = suffixTree.searchText("nab"); matches.stream().forEach(m -> LOGGER.info(m)); 

Running the code gives us only one match as expected:

hava[nab]anana

Finally, let's search for an invalid pattern nag:

List matches = suffixTree.searchText("nag"); matches.stream().forEach(m -> LOGGER.info(m));

Running the code gives us no results. We see that matches have to be exact and not partial.

Thus, our pattern search algorithm has been able to satisfy all the expectations we laid out at the beginning of this tutorial.

9. Time Complexity

When constructing the suffix tree for a given text of length t, the time complexity is O(t).

Then, for searching a pattern of length p,the time complexity is O(p). Recollect that for a brute-force search, it was O(p*t). Thus, pattern searching becomes faster after pre-processing of the text.

10. Conclusion

In diesem Artikel haben wir zunächst die Konzepte von drei Datenstrukturen verstanden - Trie, Suffix Trie und Suffix Tree. Wir haben dann gesehen, wie ein Suffixbaum verwendet werden kann, um Suffixe kompakt zu speichern.

Später haben wir gesehen, wie man einen Suffixbaum verwendet, um Daten zu speichern und eine Mustersuche durchzuführen.

Wie immer ist der Quellcode mit Tests auf GitHub verfügbar.