C++ - Как эффективно узнать, может ли какая-либо строка в векторе быть собрана из набора букв.

Question

Я реализую текстовую версию Scrabble для проекта колледжа.

У меня есть вектор, содержащий около 400 тыс. Строк (мой словарь), и в какой-то момент на каждом шагу мне нужно будет проверить , если в словаре все еще есть слово, которое можно сформировать с помощью частей в руке игрока. Я проверяю, есть ли у игрока какой-нибудь ход ... Если нет, это игра для игрока, о котором идет речь ...

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

Текстовый файл, содержащий словарь, уже упорядочен по алфавиту, поэтому вектор сортируется.

Любые предложения?

---

Проблема была представлена ​​в комментариях ниже: Любое предложение о том, как принимать во внимание письма, уже находящиеся на борту?

Answer 1

Без предоставления вам определенного кода (так как это домашнее задание в конце концов), один общий подход к рассмотрению - map от отсортированных букв в слове до фактических юридических слов.

То есть, если ваш файл словаря были только слова ape, gum и mug, ваша структура данных будет выглядеть следующим образом:

aep -> ape 
gmu -> gum, mug 

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

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

Answer 2

Вы также можете сохранить строки с символами, отсортированными по ASCII-варианту, в std :: set, затем отсортировать буквы игрока в том же порядке и выполнить поиск карты для каждой подстроки букв игрока.

Answer 3

Как о сохранении пар {слово из словаря, строка, состоящая из одних и тех же букв, но в порядке возрастания (отсортированный)}

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

Answer 4

Похоже варьирования проблемы подмножество суммы: http://en.wikipedia.org/wiki/Subset_sum_problem

Может быть, некоторые из описанных алгоритмов поможет вам.

Answer 5

На этом сайте было множество работ и вопросов по Scrabble.

Есть много доступных стратегий.

Представление вашего словаря неадекватно, есть много умных методов.Например, проверьте, что такое Trie в википедии.

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

{'as', 'ape', 'gum'} 

Trie: 

void -a-> (n) -p-> (n) -e-> (y) 
       -s-> (y) 
    -g-> (n) -u-> (n) -m-> (y) 

Где 'n' означает, что он не образует слово, а y означает, что он это делает.

Теперь вам просто нужно пройти Trie, имея в виду, какие буквы доступны.

Скажите, что у вас есть { «а», «р», «г», «т», «и»}:

1. I have a 'a' (but 'a' is not a word) 
2. I have a 'p' (but 'ap' is not a word) 
3. I don't have any 'e' so I can't go further, let's backtrack 
4. I don't have any 's' so... 
5. I have a 'g', but it's not a word 
6. I have a 'u', but 'gu' is not a word 
7. I have a 'm' and 'gum' is a word, I store it somewhere, I can't go further 

Дело в том, чтобы поддерживать набор доступных букв, когда вы берете ветвь -a->, вы удаляете «a» из этого набора, затем, когда вы берете -a-> в обратном направлении (при обратном отслеживании), вы добавляете его обратно в набор.

• Эта структура является гораздо более эффективным пространство, это фактически модели конечного автомата, который распознает язык словаря вместо того, чтобы слепо экономии все слова
• Среда должна быть намного быстрее, а, так как вы никогда не будете углубиться в древовидной структуре (у вас есть только 7 букв, доступных)
• это, конечно, не то, что я делаю, так как он не принимает плату во внимание: р

«» буквы означает, что вы можете возьмите любую из доступных ветвей. Вам не нужно использовать пробел, если у вас есть требуемая буква.

Answer 6

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

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

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

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

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

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

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

редактировать

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