trouver les numéros de ligne de toutes les occurences d'une chaîne dans un fichier texte

Question

Je suis en train d'écrire une fonction qui effectue les opérations suivantes:

Compte tenu d'un fichier texte, je veux trouver toutes les occurences d'une certaine chaîne dans ce fichier; ensuite, pour chaque occurrence, la ligne sur laquelle elle a été trouvée devrait être ajoutée à une liste. Nous supposons que chaque ligne contient au plus une occurence. Le fichier texte peut devenir très volumineux, ce qui signifie qu'une simple boucle for-itera sur chaque ligne le fichier sera trop lent.

Par exemple, disons que nous avons un fichier avec le contenu:

1. ABCDEFG
2. HJKLMNO
3. GFEDCBA
4. PQRSTUV

Si je devais rechercher "A" , la fonction le trouverait sur les lignes 1 et 3 et ainsi ajouter 1 et 3 à une liste (puis retourner la liste). Je pensais à la recherche binaire, mais il semble exiger une liste à trier et les éléments à distinguer - je cherche des valeurs identiques.

Alors, y a-t-il un autre algorithme de recherche sur lequel je peux baser ma fonction, avec à peu près les mêmes performances que la recherche binaire?

Merci!

Answer 1

Vous pouvez indexer vos lignes, si elles changent rarement et que vous effectuerez de nombreuses recherches sur celles-ci. Une façon de les indexer serait de créer un histogramme des caractères présents dans quelles lignes (et combien de fois, peut-être). Ensuite, vous pouvez inverser cela et dire que la lettre A, par exemple, apparaît sur les lignes 5, 10 et 20. Si vous cherchez "ABF", vous pouvez utiliser l'histogramme inversé pour déterminer quelles lignes sont candidates (c.-à-d. lettres «A», «B» et «F») et ensuite seulement regarder ces lignes.

Que cette stratégie soit efficace ou non dépendra de la sélectivité de vos recherches et de la longueur des chaînes de recherche, entre autres. Seuls les tests révéleront si l'algorithme a ou non un mérite pour vos habitudes d'utilisation particulières.