Converting from (telephone) number to short English phrase

Question

One way to memorize telephone numbers is to convert the number into a simple phrase in natural language (e.g., English) so that when dialing on a keypad one merely types out that word or phrase. Here are the conversions, taken from a standard telephone keypad:

subs1 = {2 -> {"a", "b", "c"}, 
         3 -> {"d", "e", "f"}, 
         4 -> {"g", "h", "i"}, 
         5 -> {"j", "k", "l"}, 
         6 -> {"m", "n", "o"}, 
         7 -> {"p", "q", "r", "s"}, 
         8 -> {"t", "u", "v"}, 
         9 -> {"w", "x", "y", "z"}};

(We'll return to the issue of 0 and 1.)

Thus the (seven-digit) telephone number 3987228 would be converted into "extract", which the user merely types into the phone, guided by the letters on the keypad. (Note that, of course, a given number might have several valid corresponding words: 228 could be converted to "act," "bat" or "cat".)

Here's simple code that finds (single) valid English words corresponding to a number (here 228):

Select[StringJoin /@ Tuples[IntegerDigits[228] /. subs1], DictionaryWordQ]

(* {"act", "bat", "cat"} *)

Likewise:

Select[StringJoin /@ Tuples[IntegerDigits[5865] /. subs], DictionaryWordQ]

(* {"junk"} *)

The overall problem gets a bit trickier for two reasons. First, one must deal with the digits 0 and 1, which do not have corresponding letters on a keypad. Second, a full 10-digit phone number rarely has a single corresponding word. So one needs to modify the above code to search for sets or phrases of valid English words (of any length) commensurate with the length of the number. (Semantic meaning of the phrase is irrelevant.) Moreover, there are a few heuristics, such as 0 can be read as "oh", 1 can be read as "one", etc.

Thus the phone number 2427793647 could be rendered as "2 happy dogs" (or, given the below substitutions, "two happy dogs" and the user knows to press $2$ rather than spell out "t w o").

Here is an expanded set of substitutions that capture some of these ideas.

subs = {0 -> {"o"}, 
        1 -> {"i", "one"}, 
        2 -> {"a", "b", "c", "two", "too"}, 
        3 -> {"d", "e", "f"}, 
        4 -> {"g", "h", "i", "for"}, 
        5 -> {"j", "k", "l"}, 
        6 -> {"m", "n", "o"}, 
        7 -> {"p", "q", "r", "s"}, 
        8 -> {"t", "u", "v"}, 
        9 -> {"w", "x", "y", "z"}};

What modification of the above code would take an arbitrary 10-digit telephone and generate a phrase in English (of any number of word/components) that could be used to memorize this number?

Surely one will want to use code to detect various splits of strings. For instance:

testphrases = {"catdog", "longit", "hotbag"};

Select[testphrases, AllTrue[StringPartition[#, 3], DictionaryWordQ] &]

(* {"catdog", "hotbag"} *)

This tests for just two valid words generated by splitting the source string after the third character. We need to check all splitting positions, and more simultaneous splitting position (giving three or four or more components).

Answer 1

10 digit is difficult...

here is a code that works with 10-digit numbers
(of course there are many limitations)
It only finds words with 1,2,3,4, or 5 letters and in a particular order, but it is fast.
The number-letter associations are based on frequency of letters in english texts (but you can change it and make your own)
Try it by placing a 10-digit number in the beginning

TenDigitNumber = 7599039547
num = IntegerDigits@TenDigitNumber;
subs = {0 -> {"u", "k"}, 1 -> {"d", "v"}, 2 -> {"r", "p", "x"}, 
3 -> {"i", "m", "z"}, 4 -> {"o", "h", "j"}, 5 -> {"t", "g", "q"}, 
6 -> {"n", "b"}, 7 -> {"s", "f"}, 8 -> {"l", "y", "e"}, 
9 -> {"a", "c", "w"}};
"" <> # & /@ Tuples[Select[Tuples[IntegerDigits[#] /. subs], (r = #;
   Length@Flatten[Select[Select[Join[p=Subsets@(def = 
             Flatten[Subsequences[r, {#}] & /@ Range@Length@r, 1];
  Do[def=DeleteCases[def,{(Delete[Alphabet[],{{1},{9}}])[[i]]}],{i,24}]; def), 
Reverse/@p],Flatten@#==r&],And @@ (DictionaryWordQ /@ StringJoin /@ #) &], 2] > 
    0) &] & /@ FromDigits /@ Partition[num, 5]]  

{stackiatof,stackiathf,stackiagos,stackictof,stackicthf,stackicgof,stackicghf,stackiwtof,stackiwthf,stackmatof,stackmaths,stackmathf,stackmagos,stackmagof,stackmaghf}

another example

TenDigitNumber = 3896164467     

{ilandnoons,ilandnoobs,ilandboons,ilandboobs,ilandboobf,mlandnoons,mlandnoobs,mlandboons,mlandboobs,mlandboobf,myandnoons,myandnoobs,myandboons,myandboobs,myandboobf,meandnoons,meandnoobs,meandboons,meandboobs,meandboobf}