streamalism.org

1. Bemutatkozás

Ebben a cikkben számos algoritmust mutatunk be egy minta keresésére egy nagy szövegben. Leírjuk az egyes algoritmusokat a megadott kóddal és egyszerű matematikai háttérrel.

Vegye figyelembe, hogy a megadott algoritmusok nem a legjobb módja a teljes szöveges keresésnek a bonyolultabb alkalmazásokban. A teljes szöveges keresés megfelelő elvégzéséhez használhatjuk a Solr vagy az ElasticSearch alkalmazást.

2. Algoritmusok

Kezdjük egy naiv szöveges keresési algoritmussal, amely a leg intuitívabb, és segít felfedezni az adott feladattal kapcsolatos egyéb speciális problémákat.

2.1. Segítő módszerek

Mielőtt elkezdenénk, definiáljunk egyszerű módszereket a Rabin Karp algoritmusban használt prímszámok kiszámításához:

public static long getBiggerPrime (int m) {BigInteger prime = BigInteger.probablePrime (getNumberOfBits (m) + 1, új Random ()); return prime.longValue (); } privát statikus int getNumberOfBits (int szám) {return Integer.SIZE - Integer.numberOfLeadingZeros (szám); } 

2.2. Egyszerű szöveges keresés

Az algoritmus neve jobban leírja, mint bármely más magyarázat. Ez a legtermészetesebb megoldás:

public static int simpleTextSearch (char [] minta, char [] text) {int patternSize = minta.hossz; int textSize = szöveg.hossz; int i = 0; míg (((i + patternSize) = patternSize) visszatér i; } i + = 1; } return -1; }

Ennek az algoritmusnak az ötlete egyszerű: ismételje meg a szöveget, és ha egyezik a minta első betűje, ellenőrizze, hogy a minta összes betűje megegyezik-e a szöveggel.

Ha m a mintában szereplő betűk száma, és n a betűk száma a szövegben, az algoritmusok időbeli összetettsége O (m (n-m + 1)).

Legrosszabb eset az a esetén fordul elő Húr sok részleges előfordulás:

Szöveg: baeldunbaeldunbaeldunbaeldun Minta: baeldung

2.3. Rabin Karp algoritmus

Mint fentebb említettük, az Egyszerű szöveges keresés algoritmus nagyon nem hatékony, ha a minták hosszúak, és ha a minta sok ismétlődő elemet tartalmaz.

A Rabin Karp algoritmus ötlete az, hogy kivonatolással keressen mintát a szövegben. Az algoritmus elején ki kell számolnunk a minta hash-ját, amelyet később az algoritmusban használnak. Ezt a folyamatot ujjlenyomat-számításnak hívják, itt részletes magyarázatot találhatunk.

Az előfeldolgozási lépésben az a fontos, hogy időbeli összetettsége igen O (m) és a szöveges iteráció eltart Tovább) amely az egész algoritmus időbeli összetettségét adja O (m + n).

Az algoritmus kódja:

public static int RabinKarpMethod (char [] minta, char [] text) {int patternSize = minta.hossz; int textSize = szöveg.hossz; hosszú prím = getBiggerPrime (patternSize); hosszú r = 1; mert (int i = 0; i <patternSize - 1; i ++) {r * = 2; r = r% prim; } long [] t = új long [textSize]; t [0] = 0; hosszú pfinger = 0; for (int j = 0; j <patternSize; j ++) {t [0] = (2 * t [0] + szöveg [j])% prím; pfinger = (2 * pfinger + minta [j])% prim; } int i = 0; logikai átadott = hamis; int diff = textSize - patternSize; for (i = 0; i <= diff; i ++) {if (t [i] == pfinger) {megfelelt = igaz; for (int k = 0; k <patternSize; k ++) {if (szöveg [i + k]! = minta [k]) {átadott = hamis; szünet; }} if (megfelelt) {return i; }} if (i <diff) {hosszú érték = 2 * (t [i] - r * text [i]) + text [i + patternSize]; t [i + 1] = ((%% prime) + prime)% prime; }} return -1; }

A legrosszabb esetben az algoritmus időbeli összetettsége igen O (m (n-m + 1)). Ennek az algoritmusnak azonban átlagosan van O (n + m) az idő bonyolultsága.

