Лучшая структура данных для поиска кроссворда
У меня есть большая база данных для решения кроссвордов, состоя из слова и описания. Мое приложение позволяет искать слова определенной длины и символов на определенных положениях (это сделано, твердый путь... проходит все слова и проверяет каждого). Плюс поиск по описанию (при необходимости)
Например, найдите слово _ _ _ _ B (6 слов буквы, третий символ A, и продержитесь B),
Я хотел бы индексировать слова таким способом, которым поиск будет действительно быстр. Моя первая идея состояла в том, чтобы использовать структуру сбалансированного дерева, какое-либо другое предложение?
5 ответов
Хорошо, я собираюсь предложить нечто странное, но, придя из 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) должны быть локальными для раздела.
Для решения in-memory у вас будет один контейнер на длину, содержащий столько индексов, сколько длин, каждый индекс - это хэш-таблица, указывающая на отсортированный список (более простое объединение)
Вот описание на python:
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)
Я добровольно предоставил аргумент длина, чтобы минимизировать размер хэшей и тем самым улучшить поиск. Кроме того, множества отсортированы по длине, чтобы вычисление пересечения было более удобным :)
Если хотите, протестируйте его против других решений :)
Этот вопрос: Хороший алгоритм и структура данных для поиска слов с пропущенными буквами? начинался именно так, как вы спрашиваете, но потом он был отредактирован на что-то совсем другое и более простое. Тем не менее, вы можете найти там несколько идей.
Вкратце, все рекомендуют загрузить весь словарь в память и разделить слова на группы в зависимости от их длины. Дальше можно двигаться в разных направлениях. Чем больше памяти вы готовы использовать, тем быстрее вы сможете работать.
Одно из хороших предложений - хранить хэш-таблицу списков слов заданной длины, в которых заданная буква находится в заданной позиции. Вы можете построить ее следующим образом (на языке 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.
Поскольку вы используете базу данных, создайте таблицу Suffixes.
Например:
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)
Вероятно, с вышеупомянутой техникой поиск будет x10 быстрее, чем поиск всех слов в вашей оригинальной программе.
Обновление 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
Вы можете хранить свою информацию в некотором дереве (возможно, в троичном дереве поиска). Алгоритм частичного поиска с использованием дерева описан в разделе 6 этой статьи Седжвика и Бентли. Вы, конечно, хотите по-разному использовать разные длины слов. В документе говорится, что алгоритм частичного поиска требует времени O (n ^ ((k-s) / k)) для s букв, указанных в дереве из n слов длины k.