Strengsøgningsalgoritmer for store tekster med Java

1. Introduktion

I denne artikel viser vi flere algoritmer til søgning efter et mønster i en stor tekst. Vi beskriver hver algoritme med angivet kode og enkel matematisk baggrund.

Bemærk, at forudsatte algoritmer ikke er den bedste måde at foretage en fuldtekstsøgning på i mere komplekse applikationer. For at udføre fuldtekstsøgning korrekt kan vi bruge Solr eller ElasticSearch.

2. Algoritmer

Vi starter med en naiv tekstsøgningsalgoritme, som er den mest intuitive og hjælper med at opdage andre avancerede problemer forbundet med denne opgave.

2.1. Hjælpemetoder

Før vi starter, lad os definere enkle metoder til beregning af primtal, som vi bruger i Rabin Karp-algoritmen:

offentlig statisk lang getBiggerPrime (int m) {BigInteger prime = BigInteger.probablePrime (getNumberOfBits (m) + 1, new Random ()); return prime.longValue (); } privat statisk int getNumberOfBits (int-nummer) {return Integer.SIZE - Integer.numberOfLeadingZeros (number); } 

2.2. Enkel tekstsøgning

Navnet på denne algoritme beskriver det bedre end nogen anden forklaring. Det er den mest naturlige løsning:

offentlig statisk int simpleTextSearch (char [] mønster, char [] tekst) {int patternSize = mønster.længde; int textSize = text.length; int i = 0; mens ((i + mønsterstørrelse) = mønsterstørrelse) returnerer jeg; } i + = 1; } return -1; }

Ideen med denne algoritme er ligetil: gentag gennem teksten, og hvis der er et match med det første bogstav i mønsteret, skal du kontrollere, om alle bogstaverne i mønsteret matcher teksten.

Hvis m er et antal bogstaver i mønsteret, og n er antallet af bogstaver i teksten, tidskompleksiteten af ​​denne algoritme er O (m (n-m + 1)).

Værste tilfælde opstår i tilfælde af a Snor har mange delvise forekomster:

Tekst: baeldunbaeldunbaeldunbaeldun Mønster: baeldung

2.3. Rabin Karp Algoritme

Som nævnt ovenfor er algoritmen til enkel tekstsøgning meget ineffektiv, når mønstre er lange, og når der er mange gentagne elementer i mønsteret.

Ideen med Rabin Karp-algoritmen er at bruge hashing til at finde et mønster i en tekst. I starten af ​​algoritmen skal vi beregne en hash af det mønster, som senere bruges i algoritmen. Denne proces kaldes fingeraftryksberegning, og vi kan finde en detaljeret forklaring her.

Det vigtige ved forbehandlingstrinnet er, at dets tidskompleksitet er O (m) og iteration gennem tekst vil tage På) hvilket giver tidskompleksitet af hele algoritmen O (m + n).

Kode for algoritmen:

offentlig statisk int RabinKarpMethod (char [] mønster, char [] tekst) {int patternSize = mønster.længde; int textSize = text.length; lang prime = getBiggerPrime (patternSize); lang r = 1; for (int i = 0; i <mønsterstørrelse - 1; i ++) {r * = 2; r = r% prime; } lang [] t = ny lang [textSize]; t [0] = 0; lang pfinger = 0; for (int j = 0; j <mønsterstørrelse; j ++) {t [0] = (2 * t [0] + tekst [j])% prime; pfinger = (2 * pfinger + mønster [j])% prime; } int i = 0; boolsk bestået = falsk; int diff = textSize - patternSize; for (i = 0; i <= diff; i ++) {if (t [i] == pfinger) {passed = true; for (int k = 0; k <mønsterstørrelse; k ++) {hvis (tekst [i + k]! = mønster [k]) {bestået = falsk; pause; }} hvis (bestået) {returnere i; }} hvis (i <diff) {lang værdi = 2 * (t [i] - r * tekst [i]) + tekst [i + mønsterstørrelse]; t [i + 1] = ((værdi% prime) + prime)% prime; }} return -1; }

I værste fald er tidskompleksiteten for denne algoritme O (m (n-m + 1)). Imidlertid har denne algoritme i gennemsnit det O (n + m) tidskompleksitet.

