Ответ 1

Я считаю, что в этом случае лучше всего использовать плоский файл, где каждое слово стоит в одной строке. Благодаря этому вы можете удобно использовать возможности поиска регулярных выражений, которые сильно оптимизированы и, вероятно, будут бить любую структуру данных, которую вы можете разработать для этой проблемы.

Решение №1: Использование Regex

Этот рабочий код Ruby для этой проблемы:

def query(str, data)    
  r = Regexp.new("^#{str.gsub("?", ".")}$")
  idx = 0
  begin
    idx = data.index(r, idx)
    if idx
      yield data[idx, str.size]
      idx += str.size + 1
    end
  end while idx
end

start_time = Time.now
query("?r?te", File.read("wordlist.txt")) do |w|
  puts w
end
puts Time.now - start_time

Файл wordlist.txt содержит 45425 слов (можно загрузить здесь). Вывод программы для запроса ?r?te:

brute
crate
Crete
grate
irate
prate
write
wrote
0.013689

Таким образом, требуется всего 37 миллисекунд, чтобы прочитать весь файл и найти в нем все совпадения. И он очень хорошо масштабируется для всех типов шаблонов запросов, даже если Trie очень медленный:

запрос ????????????????e

counterproductive
indistinguishable
microarchitecture
microprogrammable
0.018681

запрос ?h?a?r?c?l?

theatricals
0.013608

Это выглядит достаточно быстро для меня.

Решение №2: регулярное выражение с готовыми данными

Если вы хотите пойти еще быстрее, вы можете разбить список слов на строки, содержащие слова равной длины, и просто искать правильный, исходя из длины запроса. Замените последние 5 строк на этот код:

def query_split(str, data)
  query(str, data[str.length]) do |w|
    yield w
  end
end

# prepare data    
data = Hash.new("")
File.read("wordlist.txt").each_line do |w|
  data[w.length-1] += w
end

# use prepared data for query
start_time = Time.now
query_split("?r?te", data) do |w|
  puts w
end
puts Time.now - start_time

Построение структуры данных занимает около 0,4 секунды, но все запросы примерно в 10 раз быстрее (в зависимости от количества слов с этой длиной):

• ?r?te 0,001112 sec
• ?h?a?r?c?l? 0,000852 сек
• ????????????????e 0.000169 sec

Решение № 3: одна большая хэш-таблица (обновленные требования)

Поскольку вы изменили свои требования, вы можете легко расширить свою идею, используя только одну большую хэш-таблицу, которая содержит все заранее рассчитанные результаты. Но вместо того, чтобы самостоятельно работать с коллизиями, вы можете положиться на производительность правильно реализованной хэш-таблицы.

Здесь я создаю одну большую хэш-таблицу, где каждый возможный запрос отображает список его результатов:

def create_big_hash(data)
  h = Hash.new do |h,k|
    h[k] = Array.new
  end    
  data.each_line do |l|
    w = l.strip
    # add all words with one ?
    w.length.times do |i|
      q = String.new(w)
      q[i] = "?"
      h[q].push w
    end
    # add all words with two ??
    (w.length-1).times do |i|
      q = String.new(w)      
      q[i, 2] = "??"
      h[q].push w
    end
  end
  h
end

# prepare data    
t = Time.new
h = create_big_hash(File.read("wordlist.txt"))
puts "#{Time.new - t} sec preparing data\n#{h.size} entries in big hash"

# use prepared data for query
t = Time.new
h["?ood"].each do |w|
  puts w
end
puts (Time.new - t)

Выход

4.960255 sec preparing data
616745 entries in big hash
food
good
hood
mood
wood
2.0e-05

Производительность запроса - O (1), это просто поиск в хеш-таблице. Время 2.0e-05, вероятно, ниже точности таймера. При работе 1000 раз, я получаю в среднем 1,958e-6 секунд за запрос. Чтобы ускорить работу, я переключился на С++ и использовал Google Sparse Hash, который чрезвычайно эффективен в работе с памятью и быстро.

Решение №4: получить действительно серьезный

Все вышеперечисленные решения работают и должны быть достаточно хорошими для многих случаев использования. Если вы действительно хотите стать серьезными и иметь много свободного времени на своих руках, прочитайте хорошие документы:

