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.

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.

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:

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

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 .

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')

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.

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])

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': {}
    }
  }
}

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'))

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}}}

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