Brug af indexOf til at finde alle forekomster af et ord i en streng

1. Oversigt

Arbejdet med at søge efter et mønster af tegn eller et ord i en større tekststreng udføres i forskellige felter. I bioinformatik kan vi f.eks. Være nødt til at finde et DNA-uddrag i et kromosom.

I medierne finder redaktører en bestemt sætning i en omfangsrig tekst. Dataovervågning registrerer svindel eller spam ved at lede efter mistænkelige ord indlejret i data.

I enhver sammenhæng er søgningen så kendt og skræmmende for en opgave, at den populært kaldes “Nålen i et høstakproblem”. I denne vejledning demonstrerer vi en simpel algoritme, der bruger indexOf (String str, int fraIndex) metode til Java Snor klasse for at finde alle forekomster af et ord i en streng.

2. Enkel algoritme

I stedet for blot at tælle forekomsterne af et ord i en større tekst, vil vores algoritme finde og identificere hvert sted, hvor et bestemt ord findes i teksten. Vores tilgang til problemet er kort og enkel, så:

  1. Søgningen finder ordet selv inden for ord i teksten. Derfor, hvis vi søger efter ordet "stand", så finder vi det i "behagelig" og "tablet".
  2. Søgningen vil være store og små bogstaver.
  3. Algoritmen er baseret på den naive tilgang til strengesøgning. Dette betyder, at da vi er naive med hensyn til karaktererne i ordet og tekststrengen, bruger vi brutal kraft til at kontrollere hver placering af teksten for en forekomst af søgeordet.

2.1. Implementering

Nu hvor vi har defineret parametrene til vores søgning, lad os skrive en enkel løsning:

offentlig klasse WordIndexer {public List findWord (String textString, String word) {List indexes = new ArrayList (); String lowerCaseTextString = textString.toLowerCase (); String lowerCaseWord = word.toLowerCase (); int-indeks = 0; mens (index! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index); hvis (indeks! = -1) {indexes.add (index); indeks ++; }} returnere indekser; }}

2.2. Test af løsningen

For at teste vores algoritme bruger vi et uddrag af en berømt passage fra Shakespeares Hamlet og søger efter ordet “eller”, der vises fem gange:

@ Test offentligt ugyldigt givenWord_whenSearching_thenFindAllIndexedLocations () {String theString; WordIndexer wordIndexer = ny WordIndexer (); theString = "At være eller ikke være: det er spørgsmålet:" + "Hvorvidt det er ædlere i sindet at lide" + "Slynger og pile af uhyrlig formue," + "Eller at tage våben mod et hav af problemer, "+" Og ved at modsætte sig ender dem? At dø: at sove; "+" Ikke mere, og ved en søvn til at sige, slutter vi "+" Hjertesmerter og de tusind naturlige chok "+" Det kød er arving til, 'det er en fuldbyrdelse "+" Devoutly to be wish'd. At die, to sleep; "+" To sleep: perchance to dream: ay, there is the rub: "+" For in that sleep of death what dreams may komme,"; Liste forventet resultat = Arrays.asList (7, 122, 130, 221, 438); Liste actualResult = wordIndexer.findWord (theString, "eller"); assertEquals (forventet resultat, faktisk resultat); }

Når vi kører vores test, får vi det forventede resultat. Søgning efter “eller” giver fem forekomster indlejret på forskellige måder i tekststrengen:

indeks på 7, i "eller" indeks på 122, i "formue" indeks på 130, i "Eller indeks på 221, i" mere "indeks på 438, i" For "

I matematiske termer har algoritmen en Big-O-notation af O (m * (n-m)), hvor m er længden af ​​ordet og n er længden af ​​tekststrengen. Denne tilgang kan være hensigtsmæssig til tekststrenge med høstak i nogle få tusinde tegn, men vil være utåleligt langsom, hvis der er milliarder tegn.

3. Forbedret algoritme

Det enkle eksempel ovenfor viser en naiv, brutal kraft tilgang til at søge efter et givet ord i en tekststreng. Som sådan fungerer det for ethvert søgeord og enhver tekst.

Hvis vi på forhånd ved, at søgeordet ikke indeholder et gentaget mønster af tegn, såsom “aaa”, kan vi skrive en lidt mere effektiv algoritme.

I dette tilfælde kan vi sikkert undgå at tage backup for at kontrollere hver placering i tekststrengen igen som en potentiel startplacering. Når vi ringer til indeks af( ) metode glider vi simpelthen over til placeringen lige efter afslutningen af ​​den seneste forekomst. Denne enkle tweak giver et best-case scenario af På).

Lad os se på denne forbedrede version af den tidligere findWord () metode.

public List findWordUpgrade (String textString, String word) {List indexes = new ArrayList (); StringBuilder output = ny StringBuilder (); String lowerCaseTextString = textString.toLowerCase (); String lowerCaseWord = word.toLowerCase (); int wordLength = 0; int-indeks = 0; mens (index! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index + wordLength); // Lille forbedring, hvis (indeks! = -1) {indekser.add (indeks); } wordLength = word.length (); } returnere indekser; }

4. Konklusion

I denne vejledning præsenterede vi en sagsfølsom søgealgoritme for at finde alle variationer af et ord i en større tekststreng. Men lad ikke det skjule det faktum, at Java Snor klasse ' indeks af() metoden er i sagens natur store og små bogstaver og kan f.eks. skelne mellem "Bob" og "bob".

Alt i alt indeks af() er en bekvem metode til at finde en tegnsekvens, der er begravet i en tekststreng uden at foretage nogen kodning til substringmanipulationer.

Som sædvanlig er den komplette codebase i dette eksempel afsluttet på GitHub.