• пытается приблизить соответствие строк - если это хорошо реализовано, попытки могут иметь очень компактные требования к памяти (на 50% меньше места, чем сам словарь), и очень быстро.
• Agrep - быстрый приближенный инструмент для сопоставления шаблонов - Agrep основан на новом эффективном и гибком алгоритме для приближенного сопоставления строк.
• Google Scholar ищет приблизительное соответствие строк - более чем достаточно для чтения по этой теме.

Ответ 2

Учитывая текущие ограничения:

• Будет найдено до двух вопросительных знаков
• Когда есть 2 вопроса, они появляются вместе
• В словаре есть ~ 100 000 слов, средняя длина слова - 6.

У меня есть два жизнеспособных решения для вас:

Быстрое решение: HASH

Вы можете использовать хэш, какие ключи являются вашими словами, до двух "?", а значения - это список подходящих слов. Этот хэш будет иметь около 100 000 + 100 000 * 6 + 100 000 * 5 = 1200 000 записей (если у вас есть 2 вопроса, вам просто нужно найти место первого...). Каждая запись может сохранять список слов или список указателей на существующие слова. Если вы сохраните список указателей, и предположим, что в среднем меньше 20 слов, соответствующих каждому слову с двумя "?", Тогда дополнительная память составляет менее 20 * 1 200 000 = 24 000 000.

Если каждый размер указателя составляет 4 байта, тогда здесь требуется потребность в памяти (24 000 000 + 1 200 000) * 4 байта = 100 800 000 байт ~ = 96 мегабайт.

Подведем итог этому решению:

• Потребление памяти: ~ 96 МБ
• Время для каждого поиска: вычисление хэш-функции и указатель. O (1)

Примечание. Если вы хотите использовать хэш меньшего размера, вы можете, но тогда лучше сохранить сбалансированное дерево поиска в каждой записи вместо связанного списка для лучшей производительности.

Пространство, но все же очень быстрое решение: TRIE вариация

В этом решении используется следующее наблюдение:

Если '?' знаки были в конце слова, trie было бы отличным решением.

Поиск в trie будет искать длину слова, а для последних двух букв обход DFS принесет все окончания. Очень быстрое и очень сообразительное решение.

Итак, давайте использовать это наблюдение, чтобы построить что-то, чтобы работать именно так.

Вы можете думать о каждом слове, которое у вас есть в словаре, как слово, заканчивающееся на @(или любой другой символ, который не существует в вашем словаре). Таким образом, слово "пространство" будет "space @". Теперь, если вы вращаете каждое из слов с знаком "@", вы получаете следующее:

[email protected], [email protected], [email protected], *[email protected]*, [email protected]

(нет @в качестве первой буквы).

Если вы вставляете все эти вариации в TRIE, вы можете легко найти слово, которое ищете по длине слова, путем "поворота" вашего слова.

Пример: Вы хотите найти все слова, которые соответствуют "s" (один из них - пространство, другое - срез). Вы строите слово: s? Ce @и вращаете его так, чтобы? знак в конце. т.е. 'ce @s??'

Все вариации вращения существуют внутри trie, а конкретно "ce @spa" (отмечены * выше). После начала поиска - вам нужно пройти все продолжения в соответствующей длине и сохранить их. Затем вам нужно повернуть их снова, чтобы @была последней буквой, а walla - у вас есть все слова, которые вы искали!

Подведем итог этому решению:

• Потребление памяти: Для каждого слова все его вращения появляются в trie. В среднем, * 6 объема памяти сохраняется в trie. Размер три составляет около 3 (только гадание...) пространства, сохраненного внутри него. Таким образом, общее пространство, необходимое для этого три, составляет 6 * 3 * 100 000 = 1,800,000 слов ~ = 6,8 мегабайта.

• Время для каждого поиска:

  • вращение слова: O (длина слова)
  • поиск начала в trie: O (длина слова)
  • перебирает все окончания: O (количество совпадений)
  • вращение окончаний: O (общая длина ответов)

  Подводя итог, он очень быстр и зависит от длины слова * small constant.

Подводя итог...

Второй выбор имеет большую сложность времени и пространства и будет лучшим вариантом для вас. Есть несколько проблем со вторым решением (в этом случае вы можете использовать первое решение):

