В принципе, то, что я ищу, это какой-то класс или метод для реализации словаря в PHP. Например, если я строю слово unscrambler – скажем, я использовал буквы «a, e, l, p, p». Количество возможностей для размещения огромно – как я могу отображать только те, которые являются фактическими словами (яблоко, бледность и т. Д.)?
Благодаря!
Классические проблемы поиска слов могут быть эффективно решены с помощью Trie .
Я бы предложил найти список слов, скажем, из WordNet , сохранить его в Trie, а затем быстро просмотреть возможные слова.
Решение будет иметь вид:
попробуйте перестановки i = 1..N
а. перестановка подстановки я использую trie
б. если есть положительный результат, сохраните это для отображения
с. итерация (i ++)
повторите с 3.
редактировать:
Обратите внимание на то, что для любого символа слова N длины может быть N! требуемый поиск (для 7 символов, которые будут 5040). Вы должны подумать о том, чтобы сделать некоторые оптимизации для алгоритма поиска trie. Например, вы получаете значительную эффективность, выбирая недопустимые подстроки раньше и не повторяя концевых перестановок.
например, с учетом слова яблоко, если у вас была перестановка, в которой вы выбрали «ppl» в качестве первых трех символов, слово не будет найдено. Итак, независимо от того, как вы переставляете a и e в конце, вы не можете построить слово. Раннее завершение перестановок может быть важно для эффективности вашего алгоритма.
Ах, а другой ответ:
Если вы просто хотите получить все реальные слова – тогда найдите большой словарь. затем сохраните его в виде:
слово | гашиш
где слово – это само слово, а хэш сортируется в алфавитном порядке буквами:
для хеша яблока будет: aelpp или aelp2
то для заданных букв пересекаются все комбинации, используя один и тот же алгоритм для хэширования и поиска по этой таблице.
вы также можете рассмотреть pspell
http://php.net/manual/en/book.pspell.php
$ps = pspell_new("en"); foreach(array('alppe', 'plape', 'apple') as $word) if(pspell_check($ps, $word)) echo $word; Сохраните список слов в файле или базе данных, а затем попробуйте все комбинации. Вы также можете рассмотреть вероятное положение гласных против согласных, чтобы потенциально ускорить его. Вместо того, чтобы создавать собственный список слов, вы можете использовать что-то вроде WordNet .
Мне действительно нравится решение zerkms лучше, но вот еще один
создать 2 таблицы
words ----- word_id (primary key) word letter_index ----- letter (idx) word_id (idx)
Когда вы добавляете слово в таблицу слов, вы должны добавить запись в letter_index для каждой уникальной буквы. У letter_index есть первичный ключ, основанный как на букве, так и на word_id.
Чтобы найти слова, состоящие из группы букв, вы создаете запрос:
SELECT word FROM words w // for each letter in the search INNER JOIN letter_index i ON ( w.word_id = i.word_id AND i.letter = letter_1 ) INNER JOIN letter_index i ON ( w.word_id = i.word_id AND i.letter = letter_2 ) INNER JOIN letter_index i ON ( w.word_id = i.word_id AND i.letter = letter_3 ) ... INNER JOIN letter_index i ON ( w.word_id = i.word_id AND i.letter = letter_n )
или вы можете использовать developer.dictionary.com api и просто выполнить поиск слов для проверки. также может выполнять проверки орфографии.