Как получить правильные слова из базы данных MySQL, содержащей словарь из ввода букв пользователя?
Вы не делаете. Таблица реляционных баз данных не является подходящей структурой данных для решения этой проблемы так эффективно, как вам нужно.
Вместо этого вы строите структуру trie из словаря (или, если вы действительно любитель, вы создаете dawg - ориентированный ациклический граф слов - что-то вроде сжатого дерева.)
После того, как у вас есть trie / dawg, становится очень недорогим тестировать каждое слово в словаре для данной стойки, потому что вы можете "обрезать" целые огромные ветви словаря, которые стойка не может матч.
Давайте рассмотрим небольшой пример. Предположим, у вас есть словарь «OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS». Из этого вы строите этот файл: (Узлы со знаком $ - это те, которые отмечены как «слово может заканчиваться здесь») .
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ S$ T$ P$ O
| | | |
S$ S$ S$ P$
|
S$
а у вас стойка "OPS" - что вы делаете?
Сначала вы говорите: "Могу ли я спуститься по ветке О?" Да, ты можешь. Так что теперь проблема заключается в сопоставлении «PS» с ответвлением O. Можете ли вы пойти вниз P филиал? Да. У него есть маркер конца слова? Да, так что OP это совпадение. Теперь проблема заключается в сопоставлении буквы «S» с веткой OP. Можете ли вы пойти вниз по ветке Т? Нет. Можете ли вы пойти вниз по ветке S? Да. Теперь у вас есть пустая стойка, и вы должны сопоставить ее с веткой OPS. У него есть маркер конца слова? Да! Так что OPS тоже подходит. Теперь вернемся к корню.
Можете ли вы пойти вниз по ветви P? Да. Теперь проблема состоит в том, чтобы сопоставить ОС с веткой P. Спуститесь по ветке PO и сопоставьте S - что не получается. Возврат к корню.
И снова вы видите, как это происходит. В конце концов мы спускаемся по ветке SOP и находим конец слова в SOP, поэтому «SOP» соответствует этой стойке. Мы не спускаемся по ветке ST, потому что у нас нет T.
Мы перепробовали все возможные слова в словаре и обнаружили, что OP, OPS и SOP все совпадают. Но нам никогда не приходилось исследовать OPTS, POTS, STOP или STOPS, потому что у нас не было T.
Вы видите, как эта структура данных делает ее очень эффективной? Как только вы определили, что на стойке нет букв, составляющих начало слова, вам не нужно исследовать любые словарные слова, начинающиеся с этого начала. Если у вас есть PO, но нет T, вам не нужно исследовать POTSHERD или POTATO или POTASH или POTLATCH или POTABLE; все эти дорогие и бесплодные поиски уходят очень быстро.
Адаптировать систему для работы с «дикими» тайлами довольно просто; если у вас есть OPS ?, тогда просто запустите алгоритм поиска 26 раз, на OPSA, OPSB, OPSC ... Это должно быть достаточно быстро, чтобы сделать это 26 раз дешевле (или сделать это 26 x 26 раз, если у вас два пробела). )
Это основной алгоритм, используемый профессиональными программами Scrabble AI, хотя, конечно, им приходится иметь дело с такими вещами, как положение платы, управление стойкой и т. Д., Что несколько усложняет алгоритмы. Эта простая версия алгоритма будет достаточно быстрой, чтобы генерировать все возможные слова в стойке.
Не забывайте, что, конечно, вам нужно только вычислить trie / dawg один раз , если словарь не меняется со временем. Построение дерева из словаря может занять много времени, поэтому вы можете сделать это один раз , а затем найти способ сохранить дерево на диске в форме, пригодной для его восстановления. быстро с диска.
Вы можете оптимизировать использование памяти, создав DAWG из дерева. Обратите внимание, как много повторений, потому что в английском много слов конец одинаковы, так же как много слов начинаются одинаково. Trie делает большую работу по совместному использованию узлов в начале, но паршивая работа по их совместному использованию в конце. Например, вы можете заметить, что шаблон «S $ без детей» встречается крайне часто, и превратить дерево в:
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ | T$ P$ O
| \ | | |
\ \| / P$
\ |/ |
\ | /
\ | /
\ | /
\| /
|/
|
S$
Сохранение целой кучи узлов. И затем вы можете заметить, что два слова теперь заканчиваются на O-P $ -S $, а два слова заканчиваются на T $ -S $, так что вы можете сжать его до:
^root^
/ | \
O P S
| | / \
P$ O \ T
/ \| \ |
| | \|
| | O
| T$ |
\ | P$
\ | /
\| /
| /
|/
S$
И теперь у нас есть минимальная DAWG для этого словаря.
Дальнейшее чтение:
http://dl.acm.org/citation.cfm?id=42420
http://archive.msdn.microsoft.com/dawg1
http://www.gtoal.com/wordgames/scrabble.html