streamalism.org

1. Prehľad

V tomto tutoriále preskúmame koncept párovania vzorov reťazcov a ako to môžeme urýchliť. Potom si prejdeme jeho implementáciu v Jave.

2. Zosúladenie vzorov strún

2.1. Definícia

V reťazcoch je porovnávanie vzorov proces kontroly zadanej postupnosti volaných znakov vzor v postupnosti znakov nazývaných a text.

Základné očakávania zhody vzorov, keď vzor nie je regulárny výraz, sú:

• zhoda by mala byť presná - nie čiastočná
• výsledok by mal obsahovať všetky zhody - nielen prvý zápas
• výsledok by mal obsahovať pozíciu každej zhody v texte

2.2. Hľadá sa vzor

Použime príklad na pochopenie jednoduchého problému so zhodou vzorov:

Vzor: NA Text: HAVANABANANA Zápas 1: ---- NA ------ Zápas 2: -------- NA-- Zápas 3: ---------- NA

Môžeme vidieť, že vzor NA sa v texte vyskytuje trikrát. Aby sme dosiahli tento výsledok, môžeme uvažovať o posúvaní vzoru nadol po texte po jednom znaku a kontrole zhody.

Jedná sa však o prístup hrubou silou s časovou zložitosťou O (p * t) kde p je dĺžka vzoru a t je dĺžka textu.

Predpokladajme, že máme viac ako jeden vzor na hľadanie. Potom sa časová zložitosť tiež lineárne zvyšuje, pretože každý vzor bude vyžadovať samostatnú iteráciu.

2.3. Štruktúra údajov pre ukladanie vzorov

Čas vyhľadávania môžeme zlepšiť uložením vzorov do dátovej štruktúry trie, ktorá je známa svojim rýchlym opätovným načítanímtrieval položiek.

Vieme, že štruktúra údajov trie ukladá znaky reťazca do stromovej štruktúry. Teda na dve struny {NA, NAB}, dostaneme strom s dvoma cestami:

Vytvorenie trie umožňuje zosunúť skupinu vzorov nadol po texte a skontrolovať zhody iba v jednej iterácii.

Všimnite si, že používame $ znak označujúci koniec reťazca.

2.4. Prípona Trie dátová štruktúra na uloženie textu

A prípona trie, na druhej strane, je trie dátová štruktúra skonštruované pomocou všetkých možných prípon jedného reťazca.

Pre predchádzajúci príklad HAVANABANANA, môžeme skonštruovať príponu trie:

Pokusy o príponu sa vytvárajú pre text a zvyčajne sa robia ako súčasť kroku predspracovania. Potom možno hľadať vzory rýchlo vyhľadaním cesty zodpovedajúcej sekvencii vzorov.

Je však známe, že přípona trie zaberá veľa miesta, pretože každý znak reťazca je uložený na okraji.

Na vylepšenú verziu prípony trie sa pozrieme v nasledujúcej časti.

3. Príponový strom

Prípona strom je jednoducho a komprimovaná prípona trie. To znamená, že spojením hrán môžeme uložiť skupinu znakov, a tým výrazne zmenšiť úložný priestor.

Môžeme teda vytvoriť strom prípon pre ten istý text HAVANABANANA:

Každá cesta začínajúca od koreňa po list predstavuje príponu reťazca HAVANABANANA.

Príponový strom tiež ukladá pozíciu prípony v listovom uzle. Napríklad, BANANA $ je prípona začínajúca od siedmej pozície. Jeho hodnota bude teda pri číslovaní založenom na nule šesť. Podobne, A-> BANÁNY $ je ďalšia prípona začínajúca na pozícii päť, ako vidíme na obrázku vyššie.

Ak teda uvedieme veci na pravú mieru, vidíme to zhoda vzoru nastane, keď sme schopní získať cestu začínajúcu od koreňového uzla s hranami, ktoré sa úplne zodpovedajú danému vzoru pozične.

