streamalism.org

1. Oversigt

I denne vejledning undersøger vi konceptet med mønstermatchning af strenge, og hvordan vi kan gøre det hurtigere. Derefter gennemgår vi implementeringen i Java.

2. Mønster matchning af strenge

2.1. Definition

I strenge er mønstermatchning processen med at kontrollere for en given rækkefølge af kaldte tegn et mønster i en række af tegn kaldet a tekst.

De grundlæggende forventninger til mønstermatchning, når mønsteret ikke er et regelmæssigt udtryk, er:

• kampen skal være nøjagtig - ikke delvis
• resultatet skal indeholde alle kampe - ikke kun den første kamp
• resultatet skal indeholde placeringen af ​​hver kamp inden for teksten

2.2. Søger efter et mønster

Lad os bruge et eksempel til at forstå et simpelt mønstermatchproblem:

Mønster: NA Tekst: HAVANABANANA Match1: ---- NA ------ Match2: -------- NA-- Match3: ---------- NA

Vi kan se, at mønsteret NA forekommer tre gange i teksten. For at få dette resultat kan vi tænke på at skubbe mønsteret et tegn ad gangen ned ad teksten og kontrollere, om der er et match.

Dette er imidlertid en brute-force tilgang med tidskompleksitet O (p * t) hvor s er mønsterets længde, og t er længden af ​​teksten.

Antag, at vi har mere end et mønster at søge efter. Derefter øges tidskompleksiteten også lineært, da hvert mønster har brug for en separat iteration.

2.3. Trie datastruktur til at gemme mønstre

Vi kan forbedre søgetiden ved at gemme mønstrene i en triedatastruktur, som er kendt for sin hurtige genoprettelsetrieværdi af varer.

Vi ved, at en triedatastruktur lagrer tegnene i en streng i en trælignende struktur. Så for to strenge {NA, NAB}, får vi et træ med to stier:

At have en trie oprettet gør det muligt at skubbe en gruppe mønstre ned ad teksten og kontrollere for matches i kun en iteration.

Bemærk, at vi bruger $ tegn for at indikere slutningen af ​​strengen.

2.4. Suffix Trie Datastruktur for at gemme tekst

EN suffiks triepå den anden side er en trie datastruktur konstrueret ved hjælp af alle mulige suffikser af en enkelt streng.

For det foregående eksempel HAVANABANANA, kan vi konstruere et suffiks trie:

Suffiksforsøg oprettes til teksten og udføres normalt som en del af et forbehandlingstrin. Derefter kan søgning efter mønstre gøres hurtigt ved at finde en sti, der matcher mønstersekvensen.

Det er dog kendt, at et suffiks-trie bruger meget plads, da hvert tegn i strengen er gemt i en kant.

Vi ser på en forbedret version af suffikset trie i næste afsnit.

3. Suffikstræ

Et suffiks træ er simpelthen en komprimeret suffiks trie. Hvad dette betyder er, at vi ved at forbinde kanterne kan gemme en gruppe tegn og derved reducere lagerpladsen markant.

Så vi kan oprette et suffiks-træ til den samme tekst HAVANABANANA:

Hver sti, der starter fra roden til bladet, repræsenterer et suffiks af strengen HAVANABANANA.

Et suffiksetræ også gemmer placeringen af ​​suffikset i bladknuden. For eksempel, BANANA $ er et suffiks startende fra den syvende position. Derfor vil dens værdi være seks ved hjælp af nulbaseret nummerering. Ligeledes, A-> BANANA $ er et andet suffiks, der starter ved position fem, som vi ser på ovenstående billede.

Så når vi sætter tingene i perspektiv, kan vi se det et mønstermatch opstår, når vi er i stand til at få en sti, der starter fra rodnoden med kanter, der matcher det givne mønster positionalt.

Hvis stien ender ved en bladknude, får vi et suffiks match. Ellers får vi bare et substring-match. For eksempel mønsteret NA er et suffiks af HAVANABANA [NA] og et underlag af HAVA [NA] BANANA.

I det næste afsnit vil vi se, hvordan du implementerer denne datastruktur i Java.

4. Datastruktur

Lad os oprette en datastruktur for suffiksetræ. Vi har brug for to domæneklasser.

For det første har vi brug for en klasse til at repræsentere træknudepunktet. Det er nødvendigt at gemme træets kanter og dets underordnede knudepunkter. Når det er en bladknude, skal den derudover gemme suffiksets positionelle værdi.

Så lad os oprette vores Node klasse:

