streamalism.org

1. Inleiding

In dit artikel laten we verschillende algoritmen zien voor het zoeken naar een patroon in een grote tekst. We beschrijven elk algoritme met de meegeleverde code en eenvoudige wiskundige achtergrond.

Merk op dat de meegeleverde algoritmen niet de beste manier zijn om de volledige tekst te doorzoeken in complexere toepassingen. Om de volledige tekst goed te kunnen zoeken, kunnen we Solr of ElasticSearch gebruiken.

2. Algoritmen

We beginnen met een naïef algoritme voor het zoeken naar tekst, dat het meest intuïtieve is en helpt bij het ontdekken van andere geavanceerde problemen die met die taak verband houden.

2.1. Helper-methoden

Laten we, voordat we beginnen, eenvoudige methoden definiëren voor het berekenen van priemgetallen die we gebruiken in het Rabin Karp-algoritme:

openbare statische lange getBiggerPrime (int m) {BigInteger prime = BigInteger.probablePrime (getNumberOfBits (m) + 1, nieuwe Random ()); retourneer prime.longValue (); } private static int getNumberOfBits (int number) {return Integer.SIZE - Integer.numberOfLeadingZeros (nummer); } 

2.2. Eenvoudig zoeken naar tekst

De naam van dit algoritme beschrijft het beter dan enige andere uitleg. Het is de meest natuurlijke oplossing:

openbare statische int simpleTextSearch (char [] patroon, char [] tekst) {int patternSize = pattern.length; int textSize = text.length; int i = 0; while ((i + patternSize) = patternSize) retourneert i; } i + = 1; } terugkeer -1; }

Het idee van dit algoritme is eenvoudig: herhaal de tekst en als er een overeenkomst is voor de eerste letter van het patroon, controleer dan of alle letters van het patroon overeenkomen met de tekst.

Als m is een nummer van de letters in het patroon, en n is het aantal letters in de tekst, de tijdcomplexiteit van deze algoritmen is O (m (n-m + 1)).

Worst-case scenario doet zich voor in het geval van een Draad met veel gedeeltelijke gebeurtenissen:

Tekst: baeldunbaeldunbaeldunbaeldun Patroon: baeldung

2.3. Rabin Karp-algoritme

Zoals hierboven vermeld, is het Simple Text Search-algoritme erg inefficiënt wanneer patronen lang zijn en wanneer er veel herhaalde elementen van het patroon zijn.

Het idee van het Rabin Karp-algoritme is om hashing te gebruiken om een ​​patroon in een tekst te vinden. Aan het begin van het algoritme moeten we een hash van het patroon berekenen die later in het algoritme wordt gebruikt. Dit proces wordt vingerafdrukberekening genoemd en we kunnen hier een gedetailleerde uitleg vinden.

Het belangrijkste van de voorbewerkingsstap is dat de tijd complexiteit is O (m) en iteratie door tekst zal duren Aan) wat de tijdcomplexiteit van het hele algoritme geeft O (m + n).

Code van het algoritme:

openbare statische int RabinKarpMethod (char [] patroon, char [] tekst) {int patternSize = pattern.length; int textSize = text.length; long prime = getBiggerPrime (patternSize); lange r = 1; voor (int i = 0; i <patternSize - 1; i ++) {r * = 2; r = r% prime; } lang [] t = nieuw lang [textSize]; t [0] = 0; lange vinger = 0; voor (int j = 0; j <patternSize; j ++) {t [0] = (2 * t [0] + tekst [j])% prime; pfinger = (2 * pfinger + patroon [j])% prime; } int i = 0; boolean doorgegeven = false; int diff = textSize - patternSize; for (i = 0; i <= diff; i ++) {if (t [i] == pfinger) {geslaagd = waar; for (int k = 0; k <patternSize; k ++) {if (text [i + k]! = patroon [k]) {geslaagd = false; breken; }} if (geslaagd) {return i; }} if (i <diff) {lange waarde = 2 * (t [i] - r * tekst [i]) + tekst [i + patroongrootte]; t [i + 1] = ((waarde% prime) + prime)% prime; }} return -1; }

In het ergste geval is de tijdcomplexiteit voor dit algoritme O (m (n-m + 1)). Dit algoritme heeft echter gemiddeld O (n + m) tijd complexiteit.

