streamalism.org

1. Introduksjon

I denne artikkelen viser vi flere algoritmer for å søke etter et mønster i en stor tekst. Vi beskriver hver algoritme med gitt kode og enkel matematisk bakgrunn.

Legg merke til at gitt algoritmer ikke er den beste måten å gjøre et fulltekstsøk i mer komplekse applikasjoner. For å gjøre fulltekstsøk riktig kan vi bruke Solr eller ElasticSearch.

2. Algoritmer

Vi starter med en naiv algoritme for tekstsøk, som er den mest intuitive, og som hjelper deg med å oppdage andre avanserte problemer knyttet til den oppgaven.

2.1. Hjelpemetoder

Før vi begynner, la oss definere enkle metoder for å beregne primtall som vi bruker i Rabin Karp-algoritmen:

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

2.2. Enkelt tekstsøk

Navnet på denne algoritmen beskriver det bedre enn noen annen forklaring. Det er den mest naturlige løsningen:

offentlig statisk int simpleTextSearch (char [] mønster, char [] tekst) {int patternSize = mønster.lengde; int textSize = text.length; int i = 0; mens ((i + patternSize) = patternSize) returnerer jeg; } i + = 1; } retur -1; }

Ideen med denne algoritmen er grei: gjenta den gjennom teksten, og hvis det samsvarer med den første bokstaven i mønsteret, sjekk om alle bokstavene i mønsteret samsvarer med teksten.

Hvis m er et antall av bokstavene i mønsteret, og n er antall bokstaver i teksten, tidskompleksiteten til denne algoritmen er O (m (n-m + 1)).

Verste fall oppstår når det gjelder a String har mange delvise forekomster:

Tekst: baeldunbaeldunbaeldunbaeldun Mønster: baeldung

2.3. Rabin Karp Algoritme

Som nevnt ovenfor er Simple Text Search-algoritmen veldig ineffektiv når mønstre er lange og når det er mange gjentatte elementer i mønsteret.

Ideen med Rabin Karp-algoritmen er å bruke hashing for å finne et mønster i en tekst. I begynnelsen av algoritmen må vi beregne en hash av mønsteret som senere blir brukt i algoritmen. Denne prosessen kalles fingeravtrykksberegning, og vi finner en detaljert forklaring her.

Det viktige med forbehandlingstrinnet er at dets tidskompleksitet er O (m) og iterasjon gjennom tekst vil ta På) som gir tidskompleksitet av hele algoritmen O (m + n).

Kode for algoritmen:

offentlig statisk int RabinKarpMethod (char [] mønster, char [] tekst) {int patternSize = mønster.lengde; int textSize = text.length; lang prime = getBiggerPrime (patternSize); lang r = 1; for (int i = 0; i <patternSize - 1; i ++) {r * = 2; r = r% prime; } lang [] t = ny lang [textSize]; t [0] = 0; lang pingfinger = 0; for (int j = 0; j <patternSize; j ++) {t [0] = (2 * t [0] + text [j])% prime; pfinger = (2 * pfinger + mønster [j])% prime; } int i = 0; boolsk passert = falsk; int diff = textSize - patternSize; for (i = 0; i <= diff; i ++) {if (t [i] == pfinger) {passed = true; for (int k = 0; k <patternSize; k ++) {if (tekst [i + k]! = mønster [k]) {passert = false; gå i stykker; }} hvis (bestått) {return i; }} hvis (i <diff) {long value = 2 * (t [i] - r * text [i]) + text [i + patternSize]; t [i + 1] = ((verdi% prime) + prime)% prime; }} retur -1; }

I verste fall er tidskompleksiteten for denne algoritmen O (m (n-m + 1)). Imidlertid har denne algoritmen i gjennomsnitt O (n + m) tidskompleksitet.

I tillegg er det Monte Carlo-versjonen av denne algoritmen som er raskere, men det kan resultere i feil samsvar (falske positive).

2.4 Knuth-Morris-Pratt algoritme

I Simple Text Search-algoritmen så vi hvordan algoritmen kunne være treg hvis det er mange deler av teksten som samsvarer med mønsteret.

Ideen med Knuth-Morris-Pratt-algoritmen er beregningen av skifttabellen som gir oss informasjonen der vi skal søke etter mønsterkandidatene våre.

Java-implementering av KMP-algoritme:

offentlig statisk int KnuthMorrisPrattSearch (char [] mønster, char [] tekst) {int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; int [] shift = KnuthMorrisPrattShift (mønster); mens ((i + patternSize) = patternSize) returnerer jeg; } hvis (j> 0) {i + = shift [j - 1]; j = Math.max (j - shift [j - 1], 0); } annet {i ++; j = 0; }} retur -1; }

Og her er hvordan vi beregner skiftetabell:

offentlig statisk int [] KnuthMorrisPrattShift (char [] mønster) {int patternSize = mønster.lengde; 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 - shift [j - 1], 0); } annet {i = i + 1; j = 0; }}} returvakt; }

Tidskompleksiteten til denne algoritmen er også O (m + n).

2.5. Simple Boyer-Moore-algoritme

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

offentlig statisk int BoyerMooreHorspoolSimpleSearch (char [] mønster, char [] tekst) {int patternSize = pattern.length; 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 jeg; } i ++; } retur -1; }

Som forventet vil dette løpe inn O (m * n) tid. Men denne algoritmen førte til implementering av forekomst og matchheuristikken som fremskynder algoritmen betydelig. Vi finner mer her.

2.6. Boyer-Moore-Horspool algoritme

Det er mange varianter av heuristisk implementering av Boyer-Moore-algoritmen, og den enkleste er Horspool-variasjonen.

Denne versjonen av algoritmen kalles Boyer-Moore-Horspool, og denne variasjonen løste problemet med negative skift (vi kan lese om negativt skiftproblem i beskrivelsen av Boyer-Moore-algoritmen).

I likhet med Boyer-Moore-algoritmen er tidskompleksiteten i verste fall O (m * n) mens gjennomsnittlig kompleksitet er O (n). Plassbruk avhenger ikke av størrelsen på mønsteret, men bare av størrelsen på alfabetet som er 256, siden det er den maksimale verdien av ASCII-tegnet i det engelske alfabetet:

offentlig statisk int BoyerMooreHorspoolSearch (char [] mønster, char [] tekst) {int shift [] = new int [256]; for (int k = 0; k <256; k ++) {shift [k] = pattern.length; } for (int k = 0; k <mønsterlengde - 1; k ++) {skift [mønster [k]] = mønsterlengde - 1 - k; } int i = 0, j = 0; mens ((i + mønsterlengde) <= tekstlengde) {j = mønsterlengde - 1; mens (tekst [i + j] == mønster [j]) {j - = 1; hvis (j <0) returnerer jeg; } i = i + shift [tekst [i + mønster.lengde - 1]]; } retur -1; }

4. Konklusjon

I denne artikkelen presenterte vi flere algoritmer for tekstsøk. Siden flere algoritmer krever sterkere matematisk bakgrunn, prøvde vi å representere hovedideen under hver algoritme og gi den på en enkel måte.

Og som alltid kan kildekoden bli funnet på GitHub.