Вы хотите три.
http://en.wikipedia.org/wiki/Trie
Я использовал их в программах Scrabble и Boggle. Они идеально подходят для описанного вами варианта использования (быстрый поиск префиксов).
Вот пример кода для построения дерева в Python. Это из программы 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')