Utilizzo di indexOf per trovare tutte le occorrenze di una parola in una stringa

1. Panoramica

Il compito di cercare un modello di caratteri, o una parola, in una stringa di testo più grande viene svolto in vari campi. In bioinformatica, ad esempio, potremmo aver bisogno di trovare uno snippet di DNA in un cromosoma.

Nei media, gli editori individuano una frase particolare in un testo voluminoso. La sorveglianza dei dati rileva truffe o spam cercando parole sospette incorporate nei dati.

In ogni contesto, la ricerca è così ben nota e un compito arduo da essere comunemente chiamato "Needle in a Haystack Problem" . In questo tutorial, dimostreremo un semplice algoritmo che utilizza il metodo indexOf (String str, int fromIndex) della classe Java String per trovare tutte le occorrenze di una parola all'interno di una stringa.

2. Algoritmo semplice

Invece di contare semplicemente le occorrenze di una parola in un testo più grande, il nostro algoritmo troverà e identificherà ogni posizione in cui una parola specifica esiste nel testo. Il nostro approccio al problema è breve e semplice in modo che:

  1. La ricerca troverà la parola anche all'interno delle parole nel testo . Pertanto, se stiamo cercando la parola "in grado", la troveremo in "comodo" e "tablet".
  2. La ricerca non farà distinzione tra maiuscole e minuscole .
  3. L'algoritmo si basa sull'approccio ingenuo della ricerca di stringhe . Ciò significa che poiché siamo ingenui riguardo alla natura dei caratteri nella parola e nella stringa di testo, useremo la forza bruta per controllare ogni posizione del testo per un'istanza della parola di ricerca.

2.1. Implementazione

Ora che abbiamo definito i parametri per la nostra ricerca, scriviamo una semplice soluzione:

public class WordIndexer { public List findWord(String textString, String word) { List indexes = new ArrayList(); String lowerCaseTextString = textString.toLowerCase(); String lowerCaseWord = word.toLowerCase(); int index = 0; while(index != -1){ index = lowerCaseTextString.indexOf(lowerCaseWord, index); if (index != -1) { indexes.add(index); index++; } } return indexes; } }

2.2. Testare la soluzione

Per testare il nostro algoritmo, utilizzeremo uno snippet di un famoso passaggio dell'Amleto di Shakespeare e cercheremo la parola "o", che appare cinque volte:

@Test public void givenWord_whenSearching_thenFindAllIndexedLocations() { String theString; WordIndexer wordIndexer = new WordIndexer(); theString = "To be, or not to be: that is the question: " + "Whether 'tis nobler in the mind to suffer " + "The slings and arrows of outrageous fortune, " + "Or to take arms against a sea of troubles, " + "And by opposing end them? To die: to sleep; " + "No more; and by a sleep to say we end " + "The heart-ache and the thousand natural shocks " + "That flesh is heir to, 'tis a consummation " + "Devoutly to be wish'd. To die, to sleep; " + "To sleep: perchance to dream: ay, there's the rub: " + "For in that sleep of death what dreams may come,"; List expectedResult = Arrays.asList(7, 122, 130, 221, 438); List actualResult = wordIndexer.findWord(theString, "or"); assertEquals(expectedResult, actualResult); }

Quando eseguiamo il nostro test, otteniamo il risultato atteso. La ricerca di "o" produce cinque istanze incorporate in vari modi nella stringa di testo:

index of 7, in "or" index of 122, in "fortune" index of 130, in "Or index of 221, in "more" index of 438, in "For"

In termini matematici, l'algoritmo ha una notazione Big-O di O (m * (nm)) , dove m è la lunghezza della parola en è la lunghezza della stringa di testo. Questo approccio può essere appropriato per stringhe di testo di pagliaio di poche migliaia di caratteri, ma sarà intollerabilmente lento se ci sono miliardi di caratteri.

3. Algoritmo migliorato

Il semplice esempio sopra mostra un approccio ingenuo e brutale alla ricerca di una data parola in una stringa di testo. In quanto tale, funzionerà per qualsiasi parola di ricerca e qualsiasi testo.

Se sappiamo in anticipo che la parola di ricerca non contiene uno schema ripetitivo di caratteri, come "aaa", allora possiamo scrivere un algoritmo leggermente più efficiente.

In questo caso, possiamo tranquillamente evitare di eseguire il backup per ricontrollare ogni posizione nella stringa di testo come potenziale posizione di partenza. Dopo aver effettuato la chiamata al metodo indexOf () , scorreremo semplicemente nella posizione subito dopo la fine dell'ultima occorrenza trovata. Questo semplice aggiustamento produce uno scenario migliore di O (n) .

Diamo un'occhiata a questa versione migliorata del precedente metodo findWord () .

public List findWordUpgrade(String textString, String word) { List indexes = new ArrayList(); StringBuilder output = new StringBuilder(); String lowerCaseTextString = textString.toLowerCase(); String lowerCaseWord = word.toLowerCase(); int wordLength = 0; int index = 0; while(index != -1){ index = lowerCaseTextString.indexOf(lowerCaseWord, index + wordLength); // Slight improvement if (index != -1) { indexes.add(index); } wordLength = word.length(); } return indexes; }

4. Conclusione

In questo tutorial, abbiamo presentato un algoritmo di ricerca senza distinzione tra maiuscole e minuscole per trovare tutte le varianti di una parola in una stringa di testo più grande. Ma non lasciare che questo nasconda il fatto che il metodo indexOf () della classe Java String è intrinsecamente sensibile al maiuscolo / minuscolo e può distinguere tra "Bob" e "bob", per esempio.

Complessivamente, indexOf () è un metodo conveniente per trovare una sequenza di caratteri sepolta in una stringa di testo senza eseguire alcuna codifica per manipolazioni di sottostringa.

Come al solito, la base di codice completa di questo esempio è finita su GitHub.