针对只读字符串列表（约100,000个）的高效数据结构，支持快速前缀搜索

Question

我正在写一个应用程序，需要从一个文件中读取一串字符串，把它们存储在一个数据结构里，然后根据前缀来查找这些字符串。这些字符串就是某种语言中的单词列表。比如说，如果搜索功能接收到“stup”这个参数，它应该返回["stupid", "stupidity", "stupor"...]。这个查找过程的时间复杂度应该是O(log(n)*m)，其中n是数据结构的大小，m是结果的数量，而且要尽可能快。现在内存使用不是个大问题。我用的是python，所以如果你能推荐一个合适的数据结构（最好是用C实现的，并且有python的接口）那就太好了。

Answer 1

一个字典树（也叫前缀树）听起来很适合你。它可以在长度为m的前缀字符串上进行搜索，时间复杂度是O(m)，我觉得是这样的。

Answer 2

一些关于 字典树（trie） 的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 3

你需要用到一种叫做“字典树”的数据结构。

这里有个链接可以了解更多关于字典树的信息

我在拼字游戏和拼图游戏的程序中用过字典树。它非常适合你提到的情况（快速查找前缀）。

下面是一些用Python构建字典树的示例代码。这段代码来自我几个月前写的一个拼图游戏程序。剩下的部分留给你自己去练习。不过，对于前缀检查，你基本上需要一个方法，从根节点（变量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')