streamalism.org

1. Overzicht

In deze tutorial onderzoeken we het concept van patroonherkenning van strings en hoe we dit sneller kunnen maken. Vervolgens zullen we de implementatie ervan in Java doorlopen.

2. Patroonaanpassing van snaren

2.1. Definitie

In strings is patroonvergelijking het proces waarbij wordt gecontroleerd op een bepaalde reeks tekens die worden aangeroepen een patroon in een reeks karakters genaamd a tekst.

De basisverwachtingen van patroonafstemming wanneer het patroon geen reguliere expressie is, zijn:

• de overeenkomst moet exact zijn - niet gedeeltelijk
• het resultaat moet alle overeenkomsten bevatten - niet alleen de eerste overeenkomst
• het resultaat moet de positie van elke overeenkomst in de tekst bevatten

2.2. Op zoek naar een patroon

Laten we een voorbeeld gebruiken om een ​​eenvoudig probleem met het matchen van patronen te begrijpen:

Patroon: NA Tekst: HAVANABANANA Match1: ---- NA ------ Match2: -------- NA-- Match3: ---------- NA

We kunnen zien dat het patroon NA komt drie keer voor in de tekst. Om dit resultaat te krijgen, kunnen we eraan denken om het patroon teken voor teken door de tekst te schuiven en te controleren of er een overeenkomst is.

Dit is echter een brute-force-benadering met tijdcomplexiteit O (p * t) waar p is de lengte van het patroon, en t is de lengte van de tekst.

Stel dat we meer dan één patroon hebben om naar te zoeken. Dan neemt de tijdcomplexiteit ook lineair toe, aangezien elk patroon een afzonderlijke iteratie nodig heeft.

2.3. Trie datastructuur om patronen op te slaan

We kunnen de zoektijd verbeteren door de patronen op te slaan in een trie datastructuur, die bekend staat om zijn snelle reproberenwaarde van items.

We weten dat een trie-datastructuur de karakters van een string opslaat in een boomachtige structuur. Dus voor twee snaren {NA, NAB}, we krijgen een boom met twee paden:

Door een trie te maken, is het mogelijk om een ​​groep patronen door de tekst te schuiven en te controleren op overeenkomsten in slechts één iteratie.

Merk op dat we de $ teken om het einde van de string aan te geven.

2.4. Achtervoegsel Trie-gegevensstructuur om tekst op te slaan

EEN achtervoegsel trie, aan de andere kant, is een trie datastructuur geconstrueerd met behulp van alle mogelijke achtervoegsels van een enkele string.

Voor het vorige voorbeeld HAVANABANANA, kunnen we een achtervoegsel trie construeren:

Achtervoegselpogingen worden gemaakt voor de tekst en worden meestal gedaan als onderdeel van een voorbewerkingsstap. Daarna kunt u snel naar patronen zoeken door een pad te vinden dat overeenkomt met de patroonreeks.

Het is echter bekend dat een achtervoegsel trie veel ruimte in beslag neemt, aangezien elk teken van de tekenreeks in een rand is opgeslagen.

In de volgende sectie zullen we een verbeterde versie van het achtervoegsel trie bekijken.

3. Achtervoegselboom

Een achtervoegsel boom is gewoon een gecomprimeerd achtervoegsel proberen. Dit betekent dat we, door de randen samen te voegen, een groep tekens kunnen opslaan en daardoor de opslagruimte aanzienlijk kunnen verkleinen.

We kunnen dus een achtervoegselboom voor dezelfde tekst maken HAVANABANANA:

Elk pad dat begint bij de wortel tot het blad, vertegenwoordigt een achtervoegsel van de tekenreeks HAVANABANANA.

Een achtervoegselboom ook slaat de positie van het achtervoegsel op in de bladknoop. Bijvoorbeeld, BANAAN $ is een achtervoegsel vanaf de zevende positie. Daarom is de waarde zes met behulp van op nul gebaseerde nummering. Hetzelfde, A-> BANAAN $ is een ander achtervoegsel dat begint op positie vijf, zoals we zien in de bovenstaande afbeelding.

