Algoritmi di ricerca di stringhe per testi di grandi dimensioni con Java

1. Introduzione

In questo articolo, mostreremo diversi algoritmi per la ricerca di un pattern in un testo di grandi dimensioni. Descriveremo ogni algoritmo con il codice fornito e un semplice background matematico.

Si noti che gli algoritmi forniti non sono il modo migliore per eseguire una ricerca full-text in applicazioni più complesse. Per eseguire correttamente la ricerca full-text, possiamo utilizzare Solr o ElasticSearch.

2. Algoritmi

Inizieremo con un algoritmo di ricerca di testo ingenuo che è il più intuitivo e aiuta a scoprire altri problemi avanzati associati a tale attività.

2.1. Metodi di aiuto

Prima di iniziare, definiamo metodi semplici per il calcolo dei numeri primi che utilizziamo nell'algoritmo di 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. Ricerca di testo semplice

Il nome di questo algoritmo lo descrive meglio di qualsiasi altra spiegazione. È la soluzione più naturale:

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

L'idea di questo algoritmo è semplice: itera attraverso il testo e se c'è una corrispondenza per la prima lettera del pattern, controlla se tutte le lettere del pattern corrispondono al testo.

Se m è un numero delle lettere nel modello e n è il numero delle lettere nel testo, la complessità temporale di questo algoritmo è O (m (nm + 1)) .

Lo scenario peggiore si verifica nel caso di una stringa con molte occorrenze parziali:

Text: baeldunbaeldunbaeldunbaeldun Pattern: baeldung

2.3. Algoritmo di Rabin Karp

Come accennato in precedenza, l'algoritmo di ricerca del testo semplice è molto inefficiente quando i modelli sono lunghi e quando ci sono molti elementi ripetuti del modello.

L'idea dell'algoritmo di Rabin Karp è usare l'hashing per trovare un pattern in un testo. All'inizio dell'algoritmo, dobbiamo calcolare un hash del pattern che viene successivamente utilizzato nell'algoritmo. Questo processo è chiamato calcolo delle impronte digitali e possiamo trovare una spiegazione dettagliata qui.

La cosa importante della fase di pre-elaborazione è che la sua complessità temporale è O (m) e l'iterazione attraverso il testo richiederà O (n) che fornisce la complessità temporale dell'intero algoritmo O (m + n) .

Codice dell'algoritmo:

public static int RabinKarpMethod(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; long prime = getBiggerPrime(patternSize); long r = 1; for (int i = 0; i < patternSize - 1; i++) { r *= 2; r = r % prime; } long[] t = new long[textSize]; t[0] = 0; long pfinger = 0; for (int j = 0; j < patternSize; j++) { t[0] = (2 * t[0] + text[j]) % prime; pfinger = (2 * pfinger + pattern[j]) % prime; } int i = 0; boolean passed = false; int diff = textSize - patternSize; for (i = 0; i <= diff; i++) { if (t[i] == pfinger) { passed = true; for (int k = 0; k < patternSize; k++) { if (text[i + k] != pattern[k]) { passed = false; break; } } if (passed) { return i; } } if (i < diff) { long value = 2 * (t[i] - r * text[i]) + text[i + patternSize]; t[i + 1] = ((value % prime) + prime) % prime; } } return -1; }

Nello scenario peggiore, la complessità temporale per questo algoritmo è O (m (n-m + 1)) . Tuttavia, in media questo algoritmo ha una complessità temporale O (n + m) .

Inoltre, esiste una versione Monte Carlo di questo algoritmo che è più veloce, ma può causare corrispondenze errate (falsi positivi).

2.4 Algoritmo di Knuth-Morris-Pratt

Nell'algoritmo di ricerca del testo semplice, abbiamo visto come l'algoritmo potrebbe essere lento se ci sono molte parti del testo che corrispondono al modello.

L'idea dell'algoritmo di Knuth-Morris-Pratt è il calcolo della tabella di spostamento che ci fornisce le informazioni su dove dovremmo cercare i nostri candidati di pattern.

Implementazione Java dell'algoritmo KMP:

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

Ed ecco come calcoliamo la tabella dei turni:

public static int[] KnuthMorrisPrattShift(char[] pattern) { int patternSize = pattern.length; int[] shift = new int[patternSize]; shift[0] = 1; int i = 1, j = 0; while ((i + j) 
    
      0) { i = i + shift[j - 1]; j = Math.max(j - shift[j - 1], 0); } else { i = i + 1; j = 0; } } } return shift; }
    

Anche la complessità temporale di questo algoritmo è O (m + n) .

2.5. Algoritmo di Boyer-Moore semplice

Due scienziati, Boyer e Moore, hanno avuto un'altra idea. Perché non confrontare il motivo con il testo da destra a sinistra invece che da sinistra a destra, mantenendo la stessa direzione di spostamento:

public static int BoyerMooreHorspoolSimpleSearch(char[] pattern, 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] == pattern[j]) { j--; if (j < 0) return i; } i++; } return -1; }

Come previsto, verrà eseguito in tempo O (m * n) . Ma questo algoritmo ha portato all'implementazione dell'occorrenza e all'euristica della corrispondenza, che accelera notevolmente l'algoritmo. Possiamo trovare di più qui.

2.6. Algoritmo di Boyer-Moore-Horspool

Esistono molte varianti dell'implementazione euristica dell'algoritmo di Boyer-Moore e la più semplice è la variazione di Horspool.

Questa versione dell'algoritmo si chiama Boyer-Moore-Horspool e questa variazione ha risolto il problema degli spostamenti negativi (possiamo leggere il problema dello spostamento negativo nella descrizione dell'algoritmo di Boyer-Moore).

Come l'algoritmo di Boyer-Moore, la complessità temporale dello scenario peggiore è O (m * n) mentre la complessità media è O (n). L'utilizzo dello spazio non dipende dalla dimensione del motivo, ma solo dalla dimensione dell'alfabeto che è 256 poiché questo è il valore massimo del carattere ASCII nell'alfabeto inglese:

public static int BoyerMooreHorspoolSearch(char[] pattern, 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] == pattern[j]) { j -= 1; if (j < 0) return i; } i = i + shift[text[i + pattern.length - 1]]; } return -1; }

4. Conclusione

In questo articolo, abbiamo presentato diversi algoritmi per la ricerca di testo. Poiché diversi algoritmi richiedono un background matematico più forte, abbiamo cercato di rappresentare l'idea principale sotto ogni algoritmo e di fornirla in modo semplice.

E, come sempre, il codice sorgente può essere trovato su GitHub.