PHP dictionary class? or alternative?

Question

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

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.