Dus als we de dingen in perspectief plaatsen, kunnen we dat zien een patroonovereenkomst vindt plaats wanneer we in staat zijn om een ​​pad te krijgen dat begint bij het hoofdknooppunt met randen die volledig overeenkomen met het gegeven patroon positioneel.

Als het pad eindigt bij een bladknooppunt, krijgen we een achtervoegselovereenkomst. Anders krijgen we alleen een substring-match. Bijvoorbeeld het patroon NA is een achtervoegsel van HAVANABANA [NA] en een substring van HAVA [NA] BANAAN.

In de volgende sectie zullen we zien hoe deze datastructuur in Java geïmplementeerd kan worden.

4. Gegevensstructuur

Laten we een datastructuur van de achtervoegselboom maken. We hebben twee domeinklassen nodig.

Ten eerste hebben we een class om het boomknooppunt te vertegenwoordigen. Het moet de randen van de boom en de onderliggende knooppunten opslaan. Als het een bladknooppunt is, moet het bovendien de positionele waarde van het achtervoegsel opslaan.

Dus laten we onze Knooppunt klasse:

public class Node {privé String-tekst; privélijst kinderen; privé int positie; public Node (String word, int position) {this.text = word; this.position = positie; this.children = nieuwe ArrayList (); } // getters, setters, toString ()}

Ten tweede hebben we een class om de boom weer te geven en het hoofdknooppunt op te slaan. Het moet ook de volledige tekst opslaan waaruit de achtervoegsels zijn gegenereerd.

Daarom hebben we een Achtervoegselboom klasse:

openbare klasse SuffixTree {privé statische laatste String WORD_TERMINATION = "$"; privé statische laatste int POSITION_UNDEFINED = -1; privéknooppunt root; private String fullText; openbare SuffixTree (String-tekst) {root = new Node ("", POSITION_UNDEFINED); fullText = tekst; }}

5. Hulpmethoden voor het toevoegen van gegevens

Voordat we onze kernlogica schrijven om gegevens op te slaan, laten we een paar hulpmethoden toevoegen. Deze zullen later nuttig blijken.

Laten we onze Achtervoegselboom class om enkele methoden toe te voegen die nodig zijn voor het construeren van de boom.

5.1. Een kindknooppunt toevoegen

Laten we eerst een methode hebben addChildNode naar voeg een nieuw kindknooppunt toe aan een willekeurig bovenliggend knooppunt:

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

5.2. Het langste gemeenschappelijke voorvoegsel van twee strings zoeken

Ten tweede zullen we een eenvoudige hulpprogramma-methode schrijven getLongestCommonPrefix naar zoek het langste gemeenschappelijke voorvoegsel van twee strings:

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. Een knooppunt splitsen

Ten derde, laten we een methode hebben om een kindknooppunt uit een bepaalde ouder uithakken. In dit proces zijn het tekst waarde wordt afgekapt en de rechts afgekapte tekenreeks wordt de tekst waarde van het onderliggende knooppunt. Bovendien worden de kinderen van de ouder overgebracht naar het onderliggende knooppunt.

Dat kunnen we op de onderstaande afbeelding zien ANA wordt gesplitst in A-> NA. Daarna het nieuwe achtervoegsel ABANANA $ kan worden toegevoegd als A-> BANAAN $:

Kortom, dit is een gemakkelijke methode die van pas zal komen bij het invoegen van een nieuw knooppunt:

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. Hulpmethode voor verplaatsing

Laten we nu de logica maken om de boom te doorkruisen. We gebruiken deze methode zowel voor het construeren van de boom als voor het zoeken naar patronen.

6.1. Gedeeltelijke wedstrijd versus volledige wedstrijd

Laten we eerst het concept van een gedeeltelijke overeenkomst en een volledige overeenkomst begrijpen door een boom te beschouwen die is gevuld met een paar achtervoegsels:

Om een ​​nieuw achtervoegsel toe te voegen ANABANANA $, controleren we of er een knooppunt bestaat dat kan worden aangepast of uitgebreid om de nieuwe waarde te accommoderen. Hiervoor vergelijken we de nieuwe tekst met alle knooppunten en vinden dat het bestaande knooppunt [A] VANABANANA $ komt overeen met het eerste teken. Dit is dus het knooppunt dat we moeten wijzigen, en deze overeenkomst kan een gedeeltelijke overeenkomst worden genoemd.

Aan de andere kant, laten we in overweging nemen dat we naar het patroon zoeken VANE op dezelfde boom. We weten dat het gedeeltelijk overeenkomt met [VAN] ABANANA $ op de eerste drie karakters. Als alle vier de personages overeenkwamen, zouden we het een volledige overeenkomst kunnen noemen. Voor het zoeken naar patronen is een volledige match nodig.

Om samen te vatten, gebruiken we een gedeeltelijke overeenkomst bij het samenstellen van de boom en een volledige overeenkomst bij het zoeken naar patronen. We gebruiken een vlag isAllowPartialMatch om het soort match aan te geven dat we in elk geval nodig hebben.

6.2. De boom doorkruisen

Laten we nu onze logica schrijven om de boom te doorkruisen, zolang we een bepaald patroon positioneel kunnen matchen:

Lijst getAllNodesInTraversePath (String-patroon, Node startNode, boolean isAllowPartialMatch) {// ...}

We noemen dit recursief en retourneren een lijst met alle knooppunten vinden we op ons pad.

We beginnen met het vergelijken van het eerste teken van de patroontekst met de knooppunttekst:

if (pattern.charAt (0) == nodeText.charAt (0)) {// logica om de resterende tekens af te handelen} 

Voor een gedeeltelijke overeenkomst, als het patroon korter of gelijk is in lengte aan de knooppunttekst, voegen we het huidige knooppunt toe aan onze knooppunten lijst en stop hier:

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

Vervolgens vergelijken we de overige karakters van deze knooptekst met die van het patroon. Als het patroon een positionele mismatch heeft met de knooppunttekst, stoppen we hier. Het huidige knooppunt is opgenomen in knooppunten lijst alleen voor een gedeeltelijke overeenkomst:

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

Als het patroon overeenkomt met de knooppunttekst, voegen we het huidige knooppunt toe aan ons knooppunten lijst:

knooppunten.add (currentNode);

Maar als het patroon meer tekens heeft dan de knooppunttekst, moeten we de onderliggende knooppunten controleren. Hiervoor maken we een recursieve aanroep door de currentNode als het startknooppunt en het resterende deel van de patroon als het nieuwe patroon. De lijst met knooppunten die door deze aanroep zijn geretourneerd, wordt toegevoegd aan onze knooppunten lijst als het niet leeg is. Als het leeg is voor een volledig matchscenario, betekent dit dat er een mismatch was, dus om dit aan te geven, voegen we een nul item. En we retourneren de knooppunten:

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

Laten we dit allemaal samenvoegen, laten we creëren getAllNodesInTraversePath:

privélijst getAllNodesInTraversePath (String-patroon, Node startNode, boolean isAllowPartialMatch) {List nodes = new ArrayList (); voor (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); retourknooppunten; } 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); }} retourknooppunten; }} retourknooppunten; }