Ak cesta končí na uzle listu, dostaneme zhodu prípony. V opačnom prípade dostaneme iba striedajúci zápas. Napríklad vzor NA je prípona HAVANABANA [NA] a podreťazec HAVA [NA] BANANA.

V nasledujúcej časti uvidíme, ako implementovať túto dátovú štruktúru v Jave.

4. Štruktúra údajov

Vytvorme dátovú štruktúru stromu prípon. Budeme potrebovať dve doménové triedy.

Po prvé, potrebujeme a triedy, ktorá predstavuje uzol stromu. Potrebuje uložiť okraje stromu a jeho podradené uzly. Ďalej, keď je to listový uzol, musí si uložiť pozičnú hodnotu prípony.

Poďme teda vytvoriť náš Uzol trieda:

verejná trieda Uzol {súkromný text reťazca; súkromný zoznam detí; súkromná int pozícia; verejný uzol (reťazcové slovo, int pozícia) {this.text = slovo; this.position = position; this.children = new ArrayList (); } // getre, setre, toString ()}

Po druhé, potrebujeme triedy, ktorá predstavuje strom a ukladá koreňový uzol. Je tiež potrebné uložiť celý text, z ktorého sú generované prípony.

V dôsledku toho máme a SuffixTree trieda:

verejná trieda SuffixTree {private static final String WORD_TERMINATION = "$"; súkromný statický konečný int POSITION_UNDEFINED = -1; privátny koreň uzla; private String fullText; public SuffixTree (text reťazca) {root = new Node ("", POSITION_UNDEFINED); fullText = text; }}

5. Pomocné metódy pre pridávanie údajov

Predtým, ako napíšeme svoju základnú logiku na ukladanie údajov, pridajme niekoľko pomocných metód. Neskôr sa ukážu ako užitočné.

Upravme naše SuffixTree triedy na pridanie niektorých metód potrebných na zostavenie stromu.

5.1. Pridanie podriadeného uzla

Po prvé, poďme mať metódu addChildNode do pridať nový podradený uzol do ľubovoľného nadradeného uzla:

private void addChildNode (uzol parentNode, text reťazca, int index) {parentNode.getChildren (). add (nový uzol (text, index)); }

5.2. Nájdenie najdlhšej spoločnej predvoľby dvoch reťazcov

Po druhé, napíšeme jednoduchú metódu obsluhy getLongestCommonPrefix do nájsť najdlhšiu spoločnú predponu dvoch reťazcov:

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); }} návrat str1.substring (0, porovnajDĺžka); }

5.3. Rozdelenie uzla

Po tretie, poďme mať metódu vybojovať podriadený uzol od daného rodiča. V tomto procese je nadradený uzol text hodnota bude skrátená a zprava skrátený reťazec sa stane text hodnota podradeného uzla. Ďalej sa deti rodiča prenesú do podriadeného uzla.

To vidíme z obrázku nižšie ANA sa rozdelí na A-> NA. Potom nová prípona ABANANA $ možno pridať ako A-> BANÁNY $:

Stručne povedané, jedná sa o pohodlnú metódu, ktorá sa bude hodiť pri vkladaní nového uzla:

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. Pomocná metóda prechodu

Vytvorme teraz logiku prechodu stromom. Túto metódu použijeme pri konštrukcii stromu aj pri hľadaní vzorov.

6.1. Čiastočná a úplná zhoda

Po prvé, poďme pochopiť koncept čiastočnej a úplnej zhody zvážením stromu naplneného niekoľkými príponami:

Ak chcete pridať novú príponu ANABANANA $, skontrolujeme, či existuje nejaký uzol, ktorý je možné upraviť alebo rozšíriť tak, aby vyhovoval novej hodnote. Za týmto účelom porovnáme nový text so všetkými uzlami a zistíme, že existuje uzol [A] VANABANANA $ zápasy pri prvom znaku. Toto je uzol, ktorý musíme upraviť, a túto zhodu možno nazvať čiastočnou zhodou.

