streamalism.org

1. Oversikt

Oppgaven med å søke etter et mønster av tegn, eller et ord, i en større tekststreng gjøres i forskjellige felt. I bioinformatikk, for eksempel, kan det hende vi trenger å finne et DNA-snutt i et kromosom.

I media finner redaktører en bestemt setning i en omfattende tekst. Dataovervåking oppdager svindel eller spam ved å lete etter mistenkelige ord innebygd i data.

I alle sammenhenger er søket så kjent og skremmende et ork som det kalles populært “Nålen i et høystakproblem”. I denne opplæringen vil vi demonstrere en enkel algoritme som bruker indexOf (strengstreng, int fraIndex) metoden til Java String klasse for å finne alle forekomster av et ord i en streng.

2. Enkel algoritme

I stedet for å bare telle forekomsten av et ord i en større tekst, vil algoritmen vår finne og identifisere hvert sted der et bestemt ord eksisterer i teksten. Vår tilnærming til problemet er kort og enkel slik at:

1. Søket vil finne ordet selv innenfor ord i teksten. Derfor, hvis vi søker etter ordet "stand", så finner vi det på "behagelig" og "nettbrett".
2. Søket vil være store og små bokstaver.
3. Algoritmen er basert på den naive tilnærmingen til strengesøk. Dette betyr at siden vi er naive med hensyn til karakteren i ordet og tekststrengen, vil vi bruke brutal kraft for å sjekke hvert sted i teksten for en forekomst av søkeordet.

2.1. Gjennomføring

Nå som vi har definert parametrene for søket, la oss skrive en enkel løsning:

public class 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. Testing av løsningen

For å teste algoritmen vår, bruker vi et utdrag av en berømt passasje fra Shakespeares Hamlet og søker etter ordet “eller”, som vises fem ganger:

@Test offentlig ugyldig givenWord_whenSearching_thenFindAllIndexedLocations () {String theString; WordIndexer wordIndexer = ny WordIndexer (); theString = "Å være, eller ikke være: det er spørsmålet:" + "Hvorvidt det er edlere i tankene å lide" + "Slyngene og pilene til opprørende formue," + "Eller å ta våpen mot et hav av problemer, "+" Og ved å motsette dem? Å dø: å sove; "+" Ikke mer, og ved å sove for å si at vi slutter "+" Hjertesmerter og de tusen naturlige sjokkene "+" Det kjøttet er arving. til, 'er en fullbyrdelse "+" Devoutly to be wish'd. To 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 (expectResult, actualResult); }

Når vi kjører testen, får vi forventet resultat. Å søke etter "eller" gir fem forekomster innebygd på forskjellige måter i tekststrengen:

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

I matematiske termer har algoritmen en Big-O-notasjon av O (m * (n-m)), hvor m er lengden på ordet og n er lengden på tekststrengen. Denne tilnærmingen kan være hensiktsmessig for tekststakstrenger med høystakke på noen få tusen tegn, men vil være utålelig treg hvis det er milliarder tegn.

3. Forbedret algoritme

Det enkle eksemplet ovenfor viser en naiv, brute-force tilnærming til å søke etter et gitt ord i en tekststreng. Som sådan vil det fungere for ethvert søkeord og tekst.

Hvis vi på forhånd vet at søkeordet ikke inneholder et repeterende mønster av tegn, for eksempel “aaa”, så kan vi skrive en litt mer effektiv algoritme.

I dette tilfellet kan vi trygt unngå å ta sikkerhetskopien for å sjekke hvert sted i tekststrengen på nytt som et potensielt startsted. Etter at vi ringer til oversikt over( ) metode, vil vi bare skyve over til stedet like etter slutten av den siste hendelsen som ble funnet. Denne enkle finjusteringen gir et best-case scenario av På).

La oss se på denne forbedrede versjonen av den tidligere finn ord () metode.

public List findWordUpgrade (String textString, String word) {List indexes = new ArrayList (); StringBuilder-utgang = 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); // Litt forbedring hvis (indeks! = -1) {indexes.add (index); } wordLength = word.length (); } returindekser; }

4. Konklusjon

I denne opplæringen presenterte vi en saksfølsom søkealgoritme for å finne alle varianter av et ord i en større tekststreng. Men ikke la det skjule det faktum at Java String klasse' oversikt over() metoden er i hovedsak store og små bokstaver og kan for eksempel skille mellom "Bob" og "bob".

Alt i alt oversikt over() er en praktisk metode for å finne en tegnsekvens begravet i en tekststreng uten å gjøre noen koding for substringmanipulasjoner.

Som vanlig er hele kodebasen i dette eksemplet over på GitHub.