streamalism.org

1. Pregled

Zadatak pretraživanja uzorka znakova ili riječi u većem tekstualnom nizu obavlja se u raznim poljima. Primjerice, u bioinformatici možda ćemo morati pronaći isječak DNA u kromosomu.

U medijima urednici pronalaze određenu frazu u obimnom tekstu. Nadzor podataka otkriva prevare ili neželjenu poštu tražeći sumnjive riječi ugrađene u podatke.

U bilo kojem kontekstu, potraga je toliko poznata i zastrašujući posao, da je popularno nazvana "Igla u problemu plasta sijena". U ovom uputstvu demonstrirat ćemo jednostavan algoritam koji koristi indexOf (String str, int fromIndex) metoda Java Niz klasa za pronalaženje svih pojava riječi unutar niza.

2. Jednostavni algoritam

Umjesto jednostavnog brojanja pojavljivanja riječi u većem tekstu, naš će algoritam pronaći i identificirati svako mjesto na kojem u tekstu postoji određena riječ. Naš pristup problemu je kratak i jednostavan tako da:

1. Potraga naći će riječ čak i unutar riječi u tekstu. Stoga, ako tražimo riječ "sposoban", naći ćemo je u "udobnom" i "tabletu".
2. Potraga neće razlikovati mala i velika slova.
3. Algoritam temelji se na pristupu pretraživanja naivnih nizova. To znači da ćemo, budući da smo naivni prema prirodi znakova u riječi i tekstnom nizu, grubom silom provjeriti svako mjesto teksta za primjerak riječi za pretraživanje.

2.1. Provedba

Sad kad smo definirali parametre za svoje pretraživanje, napišimo jednostavno rješenje:

javna klasa WordIndexer {javni popis findWord (String textString, String word) {Indeksi popisa = novi ArrayList (); Niz lowerCaseTextString = textString.toLowerCase (); Niz lowerCaseWord = word.toLowerCase (); indeks int = 0; while (index! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index); if (indeks! = -1) {indexes.add (indeks); indeks ++; }} indeksi povrata; }}

2.2. Testiranje rješenja

Za testiranje našeg algoritma upotrijebit ćemo isječak poznatog odlomka iz Shakespeareova Hamleta i potražiti riječ "ili" koja se pojavljuje pet puta:

@Test javna praznina givenWord_whenSearching_thenFindAllIndexedLocations () {String theString; WordIndexer wordIndexer = novi WordIndexer (); theString = "Biti ili ne biti: to je pitanje:" + "Je li to plemenitije u umu da trpi" + "Priveznice i strijele nečuvene sreće," + "Ili uzeti oružje protiv mora nevolje, "+" A suprotstavljanjem da ih okončate? Umrijeti: spavati; "+" Nema više; a snom reći da prestajemo "+" Bolovi u srcu i tisuće prirodnih šokova "+" To je tijelo nasljednik to, 'to je svršetak "+" Pobožno biti poželjan. Umrijeti, zaspati; "+" Spavati: možda sanjati: ay, tu je trljanje: "+" Jer u tom snu smrti mogu sanjati dođi, "; Popis očekujeResult = Arrays.asList (7, 122, 130, 221, 438); Navesti stvarni rezultat = wordIndexer.findWord (theString, "ili"); assertEquals (očekivani rezultat, stvarni rezultat); }

Kada pokrenemo test, dobivamo očekivani rezultat. Traženje "ili" daje pet slučajeva ugrađenih na razne načine u tekstualni niz:

indeks 7, u "ili" indeks 122, u "fortune" indeks 130, u "Ili indeks 221, u" više "indeks 438, u" Za "

U matematičkom smislu, algoritam ima Big-O oznaku O (m * (n-m)), gdje m je duljina riječi i n je duljina tekstualnog niza. Ovaj pristup može biti prikladan za nizove teksta sijena od nekoliko tisuća znakova, ali bit će nesnosno spor ako postoji milijarda znakova.

3. Poboljšani algoritam

Gornji jednostavni primjer pokazuje naivan, grubi pristup traženju zadane riječi u tekstualnom nizu. Kao takav, funkcionirat će za bilo koju riječ za pretraživanje i bilo koji tekst.

Ako unaprijed znamo da riječ za pretraživanje ne sadrži ponavljajući uzorak znakova, poput "aaa", tada možemo napisati malo učinkovitiji algoritam.

U ovom slučaju možemo sigurno izbjeći izradu sigurnosne kopije kako bismo ponovno provjerili svako mjesto u tekstnom nizu kao potencijalno početno mjesto. Nakon što uputimo poziv na indexOf () metodom, jednostavno ćemo prijeći na mjesto neposredno nakon završetka zadnjeg pronađenog događaja. Ovaj jednostavan dotjerivanje daje najbolji slučaj za Na).

Pogledajmo ovu poboljšanu verziju ranije findWord () metoda.

javni popis findWordUpgrade (String textString, String word) {Indeksi popisa = novi ArrayList (); StringBuilder output = novi StringBuilder (); Niz lowerCaseTextString = textString.toLowerCase (); Niz lowerCaseWord = word.toLowerCase (); int wordLength = 0; indeks int = 0; while (index! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index + wordLength); // Neznatno poboljšanje if (index! = -1) {indexes.add (index); } wordLength = word.length (); } indeksi povrata; }

4. Zaključak

U ovom smo uputstvu predstavili algoritam pretraživanja koji ne razlikuje velika i mala slova kako bismo pronašli sve varijacije riječi u većem tekstualnom nizu. Ali neka to ne skriva činjenicu da Java Niz razred ' indexOf () metoda suštinski razlikuje velika i mala slova i može razlikovati između "Bob" i "bob", na primjer.

Sve u svemu, indexOf () je prikladna metoda za pronalaženje niza znakova zakopanih u tekstualni niz bez ikakvog kodiranja za manipulacije podnizom.

Kao i obično, kompletna baza kodova ovog primjera završena je na GitHubu.