Na druhej strane zvážme, že hľadáme vzor VANE na rovnakom strome. Vieme, že sa to čiastočne zhoduje s [VAN] ABANANA $ na prvé tri znaky. Keby sa všetky štyri postavy zhodovali, mohli by sme to nazvať úplnou zhodou. Pri vyhľadávaní vzorov je nevyhnutná úplná zhoda.

Ak to teda zhrnieme, pri konštrukcii stromu použijeme čiastočnú zhodu a pri hľadaní vzorov úplnú zhodu. Použijeme vlajku isAllowPartialMatch na označenie druhu zhody, ktorú v obidvoch prípadoch potrebujeme.

6.2. Traversing the Tree

Poďme teraz napísať našu logiku prechodu stromu, pokiaľ dokážeme zodpovedať danému vzoru pozične:

Zoznam getAllNodesInTraversePath (reťazcový vzor, ​​uzol startNode, boolean isAllowPartialMatch) {// ...}

Zavoláme to rekurzívne a vrátime zoznam všetkých uzly nachádzame v našej ceste.

Začneme porovnaním prvého znaku textu vzoru s textom uzla:

if (pattern.charAt (0) == nodeText.charAt (0)) {// logika na spracovanie zostávajúcich znakov} 

Pri čiastočnej zhode, ak je vzor kratší alebo rovnako dlhý ako text uzla, pridáme aktuálny uzol k nášmu uzly zoznam a zastavenie tu:

if (isAllowPartialMatch && pattern.length () <= nodeText.length ()) {nodes.add (currentNode); návratové uzly; } 

Potom porovnáme zostávajúce znaky tohto uzlového textu so znakmi vzoru. Ak má vzor nesúlad pozícií s textom uzla, zastavíme sa tu. Aktuálny uzol je zahrnutý v uzly zoznam iba pre čiastočnú zhodu:

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); } návratové uzly; }} 

Ak sa vzor zhodoval s textom uzla, pridáme aktuálny uzol do nášho uzly zoznam:

nodes.add (currentNode);

Ak má ale vzor viac znakov ako text uzla, musíme skontrolovať podradené uzly. Za týmto účelom urobíme rekurzívne volanie prechádzajúce cez currentNode ako východiskový uzol a zvyšná časť súboru vzor ako nový vzor. Zoznam uzlov vrátených z tohto hovoru je pripojený k nášmu uzly zoznam, ak nie je prázdny. V prípade, že je prázdny pre scenár úplnej zhody, znamená to, že došlo k nesúladu, preto na označenie toho pridáme a nulový položka. A vrátime uzly:

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); }} návratové uzly;

Keď to všetko spojíme, tvorme 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); Reťazec nodeText = currentNode.getText (); if (pattern.charAt (0) == nodeText.charAt (0)) {if (isAllowPartialMatch && pattern.length () <= nodeText.length ()) {nodes.add (currentNode); návratové uzly; } 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); }} návratové uzly; }} návratové uzly; }

7. Algoritmus

7.1. Ukladanie údajov

Teraz môžeme napísať našu logiku na ukladanie údajov. Začnime definovaním novej metódy addSuffix na SuffixTree trieda:

private void addSuffix (prípona reťazca, int pozícia) {// ...}

Volajúci poskytne polohu prípony.

Ďalej napíšeme logiku spracovania prípony. Najskôr musíme skontrolovať, či existuje cesta, ktorá čiastočne zodpovedá prípone aspoň zavolaním našej pomocnej metódy getAllNodesInTraversePath s isAllowPartialMatch nastaviť ako pravda. Ak neexistuje cesta, môžeme pridať našu príponu ako dieťa ku koreňu:

Zoznam uzlov = getAllNodesInTraversePath (vzor, ​​koreň, pravda); if (nodes.size () == 0) {addChildNode (root, sufix, position); }

Avšak ak cesta existuje, znamená to, že musíme upraviť existujúci uzol. Tento uzol bude posledný v uzle uzly zoznam. Musíme tiež zistiť, aký by mal byť nový text pre tento existujúci uzol. Ak uzly zoznam má iba jednu položku, potom použijeme prípona. V opačnom prípade vylúčime spoločnú predponu až po posledný uzol z prípona získať newText:

Uzol lastNode = nodes.remove (nodes.size () - 1); Reťazec newText = prípona; if (nodes.size ()> 0) {String existingSuffixUptoLastNode = nodes.stream () .map (a -> a.getText ()) .reduce ("", String :: concat); newText = newText.substring (existingSuffixUptoLastNode.length ()); }

Na úpravu existujúceho uzla vytvorme novú metódu extendNode, ktoré zavoláme z miesta, kde sme skončili addSuffix metóda. Táto metóda má dve kľúčové zodpovednosti. Jedným z nich je rozdelenie existujúceho uzla na rodiča a dieťa a druhým je pridanie dieťaťa do novovytvoreného nadradeného uzla. Nadradený uzol rozdelíme iba preto, aby sa stal spoločným uzlom pre všetky jeho podradené uzly. Naša nová metóda je teda pripravená:

private void extendNode (uzol uzla, reťazec newText, pozícia int) {String currentText = node.getText (); Reťazec commonPrefix = getLongestCommonPrefix (currentText, newText); if (commonPrefix! = currentText) {String parentText = currentText.substring (0, commonPrefix.length ()); Reťazec childText = currentText.substring (commonPrefix.length ()); splitNodeToParentAndChild (uzol, parentText, childText); } Reťazec zostávajúciText = novýText.substring (commonPrefix.length ()); addChildNode (uzol, zostávajúci text, pozícia); }

Teraz sa môžeme vrátiť k našej metóde pridávania prípony, ktorá má teraz zavedenú všetku logiku:

private void addSuffix (prípona reťazca, int pozícia) {List nodes = getAllNodesInTraversePath (prípona, root, true); if (nodes.size () == 0) {addChildNode (root, sufix, position); } else {Uzol lastNode = nodes.remove (nodes.size () - 1); Reťazec newText = prípona; if (nodes.size ()> 0) {String existingSuffixUptoLastNode = nodes.stream () .map (a -> a.getText ()) .reduce ("", String :: concat); newText = newText.substring (existingSuffixUptoLastNode.length ()); } extendNode (lastNode, newText, position); }}

Nakoniec si upravme našu SuffixTree konštruktor na generovanie prípon a volanie našej predchádzajúcej metódy addSuffix aby sme ich iteratívne pridali do našej dátovej štruktúry:

public void SuffixTree (text reťazca) {root = nový uzol ("", POSITION_UNDEFINED); pre (int i = 0; i <text.length (); i ++) {addSuffix (text.substring (i) + WORD_TERMINATION, i); } fullText = text; }

7.2. Vyhľadávanie údajov

Po definovaní našej stromovej štruktúry prípon na ukladanie údajov, teraz môžeme napísať logiku vykonávania nášho vyhľadávania.

Začneme pridaním novej metódy searchText na SuffixTree triedy, pričom sa vzor hľadať ako vstup:

verejný zoznam searchText (reťazcový vzor) {// ...}

Ďalej skontrolujte, či vzor existuje v našom strome prípon, nazývame našu pomocnú metódu getAllNodesInTraversePath s príznakom nastaveným iba na presné zhody, na rozdiel od pridávania údajov, keď sme povolili čiastočné zhody:

Zoznam uzlov = getAllNodesInTraversePath (vzor, ​​koreň, nepravda);

Potom dostaneme zoznam uzlov, ktoré zodpovedajú nášmu vzoru. Posledný uzol v zozname označuje uzol, ku ktorému sa vzor presne zhodoval. Naším ďalším krokom bude teda získanie všetkých listových uzlov pochádzajúcich z tohto posledného zhodného uzla a získanie pozícií uložených v týchto listových uzloch.

Vytvorme samostatnú metódu getPositions urobiť toto. Skontrolujeme, či daný uzol ukladá poslednú časť prípony, aby sme sa rozhodli, či je potrebné vrátiť hodnotu jeho polohy. Urobíme to rekurzívne pre každé dieťa daného uzla:

private List getPositions (Uzol uzol) {Pozície zoznamu = 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)))); } návratové pozície; }

