最有效的数据结构，用于字符串的只读列表（大约100000个），并具有快速的前缀搜索

Question

我正在编写一个应用程序，它需要从文件中读取字符串列表，将它们保存在数据结构中，然后通过前缀查找这些字符串。字符串列表只是给定语言中的单词列表。例如，如果搜索函数得到“stub”作为参数，它应该返回[“stuble”，“stuptity”，“stupor”…]。它应该在O（log（n）*m）时间内完成，其中n是数据结构的大小，m是结果的数量，应该尽可能快。内存消耗现在不是什么大问题。我是用python编写的，所以如果您能给我指出一个用c实现的、用python包装器实现的合适的数据结构，那就太好了。在

Answer 1

tries的一些Python实现：

• http://jtauber.com/2005/02/trie.py
• http://www.koders.com/python/fid7B6BC1651A9E8BBA547552FE3F039479A4DECC45.aspx
• http://filoxus.blogspot.com/2007/11/trie-in-python.html

Answer 2

你想试试。在

http://en.wikipedia.org/wiki/Trie

我曾在拼字游戏和拼字游戏中使用过它们。它们非常适合您描述的用例（快速前缀查找）。在

下面是一些用Python构建trie的示例代码。这是几个月前我一起做的一个令人困惑的计划。剩下的部分留给读者作为练习。但是对于前缀检查，您基本上需要一个从根节点开始的方法（变量words），跟随前缀的字母到连续的子节点，如果找到这样的路径，则返回True，否则返回False。在

class Node(object):
    def __init__(self, letter='', final=False):
        self.letter = letter
        self.final = final
        self.children = {}
    def __contains__(self, letter):
        return letter in self.children
    def get(self, letter):
        return self.children[letter]
    def add(self, letters, n=-1, index=0):
        if n < 0: n = len(letters)
        if index >= n: return
        letter = letters[index]
        if letter in self.children:
            child = self.children[letter]
        else:
            child = Node(letter, index==n-1)
            self.children[letter] = child
        child.add(letters, n, index+1)

def load_dictionary(path):
    result = Node()
    for line in open(path, 'r'):
        word = line.strip().lower()
        result.add(word)
    return result

words = load_dictionary('dictionary.txt')

Answer 3

听起来很适合你。我相信它可以在O（m）中对长度为m的前缀字符串进行搜索。在