String algoritmi za pretraživanje velikih tekstova s ​​Javom

1. Uvod

U ovom ćemo članku prikazati nekoliko algoritama za traženje uzorka u velikom tekstu. Opisat ćemo svaki algoritam s navedenim kodom i jednostavnom matematičkom pozadinom.

Primijetite da ponuđeni algoritmi nisu najbolji način pretraživanja cjelovitog teksta u složenijim aplikacijama. Da bismo pravilno pretražili cijeli tekst, možemo koristiti Solr ili ElasticSearch.

2. Algoritmi

Započet ćemo s naivnim algoritmom pretraživanja teksta koji je najintuitivniji i pomaže otkriti druge napredne probleme povezane s tim zadatkom.

2.1. Metode pomagača

Prije nego što započnemo, definirajmo jednostavne metode za izračunavanje prostih brojeva koje koristimo u algoritmu Rabin Karp:

javna statička long getBiggerPrime (int m) {BigInteger prime = BigInteger.probablePrime (getNumberOfBits (m) + 1, new Random ()); povratak prime.longValue (); } privatni statički int getNumberOfBits (int broj) {return Integer.SIZE - Integer.numberOfLeadingZeros (broj); } 

2.2. Jednostavno pretraživanje teksta

Naziv ovog algoritma opisuje ga bolje od bilo kojeg drugog objašnjenja. To je najprirodnije rješenje:

javni statički int simpleTextSearch (char [] uzorak, char [] tekst) {int patternSize = pattern.length; int textSize = text.length; int i = 0; while ((i + patternSize) = patternSize) return i; } i + = 1; } povratak -1; }

Ideja ovog algoritma je izravna: prelistajte tekst i ako postoji podudaranje za prvo slovo uzorka, provjerite podudaraju li se sva slova uzorka s tekstom.

Ako m je broj slova u uzorku i n je broj slova u tekstu, vremenska složenost ovih algoritama je O (m (n-m + 1)).

Najgori scenarij javlja se u slučaju a Niz s mnogo djelomičnih pojava:

Tekst: baeldunbaeldunbaeldunbaeldun Uzorak: baeldung

2.3. Algoritam Rabina Karpa

Kao što je gore spomenuto, algoritam jednostavnog pretraživanja teksta vrlo je neučinkovit kada su uzorci dugi i kada postoji puno ponovljenih elemenata uzorka.

Ideja algoritma Rabin Karp je koristiti raspršivanje za pronalaženje uzorka u tekstu. Na početku algoritma moramo izračunati hash uzorka koji se kasnije koristi u algoritmu. Taj se postupak naziva izračun otiska prsta i ovdje možemo pronaći detaljno objašnjenje.

Važna stvar kod koraka predobrade jest da je njegova vremenska složenost O (m) i ponavljanje kroz tekst će trajati Na) što daje vremensku složenost cijelom algoritmu O (m + n).

Šifra algoritma:

javni statički int RabinKarpMethod (char [] uzorak, char [] tekst) {int patternSize = pattern.length; int textSize = text.length; long prime = getBiggerPrime (patternSize); dugo r = 1; za (int i = 0; i <patternSize - 1; i ++) {r * = 2; r = r% prosti; } long [] t = novo dugo [textSize]; t [0] = 0; dugi pfinger = 0; za (int j = 0; j <patternSize; j ++) {t [0] = (2 * t [0] + tekst [j])% prime; pfinger = (2 * pfinger + uzorak [j])% prime; } int i = 0; boolean pass = false; int diff = textSize - patternSize; for (i = 0; i <= diff; i ++) {if (t [i] == pfinger) {pass = true; for (int k = 0; k <patternSize; k ++) {if (text [i + k]! = pattern [k]) {pass = false; pauza; }} ako (prošao) {return i; }} if (i <diff) {long value = 2 * (t [i] - r * text [i]) + text [i + patternSize]; t [i + 1] = ((vrijednost% prime) + prosta)% prime; }} povratak -1; }

U najgorem slučaju, vremenska složenost ovog algoritma je O (m (n-m + 1)). Međutim, u prosjeku ovaj algoritam ima O (n + m) složenost vremena.

