Лучшая структура данных для поиска кроссвордов

Question

У меня есть большая база данных для решения кроссвордов, состоящая из слова и описания. Мое приложение позволяет искать слова определенной длины и символы на определенных позициях (это делается сложным путем ... пройтись по всем словам и проверить каждое). Плюс поиск по описанию (при необходимости)

Например, найти слово _ _ ​​A _ _ B (6-буквенное слово, третий символ A и последний B)

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

Answer 1

Хорошо, я собираюсь предложить что-то странное, но исходя из C++ Я давно пользуюсь Boost, и я пришел к библиотеке MultiIndex.

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

Итак, давайте поместим наши слова в таблицу и разместим необходимые индексы:

word                     |length|c0|c1|c2| ... |c26|
-------------------------|------|--|--|--| ... |---|
Singapour                |9     |S |i |n | ... |0  |

Теперь запрос будет выглядеть так:

Select word From table Where length=9 And c2='n' And c8='u';

Достаточно просто, не правда ли?

Для максимальной эффективности таблица должна быть секционирована по длине, а индексы (по одному на столбец cX) должны быть локальными по отношению к разделу.

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

Вот описание питона:

class Dictionary:
  def __init__(self, length):
    self.length = length
    self.words = set([])
    self.indexes = collections.defaultdict(set)

  def add(self, word):
    if len(word) != self.length:
      raise RuntimeException(word + ' is not ' + `self.length` + ' characters long')

    if word in self.words:
      raise RuntimeException(word + ' is already in the dictionary')

    self.words.add(word)

    for i in range(0,length):
      self.indexes[(i,word[i])].add(word)

  def search(self, list):
    """list: list of tuples (position,character)
    """
    def compare(lhs,rhs): return cmp(len(lhs),len(rhs))

    sets = [self.indexes[elem] for elem in list]
    sets.sort(compare)
    return reduce(intersection, sets)

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

Если хотите, протестируйте его с другими решениями:)

Answer 2

Этот вопрос: Хороший алгоритм и структура данных для поиска слов с пропущенными буквами? начинался в точности как тот, который вы спрашиваете, но затем он был отредактирован до чего-то другого и более простого. Тем не менее, вы можете найти некоторые идеи там.

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

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

# Build a whole lot of sorted word lists
wordlists = collections.defaultdict(list)
for word in sorted(all_words):
    for position, letter in enumerate(word):
        wordlists[len(word), position, letter].append(word)

Теперь, если вам нужно 6-буквенное слово, оканчивающееся на B, вы можете просто попросить wordlists[6, 5, 'B'], и у вас есть полный список. Если вы знаете более одной буквы, как в ..A..B, вы можете выбрать любой список, который будет самым коротким, и проверить каждое слово на соответствие требуемому шаблону. В словаре моего компьютера есть только 21 шестизначное слово, заканчивающееся буквой B, из которых соответствует только SCARAB.

Answer 3

Поскольку вы используете базу данных, создайте таблицу суффиксов.
Например:

  Suffix          |   WordID   | SN
  ----------------+------------+----   
  StackOverflow           10      1
  tackOverflow            10      2
  ackOverflow             10      3
  ckOverflow              10      4
  kOverflow               10      5
  ...

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

SELECT WordID FROM suffixes
WHERE suffix >= 't' AND suffix < 'u' AND SN = 2

Получить все слова, которые содержат 't' в позиции 2.

Обновление: Если вы хотите сэкономить место и немного пожертвовать скоростью, вы можете использовать массив суффиксов .

Вы можете сохранить все слова в строке (массиве) с разделителем между ними, то есть $, и создать массив суффиксов, который будет иметь указатели на символы. Теперь, имея char c, вы можете быстро найти все экземпляры слов, которые его содержат. Тем не менее, вам придется проверить, находится ли он в правильном положении.
(проверяя, как далеко от $ s)

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

Обновление 2: Я использовал подход с базой данных в одной из моих утилит, где мне нужно было найти суффиксы, такие как, например, "ne", и я забыл настроить (оптимизировать) его для этого конкретная проблема.

Вы можете просто сохранить один символ в качестве суффикса:

  Suffix   |   WordID   | SN
  ---------+------------+----   
  S                10      1
  t                10      2
  a                10      3
  c                10      4
  k                10      5
  ...

, что экономит много места. Теперь запрос становится

SELECT WordID FROM suffixes
WHERE suffix = 't' AND SN = 2

Answer 4

Вы можете хранить свою информацию в виде некоторого дерева (возможно, троичного дерева поиска). Алгоритм частичного поиска с использованием дерева описан в разделе 6 этой статьи Седжвика и Бентли. Вы, конечно, хотите иметь разные попытки для различной длины слов. В статье говорится, что алгоритм частичного поиска требует времени O (n ^ ((k-s) / k)) для s букв, указанных в трёх словах длиной k k.

Answer 5

Вы можете использовать Дерево суффиксов или Trie.