Recherche par indexation, grep, find, ...

bonjour,

optimisée, rapide et efficace, cela dépend du contexte, dont tu ne nous dit presque rien.

Pour le nombre de recherches, à vrai dire je ne sais pas vraiment exactement (c'est d'ailleurs là, ma difficulté à trouver la bonne méthode), mais je sais que l'outil doit pouvoir traiter une centaine de fichiers par seconde. Au niveau résultat, si cela match avec un des mots clés (qui peut être : lien, mail, IP, environ une quinzaine de mots clés), ceci créé une alerte, une notification, qui sera traitée par la suite. Lorsqu'une alerte est détectée, le fichier en question est sauvegardé, tandis que les autres sont supprimés.

Comme tu parles de grep et sed, je suppose que tu es sous Linux.

Par ailleurs, tu as l'air de décrire une situation où :

• les fichiers à examiner arrivent à un certain emplacement (répertoire d'arrivée)
• où ils doivent être examinés
• s'ils correspondent à tes critères de recherche ("lien, mail, IP, environ une quinzaine de mots clés"), tu dois sauvegarder ces fichiers ailleurs (répertoire de traitement ultérieur) et noter que tu as une action à faire dessus
• s'ils ne correspondent pas, tu les supprimes du répertoire d'arrivée

Sous Linux, tu as des outils comme inotify-tools qui est une bibliothèque qui constitue un sous-système du noyau Linux permettant de détecter des changements sur le système de fichiers. Avec cet outil, tu peux déclencher des actions lorsque le contenu d'un répertoire "surveillé" change (par exemple ajout d'un fichier).

https://github.com/inotify-tools/inotify-tools/wiki

On peut l'utiliser en C et dans d'autres langages y compris de script (par exemple Python ou Perl) et la bibliothèque est aussi fournie avec des outils de ligne de commande qui peuvent être utilisés dans de simples scripts Bash.

Cela te permet de déclencher l'analyse des fichiers à mesure qu'ils "arrivent".

Par exemple : https://github.com/seb-m/pyinotify/blob/master/python2/examples/tutorial_notifier.py

Bonjour,

Sous Linux, tu as des moteurs d'indexation comme baloo (sous KDE). Il existe d'autres logiciels équivalents (voir notamment cette page).

Si je reviens à baloo, celui-ci indexe des fichiers (de ton choix, éventuellement par rapport à leur nom, leur contenu ou des métadonnées tierces) ce qui permet de les retrouver rapidement en faisant alt+espace ou alt+f2.

En admettant que baloo (et ses équivalents) ne répondent pas à tes besoins, tu peux toujours concevoir un algorithme qui fera exactement ce que tu veux, même si à mon avis, son design restera proche. En outre il faudra :

1. caractériser comment extraire les mots clés d'un fichier
2. mémoriser l'association de chaque mots clés avec les mots correspondants, idéalement avec mise à jour incrémentale
3. interroger cette mémoire au travers d'une interface pour pouvoir faire une recherche

Concernant le point (1), c'est à toi de spécifier comment tu veux le réaliser.

Concernant le point (3), tu peux imaginer une interface en mode texte (c'est finalement ce que font find et grep) ou en mode graphique (à l'image de baloo).

Concernant le point (2), c'est le plus intéressant, car plusieurs structures de données peuvent être considérées en fonction des fonctionnalités que ton logiciel doit offrir.

• Association directe : On associe dans un dictionnaire un mot avec les fichiers auxquels il se rapporte.
  • Si la requête comporte un mot, tu retrouves immédiatement les fichiers qui t'intéresse.
  • Si la requête comporte plusieurs mots, il suffit de faire l'intersection des résultats que tu aurais obtenus pour chaque mot pris individuellement.
  • Cela se fait très bien en python (on construit un dict qui associe à une str un set de pathlib.Path) ou en C++ (on construit une std::map qui associe à une std::string un std::set<std::string>)
  • Limitations :
    • Recherche non incrémentale : si on veut affiner les résultats de recherche au fur et à mesure de la saisie des caractères de la requêtes, il faut relancer la recherche "from scratch" à chaque caractère nouvellement saisi.
    • Résultats non ordonnés par pertinence.
    • Sensible aux typos
• Association au travers d'un Trie :
  • Un Trie est un arbre dans lequel chaque nœud est étiqueté par une lettre et éventuellement associés à une donnée auxiliaire (dans ton cas, un nœud qui termine un mot serait associé à un ensemble de fichiers).
  • Le mot en cours de saisie constitue un préfixe qui permet de naviguer dans le Trie et d'afficher les résultats correspondants.
  • Lorsqu'un mot est saisi et qu'on en saisit un nouveau, on reprend la recherche depuis la racine et on fait l'intersection des résultats.
  • Limitations :
    • ​​​​​​​Résultats non ordonnés par pertinence.
    • Sensible aux typos
• Recherche à la PageRank :
  • ​​​​​​​On construit un graphe biparti, où la partie gauche chaque nœud correspond à  un mot et dans la partie de droite, chaque nœud correspond à un fichier. On connecte un nœud mot à un nœud fichier si et seulement si il est en rapport.
  • Quand l'utilisateur fait une recherche (bag of words), on installe un fluide initial que l'on diffuse dans ce graphe (algorithme de D-iteration). On pondère les liens de ce graphe selon une certaine métrique (une métrique à la TF-IDF a du sens pour du texte).
  • Quand l'algorithme de D-itération a convergé, les nœuds fichiers qui ont collecté le plus de fluide sont les résultats les plus pertinents.
  • Pour plus de détails voir ce travail.
  • Limitations :
    • Recherche non incrémentale
    • Sensible aux typos
• Association au travers d'un outil à la SymSpell :
  • Symspell est conçu trouver rapidement un ensemble de mots correctement orthographiés à partir d'une saisie éventuellement mal orthographiés (ou dans ton cas, les fichiers associés à chaque mot correctement orthographié). Pour cela, Symspell repose sur une distance d'édition (typiquement la distance de Levenshtein) et c'est ce qui lui permet d'être résilient aux typos.
  • Avantages : 
    • Résilient aux typos
    • Peut-être adapté pour faire des recherches incrémentales
    • Les résultats ordonnés selon la distance d'édition sous-jacente
  • Inconvénients :
    • Les implémentations publiques de Symspell (par exemple celle là) ne sont pas prévues pour faire des recherches incrémentales.
    • Passe difficilement à l'échelle pour un nombre de typo important (en pratique, il ne faut pas espérer en dépasser 3)

Bonne chance