C++ Boggle Solver: поиск префиксов в наборе

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

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

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

Я обнаружил, что операция set.find() возвращает true только в том случае, если строка является точным совпадением. В требованиях к лаборатории профессор упомянул, что:

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

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

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

Я также думал об использовании strncmp() для сравнения текущей последовательности со словом из набора словарей, но опять же, я не знаю, как именно это будет работать в этой ситуации, если вообще будет.

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

Спасибо


c++ set prefix data-structures boggle
person Ian Mahuika    schedule 29.01.2012    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Как упоминает @Raymond Hettinger в своем ответе, trie здесь было бы чрезвычайно полезно. Однако, если вам неудобно писать трие или вы предпочитаете использовать готовые компоненты, вы можете использовать симпатичное свойство того, как слова упорядочены в алфавитном порядке, чтобы проверить за время O (log n), существует ли данный префикс. Идея заключается в следующем: предположим, например, что вы проверяете префикс «thr». Если вы обратите внимание, каждое слово, начинающееся с префикса «thr», должно быть зажато между строками «thr» и «ths». Например, через ‹ тыс. и через горло ‹ тыс. Если вы храните свои слова в гигантском отсортированном массиве, вы можете использовать модифицированную версию бинарного поиска, чтобы найти первое слово в алфавитном порядке, по крайней мере, префикс по вашему выбору, и первое слово в алфавитном порядке, по крайней мере, следующий префикс (образованный путем взятия последнего буква префикса и ее увеличение). Если это одно и то же слово, то между ними ничего нет и приставки не существует. Если это не так, то между ними что-то есть, и это делает префикс.

Поскольку вы используете C++, вы потенциально можете использовать алгоритм std::vector и std::lower_bound. Вы также можете поместить все слова в std::set и использовать версию lower_bound для set. Например:

std::set<std::string> dictionary;
std::string prefix = /* ... */

/* Get the next prefix. */
std::string nextPrefix = prefix;
nextPrefix[nextPrefix.length() - 1]++;

/* Check whether there is something with the prefix. */
if (dictionary.lower_bound(prefix) != dictionary.lower_bound(nextPrefix)) {
    /* ... something has that prefix ... */
} else {
    /* ... no word has that prefix ... */
}

Тем не менее, trie, вероятно, является лучшей структурой здесь. Если вам интересно, есть еще одна структура данных, называемая DAWG (направленный ациклический словесный граф), которая похож на trie, но использует значительно меньше памяти; на вводных курсах CS в Стэнфорде (где Boggle является заданием) студентам фактически предоставляется DAWG, содержащая все слова языка. Существует также другая структура данных, называемая троичным деревом поиска, которая находится где-то посередине между двоичным деревом поиска. и попытка, которая может быть полезна здесь, если вы хотите изучить ее.

Надеюсь это поможет!

person templatetypedef    schedule 29.01.2012
comment
Спасибо Раймонду Хеттингеру и templatetypedef. Я думаю, что попытка была бы лучшим вариантом, если бы это задание позволяло это. Я посмотрю на файл lower_bound. - person Ian Mahuika; 29.01.2012

arrow_upward
3
arrow_downward

trie является предпочтительной структурой данных для этой задачи.

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

asp -> aspberger aspire
bal -> balloon balance bale baleen ...
person Raymond Hettinger    schedule 29.01.2012
comment
Я не уверен, что согласен с тем, что отображение на префиксы здесь правильно; это чрезвычайно неэффективно для памяти. - person templatetypedef; 29.01.2012
comment
@templatetypedef Учитывая, что вам разрешено использовать только набор или отсортированный список, возможности несколько ограничены. RightCall™ должен использовать попытку. - person Raymond Hettinger; 29.01.2012