values - python boolean variable

Cómo crear un TRIE en Python

Question

Soy nuevo en Python e intento aprender y avanzar. Estoy interesado en TRIES y DAWG y he leído mucho al respecto, pero no entiendo cómo debería ser el archivo TRIE o DAWG de salida.

• ¿Debería un TRIE ser un objeto de diccionarios anidados? ¿Dónde se divide cada letra en letras y demás?
• ¿Una búsqueda realizada en dicho diccionario será 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 prefijo o sufijo de una palabra a otra parte en la estructura? [para DAWG]

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

También agradecería lo que debería ser el resultado de un DAWG junto con TRIE .

No quiero ver representaciones gráficas con burbujas vinculadas entre sí, las vi mucho mientras las leía.

Me gustaría conocer el objeto de salida una vez que un conjunto de palabras se convierte en TRIE o DAWG.

Gracias.

Answer 1

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

• marisa-trie - una implementación basada en C ++.
• https://github.com/bdimmick/python-trie : una simple implementación pura de Python.
• https://pypi.python.org/pypi/PyTrie : una implementación python pura más avanzada.

Answer 2

Echa un vistazo a esto:

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

Estructuras de Trie eficientes en memoria estática para Python (2.x y 3.x).

Los datos de cadena en un MARISA-trie pueden tomar hasta 50x-100x menos memoria que en un dict estándar de Python; la velocidad de búsqueda sin formato 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 usa marisa trie con éxito:
http://blog.repustate.com/sharing-large-data-structure-across-processes-python/

En Repustate, gran parte de nuestros modelos de datos que utilizamos en nuestro análisis de texto se pueden representar como simples pares clave-valor o diccionarios en la jerga de Python. En nuestro caso particular, nuestros diccionarios son masivos, unos cientos de MB cada uno, y necesitan ser accedidos 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 al que nos enfrentamos es cómo mantener las cosas lo más rápido posible para el cliente y lo más ligero posible para el servidor.

...

Encontré este paquete, intenta marisa, que es un contenedor de Python en torno a una implementación en C ++ de un trie marisa. "Marisa" es un acrónimo de Matching Algorithm con Recursively Implemented StorAge. Lo mejor de los intentos de marisa es que el mecanismo de almacenamiento realmente reduce la cantidad de memoria que necesitas. El autor del complemento de Python reclamó una reducción del 50-100X en el tamaño: nuestra experiencia es similar.

Lo mejor del paquete marisa trie es que la estructura trie subyacente se puede escribir en el disco y luego leer a través de un objeto mapeado en la memoria. Con una memoria asignada marisa trie, todos nuestros requisitos se cumplen ahora. El uso de la 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, querría utilizar la implementación respaldada por C ++ anterior para obtener el mejor rendimiento:

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

Answer 3

Esta versión usa recursión

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

Answer 4

Modificado del senderle de senderle (arriba). Descubrí que el defaultdict de Python es ideal para crear un trie 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'')

Answer 5

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

Probablemente, primero intentaré tener una lista global de todos los nodos hasta ahora creados, y representar los indicadores secundarios en cada nodo como una lista de índices en la lista global. Tener un diccionario para representar al niño se siente demasiado pesado para mí.

Answer 6

Si quieres un TRIE implementado 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])

Answer 7

Unwind es esencialmente correcto que hay muchas maneras diferentes de implementar un trie; y para un trie grande y escalable, los diccionarios anidados pueden volverse engorrosos, o al menos ineficaces en el espacio. Pero dado que recién estás comenzando, creo que ese es el enfoque más fácil; podrías codificar un trie simple en 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 con setdefault , simplemente busca una clave en el diccionario (aquí, letter o _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 get que también actualiza el diccionario).

Luego, una función para probar si la palabra está en el trie. Esto podría ser más escueto, pero lo dejo prolijo para que la lógica sea clara:

>>> def in_trie(trie, word):
...     current_dict = trie
...     for letter in word:
...         if letter in current_dict:
...             current_dict = current_dict[letter]
...         else:
...             return False
...     else:
...         if _end in current_dict:
...             return True
...         else:
...             return False
... 
>>> 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

Dejaré la inserción y la eliminació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 sub-nodo correcto requeriría una búsqueda lineal. Pero la búsqueda se limitaría a la cantidad de caracteres posibles, 27 si 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 DAWG sería un poco más complejo, porque tienes que detectar situaciones en las que tu palabra actual comparte un sufijo con otra palabra en la estructura. De hecho, esto puede ser bastante complejo, ¡dependiendo de cómo quiera estructurar el DAWG! Puede que tengas que aprender algunas cosas sobre Levenshtein distance Levenshtein para hacerlo bien.

Answer 8

from collections import defaultdict

Definir Trie:

_trie = lambda: defaultdict(_trie)

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