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

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

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

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

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

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

Сначала нам нужен способ сравнить строку запроса с заданной записью. Предположим, что функция использует регулярные выражения: match (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 в вашей реализации (обычно log ( n ).

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

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'])

Если у вас только ? подстановочные знаки, нет * подстановочных знаков, которые совпадают с переменным количеством символов, вы можете попробовать это: Для каждого индекса символов построить словарь из символов в наборы слов, т.е. если слова это write, write, drate, iste, 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"} и взяли бы набор пересечений.

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

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

Нужная вам структура данных называется trie - краткое описание см. в статье Википедии.

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

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

1. Сосредоточьте слова слова словаря в одной длинной Строке, разделенной несловным символом.
2. Поместите все слова в Карту Дерева, где ключом является слово, а значением - смещение начала слова в большую Строку.
3. Найдите основу строки поиска, т.е. самую большую ведущую подстроку, которая не включает в себя ''.
4. Используйте TreeMap.higherKey(base) и TreeMap.lowerKey(next(base)), чтобы найти диапазон в пределах Строки, между которыми будут найдены совпадения. (Метод next должен вычислить следующее большее слово к базовой строке с тем же самым числом или меньшим количеством символов, например next("aa") is "ab", next("az") is "b"].)
5. Создать регресс для строки поиска и использовать Matcher.find() для поиска подстроки, соответствующей диапазону.

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

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

EDIT:

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

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

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

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

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

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

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

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

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

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

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

Просто создайте БД в памяти, загрузите слова и запустите select с помощью оператора LIKE.

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

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

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

Code:

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)))

Tests: (Код также работает для шаблонов типа ?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')
[]

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

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

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

Постройте хэш-сет из всех слов. Чтобы найти совпадения, замените вопросительные знаки в шаблоне на каждую возможную комбинацию букв. Если есть два вопросительных знака, то запрос состоит из 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

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

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

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

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

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

Вы можете использовать хэш, ключами которого являются ваши слова, содержащие до двух '?', а значениями - список подходящих слов. Этот хэш будет содержать около 100,000 + 100,000*6 + 100,000*5 = 1,200,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

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

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

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

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

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

space@, pace@s, ace@sp, *ce@spa*, e@spac

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

Если Вы вставите все эти варианты в ТРИЮ, Вы сможете легко найти слово, которое ищете, по длине слова, "повернув" свое слово.

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

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

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

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

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

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

  Подводя итог, можно сказать, что это очень быстро, и зависит от длины слова * маленькая константа.

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

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

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

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

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

Для каждой длины сделайте 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, чтобы сделать g... Поэтому посмотрите в массиве 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")

На моем компьютере системный словарь имеет размер 909KB, и эта программа использует около 3.2MB памяти в дополнение к тому, что требуется только для хранения слов (указатели - 4 байта). Для этого словаря можно было бы сократить это пополам, используя вместо указателей 2-байтовые целые числа, потому что их длина меньше 2¹⁶ слов.

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

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

Рассматривали ли вы использование троичного дерева поиска ? Скорость поиска сравнима с trie, но она более компактна.

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