Comment créer un trie en Python

125

Je suis intéressé par les essais et les DAWG (graphe de mots acycliques directs) et j'ai beaucoup lu à leur sujet, mais je ne comprends pas à quoi devrait ressembler le trie de sortie ou le fichier DAWG.

  • Un trie doit-il faire l'objet de dictionnaires imbriqués? Où chaque lettre est divisée en 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 implémenter des blocs de mots composés de plus d'un mot séparés par -un espace ou?
  • Comment lier le préfixe ou le suffixe d'un mot à une autre partie de la structure? (pour DAWG)

Je veux comprendre la meilleure structure de sortie afin de comprendre comment en créer et en utiliser une.

J'apprécierais également ce que devrait être la sortie d'un DAWG avec trie .

Je ne veux pas voir de 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 DAWG.

Phil
la source
5
Lisez kmike.ru/python-data-structures pour une enquête sur les structures de données exotiques en Python
Colonel Panic

Réponses:

161

Unwind est essentiellement correct qu'il existe de nombreuses façons différentes de mettre en œuvre un trie; et pour un trie volumineux et évolutif, les dictionnaires imbriqués peuvent devenir encombrants - ou du moins peu efficaces en termes d'espace. Mais puisque vous ne faites que commencer, je pense que c'est l'approche la plus simple; vous pouvez coder un simple trieen quelques lignes. Tout 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 recherche simplement une clé dans le dictionnaire (ici, letterou _end). Si la clé est présente, elle renvoie la valeur associée; sinon, il attribue une valeur par défaut à cette clé et renvoie la valeur ( {}ou _end). (C'est comme une version deget qui met également à jour le dictionnaire.)

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

>>> 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 un exercice.

Bien sûr, la suggestion de Unwind ne serait pas beaucoup plus difficile. Il pourrait y avoir un léger inconvénient de vitesse en ce que la recherche du sous-nœud correct 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 en créant une liste massive de nœuds et en y accédant par index comme il le suggère; vous pouvez tout aussi bien imbriquer les listes.

Enfin, j'ajouterai que créer un graphe de mot 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 dans la structure. En fait, cela peut devenir assez complexe, selon la façon dont vous souhaitez structurer le DAWG! Vous devrez peut-être apprendre des choses sur la distance de Levenshtein pour bien faire les choses.

expéditeur
la source
1
Là, changement fait. Je m'en tiens à dict.setdefault()(il est sous-utilisé et pas assez connu), en partie parce qu'il aide à éviter les bogues trop faciles à créer avec un defaultdict(où vous n'obtiendrez pas de KeyErrorclés non existantes lors de l'indexation). La seule chose maintenant qui le rendrait utilisable pour le code de production est d'utiliser _end = object():-)
Martijn Pieters
@MartijnPieters hmmm, j'ai spécifiquement choisi de ne pas utiliser d'objet, mais je ne me souviens pas pourquoi. Peut-être parce que ce serait difficile à interpréter vu dans la démo? Je suppose que je pourrais en faire un objet final avec un rééd personnalisé
senderle
27

Jetez un œil à ceci:

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îne 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 de préfixes.

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

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

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

...

J'ai trouvé ce paquet, essaie marisa, qui est un wrapper Python autour d'une implémentation C ++ d'un trie marisa. «Marisa» est un acronyme pour Matching Algorithm with Récursivement Implémenté StorAge. Ce qui est génial avec marisa essaie, 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 a revendiqué une réduction de 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 puis 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'utilisation de l'implémentation du dictionnaire Python.

Il existe également quelques implémentations purement python, mais à moins que vous ne soyez sur une plate-forme restreinte, vous souhaiterez utiliser l'implémentation C ++ ci-dessus pour de meilleures performances:

Anentropique
la source
le dernier commit était en avril 2018, le dernier commit majeur était comme 2017
Boris
25

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

  • marisa-trie - une implémentation basée sur C ++.
  • python-trie - une implémentation python pure et simple.
  • PyTrie - une implémentation pure python plus avancée.
  • pygtrie - une implémentation python pure de Google.
  • datrie - une implémentation de trie à double tableau basée sur libdatrie .
Tzach
la source
18

Modifié à partir de senderlela méthode de (ci-dessus). J'ai trouvé que Python defaultdictest idéal pour créer un trie ou un arbre de préfixes.

from collections import defaultdict

class Trie:
    """
    Implement a trie with insert, search, and startsWith methods.
    """
    def __init__(self):
        self.root = defaultdict()

    # @param {string} word
    # @return {void}
    # Inserts a word into the trie.
    def insert(self, word):
        current = self.root
        for letter in word:
            current = current.setdefault(letter, {})
        current.setdefault("_end")

    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the trie.
    def search(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                return False
            current = current[letter]
        if "_end" in current:
            return True
        return False

    # @param {string} prefix
    # @return {boolean}
    # Returns if there is any word in the trie
    # that starts with the given prefix.
    def startsWith(self, prefix):
        current = self.root
        for letter in prefix:
            if letter not in current:
                return False
            current = current[letter]
        return True

# Now test the class

test = Trie()
test.insert('helloworld')
test.insert('ilikeapple')
test.insert('helloz')

print test.search('hello')
print test.startsWith('hello')
print test.search('ilikeapple')
dapangmao
la source
Ma compréhension de la complexité spatiale est O (n * m). Certains ont des discussions ici. stackoverflow.com/questions/2718816/…
dapangmao
5
@dapangmao u n'utilisez defaultdict que pour le premier caractère uniquement. Les caractères de repos utilisent toujours le dict normal. Il vaudrait mieux utiliser defaultdict imbriqué.
lionelmessi
3
En fait, le code ne semble pas non plus "utiliser" le defaultdict pour le premier caractère car il ne définit pas default_factory et utilise toujours set_default.
studgeek
12

Il n'y a pas de "devrait"; c'est à vous. Diverses implémentations auront des caractéristiques de performances différentes, prendront un certain temps à implémenter, à comprendre et à bien faire. 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 de 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 l'enfant qui relie me semble trop lourd.

se détendre
la source
2
encore une fois, merci cependant, je pense toujours que votre réponse a besoin d'un peu plus d'explications et de clarifications car ma question vise à comprendre la logique et la structure de la fonctionnalité des DAWG et des TRIE. Votre contribution supplémentaire sera très utile et appréciée.
Phil
À moins que vous n'utilisiez des objets avec des emplacements, votre espace de noms d'instance sera de toute façon des dictionnaires.
Mad Physicist
4

Si vous voulez un TRIE 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])
Noctis Skytower
la source
2
Merci @NoctisSkytower. C'est génial pour commencer, mais j'ai en quelque sorte abandonné Python et TRIES ou DAWG en raison de la consommation de mémoire extrêmement élevée de Python dans ces scénarios.
Phil
3
C'est à cela que sert ____slots____. Cela réduit la quantité de mémoire utilisée par une classe, lorsque vous en avez de nombreuses instances.
dstromberg
3

