Algorithme pour préparation de matrice creuse

Version imprimable

Bonjour, j'ai un dictionnaire de synonyme que je représente sous la forme d'un... dictionnaire Python. C'est à dire :
Code:

1 2 3 4 5 d {'abasourdi' : ['étonné', 'hébété'], 'abondant' : ['riche', 'copieux', 'luxuriant'], ... }
Afin de pouvoir travailler efficacement dessus, je souhaiterais transformer ce dictionnaire en :
1- un tuple ordonné d'entrées, donc ici quelque chose comme names = ('abasourdi', 'abondant', etc...)
2- une matrice creuse où M(i,j) == 1 si et seulement si le mot names[j] apparaît dans la liste des synonymes du mot names[i]

J'ai donc tenté de construire les trois listes I,J,V qui représentent cette matrice au format COO; c'est donc les indices de valeurs non nulle de ma matrice au format (row, column, value) avec value=1

Voici le bout de code qui effectue cette tâche :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 keys = tuple(sorted(d.keys())) Nentries = len(keys) indices = range(Nentries) # Construction of I,J,V vectors in COO format I = []; J = []; V = []; for (name, syno_list) in d.items(): rank_key = keys.index(name) rank_values = [keys.index(n) for n in syno_list] if len(rank_values)>0: # This should always be the case, but we check I.append(rank_key*len(rank_values)) J.append(rank_values) V.append([1]*len(rank_values))
Le problème ? Avec un dictionnaire qui contient Nentries = 36 178 entrées, c'est très lent !

Avez-vous des idées pour optimiser cela ?

Merci d'avance et bonne journée :)

D.

09/04/2021, 11h34
charliemtx

Bonjour,

Est-ce que vous pouvez communiquer le fichier contenant les données ?

Bonjour charliemtx,
merci pour l'intérêt porté à ma requête :)

Le fichier zip contenant les données peut être téléchargé ici : https://grammalecte.net/download/fr/thesaurus-v2.3.zip
Il s'agit du fichier "thes_fr.dat"

Voici mon script complet :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Apr  9 00:09:39 2021
 
