PHP dictionary class? or alternative?

Question

Hi. Basically, what I'm looking for is some kind of class or method to implement a dictionary in PHP. For example, if I was building a word unscrambler - lets say I used the letters 'a,e,l,p,p'. The number of possibilities for arrangement is huge - how do I only display those which are actual words (apple, pale etc )?

Thanks!

Answer 1

i prefer to solve such troubles using some kind of rdbms.

just create temporary table with one column and 5 rows (1 per each letter) and then select with multiple joins (count of joins == number of letters) without ON statement.

in this case you will get dekart multiplication which equals all combinations ;-)

Answer 2

Store a list of words in a file or a database, and then just try all the combinations. You could also consider the likely position of vowels vs consonants to potentially speed it up. Rather than making your own word list, you could use something like WordNet.

Answer 3

Ah, and the another answer:

If you just want to get all real words - then find any big dictionary. then store it in manner of:

word | hash

where word is word itself and hash is sorted alphabetically letters:

for apple hash will be: aelpp or aelp2

then for given letters traverse all combinations using the same algo for hashing and search through this table.

Answer 4

Classically word lookup problems can be efficiently solved using a Trie.

I would suggest finding a word list, say, from WordNet, store it in a Trie, and then perform fast lookups of possible words.

A solution would be of the form:

1. load the word list
2. store the word list in a trie
3. accept input for a word to unscramble

4. try permutations i=1..N

   a. lookup permutation i using the trie

   b. if there's a positive result, store this for display

   c. iterate (i++)

5. repeat from 3.

edit:

A side note here is that for any N length character word there could be N! required lookups (for 7 characters that would be 5040). You should consider making some optimizations to the trie lookup algorithm. For instance, you gain substantial efficiency by ruling out invalid substrings early, and not repeating end permutations.

e.g. given the word apple, if you had the permutation where you selected "ppl" as the first three characters, no word will be found. So, no matter how you permute the a and the e at the end you cannot construct a word. Early termination of permutations may be important to your algorithm's efficiency.

Answer 5

you can also consider 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 6

I actually like zerkms's solution better but here's another one

create 2 tables

words
-----
word_id (primary key)
word


letter_index
-----
letter (idx)
word_id (idx)

When you add a word to the words table you have to add an entry to the letter_index for each unique letter. letter_index has a primary key based on both the letter and the word_id.
To find words comprising of a group of letters you create a query something like:

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 )