Ответ 1

Отмахиваться, по сути, правильно, что существует множество различных способов реализации trie; и для больших масштабируемых триггеров вложенные словари могут стать громоздкими или, по крайней мере, неэффективными. Но поскольку вы только начинаете, я думаю, что самый простой подход; вы можете создать простой trie всего несколько строк. Во-первых, функция для построения 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_'}}}}

Если вы не знакомы с setdefault, он просто ищет ключ в словаре (здесь letter или _end). Если ключ присутствует, он возвращает соответствующее значение; если нет, он присваивает значение по умолчанию этому ключу и возвращает значение ({} или _end). (Это похоже на версию get, которая также обновляет словарь.)

Далее, функция, чтобы проверить, находится ли слово в trie. Это может быть более кратким, но я оставляю его подробным, чтобы логика была ясной:

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

Я оставлю вставку и удаление в качестве упражнения.

Конечно, предложение "Разморозить" было бы не намного сложнее. Может быть небольшое недостаток скорости в том, что для поиска правильного суб- node потребуется линейный поиск. Но поиск будет ограничен числом возможных символов - 27, если мы включим _end. Кроме того, ничего не получается, создавая массивный список узлов и получая их по индексу, как он предлагает; вы также можете просто вложить списки.

Наконец, я добавлю, что создание DAWG будет немного сложнее, потому что вы должны обнаружить ситуации, в которых ваше текущее слово разделяет суффикс с другим словом в структуре. Фактически, это может стать довольно сложным, в зависимости от того, как вы хотите структурировать DAWG! Возможно, вам придется изучить некоторые вещи о Levenshtein расстояние, чтобы исправить это.

Ответ 2

Посмотрите на это:

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

Статические структуры Trie с эффективным использованием памяти для Python (2.x и 3.x).

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

Based on marisa-trie C++ library.

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

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

...

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

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

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

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

Ответ 3

Вот список пакетов Python, которые реализуют Trie:

• marisa-trie - реализация, основанная на C++.
• Python-Trie - простая реализация на чистом Python.
• PyTrie - более продвинутая реализация чистого Python.
• pygtrie - чистая реализация Python от Google.
• datrie - реализация дерева с двойным массивом, основанная на libdatrie.

Ответ 4

Там нет "должно"; это вам. Различные реализации будут иметь разные характеристики производительности, занимать различное количество времени, чтобы реализовать, понять и получить право. Это типично для разработки программного обеспечения в целом, на мой взгляд.

Я бы, вероятно, сначала попробовал бы иметь глобальный список всех трёх узлов, созданных до сих пор, и представлять дочерние указатели в каждом node как список индексов в глобальном списке. Наличие словаря для представления привязки ребенка для меня слишком тяжело.

Ответ 5

Изменено из метода senderle (см. выше). Я обнаружил, что Python defaultdict идеально подходит для создания дерева 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')

Ответ 6

Если вы хотите, чтобы TRIE реализован как класс Python, вот что я написал после прочтения о них:

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

Ответ 7

В этой версии используется рекурсия

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👾 <algos>🚸  python trie.py
Enter a sentence to show as trie
foo bar baz fun
{
  'b': {
    'a': {
      'r': {},
      'z': {}
    }
  },
  'f': {
    'o': {
      'o': {}
    },
    'u': {
      'n': {}
    }
  }
}

Ответ 8

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

Ответ 9

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

Out

True
False
False
False
{'h': {'i': {'*': True}}}