Spójrz na to:

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

Statyczne struktury Trie wydajne dla Pythona (2.x i 3.x).

Dane łańcuchowe w MARISA-trie mogą zabierać do 50x-100x mniej pamięci niż w standardowym Pythonie dict; szybkość wyszukiwania raw jest porównywalna; trie zapewnia również szybkie zaawansowane metody, takie jak wyszukiwanie prefiksów.

Oparty na bibliotece marisa-trie C++.

Oto wpis na blogu firmy używającej marisa trie successfully:
http://blog.repustate.com/sharing-large-data-structure-across-processes-python/

W Repustate większość naszych modeli danych, których używamy w analizie tekstu, może być reprezentowana jako proste pary klucz-wartość lub słowniki w języku Python. W naszym konkretnym przypadku nasze słowniki są ogromne, po kilkaset MB każdy i muszą być stale dostępne. W rzeczywistości dla danego żądania HTTP można uzyskać dostęp do 4 lub 5 modeli, z których każdy wykonuje 20-30 wyszukań. Tak więc problem, z którym mamy do czynienia, to jak utrzymać rzeczy szybko dla klienta, jak również światło, jak to możliwe dla serwera.

...

Znalazłem ten pakiet, Marisa tries, który jest opakowaniem Pythona wokół implementacji trie w języku C++. "Marisa" jest akronimem dla algorytmu dopasowywania z rekurencyjnie zaimplementowaną pamięcią masową. Co jest świetne w Marisa próbuje jest mechanizm przechowywania naprawdę kurczy ile pamięci trzeba. Autor wtyczki Pythona twierdził, że zmniejszenie rozmiaru o 50-100X – nasze doświadczenie jest podobne.

Wspaniałe w pakiecie marisa trie jest to, że podstawowa struktura trie może być zapisana na dysk, a następnie odczytana za pomocą obiektu mapowanego w pamięci. Z pamięcią mapowane marisa trie, wszystkie nasze wymagania są teraz spełnione. Zużycie pamięci naszego serwera drastycznie spadło, o około 40%, a nasza wydajność nie zmieniła się w porównaniu z implementacją słownika Pythona.

Istnieje również kilka implementacji pure-python, choć jeśli nie jesteś na ograniczonej platformie, powinieneś użyć powyższej implementacji wspieranej przez C++, aby uzyskać najlepszą wydajność:

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

Oto lista pakietów Pythona, które implementują Trie:

• marisa-trie - implementacja oparta na C++.
• python-trie - prosta, czysta implementacja Pythona.
• PyTrie - bardziej zaawansowana implementacja czystego Pythona.

Nie ma "powinien"; to zależy od Ciebie. Różne implementacje będą miały różne charakterystyki wydajności, zajmie różne ilości czasu, aby wdrożyć, zrozumieć i uzyskać prawo. Moim zdaniem jest to typowe dla rozwoju oprogramowania jako całości.

Prawdopodobnie najpierw spróbowałbym stworzyć globalną listę wszystkich węzłów trie do tej pory utworzonych i reprezentować wskaźniki potomne w każdym węźle jako listę indeksów do listy globalnej. Posiadanie słownika tylko do reprezentowania dziecka wydaje mi się zbyt ciężki.

Zmodyfikowana z metody senderle (powyżej). Znalazłem, że Python defaultdict jest idealny do tworzenia Trie lub drzewa prefiksów.

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

Jeśli chcesz zaimplementować TRIE jako klasę Pythona, oto coś, co napisałem po przeczytaniu o nich:

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

Ta wersja używa rekurencji

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)

Wyjście:

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

Define Trie:

_trie = lambda: defaultdict(_trie)

Create Trie:

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

Lookup:

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

Test:

print(word_exist(trie, 'cam'))