Алгоритм сопоставления частично заполненных слов

Question

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

Такой алгоритм уже есть? Если нет, то может ли кто-нибудь дать приблизительное представление о том, как разработать такой алгоритм?

Заранее спасибо.

Answer 1

Ну, он еще не существует, но он уже исследован на SO, для проблем кроссвордов.

Суть решения, которое я предложил, заключалась в индексации по буквам и индексам, что в Python дает:

class Index:
  def __init__(self, list):
    self.data = defaultdict(set)
    for word in list: self.add(word)

  def add(self, word):
    for l in range(0, len(word)):
      self.data[(l, word[l])].insert(word)

  def look(self, letters):
    """letters is a list of tuples (position, letter)"""

    result = None
    for (p,l) in letters:
      set = self.data[(p,l)]
      if result == None: result = set
      else: result = result.insersection(set)

    return result

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

Для поиска вы просто пересекаете все наборы, чтобы получить общий набор слов, который соответствует всем известным буквам.

Answer 2

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

Это решение может быть весьма эффективным с точки зрения потребления памяти.

Answer 3

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

Если вам нужно еще более быстрое решение, вам нужен способ ограничения глубины поиска. Одна возможность состоит в том, чтобы складывать ответы. Например, вы можете начать с группировки слов по длине; тогда вам нужно только просмотреть списки слов определенной длины. Тогда вы можете подгруппировать по словам, содержащим определенные буквы - возможно, достаточно буквенных пар. Это дает вам массив из примерно 13000 элементов, в которые вы можете быстро проиндексировать: посчитайте количество букв в вашем слове, затем выберите самую редкую букву или две в слове и используйте это для индексации в мини-префиксное дерево, которое только содержит слова этой длины с этими буквами. В большинстве случаев эта стратегия позволяет сократить до нескольких сотен слов на одну ячейку, и поиск по дереву префиксов должен быть быстрым, даже если вы выберете большую часть ширины дерева.

Answer 4

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

Затем вам нужно перебрать все слова и проверить, есть ли совпадение.

Answer 5

test = '--a-';

for each (words as word)
{
    if ((word.length == test.length)
        && (test.index(0) == '-' || (word.index(0) == test.index(0)))
        && (test.index(1) == '-' || (word.index(1) == test.index(1)))
        && (test.index(2) == '-' || (word.index(2) == test.index(2)))
        && (test.index(3) == '-' || (word.index(3) == test.index(3))))
    {
        // match
    }
}

Это то, что тебе нужно? Очевидно, что он должен быть немного изменен, чтобы работать на разные длины.