Второе решение Анны - это вдохновение для этого.
Сначала загрузите все слова в память и разделите словарь на разделы в зависимости от длины слова.
Для каждой длины сделайте n копий массива указателей на слова. Сортируйте каждый массив так, чтобы строки выглядели в порядке при повороте на определенное количество букв . Например, предположим, что первоначальный список из 5 букв состоит из слов: [самолет, яблоко, пробел, поезд, счастливый, стек, хаки]. Тогда ваши пять массивов указателей будут:
rotated by 0 letters: [apple, hacks, happy, plane, space, stack, train]
rotated by 1 letter: [hacks, happy, plane, space, apple, train, stack]
rotated by 2 letters: [space, stack, train, plane, hacks, apple, happy]
rotated by 3 letters: [space, stack, train, hacks, apple, plane, happy]
rotated by 4 letters: [apple, plane, space, stack, train, hacks, happy]
(Вместо указателей вы можете использовать целые числа, идентифицирующие слова, если это экономит место на вашей платформе.)
Для поиска просто спросите, на сколько вам нужно повернуть шаблон , чтобы в конце появились знаки вопроса. Затем вы можете выполнить бинарный поиск в соответствующем списке.
Если вам нужно найти совпадения для ?? ppy, вам придется повернуть его на 2, чтобы сделать ppy ??. Так что смотрите в массив, который находится в порядке, когда вращается на 2 буквы. Быстрый бинарный поиск обнаруживает, что «счастливый» является единственным соответствием.
Если вам нужно найти совпадения для th g, вам придется повернуть его на 4, чтобы получить gth ??. Итак, посмотрите в массиве 4, где бинарный поиск обнаруживает, что совпадений нет.
Это работает независимо от того, сколько существует вопросительных знаков, если они все появляются вместе.
Требуется пространство в дополнение к самому словарю: для слов длиной N требуется пространство (для N раз количество слов длины N) указателей или целых чисел.
Время на поиск : O (log n), где n - количество слов соответствующей длины.
Реализация на Python:
import bisect
class Matcher:
def __init__(self, words):
# Sort the words into bins by length.
bins = []
for w in words:
while len(bins) <= len(w):
bins.append([])
bins[len(w)].append(w)
# Make n copies of each list, sorted by rotations.
for n in range(len(bins)):
bins[n] = [sorted(bins[n], key=lambda w: w[i:]+w[:i]) for i in range(n)]
self.bins = bins
def find(self, pattern):
bins = self.bins
if len(pattern) >= len(bins):
return []
# Figure out which array to search.
r = (pattern.rindex('?') + 1) % len(pattern)
rpat = (pattern[r:] + pattern[:r]).rstrip('?')
if '?' in rpat:
raise ValueError("non-adjacent wildcards in pattern: " + repr(pattern))
a = bins[len(pattern)][r]
# Binary-search the array.
class RotatedArray:
def __len__(self):
return len(a)
def __getitem__(self, i):
word = a[i]
return word[r:] + word[:r]
ra = RotatedArray()
start = bisect.bisect(ra, rpat)
stop = bisect.bisect(ra, rpat[:-1] + chr(ord(rpat[-1]) + 1))
# Return the matches.
return a[start:stop]
words = open('/usr/share/dict/words', 'r').read().split()
print "Building matcher..."
m = Matcher(words) # takes 1-2 seconds, for me
print "Done."
print m.find("st??k")
print m.find("ov???low")
На моем компьютере системный словарь имеет размер 909 КБ, и эта программа использует около 3,2 МБ памяти в дополнение к тому, что требуется только для хранения слов (указатели 4 байта). Для этого словаря вы можете сократить его пополам, используя 2-байтовые целые числа вместо указателей, потому что имеется менее 2 16 слов каждой длины.
Измерения: На моей машине m.find("st??k") выполняется за 0,000032 секунды, m.find("ov???low") за 0,000034 секунды и m.find("????????????????e") за 0,000023 секунды.
Записав двоичный поиск вместо использования class RotatedArray и библиотеки bisect, я получил эти первые два числа до 0,000016 секунд: в два раза быстрее. Реализация этого в C ++ сделает его еще быстрее.