没有“应该”，这取决于你。不同的实现将具有不同的性能特征，需要花费不同的时间来实现、理解和获得正确的结果。在我看来，这对于整个软件开发来说是典型的。

我可能会首先尝试创建一个包含迄今为止创建的所有 trie 节点的全局列表，并将每个节点中的子指针表示为全局列表中的索引列表。对我来说，用一本字典来表示孩子之间的联系感觉太沉重了。

Unwind 基本上是正确的，有许多不同的方法来实现一个尝试; 对于一个大型的、可伸缩的尝试，嵌套的字典可能会变得很麻烦——或者至少是空间效率低下。但是因为您才刚刚开始，所以我认为这是最简单的方法; 您可以用几行代码编写一个简单的 trie。首先，构造 try 的函数:

>>> _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的一个版本，也会更新字典。)

接下来，一个用于测试单词是否在 try 中的函数:

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

我会把插入和切除留给你作为练习。

当然，“放松”的建议也不会太难。找到正确的子节点需要线性搜索，这可能有一点速度上的缺点。但是搜索将限于可能的字符数——如果包括 _end，则为27。另外，按照他的建议，创建一个庞大的节点列表并通过索引访问它们也没有什么好处; 您还不如直接嵌套这些列表。

最后，我要补充的是，创建一个有向无环词图(DAWG)可能会更复杂一些，因为您必须检测当前单词与结构中的另一个单词共享后缀的情况。事实上，这可能会变得相当复杂，这取决于您希望如何构造 DAWG！你可能必须学习一些关于 Levenshtein 距离的东西才能得到正确的答案。

看看这个:

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

Python 的静态高效内存 Trie 结构(2.x 和3.x)。

MARISA-try 中的字符串数据可能比 在标准的 Python 命令行字典中; 原始查找速度是可比较的; 还提供了像前缀搜索这样的快速高级方法。

基于 marisa-trie C + + 库。

下面是一个成功使用 Marisa trie 的公司的博客文章:
Https://www.repustate.com/blog/sharing-large-data-structure-across-processes-python/

在 Repustate，我们在文本分析中使用的大多数数据模型都可以表示为简单的键-值对，或 Python 行话中的字典。在我们的特殊情况下，我们的字典非常庞大，每个字典有几百 MB，需要不断地访问它们。实际上，对于给定的 HTTP 请求，可能会访问4或5个模型，每个模型执行20-30次查找。因此，我们面临的问题是如何为客户端保持快速，为服务器保持尽可能轻量化。

...

我找到了这个包 marisa try，它是一个 Python 包装器，围绕着 marisa trie 的 C + + 实现。“ Marisa”是具有递归实现存储的匹配算法的缩写。Marisa 的优点在于它的存储机制能够真正缩小你所需要的内存。Python 插件的作者声称可以减少50-100X 的大小——我们的经验也是类似的。

Marisa trie 包的伟大之处在于，底层的 trie 结构可以写入磁盘，然后通过内存映射对象读入。有了 Marisa Trie 的记忆映射，我们所有的要求都满足了。我们的服务器的内存使用大幅下降，降幅约为40% ，与使用 Python 的 dictionary 实现时相比，我们的性能没有变化。

还有一些纯 Python 实现，不过除非你是在一个受限制的平台上，否则你会希望使用上面的 C + + 支持的实现来获得最佳性能:

• Https://github.com/bdimmick/python-trie
• Https://pypi.python.org/pypi/pytrie

如果你想把 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])

下面是实现 Trie 的 Python 包列表:

• Marisa-trie -一个基于 C + + 的实现。
• Python-trie -一个简单的纯 Python 实现。
• PyTrie -一个更高级的纯 Python 实现。
• Pygtrie -Google 的纯 Python 实现。
• Datrie -基于 Libdatrie的双数组 trie 实现。

我发现 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')

这个版本使用了递归

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

from collections import defaultdict

定义尝试:

_trie = lambda: defaultdict(_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'))

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

出去

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

用于 Trie 的 Python 类

Trie 数据结构可以用来在 O(L)中存储数据，其中 L 是字符串的长度，因此插入 N 个字符串的时间复杂度将是 O(NL)，这个字符串可以在 O(L)中搜索，只有同样的删除操作。

可以从 https://github.com/Parikshit22/pytrie.git克隆

class Node:
def __init__(self):
self.children = [None]*26
self.isend = False
        

class trie:
def __init__(self,):
self.__root = Node()
        

def __len__(self,):
return len(self.search_byprefix(''))
    

def __str__(self):
ll =  self.search_byprefix('')
string = ''
for i in ll:
string+=i
string+='\n'
return string
        

def chartoint(self,character):
return ord(character)-ord('a')
    

def remove(self,string):
ptr = self.__root
length = len(string)
for idx in range(length):
i = self.chartoint(string[idx])
if ptr.children[i] is not None:
ptr = ptr.children[i]
else:
raise ValueError("Keyword doesn't exist in trie")
if ptr.isend is not True:
raise ValueError("Keyword doesn't exist in trie")
ptr.isend = False
return
    

def insert(self,string):
ptr = self.__root
length = len(string)
for idx in range(length):
i = self.chartoint(string[idx])
if ptr.children[i] is not None:
ptr = ptr.children[i]
else:
ptr.children[i] = Node()
ptr = ptr.children[i]
ptr.isend = True
        

def search(self,string):
ptr = self.__root
length = len(string)
for idx in range(length):
i = self.chartoint(string[idx])
if ptr.children[i] is not None:
ptr = ptr.children[i]
else:
return False
if ptr.isend is not True:
return False
return True
    

def __getall(self,ptr,key,key_list):
if ptr is None:
key_list.append(key)
return
if ptr.isend==True:
key_list.append(key)
for i in range(26):
if ptr.children[i]  is not None:
self.__getall(ptr.children[i],key+chr(ord('a')+i),key_list)
        

def search_byprefix(self,key):
ptr = self.__root
key_list = []
length = len(key)
for idx in range(length):
i = self.chartoint(key[idx])
if ptr.children[i] is not None:
ptr = ptr.children[i]
else:
return None
        

self.__getall(ptr,key,key_list)
return key_list
        

t = trie()
t.insert("shubham")
t.insert("shubhi")
t.insert("minhaj")
t.insert("parikshit")
t.insert("pari")
t.insert("shubh")
t.insert("minakshi")

print(t.search("minhaj"))
print(t.search("shubhk"))
print(t.search_byprefix('m'))
print(len(t))
print(t.remove("minhaj"))
print(t)

代码选择

没错
假的
[‘ minakshi’，‘ minhaj’]
7
Minakshi
Minhajsir
帕里
狗屎
嘘
Shubham
Shubhi

这个答案很像之前的答案，但读起来更简单:

def make_trie(words):
trie = {}
for word in words:
head = trie
for char in word:
if char not in head:
head[char] = {}
head = head[char]
head["_end_"] = "_end_"
return trie

使用默认函数和 reduce 函数。

创建 Trie

from functools import reduce
from collections import defaultdict
T = lambda : defaultdict(T)
trie = T()
reduce(dict.__getitem__,'how',trie)['isEnd'] = True

尝试:

defaultdict(<function __main__.<lambda>()>,
{'h': defaultdict(<function __main__.<lambda>()>,
{'o': defaultdict(<function __main__.<lambda>()>,
{'w': defaultdict(<function __main__.<lambda>()>,
{'isEnd': True})})})})

尝试搜寻:

curr = trie
for w in 'how':
if w in curr:
curr = curr[w]
else:
print("Not Found")
break
if curr['isEnd']:
print('Found')

下面是使用 TrieNode 类的完整代码。

因为我们使用字典来存储子节点，所以不需要将 char 转换成整数，反之亦然，也不需要事先分配数组内存。

class TrieNode:
def __init__(self):
#Dict: Key = letter, Item = TrieNode
self.children = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()


def build_trie(self,words):
for word in words:
self.insert(word)


def insert(self,word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.end = True
def search(self, word):
node = self.root
for char in word:
if char in node.children:
node = node.children[char]
else:
return False
            

return node.end


def _walk_trie(self, node, word, word_list):


if node.children:
for char in node.children:
word_new = word + char
if node.children[char].end:
# if node.end:
word_list.append( word_new)
# word_list.append( word)
self._walk_trie(node.children[char],  word_new  , word_list)


def auto_complete(self, partial_word):
node = self.root


word_list = [ ]
#find the node for last char of word
for char in  partial_word:
if char in node.children:
node = node.children[char]
else:
# partial_word not found return
return word_list
         

if node.end:
word_list.append(partial_word)


#  word_list will be created in this method for suggestions that start with partial_word
self._walk_trie(node, partial_word, word_list)
return word_list

创建一个 Trie

t = Trie()
words = ['hi', 'hieght', 'rat', 'ram', 'rattle', 'hill']
t.build_trie(words)

搜索单词

words = ['hi', 'hello']
for word in  words:
print(word, t.search(word))


hi True
hel False

使用前缀搜索单词

partial_word = 'ra'
t.auto_complete(partial_word)


['rat', 'rattle', 'ram']

前缀搜索

下面是 @ senderle 的回答，稍微修改为 接受前缀搜索(不仅仅是整个单词匹配) :

_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


def in_trie(trie, word):
current_dict = trie
for letter in word:
if _end in current_dict:
return True
if letter not in current_dict:
return False
current_dict = current_dict[letter]
        

t = make_trie(['hello', 'hi', 'foo', 'bar'])
print(in_trie(t, 'hello world'))
# True

class TrieNode:
def __init__(self):
self.keys = {}
self.end = False


class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str, node=None) -> None:
if node == None:
node = self.root
# insertion is a recursive operation
# this is base case to exit the recursion
if len(word) == 0:
node.end = True
return
# if this key does not exist create a new node
elif word[0] not in node.keys:
node.keys[word[0]] = TrieNode()
self.insert(word[1:], node.keys[word[0]])
# that means key exists
else:
self.insert(word[1:], node.keys[word[0]])
def search(self, word: str, node=None) -> bool:
if node == None:
node = self.root
# this is positive base case to exit the recursion
if len(word) == 0 and node.end == True:
return True
elif len(word) == 0:
return False
elif word[0] not in node.keys:
return False
else:
return self.search(word[1:], node.keys[word[0]])
def startsWith(self, prefix: str, node=None) -> bool:
if node == None:
node = self.root
if len(prefix) == 0:
return True
elif prefix[0] not in node.keys:
return False
else:
return self.startsWith(prefix[1:], node.keys[prefix[0]])