如何在Python中创建TRIE

Question

我是Python的新手并且正在努力学习和进步.我对TRIE和DAWG很感兴趣,我一直在阅读它,但我不明白输出TRIE或DAWG文件应该是什么样的.

• TRIE应该是嵌套字典的对象吗？每个字母被分成字母等等？
• 如果有100k或500k条目,那么在这样的字典上查找是否会很快？
• 如何实现由多个单词组成的字块 - 或用空格分隔？
• 如何将单词的前缀或后缀链接到结构中的另一个部分？[对于DAWG]

我想了解最佳输出结构,以便弄清楚如何创建和使用它.

我也很感激DAWG和TRIE的输出应该是什么.

我不希望看到彼此相关的气泡的图形表示,我在阅读时看到它们很多.

一旦将一组单词转换为TRIE或DAWG,我想知道输出对象.

谢谢.

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

我将把插入和移除作为练习留给你.

当然,Unwind的建议不会太难.可能存在轻微的速度劣势,因为找到正确的子节点将需要线性搜索.但搜索将限于可能的字符数 - 如果我们包括,则为27 _end.此外,根据他的建议,通过创建大量节点列表并通过索引访问它们,无法获得任何好处; 你可能只是嵌套列表.

最后,我要补充一点,创建DAWG会有点复杂,因为你必须检测当前单词与结构中的另一个单词共享后缀的情况.事实上,这可能会变得相当复杂,这取决于你想要如何构建DAWG!你可能需要学习一些关于Levenshtein 距离才能做到正确的事情.

Answer 2

看看这个:

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

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

MARISA-trie中的字符串数据可能比标准Python字典中的内存少50x-100x; 原始查找速度可比; trie还提供快速高级方法,如前缀搜索.

基于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 tries,这是一个围绕marisa trie的C++实现的Python包装器."Marisa"是使用递归实现的StorAge的匹配算法的首字母缩写.关于marisa尝试的好处是存储机制真正缩小了你需要多少内存.Python插件的作者声称缩小了50-100倍 - 我们的经验类似.

marisa trie包的优点在于底层的trie结构可以写入磁盘然后通过内存映射对象读入.通过内存映射marisa trie,我们现在满足了所有要求.我们的服务器内存使用量急剧下降了大约40%,而且我们的性能与使用Python的字典实现时相比没有变化.

还有一些纯python实现,但除非您在受限制的平台上,否则您需要使用上面的C++支持的实现来获得最佳性能:

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

Answer 3

以下是实现Trie的python包列表:

• marisa-trie - 基于C++的实现.
• python-trie - 一个简单的纯python实现.
• PyTrie - 一个更高级的纯python实现.
• pygtrie - Google的纯python实现.

Answer 4

使用defaultdict和reduce函数。

创建特里树

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

Answer 5

没有"应该"; 由你决定.各种实现将具有不同的性能特征,需要花费不同的时间来实现,理解和正确.在我看来,这是整个软件开发的典型特征.

我可能会首先尝试创建到目前为止创建的所有trie节点的全局列表,并将每个节点中的子指针表示为全局列表中的索引列表.有一本字典只是为了代表孩子的链接,对我来说感觉太重了.

Answer 6

修改自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')

Answer 7

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

Answer 8

这是使用 TrieNode 类的完整代码。还实现了 auto_complete 方法以返回带有前缀的匹配单词。

由于我们使用字典来存储子节点，因此不需要将字符转换为整数，反之亦然，也不需要提前分配数组内存。

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