Uz to, postoji verzija Monte Carla ovog algoritma koja je brža, ali može rezultirati pogrešnim podudaranjima (lažno pozitivnim rezultatima).

2.4 Knuth-Morris-Prattov algoritam

U algoritmu Jednostavnog pretraživanja teksta vidjeli smo kako algoritam može biti spor ako postoji mnogo dijelova teksta koji odgovaraju uzorku.

Ideja Knuth-Morris-Pratt algoritma je izračunavanje tablice pomaka koja nam daje informacije gdje bismo trebali tražiti svoje kandidate za obrazac.

Java implementacija KMP algoritma:

javni statički int KnuthMorrisPrattSearch (char [] uzorak, char [] tekst) {int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; int [] shift = KnuthMorrisPrattShift (uzorak); while ((i + patternSize) = patternSize) return i; } if (j> 0) {i + = pomak [j - 1]; j = Math.max (j - pomak [j - 1], 0); } ostalo {i ++; j = 0; }} povratak -1; }

I evo kako izračunavamo tablicu smjena:

javni statički int [] KnuthMorrisPrattShift (char [] uzorak) {int patternSize = pattern.length; int [] pomak = novi int [patternSize]; pomak [0] = 1; int i = 1, j = 0; dok ((i + j)  0) {i = i + pomak [j - 1]; j = Math.max (j - pomak [j - 1], 0); } ostalo {i = i + 1; j = 0; }}} povratna smjena; }

Vremenska složenost ovog algoritma je također O (m + n).

2.5. Jednostavni Boyer-Mooreov algoritam

Dvoje znanstvenika, Boyer i Moore, iznijeli su još jednu ideju. Zašto ne usporediti uzorak s tekstom s desna na lijevo umjesto s lijeva na desno, a da smjer pomaka ostane isti:

javni statični int BoyerMooreHorspoolSimpleSearch (char [] uzorak, char [] tekst) {int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; while ((i + patternSize) <= textSize) {j = patternSize - 1; while (tekst [i + j] == uzorak [j]) {j--; if (j <0) return i; } i ++; } povratak -1; }

Kao što se očekivalo, ovo će nastupiti O (m * n) vrijeme. Ali ovaj je algoritam doveo do implementacije pojave i heuristike podudaranja što značajno ubrzava algoritam. Više možemo pronaći ovdje.

2.6. Algoritam Boyer-Moore-Horspool

Postoje mnoge varijacije heurističke provedbe Boyer-Moore algoritma, a najjednostavnija je Horspolova varijacija.

Ova verzija algoritma naziva se Boyer-Moore-Horspool, a ova je varijacija riješila problem negativnih pomaka (o problemu negativnog pomaka možemo pročitati u opisu Boyer-Mooreovog algoritma).

Poput Boyer-Moore algoritma, vremenska složenost u najgorem slučaju jest O (m * n) dok je prosječna složenost O (n). Korištenje prostora ne ovisi o veličini uzorka, već samo o veličini abecede koja je 256, jer je to maksimalna vrijednost ASCII znaka u engleskoj abecedi:

javni statični int BoyerMooreHorspoolSearch (char [] uzorak, char [] tekst) {int shift [] = novi int [256]; za (int k = 0; k <256; k ++) {pomak [k] = uzorak.duljina; } for (int k = 0; k <pattern.length - 1; k ++) {shift [pattern [k]] = pattern.length - 1 - k; } int i = 0, j = 0; while ((i + pattern.length) <= text.length) {j = pattern.length - 1; while (tekst [i + j] == uzorak [j]) {j - = 1; if (j <0) return i; } i = i + pomak [text [i + pattern.length - 1]]; } povratak -1; }

4. Zaključak

U ovom smo članku predstavili nekoliko algoritama za pretraživanje teksta. Budući da nekoliko algoritama zahtijeva jaču matematičku pozadinu, pokušali smo predstaviti glavnu ideju ispod svakog algoritma i pružiti je na jednostavan način.

Kao i uvijek, izvorni kod možete pronaći na GitHubu.