Il est indispensable de compléter les filtres (exclusion, regex …) avec un outil de recherche dans les entrées de l’index. Notamment, une fonction qui soit basée sur les chaines de caractères (égalité, sous-chaine)  et qui cible le type (fichier, répertoire …) des ces items. Le mécanisme mis en œuvre par index_search_strfind utilise un nombre indéfini de chaines de caractères à rechercher (dans une liste) que l’on peut combiner en mode OR (il suffira d’en trouver une dans le chemin complet d’un item) ou en mode AND (il faudra toutes les trouver dans le chemin complet d’un item). De cette manière nous pouvons faire des requêtes intéressantes et précises pour aller chercher quelque chose dans une arborescence texte.

Si nous généralisons, dans un arbre sérialisé les répertoires correspondent à des nœuds et les fichiers (ou les liens) correspondent aux éléments terminaux (après un nœud) dans la hiérarchie. Ce type d’approche est donc utilisable dans le cas de problématiques qui sortent du cadre d’une arborescence de répertoires et fichiers,  pour peu que l’index soit compatible (node='d', leaf='f|l' et que l’on gère les éléments sans type),  que la recherche puisse être faite dans les étiquettes qui identifient les nœuds et les feuilles (les labels doivent être signifiants) et leur hiérarchie (path) en amont.

1. Fondations

Dans un premier temps, il faut définir un système de paramétrage qui nous permets de combiner des modes de recherche OR ou AND, de prendre en compte la casse (STRICT) dans le nom des items de l’index ou pas (NOT_STRICT), de comparer chaîne à chaine (EQUAL) ou d’utiliser un match dans la chaine (FIND).  Et comme je fais partie du siècle dernier, je joue cette combinatoire sous la forme de valeurs inspirées d’une combinaison de bits :

mode_str (string)       mode (bitlist)       mode (dec) 'OR-FIND-NOT_STRICT'    [1,0,0,0,0,0,0,0]    128 'OR-FIND-STRICT'        [0,1,0,0,0,0,0,0]    64 'OR-EQUAL-NOT_STRICT'   [0,0,1,0,0,0,0,0]    32 'OR-EQUAL-STRICT'       [0,0,0,1,0,0,0,0]    16 'AND-FIND-NOT_STRICT'   [0,0,0,0,1,0,0,0]    8 'AND-FIND-STRICT'       [0,0,0,0,0,1,0,0]    4 'AND-EQUAL-NOT_STRICT'  [0,0,0,0,0,0,1,0]    2 'AND-EQUAL-STRICT'      [0,0,0,0,0,0,0,1]    1

Donc j’implémente quelques fonctions dans le module index_tools.py : index_search_modes_dump pour afficher la table des modes, index_search_str2mode(mode_str) qui me renvoie la valeur décimale, index_search_mode2str(mode) qui me renvoie l’identifiant mode_str. Egalement les fonctions index_search_mode2strict et index_search_strict2mode qui ne s’occupent que des modes 128, 32 et 16 pour des raisons de compatibilité avec de vieux codes (ou la variable strict prenait les valeurs correspondantes: 0, 1, 2).

2. Principe d’opérations

Une fois que nous avons les fondations qui vont nous éviter trop de manipulations mentales, il est possible de définir une une fonction qui traite un item sans faire intervenir les combinaisons. La fonction index_search_item_bymask(item_str, tags, mode, os_sep) utilise la valeur de l’item dans l’index, un tableau tags ou nous avons les chaînes (nombre indéfini) utilisées pour la recherche dans l’index, le mode et os_sep le caractère séparateur de répertoire. Cette fonction renvoie un masque de 0, 1 (ou plus de 1) qui correspond à chaque élément de tags. Si pour un élément de tags il s’est passé quelque chose, nous n’aurons pas une valeur de 0 dans le masque (à la même position). Cette fonction ne s’intéresse pas à AND/OR, donc nous pouvons regrouper les cas : [1, 16], [2, 32], [4, 64] et [8, 128]. Prenons le premier cas (égalité stricte) :

Le principe est de découper l’item en mots, en utilisant os_sep, puis pour chaque mot nous testons s’il y a une égalité avec un élément de tags, si oui, on accumule (+1) l’élément correspondant dans le masque de retour. Puis deux autres fonctions (index_search_item_strfind_OR et index_search_item_strfind_AND) peuvent implémenter les modes OR ou AND avec ce masque, par exemple :

• Pour OR, s’il y a au moins un 1 dans le masque, au moins un élément de tags à trouvé une correspondance, donc nous avons un signal.
• Pour AND, il faudra qu’il n’y ait aucun 0 dans le masque pour avoir un signal, dasn ce cas chaque élément de tags aura trouvé au moins une correspondance.

Puis tout est traité dans une fonction utilisateur index_search_strfind qui va différentier entre les modes AND (< 10) et OR (> 10) et traiter en fonction du format de données, dirmatrix ou simple.

def index_search_strfind(index, tags, mode, type, format='simple', verb=0):

Et nous avons un argument supplémentaire type, qui peut prendre une valeur parmi ['d', 'f', 'l', ''] pour ne s’intéresser qu’à un type d’item (répertoire, fichier, lien) ou sans se préoccuper du type. Cette fonction (non destructive) renvoie un nouvel index correspondant à la combinaison de toutes ces opérations.

3. Performances

