Cómo crear un trie en Python

124

Estoy interesado en los intentos y DAWG (gráfico de palabras acíclicas directas) y he estado leyendo mucho sobre ellos, pero no entiendo cómo debería ser el archivo trie o DAWG de salida.

  • ¿Debería un trie ser objeto de diccionarios anidados? ¿Dónde cada letra se divide en letras y así sucesivamente?
  • ¿Una búsqueda realizada en dicho diccionario sería rápida si hay 100k o 500k entradas?
  • ¿Cómo implementar bloques de palabras que consisten en más de una palabra separada con -o espacio?
  • ¿Cómo vincular el prefijo o sufijo de una palabra a otra parte de la estructura? (para DAWG)

Quiero comprender la mejor estructura de salida para descubrir cómo crear y usar una.

También agradecería cuál debería ser la salida de un DAWG junto con trie .

No quiero ver representaciones gráficas con burbujas unidas entre sí, quiero conocer el objeto de salida una vez que un conjunto de palabras se convierten en intentos o DAWG.

Phil
fuente
55
Lea kmike.ru/python-data-structures para una encuesta de estructuras de datos exóticos en Python
Coronel Panic

Respuestas:

161

Relájese es esencialmente correcto que hay muchas formas diferentes de implementar un trie; y para un trie grande y escalable, los diccionarios anidados pueden volverse engorrosos, o al menos ineficientes en cuanto al espacio. Pero como recién estás comenzando, creo que ese es el enfoque más fácil; podría codificar un simple trieen solo unas pocas líneas. Primero, una función para construir el 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 no está familiarizado setdefault, simplemente busca una clave en el diccionario (aquí lettero _end). Si la clave está presente, devuelve el valor asociado; si no, asigna un valor predeterminado a esa clave y devuelve el valor ( {}o _end). (Es como una versión de geteso que también actualiza el diccionario).

A continuación, una función para probar si la palabra está en el 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

Te dejaré la inserción y extracción como ejercicio.

Por supuesto, la sugerencia de Unwind no sería mucho más difícil. Puede haber una ligera desventaja de velocidad en que encontrar el subnodo correcto requeriría una búsqueda lineal. Pero la búsqueda se limitaría al número de caracteres posibles: 27 si los incluimos _end. Además, no se gana nada al crear una lista masiva de nodos y acceder a ellos por índice, como sugiere; también podrías anidar las listas.

Finalmente, agregaré que crear un gráfico de palabras acíclicas dirigido (DAWG) sería un poco más complejo, porque debe detectar situaciones en las que su palabra actual comparte un sufijo con otra palabra en la estructura. De hecho, esto puede ser bastante complejo, dependiendo de cómo desee estructurar el DAWG. Es posible que tenga que aprender algunas cosas sobre la distancia de Levenshtein para hacerlo bien.

senderle
fuente
1
Ahí, el cambio hecho. Me quedaría con dict.setdefault()(está subutilizado y no es lo suficientemente conocido), en parte porque ayuda a prevenir errores que son demasiado fáciles de crear con un defaultdict(donde no obtendrías KeyErrorclaves no existentes en la indexación). Lo único que lo haría utilizable para el código de producción es usar _end = object():-)
Martijn Pieters
@MartijnPieters hmmm, elegí específicamente no usar objetos, pero no recuerdo por qué. ¿Quizás porque sería difícil de interpretar cuando se ve en la demostración? Creo que podría hacer que un objeto final con un repr encargo
senderle
27

Echa un vistazo a esto:

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

Estructuras de Trie con memoria estática eficiente para Python (2.xy 3.x).

Los datos de cadena en un MARISA-trie pueden tomar hasta 50x-100x menos memoria que en un dict Python estándar; la velocidad de búsqueda sin procesar es comparable; trie también proporciona métodos rápidos y avanzados como la búsqueda de prefijos.

Basado en la biblioteca marisa-trie C ++.

Aquí hay una publicación de blog de una empresa que utiliza marisa trie con éxito:
https://www.repustate.com/blog/sharing-large-data-structure-across-processes-python/

En Repustate, muchos de nuestros modelos de datos que utilizamos en nuestro análisis de texto pueden representarse como simples pares clave-valor o diccionarios en la jerga de Python. En nuestro caso particular, nuestros diccionarios son masivos, unos pocos cientos de MB cada uno, y es necesario acceder a ellos constantemente. De hecho, para una solicitud HTTP dada, se puede acceder a 4 o 5 modelos, cada uno haciendo 20-30 búsquedas. Entonces, el problema que enfrentamos es cómo mantenemos las cosas rápidas para el cliente y lo más livianas posible para el servidor.

...