Cette version utilise la récursivité

import pprint
from collections import deque

pp = pprint.PrettyPrinter(indent=4)

inp = raw_input("Enter a sentence to show as trie\n")
words = inp.split(" ")
trie = {}


def trie_recursion(trie_ds, word):
    try:
        letter = word.popleft()
        out = trie_recursion(trie_ds.get(letter, {}), word)
    except IndexError:
        # End of the word
        return {}

    # Dont update if letter already present
    if not trie_ds.has_key(letter):
        trie_ds[letter] = out

    return trie_ds

for word in words:
    # Go through each word
    trie = trie_recursion(trie, deque(word))

pprint.pprint(trie)

Production:

Coool👾 <algos>🚸  python trie.py
Enter a sentence to show as trie
foo bar baz fun
{
  'b': {
    'a': {
      'r': {},
      'z': {}
    }
  },
  'f': {
    'o': {
      'o': {}
    },
    'u': {
      'n': {}
    }
  }
}
Naren
la source
3
from collections import defaultdict

Définissez Trie:

_trie = lambda: defaultdict(_trie)

Créer Trie:

trie = _trie()
for s in ["cat", "bat", "rat", "cam"]:
    curr = trie
    for c in s:
        curr = curr[c]
    curr.setdefault("_end")

Chercher:

