我正在编写一个应用程序,它需要从文件中读取字符串列表,将它们保存在数据结构中,然后通过前缀查找这些字符串。字符串列表只是给定语言中的单词列表。例如,如果搜索函数将“stup”作为参数,它应该返回 [“stupid”、“stupidity”、“stupor”...]。它应该在 O(log(n)*m) 时间内完成,其中 n 是数据结构的大小,m 是结果的数量,并且应该尽可能快。内存消耗现在不是一个大问题。我正在用 python 编写这个,所以如果你能指出一个合适的数据结构(最好)用 python 包装器在 c 中实现,那就太好了。
问问题
3065 次
4 回答
15
你想试一试。
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')
于 2009-07-15T12:09:40.033 回答
4
Try的一些 Python 实现:
于 2009-07-15T12:13:44.787 回答
2
一棵树(或前缀树)听起来就在你的小巷里。我相信它可以在 O(m) 中搜索长度为 m 的前缀字符串。
于 2009-07-15T12:10:52.153 回答
-1
字符串数组。
然后通过它进行二进制搜索以搜索第一个匹配项,然后逐步通过它查找所有后续匹配项
(我最初在这里也有链表......但当然这没有随机访问,所以这是'bs'(这可能解释了我被否决的原因)。我的二进制搜索算法仍然是最快的方法
于 2009-07-15T12:11:01.280 回答