• Более сложный для реализации. Я не уверен, есть ли языки программирования со встроенными встроенными программами. Если нет - это означает, что вам нужно будет реализовать его самостоятельно...
• Не масштабируется хорошо. Если завтра вы решите, что вам нужны ваши вопросительные знаки, которые распространяются по всему слову, и не обязательно объединяются вместе, вам нужно будет много подумать о том, как соответствовать второму решению. В случае первого решения - его довольно легко обобщить.

Ответ 3

Мне эта проблема звучит как хорошая подгонка для структуры данных Trie. Введите весь словарь в свой трюк, а затем найдите слово. Для отсутствующей буквы вам придется попробовать все подтемы, которые относительно легко сделать с помощью рекурсивного подхода.

EDIT. Я написал простую реализацию этого в Ruby только сейчас: http://gist.github.com/262667.

Ответ 4

Directed Acyclic Word Graph будет идеальной структурой данных для этой проблемы. Он сочетает в себе эффективность trie (trie можно рассматривать как частный случай DAWG), но гораздо эффективнее пространства. Типичный DAWG займет часть размера, в котором будет использоваться обычный текстовый файл со словами.

Перечисление слов, отвечающих определенным условиям, является простым и тем же, что и в trie - вам нужно пересекать график по глубине.

Ответ 5

Второе решение для Анны - вдохновение для этого.

Сначала загрузите все слова в память и разделите словарь на разделы на основе длины слова.

Для каждой длины сделайте 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 ¹⁶.

Измерения: На моей машине m.find("st??k") работает за 0.000032 секунды, m.find("ov???low") за 0.000034 секунды и m.find("????????????????e") за 0.000023 секунды.

Выбирая бинарный поиск вместо использования class RotatedArray и библиотеки bisect, я получил эти первые два номера до 0,000016 секунд: в два раза быстрее. Реализация этого в С++ сделает его еще быстрее.

Ответ 6

Сначала нам нужен способ сравнения строки запроса с данной записью. Пусть предполагается функция с использованием регулярных выражений: matches(query,trialstr).

Алгоритм O (n) должен состоять в простом прохождении через каждый элемент списка (ваш словарь будет представлен как список в программе), сравнивая каждую с вашей строкой запроса.

С небольшим количеством предварительных вычислений вы можете улучшить это для большого количества запросов, создав дополнительный список слов для каждой буквы, поэтому ваш словарь может выглядеть так:

wordsbyletter = { 'a' : ['aardvark', 'abacus', ... ],
                  'b' : ['bat', 'bar', ...],
                  .... }

Однако это было бы ограниченным использованием, особенно если строка запроса начинается с неизвестного символа. Поэтому мы можем сделать еще лучше, заметив, где в данном слове лежит конкретное письмо, генерируя:

wordsmap = { 'a':{ 0:['aardvark', 'abacus'],
                   1:['bat','bar'] 
                   2:['abacus']},
             'b':{ 0:['bat','bar'],
                   1:['abacus']},
             ....
           }

Как вы можете видеть, без использования индексов вы значительно увеличите количество требуемого пространства для хранения - в частности, словарь из n слов и средней длины m потребует хранения nm ². Тем не менее, вы можете очень быстро сделать свой взгляд, чтобы получить все слова из каждого набора, который может соответствовать.

Окончательная оптимизация (которую вы можете использовать с летучей мыши по наивному подходу) должна также отделить все слова одной длины с отдельными магазинами, так как вы всегда знаете, как долго это слово.

