streamalism.org

1. Áttekintés

Ebben az oktatóanyagban feltárjuk a húrok minták illesztésének koncepcióját és annak gyorsabbá tételét. Ezután áttekintjük a Java-ban történő megvalósítását.

2. A húrok mintaillesztése

2.1. Meghatározás

A karaktersorozatokban a mintaillesztés az a folyamat, amelynek során ellenőrizzük az úgynevezett karakterek sorozatát egy minta az úgynevezett karaktersorozatban szöveg.

A mintaillesztés alapvető elvárásai, ha a minta nem szabályos kifejezés:

• a mérkőzésnek pontosnak kell lennie - nem részlegesnek
• az eredménynek tartalmaznia kell az összes mérkőzést - nemcsak az első mérkőzést
• az eredménynek tartalmaznia kell az egyes mérkőzések pozícióját a szövegen belül

2.2. Minta keresése

Használjunk egy példát egy egyszerű mintaillesztési probléma megértésére:

Minta: NA Szöveg: HAVANABANANA Match1: ---- NA ------ Match2: -------- NA-- Match3: ---------- NA

Láthatjuk, hogy a minta NA háromszor fordul elő a szövegben. Ennek az eredménynek az elérésére gondolhatunk, hogy a mintát egy karakterrel lefelé csúsztatjuk le a szövegben, és ellenőrizzük az egyezést.

Ez azonban brutális erő-megközelítés, időbeli összetettséggel Dönt) hol o a minta hossza, és t a szöveg hossza.

Tegyük fel, hogy több mintát kell keresnünk. Ezután az idő bonyolultsága lineárisan növekszik is, mivel minden mintához külön iterációra lesz szükség.

2.3. Trie adatstruktúra a minták tárolásához

Javíthatjuk a keresési időt azáltal, hogy a mintákat egy trie adatstruktúrában tároljuk, amely ismert a gyors visszajelzésérőltrietételek val.

Tudjuk, hogy a trie adatstruktúra egy karaktersorozat karaktereit egy faszerű struktúrában tárolja. Tehát két húrra {NA, NAB}, kapunk egy fát két utat:

A létrehozott trie lehetővé teszi a minták egy csoportjának lecsúsztatását a szövegben és az egyezéseket egyetlen iterációban.

Vegyük észre, hogy a $ karakter a karakterlánc végének jelzésére.

2.4. Utótagolja a Trie adatstruktúráját a szöveg tárolásához

A utótag triemásrészt egy trie adatstruktúra egyetlen húr összes lehetséges utótagjának felhasználásával készült.

Az előző példához HAVANABANANA, felépíthetünk egy trie utótagot:

Az utótag próbálkozások a szöveghez jönnek létre, és általában egy előfeldolgozási lépés részeként kerülnek végrehajtásra. Ezt követően a minták keresése gyorsan elvégezhető a minta szekvenciájának megfelelő útvonal megtalálásával.

A trie utótag azonban köztudottan sok helyet foglal el, mivel a húr minden karaktere egy élben van tárolva.

A következő szakaszban megnézzük a trie utótag továbbfejlesztett változatát.

3. Utótagfa

Utótag fa egyszerűen a tömörített utótag trie. Ez azt jelenti, hogy az élek összekapcsolásával egy karaktercsoportot tárolhatunk, és ezáltal jelentősen csökkenthetjük a tárhelyet.

Tehát létrehozhatunk utótagfát ugyanarra a szövegre HAVANABANANA:

A gyökértől a levélig kezdődő minden út a sztring utótagját jelenti HAVANABANANA.

Utótagfát is eltárolja az utótag helyzetét a levélcsomópontban. Például, BANANA $ a hetedik pozíciótól kezdődő utótag. Ennélfogva értéke nulla alapú számozással hat lesz. Hasonlóképpen, A-> BANANA $ egy másik utótag, amely az ötödik pozícióból indul ki, amint azt a fenti képen látjuk.

Tehát a dolgokat perspektívába helyezve ezt láthatjuk mintaillesztés akkor következik be, amikor a gyökércsomóponttól kezdve elérhetünk egy utat, amelynek élei teljesen megfelelnek az adott mintának.

Ha az út egy levélcsomópontnál végződik, akkor utótag-egyezést kapunk. Ellenkező esetben csak egy szubstring egyezést kapunk. Például a minta NA utótagja HAVANABANA [NA] és annak egy sztringje HAVA [NA] BANANA.

