Predictive Text Input

Two questions regarding predictive text input for cell phones:

1. Given a prefix as a series of digits (thus letter ambiguity), what data structure and algorithm can efficiently, in both time and space complexity, return the completion in order of likelihood? (Assuming precalculated word frequency.) Is this problem already solved by current phones? Or are the words returned in some dumb order, like alphabetical?

2. Suppose we allow the letters of a word to be input in arbitrary order, that is, any permutation. What data structures and algorithm can quickly find the possible words? The motivation for "any permutation" stems from English suffixes. The predictor cannot disambiguate two words until it sees the suffix. By allowing any permutation, the user and type some letters of the prefix, then some letters of the suffix, then the rest of the word, hopefully reaching unambiguity with fewer keystrokes.

We need not allow the complete flexibility of arbitrary permutations. Instead, we may enforce that the initial letter be typed first, then a permutation corresponding to at most two "passes". As we follow the bouncing ball over the letters as they are typed, the ball moves backwards at most once. This corresponds to exactly "type the prefix, type the suffix, then type the middle letters exactly in order."