@author: donutman
"""
 
from scipy import sparse
from numpy import savez
 
def print_entry(name, syno_list):
    print("- %s : %s" %  (name, ' - '.join(syno_list) ) )
 
 
 
filein = './data/step0/thes_fr.dat'
fileout1 = './data/step1/thesaurus_matrix'
fileout2 = './data/step1/thesaurus_entries'
 
d = {} # empty dictionnary
name = ""
syno_list = []
 
 
# STEP 1 : we read the input file and parse the data in a dictionnary structure
print('''
******************************
 
      STEP 1
      
******************************
''')
 
with open(filein, mode='rt', encoding='utf-8') as f:
    next(f) # we skip first line
    for line in f:
        line = line.rstrip('\n')
        if not line.startswith('('): # we read a new entry !
            # First, we need to add the previous entry into our dictionnary
            # But only if name is not empty !
            if not name=="":
                #print_entry(name, syno_list)
                d[name] = syno_list
                syno_list = []
 
            (name, _) = line.split('|')
        else:
            syno_list_tmp = line.split('|')
            del syno_list_tmp[0]
            syno_list = syno_list + syno_list_tmp
 
# Now that we read all the entries we need to add the last entry
d[name] = syno_list
 
 
 
# STEP 2 : we go through the dictionnary and delete synonyms that are NOT
# an entry of the dictionnary itself (self consistency check)
 
print('''
******************************
 
      STEP 2
      
******************************
''')
 
d2 = {}
 
for (name, syno_list) in d.items():
    syno_list_2 = [syno for syno in syno_list if syno in d.keys()]
    deleted_words = set(syno_list).symmetric_difference(set(syno_list_2))
 
    if len(deleted_words)>0:
        #print('****')
        #print('l1 : %s' % ' - '.join(syno_list))
        #print('l2 : %s' % ' - '.join(syno_list_2))
        print('- Deleted entries for "%s" : %s' % ( name, " - ".join(deleted_words) ))
    d2[name] = syno_list_2
 
 
# STEP 3 : Now we want to convert all that in a sparse matrix
# This step is a little bit slow and might be in some way optmized...
print('''
******************************
 
      STEP 3
      
******************************
''')
 
 
keys = tuple(sorted(d2.keys()))
Nentries = len(keys)
indices = range(Nentries)
 
# Construction of I,J,V vectors in COO format
 
I = []; J = []; V = [];
 
for (name, syno_list) in d2.items():
    rank_key = keys.index(name)
    rank_values = [keys.index(n) for n in syno_list]
    if len(rank_values)>0: # This should always be the case, but we check
        I.extend([rank_key]*len(rank_values))
        J.extend(rank_values)
        V.extend([1]*len(rank_values))
 
 
M = sparse.coo_matrix((V, (I,J)), shape=(Nentries, Nentries), dtype=bool)
 
 
sparse.save_npz(fileout1, M)
savez(fileout2, names=keys)

Quelques remarques additionnelles :
STEP1 lit les données de thes_fr.dat et stocke tout dans un dictionnaire python
STEP2 supprime les synonymes qui ne sont pas eux-mêmes des entrées du dictionnaire (on voit à ce propos passer un certain nombre de mots mal orthographiés)
STEP3 transforme tout ça sous la forme d'une matrice creuse

Par rapport à mon post initial, j'ai remplacé les .append() par .extend() qui fusionnent les listes (c'est plus proche de ce que je souhaite faire).
In fine, j'arrive bien à mes fins mais je me demandais s'il n'était pas possible de faire plus simple et plus malin en Python...

Par exemple, j'aurais peut-être pu pré-allouer les vecteur I,J,V... je ne sais pas trop...

Merci pour tout avis sur la qualité du code :)

D.

09/04/2021, 14h57
wiztricks

Salut,

Citation:

Envoyé par DonutMan

Avec un dictionnaire qui contient Nentries = 36 178 entrées, c'est très lent !

Ça prend combien de temps? Et qu'espérez vous comme durée?

A priori, c'est une opération que vous allez faire une seule fois (puisque le dictionnaire initial évolue peu).

Sauvegarder le résultat dans un fichier dans un format approprié (json, pickle) et le relire plutôt que le recalculer pourrait être une solution qui permettra de valider ce que vous pensez faire avec cette structure là (optimiser pourra venir plus tard, mais il vaut mieux le faire lorsque l'algo et le code seront un peu stables).

- W

C'est normal que votre step 3 soit très long avec un algorithme pareil !
Toute la lenteur se trouve là :
Code:

1 2 3 4 for (name, syno_list) in d.items(): rank_key = keys.index(name) rank_values = [keys.index(n) for n in syno_list]
Votre dictionnaire contient 36178 entrées. Vous faites donc déjà autant d'appel à la fonction index. Puis ensuite pour chaque synonyme de chaque mots, vous réappeler cette méthode index. Donc au total vous appelez environ 450 000 fois cette fonction ! Mais vous vous rendez compte qu'à chaque appel de cette fonction, Python va parcourir tout votre dico, pour trouver le mot chercher (et donc sa position) ? Une fonction de recherche par définition c'est déjà pas super rapide (comparer à si vous deviez chercher la définition d'un mot dans un dictionnaire, c'est une tache tout aussi complexe pour python que pour vous), mais alors là, l'appeler autant de fois ...

Donc :
1) Les synonymes étant aussi des clés du dictionnaires on n'a pas besoin de recalculer tout ces index ! On calcule ceux des clés du dictionnaire, on les stocke, et quand on a besoin d'un index sur un synonyme et bien c'est le même que sur la clé (c'est le principe de ce genre de matrice)
2) Si on les stocke dès le départ, et bien on peut meme s'affranchir de faire une recherche d'index pour chaque mot : juste on les prends dans l'ordre, et on mémorise son index associé dans un dico.

Ca donne ca, qui s'éxécute en moins d'une seconde
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 keys = tuple(sorted(d2.keys())) Nentries = len(keys) positions = { k:i for i,k in enumerate(keys) } #### La ligne de prétraitement super importante qui stocke tous les indices pour ne pas avoir à les recalculer à chaque fois # Construction of I,J,V vectors in COO format I = []; J = []; for rank_key in range(Nentries): name = keys[rank_key] syno_list = d2[name] nb_syno = len(syno_list) if nb_syno>0: # This should always be the case, but we check I.extend([rank_key]*nb_syno) J.extend( positions[syno] for syno in syno_list ) V = [1]*len(I) M = scipy.sparse.coo_matrix((V, (I,J)), shape=(Nentries, Nentries), dtype=bool)
Et j'ai également sorti le calcul de V, car il n'a absolument pas d'intérêt de le calculer à cout d'extend successif : c'est juste un vecteur rempli de 1 qui a la meme taille que I et J.

Pour les autres step je n'ai pas regardé si le code était améliorable (certainement), vu que la lenteur vient uniquement du step 3.

09/04/2021, 17h48
DonutMan

Bonjour,
super, merci beaucoup pour cette astuce !
En effet, c'est désormais quasi instantané.

Bonne soirée à tous :)

D.