PHP словарь класс? или альтернатива?

Question

По сути, я ищу какой-то класс или метод для реализации словаря в PHP. Например, если я строил слово unscrambler - допустим, я использовал буквы «a, e, l, p, p». Количество возможностей для аранжировки огромно - как отобразить только те, которые являются реальными словами (яблоко, бледный и т. Д.)?

Спасибо!

Answer 1

Классически проблемы поиска слов могут быть эффективно решены с помощью Trie .

Я бы предложил найти список слов, скажем, из WordNet , сохранить его в Trie, а затем выполнить быстрый поиск возможных слов.

Решение будет иметь вид:

1. загрузить список слов
2. сохранить список слов в дереве
3. принять ввод для расшифровки слова

4. попробуйте перестановки i = 1..N

   а. перестановка поиска я использую три

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

   с. итерация (i ++)

5. повторить с 3.

редактирование:

Примечание: здесь для любого символа длины N может быть N! требуемый поиск (для 7 символов это будет 5040). Вам следует подумать о внесении некоторых оптимизаций в алгоритм поиска Trie. Например, вы получаете значительную эффективность, заблаговременно исключая недопустимые подстроки, а не повторяя конечные перестановки.

например. учитывая слово apple, если у вас была перестановка, в которой вы выбрали «ppl» в качестве первых трех символов, слово не будет найдено. Таким образом, независимо от того, как вы переставляете a и e в конце, вы не можете составить слово. Раннее завершение перестановок может быть важно для эффективности вашего алгоритма.

Answer 2

Ах, и другой ответ:

Если вы просто хотите получить все настоящие слова - найдите любой большой словарь. затем сохраните его в порядке:

слово | Хэш

где слово - это само слово, а хэш сортируется в алфавитном порядке:

для яблочного хэша будет: aelpp или aelp2

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

Answer 3

Вы также можете рассмотреть 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;

Answer 4

или вы можете использовать API-интерфейс developer.dictionary.com и просто выполнить поиск слова для проверки. также может выполнять проверку орфографии.

Answer 5

Мне действительно больше нравится решение 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 )

Answer 6

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