具有快速前缀搜索的只读字符串列表(约100,000)的最有效数据结构

Question

我正在编写一个应用程序,需要从文件中读取字符串列表,将它们保存在数据结构中,然后按前缀查找这些字符串.字符串列表只是给定语言中的单词列表.例如,如果搜索函数将"stup"作为参数,则应返回["stupid","stupidity","stupor"...].它应该在O(log(n)*m)时间内完成,其中n是数据结构的大小,m是结果的数量,应该尽可能快.内存消耗现在不是一个大问题.我在python中写这个,所以如果你能指出一个合适的数据结构(最好)用python包装器在c中实现它会很棒.

Answer 1

你想要一个特里.

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

我在Scrabble和Boggle程序中使用它们.它们非常适合您描述的用例(快速前缀查找).

这是一些用于在Python中构建trie的示例代码.这是几个月前我鞭打的Boggle计划.其余部分留给读者练习.但是对于前缀检查,你基本上需要一个从根节点(变量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')