Pour appréhender l’analyse de chaînes de caractères et la recherche de motifs, j'adopte une démarche de décomposition rigoureuse avant toute phase de développement. Face au problème complexe de la recherche textuelle, j'identifie précisément la nature des données manipulées, les entrées (le texte global et le motif recherché) et les sorties attendues (la liste des positions trouvées).
Par exemple, lors de l'étude des quatre algorithmes (Naïf, Knuth-Morris-Pratt, Rabin-Karp et Boyer-Moore), nous avons formalisé la logique propre à chacun pour isoler le cœur de la recherche de ses fonctions périphériques. Cette formalisation en étapes logiques en amont m’a permis de comprendre précisément les mécanismes de saut ou de fenêtres glissantes avant de transcrire le comportement des algorithmes sous forme de code fonctionnel.
Savoir sélectionner les structures de données appropriées est indispensable pour garantir l'efficacité d'un programme face à des contraintes de performance. Dans le cadre de cette SAÉ, nous avons fait le choix stratégique de manipuler le texte sous forme d'une ArrayList<Character>.
Cette structure s’est révélée particulièrement adaptée pour nos tests d'efficacité à grande échelle, facilitant la manipulation dynamique et l'accès séquentiel lors des parcours. De plus, selon l'algorithme implémenté, des structures complémentaires spécifiques ont été choisies pour optimiser les traitements, à l'image de l'utilisation de dictionnaires/tables de hachage (HashMap) pour stocker la table des sauts du mauvais caractère dans Boyer-Moore, ou de structures de tableaux d’entiers (int[]) pour la table LPS (Longest Prefix Suffix) de KMP.
L'objectif de cette compétence est de ne pas se contenter d'une solution fonctionnelle, mais de concevoir et comparer plusieurs approches algorithmiques pour retenir la plus performante selon le contexte. Nous avons ainsi mis en opposition l'algorithme Naïf avec trois algorithmes avancés de recherche de motifs.
Cette comparaison a mis en évidence qu’un algorithme n'est pas universellement optimal : si l'approche naïve s'avère coûteuse sur des textes répétitifs, des algorithmes comme Boyer-Moore ou KMP exploitent astucieusement la structure des données pour sauter des comparaisons inutiles. Boyer-Moore s'est notamment distingué comme la solution la plus optimisée et robuste en pratique, réduisant drastiquement le nombre de comparaisons sur les données aléatoires et répétitives.
Pour valider scientifiquement nos choix et mesurer l’efficacité des solutions, nous avons mis en œuvre une démarche d'évaluation expérimentale de la complexité temporelle. Nous avons implémenté des compteurs d’opérations critiques ainsi que des mesures de temps d’exécution (en millisecondes) au sein de nos programmes Java.
Les tests ont été systématiquement exécutés sur des volumes croissants de données (jusqu'à plusieurs millions de caractères) et selon deux profils de données distincts : des listes hautement répétitives et des listes générées aléatoirement via notre module randomFill. En exportant ces mesures empiriques dans un tableur, j'ai pu tracer des courbes d'évolution temporelle et vérifier la conformité des résultats avec les complexités théoriques (comme le comportement en O(n×m) du cas naïf ou la linéarité en O(n) de KMP), permettant ainsi d'identifier précisément les facteurs limitants comme l'explosion des collisions de hachage dans Rabin-Karp.
Le projet ayant été réalisé en binôme, la gestion de notre autonomie et de notre collaboration a été un facteur clé de réussite. En raison de la charge de travail conséquente (quatre algorithmes à implémenter et à analyser) et de la période de vacances, nous avons pris la décision stratégique de scinder le développement initial en deux parts équitables : je me suis investi de manière autonome sur la conception d'une partie des algorithmes, tandis que mon binôme gérait l'autre partie.
Cependant, notre démarche ne s'est pas arrêtée à un simple découpage individuel. Afin de garantir une maîtrise partagée, nous avons instauré un principe d'explication mutuelle : une fois un algorithme achevé, son concepteur en exposait la logique et les rouages à l'autre. Cette démarche collaborative nous a permis d'acquérir une compréhension globale et profonde des quatre approches. Notre implication a été totale, de la phase de codage rigoureux des fonctions de recherche jusqu'à la collecte minutieuse des métriques de performance et l'analyse statistique finale dans notre compte-rendu.
Pour mener à bien les objectifs de performance et d'analyse de cette SAÉ, nous avons judicieusement combiné des ressources de développement et d'outils d'analyse.
En premier lieu, la ressource R1.01 – Initiation au développement a constitué notre socle technique indispensable pour coder proprement les structures en Java, gérer les boucles de comparaison et implémenter les compteurs de performance. À cela s'est ajoutée la ressource R1.02 – Développement d'interfaces utilisateur (ou les concepts de tests associés) pour valider visuellement la génération de nos jeux de données via nos fonctions de test fonctionnel.