Ezen kívül létezik ennek az algoritmusnak a Monte Carlo verziója, amely gyorsabb, de rossz egyezéseket (hamis pozitívumokat) eredményezhet.

2.4 Knuth-Morris-Pratt algoritmus

Az Egyszerű szöveges keresés algoritmusban láttuk, hogyan lehet az algoritmus lassú, ha a szövegnek sok olyan része van, amely megfelel a mintának.

A Knuth-Morris-Pratt algoritmus ötlete a shift tábla kiszámítása, amely információt szolgáltat számunkra, ahol a jelöltjeinket kell keresnünk.

A KMP algoritmus Java megvalósítása:

public static int KnuthMorrisPrattSearch (char [] minta, char [] szöveg) {int patternSize = minta.hossz; int textSize = szöveg.hossz; int i = 0, j = 0; int [] shift = KnuthMorrisPrattShift (minta); míg (((i + patternSize) = patternSize) visszatér i; } if (j> 0) {i + = eltolás [j - 1]; j = Math.max (j - eltolás [j - 1], 0); } else {i ++; j = 0; }} return -1; }

És így számoljuk ki a váltástáblát:

public static int [] KnuthMorrisPrattShift (char [] minta) {int patternSize = minta.hossz; int [] shift = új int [patternSize]; eltolás [0] = 1; int i = 1, j = 0; míg ((i + j)  0) {i = i + shift [j - 1]; j = Math.max (j - eltolás [j - 1], 0); } else {i = i + 1; j = 0; }}} visszatérő műszak; }

Ezen algoritmus időbeli összetettsége is O (m + n).

2.5. Egyszerű Boyer-Moore algoritmus

Két tudós, Boyer és Moore újabb ötlettel állt elő. Miért ne hasonlíthatná össze a mintát a jobbról balra írt szöveggel balról jobbra, miközben a váltásirány ugyanaz marad:

public static int BoyerMooreHorspoolSimpleSearch (char [] minta, char [] text) {int patternSize = minta.hossz; int textSize = szöveg.hossz; int i = 0, j = 0; míg ((i + patternSize) <= textSize) {j = patternSize - 1; while (szöveg [i + j] == minta [j]) {j--; if (j <0) visszatér i; } i ++; } return -1; }

A várakozásoknak megfelelően ez be fog futni O (m * n) idő. De ez az algoritmus az előfordulás és a meccsheurisztika megvalósításához vezetett, ami jelentősen felgyorsítja az algoritmust. Itt többet találhatunk.

2.6. Boyer-Moore-Horspool algoritmus

A Boyer-Moore algoritmus heurisztikus megvalósításának számos változata létezik, és a legegyszerűbb a Horspool variáció.

Az algoritmus ezen változatát Boyer-Moore-Horspoolnak hívják, és ez a variáció megoldotta a negatív eltolódások problémáját (a negatív eltolás problémájáról a Boyer-Moore algoritmus leírásában olvashatunk).

A Boyer-Moore algoritmushoz hasonlóan a legrosszabb esetben is az idő összetettsége O (m * n) míg az átlagos komplexitás O (n). A helyhasználat nem a minta méretétől függ, hanem csak az ábécé méretétől, amely 256, mivel ez az ASCII karakter maximális értéke angol ábécében:

public static int BoyerMooreHorspoolSearch (char [] minta, char [] text) {int shift [] = új int [256]; mert (int k = 0; k <256; k ++) {shift [k] = minta.hossz; } for (int k = 0; k <minta.hossz - 1; k ++) {shift [minta [k]] = minta.hossz - 1 - k; } int i = 0, j = 0; míg ((i + minta.hossz) <= szöveg.hossz) {j = minta.hossz - 1; míg (szöveg [i + j] == minta [j]) {j - = 1; if (j <0) visszatér i; } i = i + shift [szöveg [i + minta.hossz - 1]]; } return -1; }

4. Következtetés

Ebben a cikkben számos algoritmust mutattunk be a szöveges kereséshez. Mivel számos algoritmus erősebb matematikai hátteret igényel, megpróbáltuk az egyes algoritmusok alatti fő gondolatot ábrázolni és egyszerű módon megadni.

És mint mindig, a forráskód megtalálható a GitHubon.