Nous prenons le cas d’un index généré à partir de C:\Python3\envs\prod\Lib\site-packages\ (de l’ordre de 30000 fichiers ou répertoires) non filtré. En mode dirmatrix, nous faisons une recherche tags=['Parsers', 'csvm'] qui ne porte que sur des items de type 'd' (répertoires), avec différent modes. Pour une combinaison OR nous avons :

OR-EQUAL-STRICT	4 items	0.263 s	Il n’y a que les dossiers 'csvm' qui répondent.
OR-EQUAL-NOT_STRICT	9 items	0.547 s	Les dossiers 'parsers' répondent aussi.
OR-FIND-STRICT	6 items	0.557 s	Des dossiers avec des noms composés ‘embcsvm', 'csvm2csvm' incluant 'csvm' mais pas ceux incluant 'Parsers'.
OR-FIND-NOT_STRICT	11 items	0.833 s	Des dossiers incluant 'parsers' répondent en plus.

En mode AND les choses sont plus restrictives forcément. Pour le test, nous gardons les mêmes paramètres, mais avec tags=['Parsers', 'test']. Il n’y a que les modes NOT_STRICT qui répondent, avec un seul résultat basé sur les chaînes 'parsers' et 'test'. Les temps d’exécution sont similaires à ceux du mode OR et inférieurs à la génération de l’index ou de l’index + filtrage, ce qui était l’objectif à ce niveau. Les résultats servent juste à donner un ordre d’idée car ils fluctuent avec le système, l’OS, la charge …
Les résultats sont nettement plus rapides avec le format dirmatrix qu’avec le format simple, car il n’y a pas la perte de temps imposée par la résolution du type d’item que l’on veut rechercher, d’où l’intérêt d’utiliser un filtre pour limiter l’index si on sait ce que l’on ne veut pas ou si on sait à quelle profondeur le rechercher.

4. Exemple d’utilisation intégré

Dans un cas typique, nous allons commencer par générer un index de répertoires pour une arborescence donnée (test_dir) :

# generate recursive index of directories (index_tree_dirs) from test_dir  l = index_tree_dirs(test_dir, format='dirmatrix', verb=0)

Puis nous allons appliquer deux filtres regex pour éliminer les répertoires qui ne sont pas utiles dans l’index :

# first regex filter : drop all eggs filter = [r"\.([^.]+)$", 'path', 'drop']         # all dirs with an ext in name # filter = [r'\.dist-info$', 'path', 'drop']     # all dirs with ext '.dist-info' ll = index_regexp_filter(l, filter, format='dirmatrix', verb=1) # second regex filter : drop all __pycache__ directories filter = ['__pycache__', 'path', 'drop'] ll = index_regexp_filter(ll, filter, format='dirmatrix', verb=1)

Nous sommes passés de 2876 répertoires à 1559 soit la moitié, nous pouvons faire la recherche, qui est une étape lente :

# string search in dirs (type='d') with mode=8 (AND-FIND-NOT_STRICT) tags = ['Parsers', 'test'] nl = index_search_strfind(ll, tags, 2, 'd', format='dirmatrix', verb=0)

Puis nous pouvons récupérer les résultats pour en faire quelque chose, par exemple :

# check results : printout str_matrix_dump(nl, extract=True) # check results : count counts = ideutils_print_waiting('+++ Counting ', index_simple_counter, nl, format, 0) print("[files, dirs, links, unkn, total]", counts)

Dans le cas de test_dir = C:\Python3\envs\prod\Lib\site-packages\, sans limitation de profondeur, nous n’avons qu’un hit (au format dirmatrix) : ['d', 'C:\\Python3\\envs\\prod\\Lib\\site-packages\\buildez\\parsers\\', 'test', '', ''].

Au final ce type de recherche nous à couté 1.02 s pour l’index, 0.01 s pour le filtrage, 0.03 pour la recherche, soit ~1.06 s au global. Si on enlève le filtrage nous sommes (x3) plus lents pour la recherche. Ce qui commence à être sensible, sans que cela soit monumental, mais utile sur une machine moins performante.
Ce type d’exclusion par répertoires sera également intéressant dans une recherche de fichiers. Dans ce cas, à partir de 30000 items pour l’index, nous filtrons les mêmes répertoires, puis nous cherchons avec le même filtre, mais pour des fichiers (type = 'f').  Nous avons 24 hits en 0.8 s sans filtrage et 22 hits avec filtrage. La différence s’explique par le fait que le filtre regex n’est pas discriminant sur les types d’item dans l’index (pour être le plus rapide possible). La recherche est (2x) plus rapide avec le pipeline filtré, pour un coût total (incluant la génération de l’index) de ~1.3 s au format dirmatrix.

5. Conclusion

Le module est complété par deux fonctions de scoring, la première calcule un score par item, et la seconde produit un index dont les items sont supérieurs ou égaux à un niveau de score donné. Les paramètres sont similaires, mais les fonctions sont encore assez expérimentales, dans la mesure ou il faut faire évoluer le système de score initial (par accumulation) vers un système de score plus discriminant, linéaire ou pourquoi pas non linéaire.

Nous avons donc un premier outil de recherche qui ouvre quelques perspectives intéressantes, car il permet de préfiltrer une recherche avec des sous-répertoires imbriqués, par exemple si nous cherchons quelque chose qui est sous 'usr' puis sous 'bin', puis sous … En termes d’applications, il y en a et pas que dans l’interface chimie-biologie, je peux vous dire que pour l’analyse de logs ce type de recherche est méchamment utile. Cette notion d’inclusivité n’est pas présente dans index_search_strfind mais elle est implémentée dans le module index_include.py avec la même combinaison de modes.