Saltar al contenido

Cómo crear un trie en Python

octubre 25, 2021
apple touch icon@2

Unwind es esencialmente correcto en que hay muchas formas diferentes de implementar un trie; y para un ensayo grande y escalable, los diccionarios anidados pueden volverse engorrosos o, al menos, ineficaces en cuanto al espacio. Pero como recién está comenzando, creo que ese es el enfoque más fácil; podrías codificar un simple trie en 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.)

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

Le dejo la inserción y la extracción como un ejercicio.

Por supuesto, la sugerencia de Unwind no sería mucho más difícil. Podría haber una ligera desventaja de velocidad en el sentido de 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 incluimos _end. Además, no se gana nada creando una lista masiva de nodos y accediendo a ellos por índice como sugiere; también podría anidar las listas.

Finalmente, agregaré que crear un gráfico de palabras acíclicas dirigidas (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 volverse bastante complejo, dependiendo de cómo desee estructurar el DAWG. Puede que tengas que aprender algunas cosas sobre Levenshtein distancia para hacerlo bien.

close