Encontré este paquete, Marisa intenta, que es un contenedor de Python alrededor de una implementación de C ++ de un marisa trie. "Marisa" es un acrónimo de Algoritmo de coincidencia con StorAge implementado recursivamente. Lo bueno de Marisa intenta es que el mecanismo de almacenamiento realmente reduce la cantidad de memoria que necesita. El autor del complemento Python afirmó una reducción de tamaño de 50-100X: nuestra experiencia es similar.

Lo bueno del paquete marisa trie es que la estructura trie subyacente puede escribirse en el disco y luego leerse a través de un objeto mapeado en memoria. Con una memoria mapeada marisa trie, ahora se cumplen todos nuestros requisitos. El uso de memoria de nuestro servidor se redujo drásticamente, en aproximadamente un 40%, y nuestro rendimiento no cambió desde que usamos la implementación del diccionario de Python.

También hay un par de implementaciones de Python puro, aunque a menos que esté en una plataforma restringida, desearía usar la implementación respaldada por C ++ anterior para obtener el mejor rendimiento:

Anéntrópico
fuente
la última confirmación fue en abril de 2018, la última confirmación importante fue en 2017
Boris
25

Aquí hay una lista de paquetes de Python que implementan Trie:

  • marisa-trie : una implementación basada en C ++.
  • python-trie : una implementación simple de python puro.
  • PyTrie : una implementación de Python puro más avanzada.
  • pygtrie : una implementación pura de Python de Google.
  • datrie : una implementación de trie de doble matriz basada en libdatrie .
Tzach
fuente
17

Modificado del senderlemétodo de (arriba). Descubrí que Python defaultdictes ideal para crear un árbol o un árbol de prefijos.

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
fuente
Mi comprensión de la complejidad del espacio es O (n * m). Algunos tienen discusión aquí. stackoverflow.com/questions/2718816/…
dapangmao
55
@dapangmao está utilizando defaultdict solo para el primer carácter solamente. Los caracteres de descanso todavía usan dict normal. Sería mejor usar defaultdict anidado.
lionelmessi
3
En realidad, el código no parece estar "usando" el defaultdict para el primer carácter, ya que no establece default_factory y todavía usa set_default.
studgeek
12

No hay "debería"; tu decides. Varias implementaciones tendrán diferentes características de rendimiento, tomarán diferentes cantidades de tiempo para implementar, comprender y acertar. Esto es típico para el desarrollo de software en su conjunto, en mi opinión.

Probablemente primero intente tener una lista global de todos los nodos de trie creados hasta ahora, y representar los punteros secundarios en cada nodo como una lista de índices en la lista global. Para mí, tener un diccionario solo para representar la vinculación del niño me parece demasiado pesado.

relajarse
fuente
2
una vez más, gracias, sin embargo, sigo pensando que su respuesta necesita una explicación y aclaración un poco más profunda, ya que mi pregunta tiene como objetivo descubrir la lógica y la estructura de la funcionalidad de DAWG y TRIE. Su aporte adicional será muy útil y apreciado.
Phil
A menos que use objetos con ranuras, su espacio de nombre de instancia será de todos modos diccionarios.
Físico loco
4

Si desea implementar un TRIE como una clase de Python, aquí hay algo que escribí después de leer sobre ellos:

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
fuente
2
Gracias @NoctisSkytower. Para empezar, esto es genial, pero me di por vencido en Python y TRIES o DAWG debido al consumo extremadamente alto de memoria de Python en estos casos.
Phil
3
Para eso sirve ____slots____. Reduce la cantidad de memoria utilizada por una clase, cuando tiene muchas instancias de ella.
dstromberg
3

Esta versión está usando recursividad

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)

Salida:

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
fuente
3
from collections import defaultdict

Define Trie:

_trie = lambda: defaultdict(_trie)

Crea Trie:

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

Buscar:

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

Prueba:

print(word_exist(trie, 'cam'))
DingLi
fuente
1
precaución: esto Truesolo se devuelve para una palabra completa, pero no para el prefijo, para el cambio de prefijo return '_end' in currareturn 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()

Fuera

True
False
False
False
{'h': {'i': {'*': True}}}
No
fuente
0

Clase de Python para Trie


La estructura de datos Trie se puede usar para almacenar datos en O(L)donde L es la longitud de la cadena, por lo que para insertar N cadenas, la complejidad del tiempo sería que O(NL)la cadena se puede buscar O(L)solo para eliminarla.

Se puede clonar desde 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)

Oputpt de código

Verdadero
Falso
['minakshi', 'minhaj']
7
minakshi
minhajsir
pari
parikshit
shubh
shubham
shubhi

Parikshit Agarwal
fuente