Derudover er der Monte Carlo-versionen af ​​denne algoritme, som er hurtigere, men den kan resultere i forkerte matches (falske positive).

2.4 Knuth-Morris-Pratt algoritme

I Simple Text Search-algoritmen så vi, hvordan algoritmen kunne være langsom, hvis der er mange dele af teksten, der matcher mønsteret.

Ideen med Knuth-Morris-Pratt-algoritmen er beregningen af ​​skifttabellen, der giver os de oplysninger, hvor vi skal søge efter vores mønsterkandidater.

Java-implementering af KMP-algoritme:

offentlig statisk int KnuthMorrisPrattSearch (char [] mønster, char [] tekst) {int patternSize = mønster.længde; int textSize = text.length; int i = 0, j = 0; int [] shift = KnuthMorrisPrattShift (mønster); mens ((i + mønsterstørrelse) = mønsterstørrelse) returnerer jeg; } hvis (j> 0) {i + = skift [j - 1]; j = Math.max (j - skift [j - 1], 0); } andet {i ++; j = 0; }} return -1; }

Og her beregner vi skiftetabellen:

offentlig statisk int [] KnuthMorrisPrattShift (char [] mønster) {int patternSize = mønster.længde; int [] shift = new int [patternSize]; skift [0] = 1; int i = 1, j = 0; mens ((i + j)  0) {i = i + skift [j - 1]; j = Math.max (j - skift [j - 1], 0); } andet {i = i + 1; j = 0; }}} returskift; }

Tids kompleksiteten af ​​denne algoritme er også O (m + n).

2.5. Simple Boyer-Moore algoritme

To forskere, Boyer og Moore, kom på en anden idé. Hvorfor ikke sammenligne mønsteret med teksten fra højre til venstre i stedet for fra venstre mod højre, mens du holder skiftretningen den samme:

offentlig statisk int BoyerMooreHorspoolSimpleSearch (char [] mønster, char [] tekst) {int patternSize = mønster.længde; int textSize = text.length; int i = 0, j = 0; mens ((i + patternSize) <= textSize) {j = patternSize - 1; mens (tekst [i + j] == mønster [j]) {j--; hvis (j <0) returnerer i; } i ++; } return -1; }

Som forventet løber dette ind O (m * n) tid. Men denne algoritme førte til implementering af forekomst og matchheuristikken, som fremskynder algoritmen betydeligt. Vi kan finde mere her.

2.6. Boyer-Moore-Horspool algoritme

Der er mange variationer af heuristisk implementering af Boyer-Moore-algoritmen, og den enkleste er Horspool-variation.

Denne version af algoritmen kaldes Boyer-Moore-Horspool, og denne variation løste problemet med negative skift (vi kan læse om negativt skiftproblem i beskrivelsen af ​​Boyer-Moore-algoritmen).

Ligesom Boyer-Moore-algoritmen er tidens kompleksitet i værste tilfælde O (m * n) mens gennemsnitskompleksitet er O (n). Pladsforbrug afhænger ikke af mønsterets størrelse, men kun af størrelsen på alfabetet, der er 256, da det er den maksimale værdi af ASCII-tegn i det engelske alfabet:

offentlig statisk int BoyerMooreHorspoolSearch (char [] mønster, char [] tekst) {int shift [] = ny int [256]; for (int k = 0; k <256; k ++) {shift [k] = pattern.length; } for (int k = 0; k <mønsterlængde - 1; k ++) {skift [mønster [k]] = mønsterlængde - 1 - k; } int i = 0, j = 0; mens ((i + mønster.længde) <= tekst.længde) {j = mønster.længde - 1; mens (tekst [i + j] == mønster [j]) {j - = 1; hvis (j <0) returnerer i; } i = i + skift [tekst [i + mønster.længde - 1]]; } return -1; }

4. Konklusion

I denne artikel præsenterede vi flere algoritmer til tekstsøgning. Da flere algoritmer kræver stærkere matematisk baggrund, forsøgte vi at repræsentere hovedideen under hver algoritme og give den på en enkel måde.

Og som altid kan kildekoden findes på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found