Comment créer une trie en Python ?

Question

Je m'intéresse aux tries et aux DAWG (direct acyclic word graph) et j'ai beaucoup lu à leur sujet mais je ne comprends pas à quoi doit ressembler le fichier de sortie trie ou DAWG.

• Un trie doit-il être un objet de dictionnaires imbriqués ? Où chaque lettre est divisée en plusieurs lettres et ainsi de suite ?
• Une recherche effectuée sur un tel dictionnaire serait-elle rapide s'il y a 100 000 ou 500 000 entrées ?
• Comment mettre en œuvre des blocs de mots composés de plus d'un mot séparés par des mots. - ou l'espace ?
• Comment lier le préfixe ou le suffixe d'un mot à une autre partie de la structure ? (pour DAWG)

Je veux comprendre le meilleur structure de sortie afin de savoir comment en créer et en utiliser un.

J'aimerais également savoir ce que devrait être le sortie d'un DAWG ainsi que essai .

Je ne veux pas voir des représentations graphiques avec des bulles liées les unes aux autres, je veux connaître l'objet de sortie une fois qu'un ensemble de mots est transformé en essais ou en DAWGs.

Answer 1

Détente Il est essentiellement vrai qu'il existe de nombreuses façons différentes d'implémenter un trie ; et pour un trie important et évolutif, les dictionnaires imbriqués peuvent devenir encombrants -- ou au moins inefficaces en termes d'espace. Mais puisque vous débutez, je pense que c'est l'approche la plus simple ; vous pourriez coder un simple trie en quelques lignes seulement. D'abord, une fonction pour construire le trie :

>>> _end = '_end_'
>>> 
>>> def make_trie(*words):
...     root = dict()
...     for word in words:
...         current_dict = root
...         for letter in word:
...             current_dict = current_dict.setdefault(letter, {})
...         current_dict[_end] = _end
...     return root
... 
>>> make_trie('foo', 'bar', 'baz', 'barz')
{'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 
             'z': {'_end_': '_end_'}}}, 
 'f': {'o': {'o': {'_end_': '_end_'}}}}

Si vous n'êtes pas familier avec setdefault il cherche simplement une clé dans le dictionnaire (ici, letter o _end ). Si la clé est présente, il renvoie la valeur associée ; sinon, il attribue une valeur par défaut à cette clé et renvoie cette valeur ( {} o _end ). (C'est comme une version de get qui met également à jour le dictionnaire).

Ensuite, une fonction pour tester si le mot est dans le tri :

>>> def in_trie(trie, word):
...     current_dict = trie
...     for letter in word:
...         if letter not in current_dict:
...             return False
...         current_dict = current_dict[letter]
...     return _end in current_dict
... 
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'baz')
True
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barz')
True
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barzz')
False
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'bart')
False
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'ba')
False

Je vous laisse l'insertion et le retrait comme exercice.

Bien sûr, la suggestion de Unwind ne serait pas beaucoup plus difficile. Il pourrait y avoir un léger désavantage en termes de vitesse, car trouver le bon sous-nœud nécessiterait une recherche linéaire. Mais la recherche serait limitée au nombre de caractères possibles -- 27 si nous incluons _end . De plus, il n'y a rien à gagner à créer une liste massive de nœuds et à y accéder par index comme il le suggère ; vous pourriez tout aussi bien imbriquer les listes.

Enfin, j'ajouterai que la création d'un graphe de mots acyclique dirigé (DAWG) serait un peu plus complexe, car vous devez détecter les situations dans lesquelles votre mot actuel partage un suffixe avec un autre mot de la structure. En fait, cela peut devenir assez complexe, selon la façon dont vous voulez structurer le DAWG ! Vous devrez peut-être apprendre des choses sur Levenshtein distance pour bien faire les choses.

Answer 2

Jetez un coup d'oeil à ça :

https://github.com/kmike/marisa-trie

Structures Trie statiques efficaces en mémoire pour Python (2.x et 3.x).

Les données de chaînes de caractères dans un MARISA-trie peuvent prendre jusqu'à 50x-100x moins de mémoire que dans un dict Python standard ; la vitesse de recherche brute est comparable ; trie fournit également des méthodes avancées rapides comme la recherche par préfixe.

Basé sur la bibliothèque C++ marisa-trie.

Voici un article de blog d'une entreprise qui utilise marisa trie avec succès :
https://www.repustate.com/blog/sharing-large-data-structure-across-processes-python/