7. Algoritme

7.1. Gegevens bewaren

We kunnen nu onze logica schrijven om gegevens op te slaan. Laten we beginnen met het definiëren van een nieuwe methode addSuffix op de Achtervoegselboom klasse:

private void addSuffix (String achtervoegsel, int positie) {// ...}

De beller geeft de positie van het achtervoegsel aan.

Laten we vervolgens de logica schrijven om het achtervoegsel af te handelen. Eerst moeten we controleren of er een pad bestaat dat gedeeltelijk overeenkomt met het achtervoegsel tenminste door onze hulpmethode te bellen getAllNodesInTraversePath met isAllowPartialMatch ingesteld als waar. Als er geen pad bestaat, kunnen we ons achtervoegsel als kind toevoegen aan de wortel:

Lijstknooppunten = getAllNodesInTraversePath (patroon, root, true); if (nodes.size () == 0) {addChildNode (root, achtervoegsel, positie); }

Echter, als er een pad bestaat, betekent dit dat we een bestaand knooppunt moeten wijzigen. Dit knooppunt is het laatste knooppunt in het knooppunten lijst. We moeten ook uitzoeken wat de nieuwe tekst voor dit bestaande knooppunt zou moeten zijn. Als het knooppunten lijst heeft maar één item, dan gebruiken we de achtervoegsel. Anders sluiten we het gemeenschappelijke voorvoegsel tot het laatste knooppunt uit van het achtervoegsel om het newText:

Node lastNode = nodes.remove (nodes.size () - 1); String newText = achtervoegsel; if (nodes.size ()> 0) {String existSuffixUptoLastNode = nodes.stream () .map (a -> a.getText ()) .reduce ("", String :: concat); newText = newText.substring (bestaandeSuffixUptoLastNode.length ()); }

Laten we een nieuwe methode maken om het bestaande knooppunt te wijzigen verlengenNode, die we zullen bellen vanaf waar we gebleven waren addSuffix methode. Deze methode heeft twee belangrijke verantwoordelijkheden. Een daarvan is om een ​​bestaand knooppunt op te splitsen in ouder en kind, en de andere is om een ​​kind toe te voegen aan het nieuw gemaakte bovenliggende knooppunt. We breken het bovenliggende knooppunt alleen op om het een gemeenschappelijk knooppunt te maken voor al zijn onderliggende knooppunten. Dus onze nieuwe methode is klaar:

private void extensionNode (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 resterendeText = newText.substring (commonPrefix.length ()); addChildNode (knooppunt, resterende tekst, positie); }

We kunnen nu terugkomen op onze methode voor het toevoegen van een achtervoegsel, die nu alle logica bevat:

private void addSuffix (String achtervoegsel, int positie) {List nodes = getAllNodesInTraversePath (achtervoegsel, root, true); if (nodes.size () == 0) {addChildNode (root, achtervoegsel, positie); } else {Node lastNode = nodes.remove (nodes.size () - 1); String newText = achtervoegsel; if (nodes.size ()> 0) {String existSuffixUptoLastNode = nodes.stream () .map (a -> a.getText ()) .reduce ("", String :: concat); newText = newText.substring (bestaandeSuffixUptoLastNode.length ()); } extensionNode (lastNode, newText, position); }}

Laten we tot slot onze Achtervoegselboom constructor om de achtervoegsels te genereren en onze vorige methode aan te roepen addSuffix om ze iteratief toe te voegen aan onze datastructuur:

public void SuffixTree (String text) {root = new Node ("", POSITION_UNDEFINED); voor (int i = 0; i <text.length (); i ++) {addSuffix (text.substring (i) + WORD_TERMINATION, i); } fullText = tekst; }

7.2. Gegevens zoeken

Nadat we onze achtervoegselboomstructuur hebben gedefinieerd om gegevens op te slaan, we kunnen nu de logica schrijven voor het uitvoeren van onze zoektocht.

We beginnen met het toevoegen van een nieuwe methode searchText op de Achtervoegselboom klasse, waarbij je de patroon zoeken als invoer:

openbare lijst searchText (tekenreekspatroon) {// ...}

Vervolgens om te controleren of het patroon bestaat in onze achtervoegselboom, noemen we onze helper-methode getAllNodesInTraversePath waarbij de vlag alleen is ingesteld voor exacte overeenkomsten, in tegenstelling tot tijdens het toevoegen van gegevens toen we gedeeltelijke overeenkomsten toestonden:

Lijstknooppunten = getAllNodesInTraversePath (patroon, root, false);

We krijgen dan de lijst met knooppunten die overeenkomen met ons patroon. Het laatste knooppunt in de lijst geeft het knooppunt aan waarop het patroon exact overeenkomt. Dus onze volgende stap zal zijn om alle leaf-knooppunten die afkomstig zijn van dit laatste overeenkomende knooppunt te krijgen en de posities op te halen die zijn opgeslagen in deze leaf-knooppunten.

Laten we een aparte methode maken getPositions om dit te doen. We zullen controleren of het gegeven knooppunt het laatste deel van een achtervoegsel opslaat om te beslissen of de positiewaarde moet worden geretourneerd. En we zullen dit recursief doen voor elk kind van het gegeven knooppunt:

privélijst getPositions (knooppunt) {Lijstposities = nieuwe ArrayList (); if (node.getText (). endsWith (WORD_TERMINATION)) {position.add (node.getPosition ()); } voor (int i = 0; i <node.getChildren (). size (); i ++) {posities.addAll (getPositions (node.getChildren (). get (i))); } terugkeerposities; }

Zodra we de reeks posities hebben, is de volgende stap om deze te gebruiken om de patronen te markeren op de tekst die we in onze achtervoegselboom hebben opgeslagen. De positiewaarde geeft aan waar het achtervoegsel begint, en de lengte van het patroon geeft aan hoeveel tekens er vanaf het startpunt moeten worden verschoven. Laten we deze logica toepassen en een eenvoudige hulpprogramma-methode maken:

private String markPatternInText (Integer startPosition, String-patroon) {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; }

Nu hebben we onze ondersteunende methoden klaar. Daarom we kunnen ze toevoegen aan onze zoekmethode en de logica voltooien:

openbare lijst searchText (tekenreekspatroon) {Lijstresultaat = nieuwe ArrayList (); Lijstknooppunten = getAllNodesInTraversePath (patroon, root, false); if (nodes.size ()> 0) {Node lastNode = nodes.get (nodes.size () - 1); if (lastNode! = null) {Lijstposities = getPositions (lastNode); posities = posities.stream () .sorted () .collect (Collectors.toList ()); posities.forEach (m -> resultaat.add ((markPatternInText (m, patroon)))); }} resultaat retourneren; }

8. Testen

Nu we ons algoritme hebben ingevoerd, gaan we het testen.

Laten we eerst een tekst opslaan in ons Achtervoegselboom:

SuffixTree suffixTree = nieuwe SuffixTree ("havanabanana"); 

Laten we vervolgens naar een geldig patroon zoeken een:

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

Als we de code uitvoeren, krijgen we zes overeenkomsten zoals verwacht:

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

Laten we het volgende doen zoek naar een ander geldig patroon nab:

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

Het uitvoeren van de code levert ons slechts één overeenkomst op zoals verwacht:

hava [nab] anana

Laten we tot slot zoek naar een ongeldig patroon zeuren:

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

Het uitvoeren van de code levert geen resultaten op. We zien dat overeenkomsten exact moeten zijn en niet gedeeltelijk.

Ons algoritme voor het zoeken naar patronen heeft dus aan alle verwachtingen kunnen voldoen die we aan het begin van deze tutorial hebben uiteengezet.

9. Tijdscomplexiteit

Bij het construeren van de achtervoegselboom voor een gegeven tekst met lengte t, de tijd complexiteit is O (t).

Dan, voor het zoeken naar een patroon van lengte p,de tijdcomplexiteit is O (p). Bedenk dat het voor een zoektocht met brute kracht was O (p * t). Dus, het zoeken naar patronen gaat sneller na de voorbewerking van de tekst.

10. Conclusie

In dit artikel hebben we eerst de concepten van drie datastructuren begrepen: trie, suffix trie en suffix tree. We hebben toen gezien hoe een achtervoegselboom kan worden gebruikt om achtervoegsels compact op te slaan.

Later zagen we hoe we een achtervoegselboom konden gebruiken om gegevens op te slaan en een patroonzoekopdracht uit te voeren.

Zoals altijd is de broncode met tests beschikbaar op GitHub.