Взгляните на это:

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

Статическая память Trie-структуры для Python (2.x и 3.x).

Строковые данные в MARISA-trie могут занимать до 50x100x меньше памяти, чем в стандартном Python dict; необработанная скорость поиска сопоставима; trie также предоставляет быстрые продвинутые методы, такие как префиксный поиск.

Основано на библиотеке C ++ для marisa-trie.

Вот сообщение в блоге от компании, использующей marisa trie успешно: http://blog.repustate.com/sharing-large-data-structure-across-processes-python/

В Repustate большинство наших моделей данных мы используем в наш текстовый анализ может быть представлен как простые пары ключ-значение, или словари в Pingon lingo. В нашем конкретном случае наши словари массовые, по несколько сотен МБ, и к ним нужно постоянно обращаться. Фактически для данного HTTP-запроса можно получить доступ к 4 или 5 моделям, каждый из которых выполняет поиск по 20-30. Таким образом, проблема, с которой мы сталкиваемся, заключается в том, как мы можем быстро и быстро поддерживать клиента, а также как можно больше света для сервера.

...

Я нашел этот пакет, marisa пытается, который представляет собой оболочку Python вокруг реализации C ++ для marisa. «Marisa» является аббревиатурой для алгоритма соответствия с рекурсивно реализованным StorAge. Что замечательно в попытках мариссы - механизм хранения действительно сокращает количество памяти, в которой вы нуждаетесь. Автор плагина Python утверждал, что размер 50-100X меньше - наш опыт аналогичен.

Что отличает нас от пакета marisa trie, так это то, что базовая структура trie может быть записана на диск, а затем читать через объект с отображением памяти. С памятью marisa trie, все наши требования теперь выполнены. Использование памяти в нашем сервере резко сократилось примерно на 40%, и наша производительность не изменилась с того момента, когда мы использовали реализацию словаря Python.

Существует также несколько реализаций с использованием чистого питона, вы находитесь на ограниченной платформе, для которой вы хотите использовать вышеприведенную реализацию C ++, для лучшей производительности:

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

Изменено по методу senderle (см. выше). Я обнаружил, что defaultdict Python идеально подходит для создания дерева trie или префикса.

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

from collections import defaultdict

Определить Trie:

_trie = lambda: defaultdict(_trie)

Создать Trie:

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

Поиск:

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

Тест:

print(word_exist(trie, 'cam'))

Эта версия использует рекурсию

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)

Выход:

Coool