Keď máme množinu pozícií, ďalším krokom je jej použitie na označenie vzorov na texte, ktorý sme uložili do nášho stromu prípon. Hodnota polohy označuje, kde prípona začína, a dĺžka vzoru označuje, koľko znakov sa má posunúť od začiatočného bodu. Pomocou tejto logiky vytvorme jednoduchú metódu obslužného programu:

private String markPatternInText (Integer startPosition, String pattern) {String matchingTextLHS = fullText.substring (0, startPosition); Reťazec matchingText = fullText.substring (startPosition, startPosition + pattern.length ()); Reťazec matchingTextRHS = fullText.substring (startPosition + pattern.length ()); vrátiť matchingTextLHS + "[" + matchingText + "]" + matchingTextRHS; }

Teraz máme pripravené podporné metódy. Preto môžeme ich pridať do našej metódy vyhľadávania a dokončiť logiku:

public List searchText (reťazcový vzor) {Výsledok zoznamu = nový ArrayList (); Zoznam uzlov = getAllNodesInTraversePath (vzor, ​​koreň, nepravda); if (nodes.size ()> 0) {Node lastNode = nodes.get (nodes.size () - 1); if (lastNode! = null) {Pozície zoznamu = getPositions (lastNode); pozície = polohy.prúd (). roztriedené () .collect (Collectors.toList ()); positions.forEach (m -> result.add ((markPatternInText (m, pattern)))); }} vrátiť výsledok; }

8. Testovanie

Teraz, keď máme náš algoritmus zavedený, otestujme ho.

Najskôr si uložme text do nášho SuffixTree:

SuffixTree suffixTree = nový SuffixTree ("havanabanana"); 

Ďalej hľadajme platný vzor a:

Zoznam zápasov = suffixTree.searchText ("a"); match.stream (). forEach (m -> LOGGER.info (m));

Spustenie kódu nám dáva šesť zápasov podľa očakávaní:

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

Ďalej, poďme hľadať iný platný vzor nab:

Zoznam zápasov = suffixTree.searchText ("nab"); match.stream (). forEach (m -> LOGGER.info (m)); 

Spustenie kódu nám dá podľa očakávaní iba jednu zhodu:

hava [nab] anana

Nakoniec poďme hľadať neplatný vzor nag:

Zoznam zápasov = suffixTree.searchText ("nag"); match.stream (). forEach (m -> LOGGER.info (m));

Spustenie kódu nám neprináša žiadne výsledky. Vidíme, že zhody musia byť presné a nie čiastočné.

Náš algoritmus vyhľadávania vzorov teda dokázal uspokojiť všetky očakávania, ktoré sme si stanovili na začiatku tohto tutoriálu.

9. Časová zložitosť

Pri konštrukcii stromu prípon pre daný text dĺžky t, časová zložitosť je O (t).

Potom na hľadanie vzoru dĺžky p,časová zložitosť je O (p). Pamätajte, že pri hľadaní hrubou silou to bolo O (p * t). Teda vyhľadávanie vzorov sa zrýchli po predbežnom spracovaní textu.

10. Záver

V tomto článku sme najskôr pochopili koncepty troch dátových štruktúr - trie, prípona trie a strom prípon. Potom sme videli, ako je možné použiť strom prípon na kompaktné ukladanie prípon.

Neskôr sme videli, ako použiť strom prípon na ukladanie údajov a vyhľadávanie vzorov.

Ako vždy, zdrojový kód s testami je k dispozícii na GitHub.