Utilisation d'indexOf pour rechercher toutes les occurrences d'un mot dans une chaîne

1. Vue d'ensemble

La corvée de recherche d'un modèle de caractères, ou d'un mot, dans une chaîne de texte plus grande se fait dans divers champs. En bioinformatique, par exemple, nous pouvons avoir besoin de trouver un extrait d'ADN dans un chromosome.

Dans les médias, les rédacteurs localisent une phrase particulière dans un texte volumineux. La surveillance des données détecte les escroqueries ou les spams en recherchant des mots suspects intégrés dans les données.

Dans tous les contextes, la recherche est si connue et si intimidante qu'elle est communément appelée «l'aiguille dans un problème de meule de foin» . Dans ce didacticiel, nous allons démontrer un algorithme simple qui utilise la méthode indexOf (String str, int fromIndex) de la classe Java String pour rechercher toutes les occurrences d'un mot dans une chaîne.

2. Algorithme simple

Au lieu de simplement compter les occurrences d'un mot dans un texte plus grand, notre algorithme trouvera et identifiera chaque emplacement où un mot spécifique existe dans le texte. Notre approche du problème est courte et simple afin que:

  1. La recherche trouvera le mot même dans les mots du texte . Par conséquent, si nous recherchons le mot «capable», nous le trouverons dans «confortable» et «tablette».
  2. La recherche sera insensible à la casse .
  3. L'algorithme est basé sur l'approche naïve de recherche de chaînes . Cela signifie que puisque nous sommes naïfs sur la nature des caractères du mot et de la chaîne de texte, nous utiliserons la force brute pour vérifier chaque emplacement du texte pour une instance du mot recherché.

2.1. la mise en oeuvre

Maintenant que nous avons défini les paramètres de notre recherche, écrivons une solution simple:

public class WordIndexer { public List findWord(String textString, String word) { List indexes = new 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++; } } return indexes; } }

2.2. Tester la solution

Pour tester notre algorithme, nous allons utiliser un extrait d'un passage célèbre du Hamlet de Shakespeare et rechercher le mot «ou», qui apparaît cinq fois:

@Test public void givenWord_whenSearching_thenFindAllIndexedLocations() { String theString; WordIndexer wordIndexer = new WordIndexer(); theString = "To be, or not to be: that is the question: " + "Whether 'tis nobler in the mind to suffer " + "The slings and arrows of outrageous fortune, " + "Or to take arms against a sea of troubles, " + "And by opposing end them? To die: to sleep; " + "No more; and by a sleep to say we end " + "The heart-ache and the thousand natural shocks " + "That flesh is heir to, 'tis a consummation " + "Devoutly to be wish'd. To die, to sleep; " + "To sleep: perchance to dream: ay, there's the rub: " + "For in that sleep of death what dreams may come,"; List expectedResult = Arrays.asList(7, 122, 130, 221, 438); List actualResult = wordIndexer.findWord(theString, "or"); assertEquals(expectedResult, actualResult); }

Lorsque nous exécutons notre test, nous obtenons le résultat attendu. La recherche de «ou» génère cinq instances intégrées de différentes manières dans la chaîne de texte:

index of 7, in "or" index of 122, in "fortune" index of 130, in "Or index of 221, in "more" index of 438, in "For"

En termes mathématiques, l'algorithme a une notation Big-O de O (m * (nm)) , où m est la longueur du mot et n est la longueur de la chaîne de texte. Cette approche peut être appropriée pour des chaînes de texte de botte de foin de quelques milliers de caractères mais sera intolérablement lente s'il y a des milliards de caractères.

3. Algorithme amélioré

L'exemple simple ci-dessus illustre une approche naïve de force brute pour rechercher un mot donné dans une chaîne de texte. En tant que tel, il fonctionnera pour n'importe quel mot de recherche et n'importe quel texte.

Si nous savons à l'avance que le mot recherché ne contient pas de motif répétitif de caractères, tel que «aaa», alors nous pouvons écrire un algorithme légèrement plus efficace.

Dans ce cas, nous pouvons éviter en toute sécurité de faire la sauvegarde pour revérifier chaque emplacement de la chaîne de texte comme emplacement de départ potentiel. Après avoir appelé la méthode indexOf () , nous allons simplement glisser sur l'emplacement juste après la fin de la dernière occurrence trouvée. Ce simple ajustement donne un meilleur scénario de O (n) .

Regardons cette version améliorée de la méthode précédente findWord () .

public List findWordUpgrade(String textString, String word) { List indexes = new ArrayList(); StringBuilder output = new StringBuilder(); String lowerCaseTextString = textString.toLowerCase(); String lowerCaseWord = word.toLowerCase(); int wordLength = 0; int index = 0; while(index != -1){ index = lowerCaseTextString.indexOf(lowerCaseWord, index + wordLength); // Slight improvement if (index != -1) { indexes.add(index); } wordLength = word.length(); } return indexes; }

4. Conclusion

Dans ce didacticiel, nous avons présenté un algorithme de recherche insensible à la casse pour trouver toutes les variantes d'un mot dans une chaîne de texte plus grande. Mais ne laissez pas cela cacher le fait que la méthode indexOf () de la classe Java String est intrinsèquement sensible à la casse et peut faire la distinction entre «Bob» et «bob», par exemple.

Dans l'ensemble, indexOf () est une méthode pratique pour trouver une séquence de caractères enfouie dans une chaîne de texte sans faire de codage pour les manipulations de sous-chaînes.

Comme d'habitude, la base de code complète de cet exemple est terminée sur GitHub.