streamalism.org

1. Úvod

V tomto článku si ukážeme niekoľko algoritmov na hľadanie vzoru vo veľkom texte. Popíšeme každý algoritmus s poskytnutým kódom a jednoduchým matematickým pozadím.

Všimnite si, že poskytnuté algoritmy nie sú najlepším spôsobom, ako vykonať fulltextové vyhľadávanie v zložitejších aplikáciách. Na správne vykonávanie fulltextového vyhľadávania môžeme použiť službu Solr alebo ElasticSearch.

2. Algoritmy

Začneme s naivným algoritmom hľadania textu, ktorý je najintuitívnejší a ktorý pomáha odhaliť ďalšie pokročilé problémy spojené s touto úlohou.

2.1. Pomocné metódy

Než začneme, definujme si jednoduché metódy výpočtu prvočísel, ktoré používame v algoritme Rabin Karp:

public static long 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. Jednoduché textové vyhľadávanie

Názov tohto algoritmu ho vystihuje lepšie ako akékoľvek iné vysvetlenie. Je to najprirodzenejšie riešenie:

public static int simpleTextSearch (char [] vzor, ​​char [] text) {int patternSize = pattern.length; int textSize = text.length; int i = 0; while ((i + patternSize) = patternSize) return i; } i + = 1; } návrat -1; }

Myšlienka tohto algoritmu je jasná: iterujte textom a ak existuje zhoda pre prvé písmeno vzoru, skontrolujte, či sa všetky písmená vzoru zhodujú s textom.

Ak m je počet písmen vo vzore a n je počet písmen v texte, časová zložitosť týchto algoritmov je O (m (n-m + 1)).

Najhorší scenár nastáva v prípade a String s mnohými čiastočnými výskytmi:

Text: baeldunbaeldunbaeldunbaeldun Vzor: baeldung

2.3. Algoritmus Rabin Karp

Ako už bolo spomenuté vyššie, algoritmus Simple Text Search je veľmi neefektívny, ak sú vzory dlhé a keď sa v nich opakuje veľa prvkov.

Myšlienkou algoritmu Rabin Karp je použitie hašovania na nájdenie vzoru v texte. Na začiatku algoritmu musíme vypočítať hash vzoru, ktorý sa neskôr použije v algoritme. Tento proces sa nazýva výpočet odtlačkov prstov a tu môžeme nájsť podrobné vysvetlenie.

Dôležitá vec kroku predspracovania je, že je časovo zložitá O (m) a iterácia prostredníctvom textu bude trvať O (n) čo dáva časovú zložitosť celého algoritmu O (m + n).

Kód algoritmu:

public static int RabinKarpMethod (char [] vzor, ​​char [] text) {int patternSize = pattern.length; int textSize = text.length; long prime = getBiggerPrime (patternSize); dlhé r = 1; pre (int i = 0; i <patternSize - 1; i ++) {r * = 2; r = r% prime; } long [] t = new long [textSize]; t [0] = 0; long pfinger = 0; pre (int j = 0; j <patternSize; j ++) {t [0] = (2 * t [0] + text [j])% prime; pfinger = (2 * pfinger + vzor [j])% prime; } int i = 0; boolean prešiel = false; int diff = textSize - patternSize; pre (i = 0; i <= rozdiel; i ++) {if (t [i] == pfinger) {prešiel = pravda; pre (int k = 0; k <patternSize; k ++) {if (text [i + k]! = vzor [k]) {prešiel = false; prestávka; }} if (odovzdané) {return i; }} if (i <diff) {long value = 2 * (t [i] - r * text [i]) + text [i + patternSize]; t [i + 1] = ((hodnota% prvočíslo) + prvočíslo)% prvočíslo; }} návrat -1; }

V najhoršom prípade je časová zložitosť tohto algoritmu O (m (n-m + 1)). Tento algoritmus však v priemere má O (n + m) časová zložitosť.

Ďalej existuje Monte Carlo verzia tohto algoritmu, ktorá je rýchlejšia, ale môže viesť k nesprávnym zhodám (falošným pozitívom).

2.4 Algoritmus Knuth-Morris-Pratt

V algoritme Simple Text Search sme videli, ako môže byť algoritmus pomalý, ak existuje veľa častí textu, ktoré zodpovedajú vzoru.

Myšlienkou algoritmu Knuth-Morris-Pratt je výpočet tabuľky posunov, ktorá nám poskytuje informácie, kde by sme mali hľadať našich kandidátov na vzory.

Implementácia algoritmu KMP v jazyku Java:

public static int KnuthMorrisPrattSearch (char [] vzor, ​​char [] text) {int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; int [] shift = KnuthMorrisPrattShift (vzor); while ((i + patternSize) = patternSize) return i; } if (j> 0) {i + = shift [j - 1]; j = Math.max (j - posun [j - 1], 0); } else {i ++; j = 0; }} návrat -1; }

A takto vypočítame tabuľku posunov:

public static int [] KnuthMorrisPrattShift (char [] vzor) {int patternSize = pattern.length; int [] shift = new int [patternSize]; posun [0] = 1; int i = 1, j = 0; while ((i + j)  0) {i = i + shift [j - 1]; j = Math.max (j - posun [j - 1], 0); } else {i = i + 1; j = 0; }}} spiatočná zmena; }

Časová zložitosť tohto algoritmu je tiež O (m + n).

2.5. Jednoduchý Boyer-Moorov algoritmus

Dvaja vedci, Boyer a Moore, prišli s ďalším nápadom. Prečo neporovnať vzor s textom sprava doľava namiesto zľava doprava pri zachovaní rovnakého smeru posunu:

public static int BoyerMooreHorspoolSimpleSearch (char [] vzor, ​​char [] text) {int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; while ((i + patternSize) <= textSize) {j = patternSize - 1; while (text [i + j] == vzor [j]) {j--; if (j <0) return i; } i ++; } návrat -1; }

Podľa očakávania to bude prebiehať v roku O (m * n) čas. Ale tento algoritmus viedol k implementácii výskytu a heuristike zhody, čo algoritmus výrazne urýchli. Viac nájdeme tu.

2.6. Algoritmus Boyer-Moore-Horspool

Existuje veľa variácií heuristickej implementácie algoritmu Boyer-Moore a najjednoduchšou z nich je variácia Horspool.

Táto verzia algoritmu sa nazýva Boyer-Moore-Horspool a táto variácia vyriešila problém negatívnych posunov (o probléme negatívnych posunov sa dočítame v popise algoritmu Boyer-Moore).

Rovnako ako Boyer-Mooreov algoritmus je aj časová zložitosť najhoršieho scenára O (m * n) zatiaľ čo priemerná zložitosť je O (n). Využitie priestoru nezávisí od veľkosti vzoru, ale iba od veľkosti abecedy, ktorá je 256, pretože to je maximálna hodnota znaku ASCII v anglickej abecede:

public static int BoyerMooreHorspoolSearch (char [] vzor, ​​char [] text) {int shift [] = new int [256]; for (int k = 0; k <256; k ++) {shift [k] = pattern.length; } 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 (text [i + j] == vzor [j]) {j - = 1; if (j <0) return i; } i = i + shift [text [i + pattern.length - 1]]; } návrat -1; }

4. Záver

V tomto článku sme predstavili niekoľko algoritmov pre textové vyhľadávanie. Pretože niekoľko algoritmov vyžaduje silnejšie matematické pozadie, pokúsili sme sa predstaviť hlavnú myšlienku pod každým algoritmom a poskytnúť ju jednoduchým spôsobom.

A ako vždy, zdrojový kód nájdete na GitHub.