streamalism.org

1. Áttekintés

Ebben a gyors bemutatóban megmutatjuk, hogyan működik a mintaillesztéses motor. Az optimalizálás különféle módjait is bemutatjuk reguláris kifejezések Java-ban.

Bevezetés a reguláris kifejezések, kérjük, olvassa el ezt a cikket itt.

2. A mintaillesztõ motor

A java.util.regex A csomag a mintának megfelelő motortípust használja Nemdeterminisztikus véges automatika (NFA). Fontosnak tartják nem meghatározó mert miközben megpróbálunk egy szabályos kifejezést illeszteni egy adott karaktersorozatba, a bemenet minden karakterét többször is ellenőrizhetjük a reguláris kifejezés különböző részeivel.

A háttérben a fent említett motor használ visszalépés. Ez az általános algoritmus minden lehetőséget megpróbál kimeríteni, amíg kudarcot nem nyilvánít. Fontolja meg a következő példát, hogy jobban megértse a NFA:

"tra (vel | ce | de) m"

A bemenettel Húr “utazás„, A motor először keresitra”És azonnal megtalálja.

Ezután megpróbál megfelelnivel”A negyedik karaktertől kezdve. Ez meg fog egyezni, így megy előre, és megpróbáljam“.

Ez nem fog egyezni, és emiatt visszatér a negyedik karakterre, és a következőre keres:ce“. Ez megint nem fog egyezni, így visszatér a negyedik helyre, és megpróbálja a következővel:de“. Ez a karakterlánc sem fog egyezni, ezért visszatér a beviteli karakterlánc második karakteréhez, és megpróbál keresni egy másiktra“.

A legutóbbi hiba esetén az algoritmus visszaállítja a hibát.

Az egyszerű utolsó példával a motornak többször kellett visszalépnie, miközben megpróbált egyeztetni a bemenettel Húr a reguláris kifejezésre. Amiatt, fontos, hogy minimalizáljuk a visszalépés mennyiségét.

3. Az optimalizálás módjai Reguláris kifejezések

3.1. Kerülje az újrafordítást

A Java rendszeres kifejezései belső adatstruktúrává állnak össze. Ez az összeállítás időigényes folyamat.

Valahányszor a String.matches (String regex) módszerrel a megadott reguláris kifejezés újrafordításra kerül:

if (input.matches (regexPattern)) {// csináljon valamit}

Mint láthatjuk, a feltétel kiértékelésekor a regex kifejezést állítják össze.

Az optimalizálás érdekében először összeállíthatja a mintát, majd létrehozhatja a Matcher hogy megtalálja az érték egybeeséseit:

Mintaminta = Pattern.compile (regexPattern); for (String érték: értékek) {Matcher matcher = minta.matcher (érték); if (matcher.matches ()) {// csináljon valamit}}

A fenti optimalizálás alternatívája ugyanaz Matcher például annak Visszaállítás() módszer:

Mintaminta = Pattern.compile (regexPattern); Matcher matcher = minta.matcher (""); for (String érték: értékek) {matcher.reset (érték); if (matcher.matches ()) {// csináljon valamit}}

A tény miatt Matcher nem biztonságos a menet, óvatosnak kell lennünk ennek a variációnak a használatával. Többszálú esetekben valószínűleg veszélyes lehet.

Összefoglalva: minden olyan helyzetben, ahol biztosak vagyunk abban, hogy a felhasználónak csak egy felhasználója van Matcher bármely időpontban rendben van vele újrafelhasználás Visszaállítás. A többire elegendő az előre lefordított adatok újrafelhasználása.

3.2. Munka az alternációval

Amint éppen az utolsó részben ellenőriztük, a váltakozások nem megfelelő használata káros lehet a teljesítményre. Fontos, hogy olyan opciókat helyezzen el, amelyek nagyobb eséllyel történnek, hogy gyorsabban illeszthessék őket.

Ezenkívül közös mintákat kell kivonnunk közöttük. Nem ugyanaz a fogalmazás:

(utazás | kereskedelem | nyom)

Mint:

tra (vel | de | ce)

Ez utóbbi gyorsabb, mert a NFA megpróbál megfelelnitra”, És nem fogja kipróbálni egyik alternatívát sem, ha nem találja meg.

3.3. Csoportok rögzítése

Valahányszor csoportokat ragadunk meg, kis időre kiszabott büntetés jár.

Ha nem kell a szöveget rögzítenünk egy csoporton belül, akkor fontolóra kell venni a nem elfogó csoportok használatát. Helyett(M)", kérlek használd "(?: M)“.

4. Következtetés

Ebben a gyors cikkben röviden áttekintettük, hogyan NFA művek. Ezután azt kutattuk, hogyan lehet optimalizálni a reguláris kifejezéseink teljesítményét azáltal, hogy előre összeállítjuk a mintáinkat és újrafelhasználjuk a Matcher.

Végül rámutattunk néhány szempontra, amelyet szem előtt kell tartani, miközben váltakozással és csoportokkal dolgozunk.

Szokás szerint a teljes forráskód megtalálható a GitHubon.