Algorithmes de recherche de chaînes pour les textes volumineux avec Java

1. Introduction

Dans cet article, nous allons montrer plusieurs algorithmes pour rechercher un modèle dans un grand texte. Nous décrirons chaque algorithme avec le code fourni et des connaissances mathématiques simples.

Notez que les algorithmes fournis ne sont pas le meilleur moyen d'effectuer une recherche en texte intégral dans des applications plus complexes. Pour effectuer correctement une recherche en texte intégral, nous pouvons utiliser Solr ou ElasticSearch.

2. Algorithmes

Nous allons commencer par un algorithme de recherche de texte naïf qui est le plus intuitif et qui aide à découvrir d'autres problèmes avancés associés à cette tâche.

2.1. Méthodes d'assistance

Avant de commencer, définissons des méthodes simples de calcul des nombres premiers que nous utilisons dans l'algorithme de Rabin Karp:

public static long getBiggerPrime(int m) { BigInteger prime = BigInteger.probablePrime(getNumberOfBits(m) + 1, new Random()); return prime.longValue(); } private static int getNumberOfBits(int number) { return Integer.SIZE - Integer.numberOfLeadingZeros(number); } 

2.2. Recherche de texte simple

Le nom de cet algorithme le décrit mieux que toute autre explication. C'est la solution la plus naturelle:

public static int simpleTextSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0; while ((i + patternSize) = patternSize) return i; } i += 1; } return -1; }

L'idée de cet algorithme est simple: parcourez le texte et s'il y a une correspondance pour la première lettre du motif, vérifiez si toutes les lettres du motif correspondent au texte.

Si m est un nombre de lettres dans le modèle et n est le nombre de lettres dans le texte, la complexité temporelle de cet algorithme est O (m (nm + 1)) .

Le pire des cas se produit dans le cas d'une chaîne ayant de nombreuses occurrences partielles:

Text: baeldunbaeldunbaeldunbaeldun Pattern: baeldung

2.3. Algorithme de Rabin Karp

Comme mentionné ci-dessus, l'algorithme de recherche de texte simple est très inefficace lorsque les motifs sont longs et lorsqu'il y a beaucoup d'éléments répétés du motif.

L'idée de l'algorithme de Rabin Karp est d'utiliser le hachage pour trouver un motif dans un texte. Au début de l'algorithme, nous devons calculer un hachage du motif qui sera ensuite utilisé dans l'algorithme. Ce processus s'appelle le calcul des empreintes digitales, et nous pouvons trouver une explication détaillée ici.

La chose importante à propos de l'étape de prétraitement est que sa complexité temporelle est O (m) et l'itération à travers le texte prendra O (n), ce qui donne la complexité temporelle de tout l'algorithme O (m + n) .

Code de l'algorithme:

public static int RabinKarpMethod(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; long prime = getBiggerPrime(patternSize); long r = 1; for (int i = 0; i < patternSize - 1; i++) { r *= 2; r = r % prime; } long[] t = new long[textSize]; t[0] = 0; long pfinger = 0; for (int j = 0; j < patternSize; j++) { t[0] = (2 * t[0] + text[j]) % prime; pfinger = (2 * pfinger + pattern[j]) % prime; } int i = 0; boolean passed = false; int diff = textSize - patternSize; for (i = 0; i <= diff; i++) { if (t[i] == pfinger) { passed = true; for (int k = 0; k < patternSize; k++) { if (text[i + k] != pattern[k]) { passed = false; break; } } if (passed) { return i; } } if (i < diff) { long value = 2 * (t[i] - r * text[i]) + text[i + patternSize]; t[i + 1] = ((value % prime) + prime) % prime; } } return -1; }

Dans le pire des cas, la complexité temporelle de cet algorithme est O (m (n-m + 1)) . Cependant, en moyenne, cet algorithme a une complexité temporelle O (n + m) .

De plus, il existe une version Monte Carlo de cet algorithme qui est plus rapide, mais cela peut entraîner des correspondances erronées (faux positifs).

2.4 Algorithme de Knuth-Morris-Pratt

Dans l'algorithme de recherche de texte simple, nous avons vu comment l'algorithme pouvait être lent s'il y avait de nombreuses parties du texte qui correspondent au modèle.

L'idée de l'algorithme de Knuth-Morris-Pratt est le calcul de la table de décalage qui nous fournit les informations où nous devons rechercher nos modèles candidats.

Implémentation Java de l'algorithme KMP:

public static int KnuthMorrisPrattSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; int[] shift = KnuthMorrisPrattShift(pattern); while ((i + patternSize) = patternSize) return i; } if (j > 0) { i += shift[j - 1]; j = Math.max(j - shift[j - 1], 0); } else { i++; j = 0; } } return -1; }

Et voici comment nous calculons la table de décalage:

public static int[] KnuthMorrisPrattShift(char[] pattern) { int patternSize = pattern.length; int[] shift = new int[patternSize]; shift[0] = 1; int i = 1, j = 0; while ((i + j) 
    
      0) { i = i + shift[j - 1]; j = Math.max(j - shift[j - 1], 0); } else { i = i + 1; j = 0; } } } return shift; }
    

La complexité temporelle de cet algorithme est également O (m + n) .

2.5. Algorithme de Boyer-Moore simple

Deux scientifiques, Boyer et Moore, ont proposé une autre idée. Pourquoi ne pas comparer le motif au texte de droite à gauche au lieu de gauche à droite, tout en gardant la même direction de décalage:

public static int BoyerMooreHorspoolSimpleSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; while ((i + patternSize) <= textSize) { j = patternSize - 1; while (text[i + j] == pattern[j]) { j--; if (j < 0) return i; } i++; } return -1; }

Comme prévu, cela se déroulera dans le temps O (m * n) . Mais cet algorithme a conduit à la mise en œuvre de l'occurrence et de l'heuristique de correspondance qui accélère considérablement l'algorithme. On peut en trouver plus ici.

2.6. Algorithme de Boyer-Moore-Horspool

Il existe de nombreuses variantes d'implémentation heuristique de l'algorithme de Boyer-Moore, et la plus simple est la variante Horspool.

Cette version de l'algorithme est appelée Boyer-Moore-Horspool, et cette variation a résolu le problème des décalages négatifs (nous pouvons lire sur le problème de décalage négatif dans la description de l'algorithme de Boyer-Moore).

Comme l'algorithme de Boyer-Moore, la complexité temporelle du pire des cas est O (m * n) tandis que la complexité moyenne est O (n). L'utilisation de l'espace ne dépend pas de la taille du motif, mais uniquement de la taille de l'alphabet qui est de 256 puisque c'est la valeur maximale du caractère ASCII dans l'alphabet anglais:

public static int BoyerMooreHorspoolSearch(char[] pattern, char[] text) { int shift[] = new int[256]; for (int k = 0; k < 256; k++) { shift[k] = pattern.length; } for (int k = 0; k < pattern.length - 1; k++){ shift[pattern[k]] = pattern.length - 1 - k; } int i = 0, j = 0; while ((i + pattern.length) <= text.length) { j = pattern.length - 1; while (text[i + j] == pattern[j]) { j -= 1; if (j < 0) return i; } i = i + shift[text[i + pattern.length - 1]]; } return -1; }

4. Conclusion

Dans cet article, nous avons présenté plusieurs algorithmes de recherche de texte. Étant donné que plusieurs algorithmes nécessitent des connaissances mathématiques plus solides, nous avons essayé de représenter l'idée principale sous chaque algorithme et de la fournir de manière simple.

Et, comme toujours, le code source peut être trouvé sur GitHub.