offentlig klasse Node {privat strengtekst; private liste børn; privat int position public Node (String word, int position) {this.text = word; denne. position = position; this.children = ny ArrayList (); } // getters, setters, toString ()}

For det andet har vi brug for en klasse til at repræsentere træet og gemme rodnoden. Det skal også gemme den fulde tekst, hvorfra suffikser genereres.

Derfor har vi en SuffixTree klasse:

offentlig klasse SuffixTree {privat statisk endelig streng WORD_TERMINATION = "$"; privat statisk endelig int POSITION_UNDEFINED = -1; privat node rod; privat streng fuldtekst; public SuffixTree (String text) {root = new Node ("", POSITION_UNDEFINED); fullText = tekst; }}

5. Hjælpemetoder til tilføjelse af data

Før vi skriver vores kernelogik til at gemme data, lad os tilføje et par hjælpemetoder. Disse vil vise sig nyttige senere.

Lad os ændre vores SuffixTree klasse for at tilføje nogle nødvendige metoder til konstruktion af træet.

5.1. Tilføjelse af en undernode

Lad os først have en metode addChildNode til tilføj en ny underordnet node til en given overordnet node:

privat tomrum addChildNode (Node parentNode, String text, int index) {parentNode.getChildren (). add (ny Node (tekst, index)); }

5.2. Find længste fælles præfiks med to strenge

For det andet skriver vi en simpel hjælpemetode getLongestCommonPrefix til find det længste fælles præfiks på to strenge:

private String getLongestCommonPrefix (String str1, String str2) {int CompareLength = Math.min (str1.length (), str2.length ()); for (int i = 0; i <comparLength; i ++) {if (str1.charAt (i)! = str2.charAt (i)) {return str1.substring (0, i); }} returner str1.substring (0, sammenlignLængde); }

5.3. Opdeling af en node

For det tredje, lad os have en metode til udskære en barneknude fra en given forælder. I denne proces er det overordnede knudepunkt tekst værdi bliver afkortet, og den højre afkortede streng bliver til tekst værdien af ​​den underordnede node. Derudover overføres forældrenes børn til barneknudepunktet.

Vi kan se på billedet nedenfor ANA bliver delt til A-> NA. Bagefter det nye suffiks ABANANA $ kan tilføjes som A-> BANANA $:

Kort sagt er dette en bekvemhedsmetode, der vil være praktisk, når du indsætter en ny node:

privat ugyldigt splitNodeToParentAndChild (Node parentNode, String parentNewText, String childNewText) {Node childNode = ny Node (childNewText, parentNode.getPosition ()); hvis (parentNode.getChildren (). størrelse ()> 0) {mens (parentNode.getChildren (). størrelse ()> 0) {childNode.getChildren () .add (parentNode.getChildren (). fjern (0)); }} parentNode.getChildren (). tilføj (childNode); parentNode.setText (parentNewText); parentNode.setPosition (POSITION_UNDEFINED); }

6. Hjælpemetode til gennemkørsel

Lad os nu oprette logikken til at krydse træet. Vi bruger denne metode til både at konstruere træet og søge efter mønstre.

6.1. Delvist match mod fuld match

Lad os først forstå konceptet med en delvis match og en fuld match ved at overveje et træ, der er befolket med et par suffikser:

For at tilføje et nyt suffiks ANABANANA $, kontrollerer vi, om der findes en knude, der kan ændres eller udvides til at rumme den nye værdi. Til dette sammenligner vi den nye tekst med alle knudepunkterne og finder ud af, at den eksisterende knude [A] VANABANANA $ matcher ved første tegn. Så dette er den knude, vi skal ændre, og denne kamp kan kaldes en delvis match.

På den anden side, lad os overveje, at vi søger efter mønsteret VANE på det samme træ. Vi ved, at det delvis stemmer overens med [VAN] ABANANA $ på de første tre tegn. Hvis alle de fire tegn havde matchet, kunne vi kalde det en fuld match. For mønstersøgning er et komplet match nødvendigt.

Så for at opsummere bruger vi en delvis match, når vi konstruerer træet, og en fuld match, når vi søger efter mønstre. Vi bruger et flag isAllowPartialMatch for at angive den slags match, vi har brug for i hvert enkelt tilfælde.

6.2. Traversing the Tree

Lad os nu skrive vores logik for at krydse træet, så længe vi er i stand til at matche et givet mønster positionelt:

Liste getAllNodesInTraversePath (strengmønster, node startNode, boolsk isAllowPartialMatch) {// ...}

Vi kalder dette rekursivt og returnerer en liste over alle noder vi finder på vores vej.

Vi starter med at sammenligne mønstertekstens første tegn med nodeteksten:

if (pattern.charAt (0) == nodeText.charAt (0)) {// logik til håndtering af resterende tegn} 

For en delvis matchning, hvis mønsteret er kortere eller lig med længden på nodeteksten, tilføjer vi den aktuelle node til vores noder liste og stop her:

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

Derefter sammenligner vi de resterende tegn i denne node-tekst med mønsteret. Hvis mønsteret har en positionel uoverensstemmelse med nodeteksten, stopper vi her. Den aktuelle node er inkluderet i noder liste kun til en delvis kamp:

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

Hvis mønsteret matchede nodeteksten, tilføjede vi den aktuelle node til vores noder liste:

nodes.add (nuværendeNode);

Men hvis mønsteret har flere tegn end nodeteksten, skal vi kontrollere underordnede noder. Til dette foretager vi et rekursivt opkald, der passerer nuværendeNode som startknudepunkt og resterende del af mønster som det nye mønster. Listen over noder, der returneres fra dette opkald, føjes til vores noder liste, hvis den ikke er tom. Hvis det er tomt for et fuldt match-scenarie, betyder det, at der var en uoverensstemmelse, så for at angive dette tilføjer vi et nul vare. Og vi returnerer noder:

hvis (mønster.længde ()> sammenlignLængde) {Liste noder2 = getAllNodesInTraversePath (mønster.substring (sammenlignLængde), currentNode, erAllowPartialMatch); hvis (nodes2.size ()> 0) {nodes.addAll (nodes2); } ellers hvis (! isAllowPartialMatch) {nodes.add (null); }} returner noder;

Lad os skabe alt dette sammen getAllNodesInTraversePath:

privat liste getAllNodesInTraversePath (strengmønster, node startNode, boolsk isAllowPartialMatch) {List noder = ny ArrayList (); for (int i = 0; i <startNode.getChildren (). størrelse (); i ++) {Node currentNode = startNode.getChildren (). get (i); Streng nodeText = currentNode.getText (); if (pattern.charAt (0) == nodeText.charAt (0)) {if (isAllowPartialMatch && pattern.length () <= nodeText.length ()) {nodes.add (currentNode); returknudepunkter } int CompareLength = Math.min (nodeText.length (), pattern.length ()); for (int j = 1; j CompareLength) {List nodes2 = getAllNodesInTraversePath (pattern.substring (CompareLength), currentNode, isAllowPartialMatch); hvis (nodes2.size ()> 0) {nodes.addAll (nodes2); } ellers hvis (! isAllowPartialMatch) {nodes.add (null); }} returnere noder; }} returner noder; }

7. Algoritme

7.1. Lagring af data

Vi kan nu skrive vores logik til at gemme data. Lad os starte med at definere en ny metode addSuffix på den SuffixTree klasse:

privat ugyldigt addSuffix (streng-suffiks, int-position) {// ...}

Den, der ringer op, angiver placeringen af ​​suffikset.

Lad os derefter skrive logikken til at håndtere suffikset. Først skal vi kontrollere, om der findes en sti, der delvis matcher suffikset i det mindste ved at kalde vores hjælpemetode getAllNodesInTraversePath med isAllowPartialMatch angivet som rigtigt. Hvis der ikke findes nogen sti, kan vi tilføje vores suffiks som barn til roden:

Liste noder = getAllNodesInTraversePath (mønster, rod, sand); hvis (nodes.size () == 0) {addChildNode (rod, suffiks, position); }

Imidlertid, hvis der findes en sti, betyder det, at vi skal ændre en eksisterende node. Denne node vil være den sidste i noder liste. Vi skal også finde ud af, hvad der skal være den nye tekst til denne eksisterende node. Hvis den noder listen har kun et element, så bruger vi suffiks. Ellers udelukker vi det fælles præfiks op til den sidste node fra suffiks at få newText:

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

Lad os oprette en ny metode til at ændre den eksisterende node udvid Node, som vi kalder fra hvor vi slap addSuffix metode. Denne metode har to hovedansvar. Den ene er at opdele en eksisterende knude til forælder og barn, og den anden er at føje et barn til den nyoprettede forældreknude. Vi opdeler kun forældreknudepunktet for at gøre det til en fælles knudepunkt for alle dets underknudepunkter. Så vores nye metode er klar:

privat ugyldigt 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); } Streng leftText = newText.substring (commonPrefix.length ()); addChildNode (node, gjenværende tekst, position); }

Vi kan nu vende tilbage til vores metode til tilføjelse af et suffiks, som nu har al logikken på plads:

privat tomrum addSuffix (streng-suffiks, int-position) {List nodes = getAllNodesInTraversePath (suffix, root, true); hvis (nodes.size () == 0) {addChildNode (rod, suffiks, position); } ellers {Node lastNode = nodes.remove (nodes.size () - 1); String newText = suffiks; hvis (nodes.size ()> 0) {String eksisterendeSuffixUptoLastNode = nodes.stream () .map (a -> a.getText ()) .reduce ("", String :: concat); newText = newText.substring (eksisterendeSuffixUptoLastNode.length ()); } expandNode (lastNode, newText, position); }}

Lad os endelig ændre vores SuffixTree konstruktør til at generere suffikser og kalde vores tidligere metode addSuffix for at tilføje dem iterativt til vores datastruktur:

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); } fuldtekst = tekst; }