A következő szakaszban megnézzük, hogyan lehet ezt az adatstruktúrát megvalósítani a Java-ban.

4. Adatszerkezet

Hozzunk létre utótag-fa adatszerkezetet. Két domain osztályra lesz szükségünk.

Először is szükségünk van a osztály a fa csomópont képviseletére. Tárolnia kell a fa széleit és gyermekcsomópontjait. Ezenkívül, ha levélcsomópontról van szó, el kell tárolnia az utótag helyzeti értékét.

Tehát hozzuk létre a sajátunkat Csomópont osztály:

public class Csomópont {private String text; privát Lista gyerekek; magán int pozíció; public Node (Karaktersorozat, int pozíció) {this.text = szó; ez.pozíció = pozíció; this.children = new ArrayList (); } // getters, setters, toString ()}

Másodszor szükségünk van a osztály képviseli a fát és tárolja a gyökércsomópontot. Tárolnia kell a teljes szöveget is, amelyből az utótagok keletkeznek.

Következésképpen van egy SuffixTree osztály:

public class SuffixTree {private static final String WORD_TERMINATION = "$"; privát statikus végső int POSITION_UNDEFINED = -1; private Node gyökér; privát String fullText; public SuffixTree (String text) {root = new Node ("", POSITION_UNDEFINED); fullText = text; }}

5. Segítő módszerek az adatok hozzáadásához

Mielőtt megírnánk az alapvető logikánkat az adatok tárolására, adjunk hozzá néhány segítő módszert. Ezek később hasznosnak bizonyulnak.

Módosítsuk a SuffixTree osztályban a fa felépítéséhez szükséges néhány módszer hozzáadásához.

5.1. Gyermekcsomópont hozzáadása

Először is, legyen egy módszerünk addChildNode nak nek adjon hozzá új gyermekcsomópontot az adott szülőcsomóponthoz:

private void addChildNode (Csomópont parentNode, String text, int index) {parentNode.getChildren (). add (új Node (szöveg, index)); }

5.2. Két húr leghosszabb közös előtagjának megkeresése

Másodszor, írunk egy egyszerű segédprogram-módszert getLongestCommonPrefix nak nek keresse meg a két karakterlánc leghosszabb közös előtagját:

privát karakterlánc getLongestCommonPrefix (String str1, String str2) {int CompareLength = Math.min (str1.length (), str2.length ()); mert (int i = 0; i <összehasonlítHossz; i ++) {if (str1.charAt (i)! = str2.charAt (i)) {return str1.substring (0, i); }} return str1.substring (0, CompareLength); }

5.3. Csomópont felosztása

Harmadszor, legyen egy módszerünk faragni egy gyermek csomópontot az adott szülőtől. Ebben a folyamatban a szülő csomópontok szöveg Az érték csonkolva lesz, és a jobb csonka karakterlánc lesz a szöveg a gyermekcsomópont értéke. Ezenkívül a szülő gyermekei átkerülnek a gyermek csomópontjába.

Az alábbi képből láthatjuk ANA szétválik A-> NA. Utána az új utótag ABANANA $ hozzáadható A-> BANANA $:

Röviden, ez egy kényelmi módszer, amely hasznos lesz egy új csomópont beszúrásakor:

private void splitNodeToParentAndChild (Csomópont parentNode, String parentNewText, String childNewText) {Csomópont childNode = új Csomópont (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. Segítő módszer a bejárásra

Készítsük el most a fán való áthaladás logikáját. Ezt a módszert mind a fa felépítéséhez, mind a minták kereséséhez használjuk.

6.1. Részleges és teljes mérkőzés

Először értsük meg a részleges egyezés és a teljes egyezés fogalmát, figyelembe véve a néhány utótaggal benépesített fát:

Új utótag hozzáadása ANABANANA $, ellenőrizzük, hogy létezik-e olyan csomópont, amely módosítható vagy bővíthető az új érték befogadásához. Ehhez összehasonlítjuk az új szöveget az összes csomóponttal, és megállapítjuk, hogy a meglévő csomópont [A] VANABANANA $ egyezik az első karakterrel. Tehát ez az a csomópont, amelyet módosítanunk kell, és ezt az egyezést részleges egyezésnek nevezhetjük.

Másrészt vegyük figyelembe, hogy a mintát keressük LAPÁT ugyanazon a fán. Tudjuk, hogy részben egyezik a [VAN] ABANANA $ az első három karakteren. Ha mind a négy karakter egyezik, akkor teljes meccsnek nevezhetjük. A minta kereséséhez teljes egyezésre van szükség.

Összefoglalva tehát a fa felépítésekor részleges egyezést, a minták keresésekor pedig teljes egyezést fogunk használni. Zászlót fogunk használni isAllowPartialMatch hogy minden esetben megadjuk, hogy milyen meccsre van szükségünk.

6.2. A fán való áthaladás

Most írjuk meg a logikánkat, hogy addig haladjunk a fán, amíg képesek vagyunk egy adott mintát helyileg egyeztetni:

A getAllNodesInTraversePath (karakterláncminta, Node startNode, logikai isAllowPartialMatch) {// ...} lista

Ezt rekurzív módon hívjuk, és visszaküldjük az összes listát csomópontok utunkon találunk.

Először összehasonlítjuk a mintaszöveg első karakterét a csomópont szövegével:

if (minta.charAt (0) == nodeText.charAt (0)) {// logika a többi karakter kezeléséhez} 

Részleges egyezés esetén, ha a minta rövidebb vagy egyenlő a csomópont szövegével, hozzáadjuk az aktuális csomópontot a mi csomópontunkhoz csomópontok listázzon és álljon meg itt:

if (isAllowPartialMatch && pattern.length () <= nodeText.length ()) {nodes.add (currentNode); visszatérő csomópontok; } 

Ezután összehasonlítjuk ennek a csomópontszövegnek a többi karakterét a mintával. Ha a mintának van egy pozícióbeli eltérése a csomópont szövegével, itt állunk meg. Az aktuális csomópont benne van csomópontok csak részleges egyezés esetén:

int CompareLength = Math.min (nodeText.length (), pattern.length ()); mert (int j = 1; j <összehasonlítHossz; j ++) {if (minta.charAt (j)! = nodeText.charAt (j)) {if (isAllowPartialMatch) {csomópontok.add (currentNode); } visszatérési csomópontok; }} 

Ha a minta megegyezett a csomópont szövegével, hozzáadjuk az aktuális csomópontot a mi csomópontunkhoz csomópontok lista:

csomópontok.add (currentNode);

De ha a mintának több karaktere van, mint a csomópont szövege, akkor ellenőriznünk kell a gyermek csomópontjait. Ehhez rekurzív hívást kezdeményezünk a currentNode mint a kezdő csomópont és a minta mint az új minta. Az ebből a hívásból visszaküldött csomópontok listája a mellékletünkhöz tartozik csomópontok listát, ha nem üres. Abban az esetben, ha a teljes meccs forgatókönyve üres, ez azt jelenti, hogy eltérés történt, ezért ennek jelzéséhez hozzáadunk egy a-t nulla tétel. És visszaadjuk a csomópontok:

if (minta.hossz ()> összehasonlítHossz) {Csomópontok felsorolása2 = getAllNodesInTraversePath (minta.substring (összehasonlítHossz), currentNode, isAllowPartialMatch); if (csomópontok2.méret ()> 0) {csomópontok.addAll (csomópontok2); } else if (! isAllowPartialMatch) {csomópontok.add (null); }} visszatérési csomópontok;

Mindezt összerakva alkossunk getAllNodesInTraversePath:

privát lista getAllNodesInTraversePath (karakterlánc minta, Csomópont startNode, logikai isAllowPartialMatch) {List csomópontok = új ArrayList (); for (int i = 0; i <startNode.getChildren (). size (); i ++) {Node currentNode = startNode.getChildren (). get (i); Karakterlánc nodeText = currentNode.getText (); if (minta.charAt (0) == nodeText.charAt (0)) {if (isAllowPartialMatch && pattern.length () <= nodeText.length ()) {csomópontok.add (currentNode); visszatérő csomópontok; } int CompareLength = Math.min (nodeText.length (), pattern.length ()); for (int j = 1; j CompareLength) {Csomópontok listája2 = getAllNodesInTraversePath (pattern.substring (CompareLength), currentNode, isAllowPartialMatch); if (csomópontok2.méret ()> 0) {csomópontok.addAll (csomópontok2); } else if (! isAllowPartialMatch) {csomópontok.add (null); }} visszatérési csomópontok; }} visszatérési csomópontok; }

7. Algoritmus

7.1. Adatok tárolása

Most megírhatjuk logikánkat az adatok tárolására. Kezdjük egy új módszer definiálásával addSuffix a SuffixTree osztály:

private void addSuffix (karakterlánc utótag, int pozíció) {// ...}

A hívó megadja az utótag helyzetét.

Ezután írjuk meg az utótag kezelésének logikáját. Először ellenőriznünk kell, hogy létezik-e olyan útvonal, amely részben illeszkedik az utótaghoz legalább a segítő módszerünk felhívásával getAllNodesInTraversePath val vel isAllowPartialMatch beállítva igaz. Ha nincs útvonal, hozzáadhatjuk utótagunkat gyermekként a gyökérhez:

Csomópontok listája = getAllNodesInTraversePath (minta, gyökér, igaz); if (csomópontok.méret () == 0) {addChildNode (gyökér, utótag, pozíció); }

Azonban, ha létezik útvonal, ez azt jelenti, hogy módosítanunk kell egy meglévő csomópontot. Ez a csomópont lesz az utolsó csomópontok lista. Ki kell találnunk azt is, hogy mi legyen ennek a meglévő csomópontnak az új szövege. Ha a csomópontok a listának csak egy eleme van, akkor a utótag. Ellenkező esetben kizárjuk a közös előtagot az utolsó csomópontig a utótag hogy megkapja a newText:

Csomópont lastNode = csomópontok.remove (csomópontok.méret () - 1); String newText = utótag; if (nodes.size ()> 0) {String existingSuffixUptoLastNode = nodes.stream () .map (a -> a.getText ()) .reduce ("", String :: concat); newText = newText.substring (existingSuffixUptoLastNode.length ()); }

A meglévő csomópont módosításához hozzunk létre egy új módszert expandNode, amit onnan hívunk, ahol abbahagytuk addSuffix módszer. Ennek a módszernek két fő feladata van. Az egyik egy meglévő csomópont felosztása a szülő és a gyermek számára, a másik pedig egy gyermek hozzáadása az újonnan létrehozott szülő csomóponthoz. A szülőcsomópontot csak azért bontjuk fel, hogy közös csomópont legyen az összes gyermekcsomópont számára. Tehát új módszerünk készen áll:

private void expandNode (Csomópont csomópont, String newText, int pozíció) {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 (csomópont, parentText, childText); } String paliekText = newText.substring (commonPrefix.length ()); addChildNode (csomópont, maradtText, pozíció); }

Most visszatérhetünk az utótag hozzáadására vonatkozó módszerünkhöz, amelynek most már minden logikája a helyén van:

private void addSuffix (String utótag, int pozíció) {Csomópontok listája = getAllNodesInTraversePath (utótag, gyökér, true); if (csomópontok.méret () == 0) {addChildNode (gyökér, utótag, pozíció); } else {Csomópont lastNode = csomópontok.eltávolítás (csomópontok.méret () - 1); String newText = utótag; if (nodes.size ()> 0) {String existingSuffixUptoLastNode = nodes.stream () .map (a -> a.getText ()) .reduce ("", String :: concat); newText = newText.substring (existingSuffixUptoLastNode.length ()); } expandNode (lastNode, newText, position); }}

Végül módosítsuk SuffixTree konstruktor az utótagok előállításához és az előző módszerünk meghívásához addSuffix hogy iteratív módon hozzáadjuk őket az adatstruktúránkhoz:

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. Adatok keresése

Miután meghatároztuk utótag-fa struktúránkat az adatok tárolására, most megírhatjuk a keresés végrehajtásának logikáját.

Egy új módszer hozzáadásával kezdjük searchText a SuffixTree osztályban, a minta keresni bemenetként:

public List searchText (karakterlánc minta) {// ...}

Ezután ellenőrizze, hogy a minta utótagfánkban létezik, hívjuk segítő módszerünket getAllNodesInTraversePath csak a pontos egyezésekre beállított zászlóval, ellentétben az adatok hozzáadásával, amikor részleges egyezéseket engedélyeztünk:

Csomópontok listája = getAllNodesInTraversePath (minta, gyökér, hamis);

Ezután megkapjuk a mintánknak megfelelő csomópontok listáját. A lista utolsó csomópontja azt a csomópontot jelöli, amelyhez a minta pontosan illeszkedik. Tehát a következő lépésünk az lesz, hogy megszerezzük az összes egyező csomópontból származó levélcsomópontot, és megkapjuk az ezekben a levélcsomópontokban tárolt pozíciókat.

Hozzunk létre egy külön módszert getPositions ezt csináld meg. Megvizsgáljuk, hogy az adott csomópont tárolja-e az utótag utolsó részét, hogy eldöntsük, vissza kell-e adni a pozíció értékét. Ezt rekurzív módon meg fogjuk tenni az adott csomópont minden gyermekének:

privát lista getPositions (csomópont csomópont) {Lista pozíciók = új ArrayList (); if (csomópont.getText (). végződik (WORD_TERMINATION)) {pozíciók.add (csomópont.getPosition ()); } for (int i = 0; i <csomópont.getChildren (). size (); i ++) {pozíciók.addAll (getPositions (node.getChildren (). get (i))); } visszatérő pozíciók; }

Miután megvan a pozíciók halmaza, a következő lépés az, hogy ezzel jelöljük a mintákat az utótagfánkban tárolt szövegre. A pozíció értéke jelzi, hogy hol kezdődik az utótag, és a minta hossza azt jelzi, hogy hány karaktert kell eltolni a kezdőponttól. Ezen logika alkalmazásával hozzunk létre egy egyszerű segédprogram-módszert:

privát karakterlánc markPatternInText (egész kezdőpozíció, karakterláncminta) {String matchingTextLHS = fullText.substring (0, startPosition); String matchingText = fullText.substring (startPosition, startPosition + pattern.length ()); String matchingTextRHS = fullText.substring (startPosition + minta.length ()); return matchingTextLHS + "[" + matchingText + "]" + matchingTextRHS; }

Most elkészültek támogató módszereink. Ebből kifolyólag, felvehetjük őket a keresési módszerünkbe, és kiegészíthetjük a logikát:

public List searchText (String pattern) {Lista eredménye = new ArrayList (); Csomópontok listája = getAllNodesInTraversePath (minta, gyökér, hamis); if (csomópontok.méret ()> 0) {Csomópont lastNode = csomópontok.get (csomópontok.méret () - 1); if (lastNode! = null) {List pozíciók = getPositions (lastNode); pozíciók = pozíciók.folyam () .rendezve () .collect (Collectors.toList ()); position.forEach (m -> eredmény.add ((markPatternInText (m, minta)))); }} visszatérési eredmény; }

8. Tesztelés

Most, hogy az algoritmusunk a helyén van, teszteljük.

Először tároljunk egy szöveget a SuffixTree:

SuffixTree suffixTree = új SuffixTree ("havanabanana"); 

Ezután keressünk érvényes mintát a:

Lista egyezés = suffixTree.searchText ("a"); match.stream (). forEach (m -> LOGGER.info (m));

A kód futtatása a várakozásoknak megfelelően hat mérkőzést eredményez:

h [a] vanabanana hav [a] nabanana havan [a] banán havanab [a] nana havanaban [a] na havanabanan [a]

Ezután menjünk keressen egy másik érvényes mintát elcsíp:

A mérkőzések felsorolása = suffixTree.searchText ("nab"); match.stream (). forEach (m -> LOGGER.info (m)); 

A kód futtatása a várakozásoknak megfelelően csak egy mérkőzést eredményez:

hava [nab] anana

Végül pedig érvénytelen minta keresése gebe:

A mérkőzések felsorolása = suffixTree.searchText ("nag"); match.stream (). forEach (m -> LOGGER.info (m));

A kód futtatása nem eredményez bennünket. Látjuk, hogy a mérkőzéseknek pontosaknak és nem részlegeseknek kell lenniük.

Így a minta keresési algoritmusunk képes volt kielégíteni az összes elvárást, amelyet a bemutató elején megfogalmaztunk.

9. Az idő komplexitása

Amikor egy utótagfát szerkesztünk egy adott hosszúságú szöveghez t, a az idő bonyolultsága az O (t).

Ezután hosszminta keresésére p,az idő bonyolultsága az O (p). Emlékezz rá, hogy egy brutális erő keresésére az volt Dönt). Így, a minták keresése gyorsabbá válik a szöveg előzetes feldolgozása után.

10. Következtetés

Ebben a cikkben először három adatstruktúra - trie, trie utótag és utótagfa - fogalmát értettük meg. Ezután láttuk, hogyan lehet egy utótagfát használni az utótagok kompakt tárolásához.

Később láttuk, hogyan kell egy utótagfát használni az adatok tárolására és a mintakeresésre.

Mint mindig, a tesztekkel ellátott forráskód is elérhető a GitHubon.