def word_exist(trie, word):
    curr = trie
    for w in word:
        if w not in curr:
            return False
        curr = curr[w]
    return '_end' in curr

Tester:

print(word_exist(trie, 'cam'))
DingLi
la source
1
attention: cela Truene renvoie que pour un mot entier, mais pas pour le préfixe, pour le changement de préfixe return '_end' in currenreturn True
Shrikant Shete
0
class Trie:
    head = {}

    def add(self,word):

        cur = self.head
        for ch in word:
            if ch not in cur:
                cur[ch] = {}
            cur = cur[ch]
        cur['*'] = True

    def search(self,word):
        cur = self.head
        for ch in word:
            if ch not in cur:
                return False
            cur = cur[ch]

        if '*' in cur:
            return True
        else:
            return False
    def printf(self):
        print (self.head)

dictionary = Trie()
dictionary.add("hi")
#dictionary.add("hello")
#dictionary.add("eye")
#dictionary.add("hey")


print(dictionary.search("hi"))
print(dictionary.search("hello"))
print(dictionary.search("hel"))
print(dictionary.search("he"))
dictionary.printf()

En dehors

True
False
False
False
{'h': {'i': {'*': True}}}
Non
la source
0

Classe Python pour Trie


La structure de données Trie peut être utilisée pour stocker des données dans O(L)lesquelles L est la longueur de la chaîne, de sorte que pour l'insertion de N chaînes, la complexité du temps serait que O(NL)la chaîne puisse être recherchée dansO(L) que pour la suppression.

Peut être cloné à partir de https://github.com/Parikshit22/pytrie.git

class Node:
    def __init__(self):
        self.children = [None]*26
        self.isend = False
        
class trie:
    def __init__(self,):
        self.__root = Node()
        
    def __len__(self,):
        return len(self.search_byprefix(''))
    
    def __str__(self):
        ll =  self.search_byprefix('')
        string = ''
        for i in ll:
            string+=i
            string+='\n'
        return string
        
    def chartoint(self,character):
        return ord(character)-ord('a')
    
    def remove(self,string):
        ptr = self.__root
        length = len(string)
        for idx in range(length):
            i = self.chartoint(string[idx])
            if ptr.children[i] is not None:
                ptr = ptr.children[i]
            else:
                raise ValueError("Keyword doesn't exist in trie")
        if ptr.isend is not True:
            raise ValueError("Keyword doesn't exist in trie")
        ptr.isend = False
        return
    
    def insert(self,string):
        ptr = self.__root
        length = len(string)
        for idx in range(length):
            i = self.chartoint(string[idx])
            if ptr.children[i] is not None:
                ptr = ptr.children[i]
            else:
                ptr.children[i] = Node()
                ptr = ptr.children[i]
        ptr.isend = True
        
    def search(self,string):
        ptr = self.__root
        length = len(string)
        for idx in range(length):
            i = self.chartoint(string[idx])
            if ptr.children[i] is not None:
                ptr = ptr.children[i]
            else:
                return False
        if ptr.isend is not True:
            return False
        return True
    
    def __getall(self,ptr,key,key_list):
        if ptr is None:
            key_list.append(key)
            return
        if ptr.isend==True:
            key_list.append(key)
        for i in range(26):
            if ptr.children[i]  is not None:
                self.__getall(ptr.children[i],key+chr(ord('a')+i),key_list)
        
    def search_byprefix(self,key):
        ptr = self.__root
        key_list = []
        length = len(key)
        for idx in range(length):
            i = self.chartoint(key[idx])
            if ptr.children[i] is not None:
                ptr = ptr.children[i]
            else:
                return None
        
        self.__getall(ptr,key,key_list)
        return key_list
        

t = trie()
t.insert("shubham")
t.insert("shubhi")
t.insert("minhaj")
t.insert("parikshit")
t.insert("pari")
t.insert("shubh")
t.insert("minakshi")
print(t.search("minhaj"))
print(t.search("shubhk"))
print(t.search_byprefix('m'))
print(len(t))
print(t.remove("minhaj"))
print(t)

Code Oputpt

Vrai
Faux
[ 'Minakshi', 'Minhaj']
7
Minakshi
minhajsir
pari
Parikshit
shubh
shubham
shubhi

Parikshit Agarwal
la source