streamalism.org

1. Prehľad

Hľadanie vzoru znakov alebo slova vo väčšom textovom reťazci sa vykonáva v rôznych oblastiach. Napríklad v bioinformatike možno budeme musieť nájsť fragment DNA v chromozóme.

V médiách editori nájdu konkrétnu frázu v objemnom texte. Dátový dohľad zisťuje podvody alebo spam vyhľadaním podozrivých slov vložených do údajov.

V každom kontexte je hľadanie také známe a odstrašujúce, že sa ľudovo nazýva „Ihla v kope sena“. V tomto výučbe si ukážeme jednoduchý algoritmus, ktorý používa indexOf (String str, int fromIndex) metóda Java String triedy na vyhľadanie všetkých výskytov slova v reťazci.

2. Jednoduchý algoritmus

Namiesto jednoduchého počítania výskytov slova vo väčšom texte náš algoritmus vyhľadá a identifikuje všetky miesta, kde sa v texte nachádza konkrétne slovo. Náš prístup k problému je krátky a jednoduchý, takže:

1. Hľadanie nájdu slovo aj v rámci slov v texte. Preto, ak hľadáme slovo „schopný“, nájdeme ho v „pohodlnom“ a „tablete“.
2. Hľadanie nebude rozlišovať veľké a malé písmená.
3. Algoritmus je založený na prístupe vyhľadávania naivných reťazcov. To znamená, že keďže sme naivní v otázke povahy znakov v slove a textovom reťazci, použijeme hrubou silou na to, aby sme skontrolovali každé umiestnenie textu pre prípad hľadaného slova.

2.1. Implementácia

Teraz, keď sme definovali parametre nášho vyhľadávania, napíšme jednoduché riešenie:

public class WordIndexer {public List findWord (String textString, String word) {List indexes = new ArrayList (); Reťazec lowerCaseTextString = textString.toLowerCase (); Reťazec lowerCaseWord = word.toLowerCase (); int index = 0; while (index! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index); if (index! = -1) {indexes.add (index); index ++; }} návratové indexy; }}

2.2. Testovanie riešenia

Na otestovanie nášho algoritmu použijeme úryvok slávnej pasáže od Shakespearovho Hamleta a vyhľadáme slovo „alebo“, ktoré sa objaví päťkrát:

@Test public void givenWord_whenSearching_thenFindAllIndexedLocations () {String theString; WordIndexer wordIndexer = nový WordIndexer (); theString = "Byť alebo nebyť: to je otázka:" + "Či je ušľachtilejšie myslieť trpieť" + "Viazacie prostriedky a šípy nehorázneho šťastia," + "Alebo vziať zbrane proti moru mora ťažkosti, "+" A keď ich postavíme proti? Zomrieme: spíme; "+" Už nie; a spánkom povedzme, že skončíme "+" Bolesť srdca a tisíc prírodných šokov "+" To mäso je dedičom " je, je to zavŕšenie "+" Zbožne si prajem. Zomrieť, spať; "+" Spať: možnosť snívať: ay, je tu rub: "+" Lebo v tom spánku smrti môžu byť sny prísť, "; Zoznam očakávaných výsledkov = Arrays.asList (7, 122, 130, 221, 438); Zoznam skutočných výsledkov = wordIndexer.findWord (reťazec, "alebo"); assertEquals (expectResult, actualResult); }

Keď spustíme náš test, dostaneme očakávaný výsledok. Vyhľadávanie výrazu „alebo“ prinesie päť inštancií vložených rôznymi spôsobmi do textového reťazca:

index 7, v indexe „alebo“ 122, v indexe „šťastia“ 130, v „Alebo index 221, v„ viac “index 438, v„ Pre “

Z matematického hľadiska má algoritmus označenie Big-O O (m * (n-m)), kde m je dĺžka slova a n je dĺžka textového reťazca. Tento prístup môže byť vhodný pre textové reťazce sena s niekoľko tisíc znakmi, ale bude neúnosne pomalý, ak budú obsahovať miliardy znakov.

3. Vylepšený algoritmus

Jednoduchý príklad vyššie demonštruje naivný prístup hrubou silou k hľadaniu daného slova v textovom reťazci. Ako taký bude fungovať pre každé hľadané slovo a akýkoľvek text.

Ak vopred vieme, že hľadané slovo neobsahuje opakujúce sa vzory znakov, napríklad „aaa“, môžeme napísať o niečo efektívnejší algoritmus.

V takom prípade sa môžeme bezpečne vyhnúť zálohovaniu, aby sme znova skontrolovali každé miesto v textovom reťazci ako potenciálne počiatočné miesto. Potom, čo zavoláme do indexOf () metódou, jednoducho sa presunieme na miesto bezprostredne po konci posledného nájdeného výskytu. Toto jednoduché vyladenie poskytuje najlepší možný scenár O (n).

Pozrime sa na túto vylepšenú verziu predchádzajúcej verzie findWord () metóda.

public List findWordUpgrade (String textString, String word) {List indexes = new ArrayList (); Výstup StringBuilder = nový StringBuilder (); Reťazec lowerCaseTextString = textString.toLowerCase (); Reťazec lowerCaseWord = word.toLowerCase (); int wordLength = 0; int index = 0; while (index! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index + wordLength); // Mierne zlepšenie if (index! = -1) {indexes.add (index); } wordLength = word.length (); } návratové indexy; }

4. Záver

V tomto tutoriáli sme predstavili vyhľadávací algoritmus, ktorý nerozlišuje veľkosť písmen, aby sme našli všetky variácie slova vo väčšom textovom reťazci. Ale nenechajte sa tým skryť skutočnosť, že Java String trieda' indexOf () Táto metóda vo svojej podstate rozlišuje veľké a malé písmená a môže rozlišovať napríklad medzi „Bob“ a „bob“.

Celkom, indexOf () je pohodlná metóda na vyhľadanie postupnosti znakov zakopaných v textovom reťazci bez nutnosti kódovania manipulácie s podreťazcami.

Ako obvykle je celá základňa kódov tohto príkladu na GitHub skončená.