Sérialisation rapide d'un trie

Question

Une partie de mon application utilise un trie à chunk les mots ensemble. Par exemple, ["Summer", "in", "Los", "Angeles"] devient ["Summer", "in", "Los Angeles"].

Maintenant, ce trie est rempli à partir de a large database, stocké localement en tant que SQL, au démarrage de l'application. Cela prend beaucoup de temps, environ 15s. Je voudrais réduire le temps de démarrage de l'application, donc j'ai envisagé de sérialiser le Trie. Malheureusement, pickling est trop lent - plus lent que le chargement de tout de la base de données.

Existe-t-il un moyen plus rapide de sérialiser mon trie?

Voici ce que la classe Trie ressemble:

class Trie: 
    def __init__(self): 
     self.values = set() 
     self.children = dict() 

    def insert(self, key, value): 
     """Insert a (key,value) pair into the trie. 
     The key should be a list of strings. 
     The value can be of arbitrary type.""" 
     current_node = self 
     for key_part in key: 
      if key_part not in current_node.children: 
       current_node.children[key_part] = Trie() 
      current_node = current_node.children[key_part] 
     current_node.values.add(value) 

    def retrieve(self, key): 
     """Returns either the value stored at the key, or raises KeyError.""" 
     current_node = self 
     for key_part in key: 
      current_node = current_node.children[key_part] 
     return current_node.values 

Est-il possible de changer qui rendrait plus sérialisable?

Answer 1

J'ai fini par stocker le trie dans MongoDB.

Il y a un surdébit réseau, mais si la base de données est sur localhost, ce n'est pas trop grave.

Answer 2

Je sais que je ne donne pas une réponse python mais cela pourrait être utile:

Création, la compression et le stockage d'une structure arborescente est vraiment une tâche difficile. Je passe pas mal de temps à penser à des structures de données pour des suggestions d'automobiles et au mieux de ma connaissance, la solution la plus élégante est fourni par Giuseppe Ottaviano et partly described in my blog article

Même si elle ne sera pas judicieux de mettre en œuvre l'ensemble de la solution de Ottaviano as described in his paper En python, il peut toujours être logique de suivre l'idée de base de stocker le trie complet comme un grand bloc de mémoire et de n'avoir que des références à la position où sauter ensuite. De cette manière, vous pouvez facilement sérialiser ce tableau ou ce bloc de mémoire sur le disque dur. Je ne suis pas tout à fait sûr de python mais je pense que cette opération devrait fonctionner et aussi être beaucoup plus rapide que la sérialisation d'une structure de données.

Je sais que c une implémentation du travail Ottavianos existe, vous pouvez même utiliser les liaisons python c.