Az indexOf használata egy szó minden előfordulásának megkereséséhez egy karakterláncban

1. Áttekintés

Karakterminta vagy szó keresése a nagyobb szöveges karakterláncban különféle mezőkön történik. A bioinformatikában például előfordulhat, hogy egy kromoszómában meg kell találnunk egy DNS-részletet.

A médiában a szerkesztők megkeresik egy adott kifejezést egy terjedelmes szövegben. Az adatfelügyelet az adatokba ágyazott gyanús szavak keresésével észleli a csalásokat vagy a spamet.

Bármilyen összefüggésben a keresés annyira közismert és félelmetes munka, hogy népszerûen hívják a „tű a szénakazalban”. Ebben az oktatóanyagban bemutatunk egy egyszerű algoritmust, amely a indexOf (String str, int fromIndex) módszer a Java Húr osztály, hogy megtalálja a szó minden előfordulását egy karakterláncban.

2. Egyszerű algoritmus

Ahelyett, hogy egyszerűen megszámolnánk egy szó előfordulását egy nagyobb szövegben, algoritmusunk megtalálja és azonosítja azokat a helyeket, ahol egy adott szó létezik a szövegben. Megközelítésünk a problémára rövid és egyszerű, így:

  1. A keresés még a szavakban is megtalálják a szót a szövegben. Ezért, ha a „képes” szóra keresünk, akkor a „kényelmes” és a „táblagép” szavakban találjuk meg.
  2. A keresés kis- és nagybetűk nem lesznek.
  3. Az algoritmus naiv karakterlánc-keresési megközelítésen alapul. Ez azt jelenti, hogy mivel naivak vagyunk a szóban és a szövegben szereplő karakterek természetével kapcsolatban, nyers erővel ellenőrizzük a szöveg minden helyét a keresett szó egyik példányában.

2.1. Végrehajtás

Most, hogy meghatároztuk a keresés paramétereit, írjunk egy egyszerű megoldást:

public class WordIndexer {public List findWord (String textString, String word) {List indexek = new ArrayList (); String lowerCaseTextString = textString.toLowerCase (); Karakterlánc alsóCaseWord = word.toLowerCase (); int index = 0; while (index! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index); if (index! = -1) {indexek.add (index); index ++; }} visszatérési indexek; }}

2.2. A megoldás tesztelése

Algoritmusunk teszteléséhez használjuk Shakespeare Hamlet híres részének részletét, és keressük meg az ötször megjelenő „vagy” szót:

@Test public void givenWord_whenSearching_thenFindAllIndexedLocations () {String theString; WordIndexer wordIndexer = új WordIndexer (); theString = "Lenni vagy nem lenni: ez a kérdés:" + "Vajon nemesebb-e az elmében szenvedni" + "A felháborító vagyon hevederei és nyilai," + "Vagy fegyvert fogni a tengerre bajok, "+" És azzal, hogy szembeszállnak velük? Meghalni: aludni; "+" Nincs több; és alvással azt mondani, hogy véget érünk "+" A szívfájdalom és az ezer természetes sokk "+" Ez a test örökös "," ez kiteljesedés "+" Áhítatosan kívánni kívánni. Meghalni, aludni; "+" Aludni: az álom képessége: ay, ott van a dörzsölés: "+" Mert ebben a halálálomban milyen álmok lehetnek jön,"; List Várható Eredmény = Tömbök.asList (7, 122, 130, 221, 438); Sorolja fel a actualResult = wordIndexer.findWord listát (theString, "vagy"); assertEquals (várható eredmény, tényleges eredmény); }

Amikor lefuttatjuk tesztünket, megkapjuk a várt eredményt. A „vagy” keresésre öt különböző módon beágyazott példány jön létre a szöveges karakterláncban:

index 7, in "vagy" index 122, a "szerencse" index 130, a "Vagy index 221, a" több "index 438, a" For "

Matematikai szempontból az algoritmus Big-O jelölésével rendelkezik O (m * (n-m)), hol m a szó hossza és n a szöveges karakterlánc hossza. Ez a megközelítés megfelelő lehet néhány ezer karakteres szénakazal szöveges karakterláncok esetében, de elviselhetetlenül lassú lesz, ha több milliárd karakter van.

3. Továbbfejlesztett algoritmus

A fenti egyszerű példa naiv, durva erővel szemlélteti az adott szó keresését egy szövegláncban. Mint ilyen, minden keresőszóra és szövegre használható.

Ha előre tudjuk, hogy a keresőszó nem tartalmaz ismétlődő karaktermintát, például „aaa”, akkor valamivel hatékonyabb algoritmust írhatunk.

Ebben az esetben biztonságosan elkerülhetjük a biztonsági másolat készítését, hogy a szöveges karaktersorozat minden helyét újra ellenőrizzük potenciális kiindulási helyként. Miután felhívtuk a indexe( ) módszerrel egyszerűen átcsúszunk a helyre, közvetlenül a legutóbbi talált esemény vége után. Ez az egyszerű csípés a legjobb esetet eredményezi Tovább).

Nézzük meg a korábbiak ezt a továbbfejlesztett változatát findWord () módszer.

public List findWordUpgrade (String textString, String word) {Lista indexek = new ArrayList (); StringBuilder kimenet = new StringBuilder (); String lowerCaseTextString = textString.toLowerCase (); Karakterlánc alsóCaseWord = word.toLowerCase (); int szóHossz = 0; int index = 0; while (index! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index + wordLength); // Enyhe javulás if (index! = -1) {indexes.add (index); } szóHossz = szó.hossz (); } visszatérési indexek; }

4. Következtetés

Ebben az oktatóanyagban egy kis- és nagybetû nélküli keresési algoritmust mutattunk be, amely egy szó minden változatát egy nagyobb szöveges karakterláncban találja meg. De ne hagyd, hogy ez elrejtse azt a tényt, hogy a Java Húr osztály' indexe() A módszer eleve különbséget tesz a kis- és nagybetűk között, és megkülönböztetheti például a „Bob” és a „bob” szavakat.

Teljesen, indexe() egy kényelmes módszer a karakterláncokba eltemetve egy szöveg karaktersorozatba, anélkül, hogy bármilyen kódolást végeznénk a szubsztrációs manipulációkhoz.

Szokás szerint ennek a példának a teljes kódalapja befejeződött a GitHubon.