7.2. Søgning efter data

Efter at have defineret vores suffiks træstruktur til at gemme data, vi kan nu skrive logikken til at udføre vores søgning.

Vi begynder med at tilføje en ny metode searchText på den SuffixTree klasse, tager i mønster at søge som input:

public List searchText (strengemønster) {// ...}

Dernæst for at kontrollere, om mønster findes i vores suffiksetræ, kalder vi vores hjælpemetode getAllNodesInTraversePath med flag kun indstillet til nøjagtige matches, i modsætning til under tilføjelsen af ​​data, da vi tillod delvise matches:

Liste noder = getAllNodesInTraversePath (mønster, rod, falsk);

Vi får derefter listen over noder, der matcher vores mønster. Den sidste node på listen angiver den node, som mønsteret matchede nøjagtigt med. Så vores næste trin vil være at hente alle bladknudepunkter, der stammer fra denne sidste matchende knude, og få positionerne gemt i disse bladknudepunkter.

Lad os oprette en separat metode getPositions at gøre dette. Vi kontrollerer, om den givne node gemmer den sidste del af et suffiks for at afgøre, om dens positionsværdi skal returneres. Og vi gør dette rekursivt for hvert barn af den givne knude:

private List getPositions (Node node) {List positions = new ArrayList (); hvis (node.getText (). slutter med (WORD_TERMINATION)) {positions.add (node.getPosition ()); } for (int i = 0; i <node.getChildren (). størrelse (); i ++) {positions.addAll (getPositions (node.getChildren (). get (i))); } returpositioner; }

Når vi først har sætet positioner, er det næste trin at bruge det til at markere mønstrene på teksten, vi har gemt i vores suffiksetræ. Positionsværdien angiver, hvor suffikset starter, og længden af ​​mønsteret angiver, hvor mange tegn der skal forskydes fra startpunktet. Brug denne logik, lad os oprette en simpel hjælpemetode:

private String markPatternInText (Integer startPosition, String pattern) {String matchingTextLHS = fullText.substring (0, startPosition); Streng matchingText = fullText.substring (startPosition, startPosition + mønster.længde ()); Streng matchingTextRHS = fullText.substring (startPosition + mønster.længde ()); return matchingTextLHS + "[" + matchingText + "]" + matchingTextRHS; }

Nu har vi vores støttemetoder klar. Derfor, vi kan føje dem til vores søgemetode og fuldføre logikken:

public List searchText (String pattern) {List result = new ArrayList (); Liste noder = getAllNodesInTraversePath (mønster, rod, falsk); hvis (nodes.size ()> 0) {Node lastNode = nodes.get (nodes.size () - 1); hvis (lastNode! = null) {Listepositioner = getPositions (lastNode); positioner = positions.stream () .sorted () .collect (Collectors.toList ()); positions.forEach (m -> result.add ((markPatternInText (m, mønster)))); }} returner resultat; }

8. Testning

Nu hvor vi har vores algoritme på plads, lad os teste den.

Lad os først gemme en tekst i vores SuffixTree:

SuffixTree suffixTree = ny SuffixTree ("havanabanana"); 

Lad os derefter søge efter et gyldigt mønster -en:

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

At køre koden giver os seks kampe som forventet:

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

Lad os derefter søg efter et andet gyldigt mønster nab:

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

At køre koden giver os kun en kamp som forventet:

hava [nab] anana

Endelig, lad os søg efter et ugyldigt mønster nag:

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

At køre koden giver os ingen resultater. Vi ser, at kampe skal være nøjagtige og ikke delvise.

Således har vores mønstersøgningsalgoritme været i stand til at tilfredsstille alle de forventninger, vi stillede i starten af ​​denne vejledning.

9. Tidskompleksitet

Når du konstruerer suffiksetræet til en given længdetekst t, det tidskompleksitet er O (t).

Derefter til søgning i et længdemønster p,tidskompleksiteten er O (p). Husk, at det var en søgning efter brute-force O (p * t). Dermed, mønstersøgning bliver hurtigere efter forbehandling af teksten.

10. Konklusion

I denne artikel forstod vi først begreberne med tre datastrukturer - trie, suffiks trie og suffiksetræ. Vi så derefter, hvordan et suffiksetræ kunne bruges til kompakt lagring af suffikser.

Senere så vi, hvordan man bruger et suffiks-træ til at gemme data og udføre en mønstersøgning.

Som altid er kildekoden med tests tilgængelig på GitHub.