Класс словаря PHP? или альтернатива?
В основном то, что я ищу, является некоторым классом или методом для реализации словаря в PHP. Например, если я создавал нескремблер слова - позволяет, говорят, что я использовал буквы 'a, e, l, p, p'. Количество возможностей для расположения огромно - как я только отображаю тех, которые являются фактическими словами (яблоко, бледное и т.д.)?
Спасибо!
5 ответов
Классические задачи поиска слов могут быть эффективно решены с использованием Trie .
Я бы посоветовал найти список слов, скажем, из WordNet , сохранить его в Trie, а затем выполнить быстрый поиск возможных слов.
Решение будет иметь следующий вид:
- загрузить список слов
- сохранить список слов в дереве
- принять ввод для слова для расшифровки
попробовать перестановки i = 1..N
а. поиск перестановки i с использованием дерева
b. если есть положительный результат, сохраните его для отображения
c. iterate (i ++)
repeat from 3.
edit:
Замечание: для любого символьного слова длиной N может быть N! требуемый поиск (для 7 символов это будет 5040). Вам следует подумать об оптимизации алгоритма поиска в дереве. Например, вы получаете существенную эффективность, исключая недопустимые подстроки на раннем этапе и не повторяя перестановки концов.
например. учитывая слово «яблоко», если у вас была перестановка, в которой вы выбрали «ppl» в качестве первых трех символов, слово не будет найдено. Итак, как бы вы ни переставляли a и e в конце, вы не можете составить слово. Раннее прекращение перестановок может быть важным для эффективности вашего алгоритма.
А, и еще один ответ:
Если вы просто хотите получить все настоящие слова - найдите любой большой словарь. затем сохраните его в виде:
слово | hash
, где слово - это само слово, а хеш отсортирован по алфавиту:
для яблока хеш будет: 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 имеет первичный ключ, основанный как на letter, так и на 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 )