On dispose d'un gros volume de données sous forme de texte brut stocké dans des fichiers, dans lesquels on souhaite chercher des chaînes de caractères précises. Pour chaque fichier à analyser, on souhaite connaître l'ensemble des correspondances trouvées ainsi que leur position dans le fichier.

Je me suis dis que que si l'on cherche le nombre d'occurence d'une chaine donner dans une chaines. Il suffit de diviser la chaine de base en question par l'occurence que l'on cherche vu que ce qui nous interesse c'est le decalage c'est assez simple on addition a chaque fois la taille de la chaine rechercher car ce dernier sera omit car le diviseur, et comme il s'agit de decalage la taille precedante n'est donc pas omit ce qui nous amene a une addition jusqu'a l'avant dernier element du table car le dernier etant la fin. J'ai testé mon idée avec une fonction simple, une fois j'ai le comptement voulu, je l'ai donc adapté a la consigne de l'exercice.

La logique de mon algorithme est donc la suivante :

• J'ai creer une fois qui me renvoie une le decalage d'une occurence dans une chaine donner search_patterns_in_file
• J'ecouter les argmuments du terminal comme les options ainsi que les fichier
• ensuite j'itere sur la par fichier et dans chacun des fichier, j'itere sur l'occurence rechercher
• Je fais appel appel a ma fonction search_patterns_in_file pour l'ajouter dans mon tableau de resultat

lipsum.txt:

Neque porro quisquam est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci velit, sed quia non numquam eius modi tempora incidunt ut labore et dolore magnam aliquam quaerat voluptatem.

python3 pattern_particulier.py -e dolor -e volupta lipsum.txt

[
  {
    "file": null,
    "pattern": "dolor",
    "offset": 30
  },
  {
    "file": null,
    "pattern": "dolor",
    "offset": 49
  },
  {
    "file": null,
    "pattern": "dolor",
    "offset": 155
  },
  {
    "file": null,
    "pattern": "volupta",
    "offset": 185
  }
]

La fonction search_patterns_in_file lit d'abord le contenu complet d'un fichier:

with open(file_path, 'r', encoding='utf-8') as file:
    content = file.read()

Pour un fichier de taille N (nombre de caractères), cette opération a une complexité de O(N).

Pour chaque motif P dans l'ensemble des motifs recherchés, nous utilisons re.finditer(pattern, content):

for pattern in patterns:
    for match in re.finditer(pattern, content):
        
        

La fonction re.finditer du module re de Python implémente une recherche d'expressions régulières basée sur l'algorithme de Thompson NFA (automate fini non-déterministe). Sa complexité dépend:

Pour les expressions régulières simples (recherche de chaîne littérale): O(N) où N est la taille du texte Pour les expressions régulières complexes (avec backtracking): potentiellement O(2^N) dans le pire cas

En pratique, pour des motifs raisonnables, nous pouvons considérer que la complexité moyenne est O(N) par motif.

Si nous définissons:

N : taille moyenne d'un fichier (en caractères) M : nombre de motifs à rechercher F : nombre de fichiers à traiter

La complexité totale est:

O(F × (N + M × N)) = O(F × N × (1 + M)) = O(F × M × N)

La complexité temporelle de l'algorithme est ````O(F × M × N)``` où:

F est le nombre de fichiers M est le nombre de motifs N est la taille moyenne des fichiers

Cette complexité est optimale pour ce type de problème, car nous devons nécessairement:

Lire chaque caractère de chaque fichier au moins une fois: O(F × N) Rechercher chaque motif dans chaque fichier: O(F × M × N)

Aucune de ces étapes ne peut être évitée pour résoudre le problème posé.