streamalism.org

1. Overzicht

Het zoeken naar een patroon van tekens, of een woord, in een grotere tekstreeks gebeurt in verschillende velden. In bio-informatica moeten we bijvoorbeeld mogelijk een DNA-fragment in een chromosoom vinden.

In de media zoeken redacteuren een bepaalde zin in een omvangrijke tekst. Gegevensbewaking detecteert oplichting of spam door te zoeken naar verdachte woorden die in gegevens zijn ingebed.

In elke context is de zoektocht zo bekend en ontmoedigend dat het in de volksmond wordt genoemd het "Naald in een hooibergprobleem". In deze tutorial demonstreren we een eenvoudig algoritme dat de indexOf (String str, int fromIndex) methode van de Java Draad class om alle exemplaren van een woord binnen een string te vinden.

2. Eenvoudig algoritme

In plaats van simpelweg het aantal keren dat een woord voorkomt in een grotere tekst te tellen, zoekt en identificeert ons algoritme elke locatie waar een specifiek woord in de tekst voorkomt. Onze benadering van het probleem is kort en eenvoudig, zodat:

1. De zoektocht vindt het woord zelfs binnen woorden in de tekst. Daarom, als we zoeken naar het woord ‘in staat’, dan vinden we het in ‘comfortabel’ en ‘tablet’.
2. De zoektocht zal niet hoofdlettergevoelig zijn.
3. Het algoritme is gebaseerd op de naïeve string-zoekbenadering. Dit betekent dat, aangezien we naïef zijn over de aard van de tekens in het woord en de tekstreeks, we brute kracht zullen gebruiken om elke locatie van de tekst te controleren op een instantie van het zoekwoord.

2.1. Implementatie

Nu we de parameters voor onze zoekopdracht hebben gedefinieerd, gaan we een eenvoudige oplossing schrijven:

openbare klasse WordIndexer {openbare lijst findWord (tekenreeks textString, tekenreekswoord) {lijstindexen = nieuwe ArrayList (); String lowerCaseTextString = textString.toLowerCase (); String lowerCaseWord = word.toLowerCase (); int index = 0; while (index! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index); if (index! = -1) {indexes.add (index); index ++; }} retourneer indexen; }}

2.2. De oplossing testen

Om ons algoritme te testen, gebruiken we een fragment van een beroemde passage uit Shakespeare's Hamlet en zoeken we naar het woord 'of', dat vijf keer voorkomt:

@Test openbare leegte gegevenWord_whenSearching_thenFindAllIndexedLocations () {String theString; WordIndexer wordIndexer = nieuwe WordIndexer (); theString = "Zijn of niet zijn: dat is de vraag:" + "Of het nobeler is om te lijden" + "De slingers en pijlen van een buitensporig fortuin", + "Of om wapens te nemen tegen een zee van problemen, "+" En door ze tegen te werken, beëindigen ze? Om te sterven: om te slapen; "+" Niet meer; en door te slapen om te zeggen dat we eindigen "+" De hartpijn en de duizend natuurlijke schokken "+" Dat vlees is erfgenaam naar, 't is een voleinding "+" Vroomwild gewenst. Sterven, slapen; "+" Slapen: misschien dromen: ay, daar is het probleem: "+" Want in die slaap des doods, wat dromen kunnen komen,"; Lijst verwachteResultaat = Arrays.asList (7, 122, 130, 221, 438); Lijst actualResult = wordIndexer.findWord (theString, "of"); assertEquals (verwachtResultaat, actueelResultaat); }

Als we onze test uitvoeren, krijgen we het verwachte resultaat. Zoeken naar 'of' levert vijf instanties op die op verschillende manieren in de tekstreeks zijn ingesloten:

index van 7, in "of" index van 122, in "fortuin" index van 130, in "Of index van 221, in" meer "index van 438, in" Voor "

In wiskundige termen heeft het algoritme een Big-O-notatie van O (m * (n-m)), waar m is de lengte van het woord en n is de lengte van de tekstreeks. Deze benadering kan geschikt zijn voor hooiberg-tekstreeksen van een paar duizend tekens, maar zal ondraaglijk traag zijn als er miljarden tekens zijn.

3. Verbeterd algoritme

Het eenvoudige voorbeeld hierboven demonstreert een naïeve, brutale benadering van het zoeken naar een bepaald woord in een tekstreeks. Als zodanig werkt het voor elk zoekwoord en elke tekst.

Als we van tevoren weten dat het zoekwoord geen herhalend patroon van karakters bevat, zoals “aaa”, dan kunnen we een iets efficiënter algoritme schrijven.

In dit geval kunnen we veilig voorkomen dat we de back-up uitvoeren om elke locatie in de tekstreeks opnieuw te controleren op een mogelijke startlocatie. Nadat we hebben gebeld naar het index van( ) methode, schuiven we gewoon naar de locatie net na het einde van de laatste gevonden gebeurtenis. Deze eenvoudige aanpassing levert een best-case scenario op van Aan).

Laten we eens kijken naar deze verbeterde versie van de eerdere findWord () methode.

openbare lijst findWordUpgrade (String textString, String word) {List indexes = new ArrayList (); StringBuilder output = nieuwe StringBuilder (); String lowerCaseTextString = textString.toLowerCase (); String lowerCaseWord = word.toLowerCase (); int wordLength = 0; int index = 0; while (index! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index + wordLength); // Lichte verbetering if (index! = -1) {indexes.add (index); } wordLength = word.length (); } retourneer indexen; }

4. Conclusie

In deze zelfstudie hebben we een hoofdletterongevoelig zoekalgoritme gepresenteerd om alle variaties van een woord in een grotere tekstreeks te vinden. Maar laat dat niet verbergen dat de Java Draad klasse' index van() De methode is inherent hoofdlettergevoelig en kan bijvoorbeeld onderscheid maken tussen "Bob" en "bob".

Allemaal samen, index van() is een handige methode om een ​​tekenreeks te vinden die in een tekstreeks is begraven zonder enige codering voor substringmanipulaties.

Zoals gewoonlijk is de volledige codebase van dit voorbeeld voorbij op GitHub.