Bovendien is er een Monte Carlo-versie van dit algoritme die sneller is, maar het kan resulteren in verkeerde overeenkomsten (false positives).

2.4 Knuth-Morris-Pratt-algoritme

In het Simple Text Search-algoritme hebben we gezien hoe het algoritme traag kan zijn als er veel delen van de tekst zijn die overeenkomen met het patroon.

Het idee van het Knuth-Morris-Pratt-algoritme is de berekening van de verschuiftabel die ons de informatie geeft waar we naar onze patroonkandidaten moeten zoeken.

Java-implementatie van KMP-algoritme:

openbare statische int KnuthMorrisPrattSearch (char [] patroon, char [] tekst) {int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; int [] shift = KnuthMorrisPrattShift (patroon); while ((i + patternSize) = patternSize) retourneert i; } if (j> 0) {i + = shift [j - 1]; j = Math.max (j - shift [j - 1], 0); } anders {i ++; j = 0; }} return -1; }

En hier is hoe we de shift-tafel berekenen:

openbare statische int [] KnuthMorrisPrattShift (char [] patroon) {int patternSize = pattern.length; int [] shift = nieuwe int [patternSize]; shift [0] = 1; int i = 1, j = 0; terwijl ((i + j)  0) {i = i + verschuiving [j - 1]; j = Math.max (j - shift [j - 1], 0); } anders {i = i + 1; j = 0; }}} terugkeerploeg; }

De tijdcomplexiteit van dit algoritme is ook O (m + n).

2.5. Eenvoudig Boyer-Moore-algoritme

Twee wetenschappers, Boyer en Moore, kwamen met een ander idee. Waarom vergelijk je het patroon niet met de tekst van rechts naar links in plaats van van links naar rechts, terwijl je de verschuivingsrichting hetzelfde houdt:

openbare statische int BoyerMooreHorspoolSimpleSearch (char [] patroon, 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] == patroon [j]) {j--; if (j <0) retourneert i; } i ++; } terugkeer -1; }

Zoals verwacht loopt deze binnen O (m * n) tijd. Maar dit algoritme heeft geleid tot de implementatie van het voorkomen en de matchheuristiek die het algoritme aanzienlijk versnelt. We kunnen hier meer vinden.

2.6. Boyer-Moore-Horspool-algoritme

Er zijn veel variaties op de heuristische implementatie van het Boyer-Moore-algoritme, en de eenvoudigste is de Horspool-variatie.

Deze versie van het algoritme heet Boyer-Moore-Horspool, en deze variatie loste het probleem van negatieve verschuivingen op (we kunnen lezen over het probleem van negatieve verschuivingen in de beschrijving van het Boyer-Moore-algoritme).

Net als het Boyer-Moore-algoritme is de tijdcomplexiteit in het worstcasescenario O (m * n) terwijl de gemiddelde complexiteit O (n) is. Het ruimtegebruik is niet afhankelijk van de grootte van het patroon, maar alleen van de grootte van het alfabet, dat 256 is, aangezien dat de maximale waarde is van het ASCII-teken in het Engelse alfabet:

openbare statische int BoyerMooreHorspoolSearch (char [] patroon, char [] tekst) {int shift [] = nieuwe int [256]; voor (int k = 0; k <256; k ++) {shift [k] = patroon.lengte; } voor (int k = 0; k <patroon.lengte - 1; k ++) {verschuiving [patroon [k]] = patroon.lengte - 1 - k; } int i = 0, j = 0; while ((i + pattern.length) <= text.length) {j = pattern.length - 1; while (tekst [i + j] == patroon [j]) {j - = 1; if (j <0) retourneer i; } i = i + verschuiving [tekst [i + patroon.lengte - 1]]; } terugkeer -1; }

4. Conclusie

In dit artikel hebben we verschillende algoritmen voor het zoeken naar tekst gepresenteerd. Omdat verschillende algoritmen een sterkere wiskundige achtergrond vereisen, hebben we geprobeerd om het hoofdidee onder elk algoritme weer te geven en op een eenvoudige manier aan te bieden.

En, zoals altijd, is de broncode te vinden op GitHub.