Эта версия будет O (kx), где k - число известных букв в слове запроса, а x= x ( n) - время поиска одного элемента в словаре длиной n в вашей реализации (обычно войти (<я > п).

Итак, с последним словарем вроде:

allmap = { 
           3 : { 
                  'a' : {
                          1 : ['ant','all'],
                          2 : ['bar','pat']
                         }
                  'b' : {
                          1 : ['bar','boy'],
                      ...
                }
           4 : {
                  'a' : {
                          1 : ['ante'],
                      ....

Тогда наш алгоритм справедлив:

possiblewords = set()
firsttime = True
wordlen = len(query)
for idx,letter in enumerate(query):
    if(letter is not '?'):
        matchesthisletter = set(allmap[wordlen][letter][idx])
        if firsttime:
             possiblewords = matchesthisletter
        else:
             possiblewords &= matchesthisletter

В конце набор possiblewords будет содержать все соответствующие буквы.

Ответ 7

Если вы создаете все возможные слова, соответствующие шаблону (arate, arbte, arcte... zryte, zrzte), а затем просматривайте их в двоичном представлении дерева словаря, который будет иметь средние рабочие характеристики O (e ^ N1 * log (N2)), где N1 - количество вопросительных знаков, а N2 - размер словаря. Кажется достаточно хорошим для меня, но я уверен, что можно найти лучший алгоритм.

РЕДАКТИРОВАТЬ. Если у вас будет больше, чем сказать, три вопросительных знака, посмотрите на ответ Фила Х и его подход к индексированию письма.

Ответ 8

Предположим, что у вас достаточно памяти, вы можете построить гигантский хэш файл, чтобы обеспечить ответ в постоянное время. Вот краткий пример в python:

from array import array
all_words = open("english-words").read().split()
big_map = {}

def populate_map(word):
  for i in range(pow(2, len(word))):
    bin = _bin(i, len(word))
    candidate = array('c', word)
    for j in range(len(word)):
      if bin[j] == "1":
        candidate[j] = "?"
    if candidate.tostring() in big_map:
      big_map[candidate.tostring()].add(word)
    else:
      big_map[candidate.tostring()] = set([word])

def _bin(x, width):
    return ''.join(str((x>>i)&1) for i in xrange(width-1,-1,-1))

def run():
  for word in all_words:
    populate_map(word)

run()

>>> big_map["y??r"]
set(['your', 'year'])
>>> big_map["yo?r"]
set(['your'])
>>> big_map["?o?r"]
set(['four', 'poor', 'door', 'your', 'hour'])

Ответ 9

Вы можете посмотреть, как это делается в aspell. Он предлагает предложения правильного слова для слов с ошибками.

Ответ 10

Создайте хэш-набор всех слов. Чтобы найти совпадения, замените вопросительные знаки в шаблоне каждой возможной комбинацией букв. Если есть две вопросительные знаки, запрос состоит из 26 ²= 676 быстрых, хеш-таблиц с постоянным ожидаемым временем.

import itertools

words = set(open("/usr/share/dict/words").read().split())

def query(pattern):
    i = pattern.index('?')
    j = pattern.rindex('?') + 1
    for combo in itertools.product('abcdefghijklmnopqrstuvwxyz', repeat=j-i):
        attempt = pattern[:i] + ''.join(combo) + pattern[j:]
        if attempt in words:
            print attempt

Это использует меньше памяти, чем мой другой ответ, но она экспоненциально медленнее, поскольку вы добавляете дополнительные вопросительные знаки.

Ответ 11

Если точность 80-90% приемлема, вы можете справиться с Peter Norvig проверка орфографии. Реализация маленькая и элегантная.

Ответ 12

Решение на основе регулярных выражений рассмотрит все возможные значения в вашем словаре. Если производительность является вашим самым большим ограничением, можно создать индекс, чтобы значительно ускорить его.

Вы можете начать с индекса на каждую длину слова, содержащую индекс каждого набора совпадений с индексом = символ. Для длины 5 слов, например, 2=r : {write, wrote, drate, arete, arite}, 3=o : {wrote, float, group} и т.д. Чтобы получить возможные совпадения для исходного запроса, скажем '? Ro??', наборы слов будут пересекаться, в результате получится {wrote, group} в этом случае.

Предполагается, что единственным подстановочным знаком будет один символ и что длина слова известна заранее. Если это недопустимые предположения, я могу рекомендовать соответствие текста на основе n-грамм, например, в в этой статье.

Ответ 13

Структура данных, которую вы хотите, называется trie - см. статью в википедии для краткого резюме.

A trie - это древовидная структура, в которой пути через дерево образуют множество всех слов, которые вы хотите кодировать - каждый node может иметь до 26 детей, для каждой возможной буквы в следующей позиции символа. См. Диаграмму в статье wikipedia, чтобы понять, что я имею в виду.

Ответ 14

Вот как бы я это сделал:

• Объединить слова словаря в одну длинную строку, разделенную символом, отличным от слова.
• Поместите все слова в TreeMap, где ключ - это слово, а значение - смещение начала слова в большой строке.
• Найдите базу строки поиска; то есть самая большая ведущая подстрока, которая не включает '?'.
• Используйте TreeMap.higherKey(base) и TreeMap.lowerKey(next(base)), чтобы найти диапазон внутри строки, между которыми будут найдены совпадения. (Метод next должен рассчитать следующее большее слово в базовой строке с тем же числом или меньшим количеством символов, например next("aa") is "ab", next("az") is "b".)
• Создайте регулярное выражение для строки поиска и используйте Matcher.find() для поиска подстроки, соответствующей диапазону.

Шаги 1 и 2 выполняются заранее, давая структуру данных, используя O(NlogN) пространство, где N - количество слов.

Этот подход вырождается в поиск регулярных выражений грубой силы всего словаря, когда '?' появляется в первой позиции, но чем дальше, тем меньше согласование должно быть выполнено.

ИЗМЕНИТЬ:

Чтобы повысить производительность в случае, когда '?' является первым символом, создайте вторичную таблицу поиска, которая записывает смещения начала и конца прогонов слов, вторым символом которых является "a", "b" и т.д., Это можно использовать в случае, когда первый не-? является вторым персонажем. Вы можете использовать аналогичный подход для случаев, когда первый не-? это третий символ, четвертый символ и т.д., но в итоге вы получаете большее и большее количество меньших и меньших тиражей, и в конечном итоге эта "оптимизация" становится неэффективной.

Альтернативный подход, требующий значительно большего пространства, но который в большинстве случаев быстрее, заключается в том, чтобы подготовить структуру словарных данных, как указано выше, для всех поворотов слов в словаре. Например, первое вращение будет состоять из всех слов 2 или более символов с первым символом слова, перенесенным в конец слова. Второе вращение будет состоять из слов 3 или более символов с первыми двумя символами, перенесенными в конец, и так далее. Затем, чтобы выполнить поиск, найдите самую длинную последовательность не-? символов в строке поиска. Если индекс первого символа этой подстроки N, используйте поворот Nth, чтобы найти диапазоны и выполнить поиск в списке N-го ротационного слова.

Ответ 15

У моего первого сообщения была ошибка, которую нашел Джейсон, это не сработало, когда? был в начале. Я теперь заимствовал циклические смены от Анны.

Мое решение: Введите символ конца слова (@) и сохраните все циклические сдвинутые слова в отсортированных массивах! Используйте один отсортированный массив для каждой длины слова. При поиске "th? E @" сдвиньте строку, чтобы переместить "-марки" в конец (получение e @th??) и выберите массив, содержащий слова длиной 5, и выполните двоичный поиск первого слова, происходящего после строки "e @th". Все остальные слова в массиве совпадают, т.е. Мы найдем "e @thoo (thoose), e @thes (these) и т.д.

Решение имеет временную сложность Log (N), где N - размер словаря, и он расширяет размер данных примерно в 6 раз (средняя длина слова)

Ответ 16

Считаете ли вы использование Ternary Search Tree? Скорость поиска сопоставима с trie, но она более экономична.

Я несколько раз реализовал эту структуру данных, и это довольно простая задача на большинстве языков.

Ответ 17

Резюме: Используйте два компактных бинарных индекса, одно из слов и одно из обратных слов. Стоимость пространства составляет 2N указателей для индексов; почти все поиски идут очень быстро; худший случай, "э", по-прежнему приличный. Если вы производите отдельные таблицы для каждой длины слова, это сделает очень худший случай очень быстрым.

Детали: Стивен К. опубликовал хорошую идею: найдите упорядоченный словарь, чтобы найти диапазон, в котором может отображаться шаблон. Это не помогает, однако, когда шаблон начинается с шаблона. Вы также можете индексировать по длине слова, но здесь другая идея: добавить упорядоченный указатель на словах с переворотом словаря; то шаблон всегда дает небольшой диапазон либо в прямом индексе, либо в индексе обратного слова (поскольку нам говорят, что нет таких шаблонов, как ABCD?). Сами слова нужно хранить только один раз, причем записи обеих структур указывают на одни и те же слова, а процедура поиска просматривает их либо вперед, либо наоборот; но для использования встроенной функции двоичного поиска Python я создал вместо этого два массива строк, теряя пространство. (Я использую отсортированный массив вместо дерева, как предложили другие, поскольку он экономит место и идет как минимум так же быстро.)

Код

import bisect, re

def forward(string): return string
def reverse(string): return string[::-1]

index_forward = sorted(line.rstrip('\n')
                       for line in open('/usr/share/dict/words'))
index_reverse = sorted(map(reverse, index_forward))

def lookup(pattern):
    "Return a list of the dictionary words that match pattern."
    if reverse(pattern).find('?') <= pattern.find('?'):
        key, index, fixup = pattern, index_forward, forward
    else:
        key, index, fixup = reverse(pattern), index_reverse, reverse
    assert all(c.isalpha() or c == '?' for c in pattern)
    lo = bisect.bisect_left(index, key.replace('?', 'A'))
    hi = bisect.bisect_right(index, key.replace('?', 'z'))
    r = re.compile(pattern.replace('?', '.') + '$')
    return filter(r.match, (fixup(index[i]) for i in range(lo, hi)))

Тесты: (код также работает для таких шаблонов, как AB? D?, хотя без гарантии скорости.)

>>> lookup('hello')
['hello']
>>> lookup('??llo')
['callo', 'cello', 'hello', 'uhllo', 'Rollo', 'hollo', 'nullo']
>>> lookup('hel??')
['helio', 'helix', 'hello', 'helly', 'heloe', 'helve']
>>> lookup('he?l')
['heal', 'heel', 'hell', 'heml', 'herl']
>>> lookup('hx?l')
[]

Эффективность: Для этого нужны указатели 2N плюс пространство, необходимое для хранения текста словарного слова (в настроенной версии). В худшем случае наступает шаблон "??", который смотрит на 44062 кандидатов в 235k-word/usr/share/dict/words; но почти все запросы намного быстрее, например, "h?? lo", смотря на 190, и сначала индексирование по длине слова уменьшит "почти до нуля", если понадобится. Каждая проверка кандидатов проходит быстрее, чем другие хеш-таблицы, которые другие предложили.

Это похоже на решение rotations-index, которое позволяет избежать всех кандидатов с ложным совпадением за счет необходимости иметь около 10N указателей вместо 2N (предположим, что средняя длина слова около 10, как в моих /usr/share/dict/words ).

Вы можете сделать один бинарный поиск для каждого поиска вместо двух, используя функцию пользовательского поиска, которая выполняет поиск как низкозатратных, так и высокосвязных (так что общая часть поиска не повторяется).

Ответ 18

Ленивое решение - позволить SQLite или другой СУБД выполнить эту работу для вас.

Просто создайте базу данных в памяти, загрузите свои слова и запустите выбор, используя оператор LIKE.

Ответ 19

Если у вас есть только ? подстановочные знаки, подстановочные знаки *, которые соответствуют переменному количеству символов, вы можете попробовать следующее: для каждого символьного индекса создайте словарь от символов до наборов слов. то есть, если слова написаны, написаны, drate, arete, arite, ваша структура словарей будет выглядеть так:

Character Index 0:
  'a' -> {"arete", "arite"}
  'd' -> {"drate"}
  'w' -> {"write", "wrote"}
Character Index 1:
  'r' -> {"write", "wrote", "drate", "arete", "arite"}
Character Index 2:
  'a' -> {"drate"}
  'e' -> {"arete"}
  'i' -> {"write", "arite"}
  'o' -> {"wrote"}
...

Если вы хотите найти a?i??, вы должны взять набор, соответствующий индексу символов 0 = > 'a' { "iste", "arite" } и множеству, соответствующему символьному индексу 2 = 'i' = > { "write", "arite" } и взять множество пересечений.

Ответ 20

Если вы серьезно хотите что-то порядка миллиарда поисковых запросов в секунду (хотя я не могу мечтать, почему кто-то, кроме кого-то, кто сделает следующий великий мастер-скребок AI или что-то для огромного веб-сервиса, захочет это быстро) Я рекомендую использовать threading для создания [количества ядер на вашей машине] потоков + основной поток, который делегирует работу всем этим потокам. Затем примените лучшее решение, которое вы нашли до сих пор, и надеемся, что у вас не закончится память.

Идея, которую я имел, заключается в том, что вы можете ускорить некоторые случаи, подготовив нарезанные словари буквой, а затем, если вы знаете первую букву выбора, вы можете прибегнуть к просмотру гораздо меньшего стога сена.

Другая мысль, что у меня была, это то, что вы пытались переборщить что-то - возможно, создайте БД или список или что-то для царапин?