Chez Repustate, la plupart des modèles de données que nous utilisons dans notre analyse de texte peuvent être représentés par de simples paires clé-valeur, ou dictionnaires en langage Python. Dans notre cas particulier, nos dictionnaires sont massifs, quelques centaines de Mo chacun, et il faut y accéder constamment. En fait, pour une requête HTTP donnée, 4 ou 5 modèles peuvent être consultés, chacun effectuant 20 à 30 recherches. Le problème auquel nous sommes confrontés est donc de savoir comment faire pour que les choses restent rapides pour le client et aussi légères que possible pour le serveur.

...

J'ai trouvé ce paquet, marisa tries, qui est une enveloppe Python autour d'une implémentation C++ d'un marisa trie. "Marisa" est un acronyme pour Matching Algorithm with Recursively Implemented StorAge. Ce qui est génial avec les essais marisa, c'est que le mécanisme de stockage réduit vraiment la quantité de mémoire dont vous avez besoin. L'auteur du plugin Python revendique une réduction de la taille de 50 à 100 fois - notre expérience est similaire.

Ce qui est génial avec le paquet marisa trie, c'est que la structure trie sous-jacente peut être écrite sur le disque et ensuite lue via un objet mappé en mémoire. Avec un marisa trie mappé en mémoire, toutes nos exigences sont maintenant satisfaites. L'utilisation de la mémoire de notre serveur a considérablement diminué, d'environ 40 %, et nos performances sont restées inchangées par rapport à l'implémentation du dictionnaire de Python.

Il existe également quelques implémentations purement Python, mais à moins que vous ne disposiez d'une plate-forme restreinte, il est préférable d'utiliser l'implémentation C++ ci-dessus pour obtenir les meilleures performances :

• https://github.com/bdimmick/python-trie
• https://pypi.python.org/pypi/PyTrie

Answer 3

Voici une liste de paquets python qui implémentent Trie :

• marisa-trie - une implémentation basée sur C++.
• python-trie - une simple implémentation en python pur.
• PyTrie - une implémentation plus avancée en pur python.
• pygtrie - une implémentation en python pur par Google.
• datrie - une implémentation de trie à double réseau basée sur libdatrie .

Answer 4

Il n'y a pas de "devrait" ; c'est à vous de décider. Les différentes implémentations auront des caractéristiques de performance différentes, prendront plus ou moins de temps à mettre en œuvre, à comprendre et à réaliser. C'est typique du développement logiciel dans son ensemble, à mon avis.

J'essaierais probablement d'abord d'avoir une liste globale de tous les nœuds trie créés jusqu'à présent, et de représenter les pointeurs enfants dans chaque nœud comme une liste d'indices dans la liste globale. Avoir un dictionnaire juste pour représenter le lien enfant me semble trop lourd.

Answer 5

Si vous souhaitez qu'un TRIE soit implémenté en tant que classe Python, voici quelque chose que j'ai écrit après avoir lu à leur sujet :

class Trie:

    def __init__(self):
        self.__final = False
        self.__nodes = {}

    def __repr__(self):
        return 'Trie<len={}, final={}>'.format(len(self), self.__final)

    def __getstate__(self):
        return self.__final, self.__nodes

    def __setstate__(self, state):
        self.__final, self.__nodes = state

    def __len__(self):
        return len(self.__nodes)

    def __bool__(self):
        return self.__final

    def __contains__(self, array):
        try:
            return self[array]
        except KeyError:
            return False

    def __iter__(self):
        yield self
        for node in self.__nodes.values():
            yield from node

    def __getitem__(self, array):
        return self.__get(array, False)

    def create(self, array):
        self.__get(array, True).__final = True

    def read(self):
        yield from self.__read([])

    def update(self, array):
        self[array].__final = True

    def delete(self, array):
        self[array].__final = False

    def prune(self):
        for key, value in tuple(self.__nodes.items()):
            if not value.prune():
                del self.__nodes[key]
        if not len(self):
            self.delete([])
        return self

    def __get(self, array, create):
        if array:
            head, *tail = array
            if create and head not in self.__nodes:
                self.__nodes[head] = Trie()
            return self.__nodes[head].__get(tail, create)
        return self

    def __read(self, name):
        if self.__final:
            yield name
        for key, value in self.__nodes.items():
            yield from value.__read(name + [key])