Marcel Proust and Markov decipher security service’s T9 texts

Question

As if this challenge could be any more Pythonesque in spirit... No prior knowledge of Markov chains or encryption techniques is required.

You are a spy who needs to obtain some crucial information from the British security service M1S. The agents of M1S are well aware that their Wi-Fi signals can be intercepted, their Android/iOS security vulnerabilities exploited etc., so all of them are using Nokia 3310’s to transmit text information which is typed using the T9 auto-completion.

You had previously hacked the phones to be delivered to the intelligence agency and had installed keyloggers under their glorious plastic keyboards, so now you receive sequences of numbers corresponding to the letters they typed, so “the eagle has left the nest alert the agents” becomes

84303245304270533808430637802537808430243687

But wait! Some T9 sequences are ambiguous (“6263” could be “name”, “mane” or “oboe”; the more obscure, the more suspicious it gets!), so what do you do? You know that the only entrance examination M1S uses is summarising Marcel Proust’s masterpiece “Remembrance of Things Past” in 15 seconds, so you want to pick the word that comes next after the previous one according to its frequency distribution in the entire chef-d’œuvre of Proust!

Can you crack the code and obtain what could be the original message?

The principle of T9

The T9 auto-completion mechanism can be described as follows. It maps alphabetic characters to numbers as shown on the picture above.

abc     -> 2
def     -> 3
ghi     -> 4
jkl     -> 5
mno     -> 6
pqrs    -> 7
tuv     -> 8
wxyz    -> 9
<space> -> 0
<other> -> <is deleted>

The T9 decryptor receives a sequence of digits and tries to guess the word that could be typed with those keypresses. It might use a standard frequency table, but we are going one step further and predicting the next word using a Markov chain!

Learning sample

The corpus is this heavily stripped version of Proust’s “Remembrance of Things Past” (s/-/ /g, s/['’]s //g and s/[^a-zA-Z ]//g — begone confusing possessive 's!) originally published on the University of Adelaide website (the text of this work is in the Public Domain in Australia).

The whole text must be analysed as one string, as one long sentence, as one long vector of words (whichever is more convenient for your language), stripped of linebreaks, and split into words at spaces. (I do not supply a single-paragraph file because such might be frowned upon by github tools.)

How do I read the whole text as one string / sentence? An example in R:

p_raw  <- read.table("proust.txt", sep="\t") # Because there are no tabs
p_vec  <- as.character(p_raw$V1)       # Conversion to character vector
p_str  <- paste(p_vec, collapse=" ")   # One long string with spaces
p_spl  <- strsplit(p_str, split=" ")[[1]] # Vector of 1360883 words
proust <- p_spl[p_spl!=""]           # Remove empty entries — 1360797

Task

Given a sequence of digits as a number, return a possible text string that could be typed using the corresponding T9 keys using a probabilty chain to predict the next word X based on this training text treated as one long sentence.

If X is the first T9-word of the text and there are multiple guesses, pick one at random, otherwise pick the only one possible.

For all subsequent T9-words X(i) preceded by a word already deciphered w(i-1):

1. If a T9-word X can be converted into a normal word x in one unique way, do it.
2. If there are multiple conversion options available for X, say x1, x2, ..., look up the preceding guessed word w.
   • If w is never followed by anything that maps to X in the original work of Proust, pick any of the possible x1, x2, ... at random.
   • If w X always corresponds to w x1 in the original and there are no concurrent xi’s that could be mapped into X, pick x1.
   • If w X can be converted to w x1, w x2, ... that can be found in the corpus, then count all possible xi’s that follow w and map to X in the corpus and pick xi with probability xi/(x1 + x2 + ...).

Example 2a. If the message is 76630489, where 489 could be guy or ivy (they occur in the corpus at least once), 7663 can be deciphered as some (a very probable first word). If some is never followed by anything that maps to 489 in the corpus, then pick guy or ivy at random with probability 0.5.

Example 2b. If the message is 766302277437, where 2277437 could be barrier or carrier, 7663 can be deciphered as some. If Proust always used some carrier and never some barrier, then pick some carrier.

Example 2c. Suppose that you want to decipher the sequence 536307663. 5363 was predicted as lend. 7663 could be any of these: pond, roof and some. You count the occurrences of the word following lend in the sample corpus. Suppose you get something like this (just to illustrate):

        T9  Word following lend  Occurrences
      7663  some                           7
      7663  pond                           2
      7663  roof                           1

So if 7663 is preceded by lend, there is 7/(7+2+1)=70% probability that 7663 stands for some, 20% pond and 10% roof. Your algorithm should produce lend some in 70% cases, lend pond in 20% cases etc.

You may safely assume that the agents use only a-z letters and spaces (no punctuation marks, no possessive 's, and no numbers).

You may also assume that the agents of M1S never use any words outside the scope of “Remembrance of Things Past” (which is a whopping vocabulary of 29,237 words!).

The T9 fuctionality was implemented in this challenge, so you might have a look at it.

If you need any help, probabilistic chains were gloriously tamed in this, that and the following challenges, but you do not even need to know the principle of such chains: everything is stated in the task.

Test cases

--Inputs--
20784250276960369
20784250276960369
84303245304270533808430637802537808430243687
94280343084306289072908608430262780482737
94280343084306289072908608430262780482737

--Possible outputs--
c quick brown fox
a stick crown fox
the eagle gas left the nest blest vie agents
what did the navy pay to the coast guards
what did the navy raz un the coast guards

Rules:

• Standard loopholes apply.
• You do not know the original message, all you get is a sequence of digits and the file proust.txt that you just need to load in the memory / workspace / whatever. There is no need to have anything self-contained; assume proust.txt is always accessible.
• Your algorithm must be able to produce different outputs with respective probabilities if more than one decryption option is probable according to the corpus (see Example 2c).

You need to stay as discreet as possible, so the shortest code wins!

P.S. The obvious benefit of this probabilistic algorithm is the fact that the probability you will get a true original string for an ambiguous deciphered string tends to one — just wait...

P.P.S. See also Prediction by Partial Matching.

Answer 1

R solution, non-competing illustration of what can be done

Firstly, we load the sequence of words into the memory:

p_raw  <- read.table("proust.txt", sep="\t") # Because there are no tabs
p_vec  <- as.character(p_raw$V1)       # Conversion to character vector
p_str  <- paste(p_vec, collapse=" ")   # One long string with spaces
p_spl  <- strsplit(p_str, split=" ")[[1]] # Vector of 1360883 words
proust <- p_spl[p_spl!=""]           # Remove empty entries — 1360797

Secondly, we need a function that T9-ifies any text:

t9 <- function (x) {
  x <- chartr(paste(c(letters, " "), collapse=""), "222333444555666777788899990", tolower(x))
  x <- gsub("[^0-9]", "", x, perl = TRUE) # Safety check
  x <- x[x!=""] # Also for safety because... you know...
  x
}

Then, we T9-ify Proust:

p9 <- t9(proust)

Final preparation: we split the input string at zeros using a function that we call prep):

prep <- function (x) {
  x <- chartr("0", " ", x)
  x <- strsplit(x, " ")[[1]]
  x <- x[x!=""] # Boil the empty strings for safety
  x
}

And now I propose a function that takes any input string of numbers, preps it and deciphers the words one by one:

decip <- function(x, verbose = FALSE) {
  x <- prep(x)
  l <- length(x)
  decrypted <- rep(NA, l)
  tb <- table(proust[which(p9 == x[1])])
  decrypted[1] <- sample(names(tb), 1, prob=tb/sum(tb))
  if (verbose) print(decrypted[1])
  for (i in 2:l) {
    mtchl <- p9 == x[i]
    mtch <- which(mtchl)  # Positions that matched
    pmtch <- proust[mtch] # Words that matched
    tb <- table(pmtch)    # Count occurrences that matched
    if (length(tb)==1) {  # It is either 1 or >1
      decrypted[i] <- names(tb)[1]
      if (verbose) print(paste0("i = ", i, ", case 1: unique decryption"))
      } else {  # If there are more than one ways to decipher...
      preced <- proust[mtch-1] 
      s <- sum(preced==decrypted[i-1])
      if (s==0) {
        decrypted[i] <- sample(names(tb), 1)
        if (verbose) print(paste0("i = ", i, ", case 2a: multiple decryption, collocation never used, picking at random"))
        } else {
        tb2 <- table(pmtch[preced==decrypted[i-1]])
        if (length(tb2)==1) {
          decrypted[i] <-  names(tb2)[1]
          if (verbose) print(paste0("i = ", i, ", case 2b: multiple decryption, only one collocation found, using it"))
        } else {
          decrypted[i] <- sample(names(tb2), 1, prob = tb2/sum(tb2))
          if (verbose) print(paste0("i = ", i, ", case 2c: multiple decryption, ", length(tb2), " choices"))
          }
      }
    }
    if(verbose) print(decrypted[i])
  }
  decrypted
}

And now what it is actually doing:

decip("20784250276960369", verbose=TRUE)
----
[1] "a"
[1] "i = 2, case 2c: multiple decryption, 2 choices"
[1] "quick"
[1] "i = 3, case 2a: multiple decryption, collocation never used, picking at random"
[1] "brown"
[1] "i = 4, case 1: unique decryption"
[1] "fox"
[1] "a"     "quick" "brown" "fox" 

Second example:

decip("84303245304270533808430637802537808430243687", verbose=TRUE)
----
[1] "what"
[1] "i = 2, case 2b: multiple decryption, only one collocation found, using it"
[1] "did"
[1] "i = 3, case 2b: multiple decryption, only one collocation found, using it"
[1] "the"
[1] "i = 4, case 1: unique decryption"
[1] "navy"
[1] "i = 5, case 2a: multiple decryption, collocation never used, picking at random"
[1] "raz"
[1] "i = 6, case 2a: multiple decryption, collocation never used, picking at random"
[1] "um"
[1] "i = 7, case 2a: multiple decryption, collocation never used, picking at random"
[1] "the"
[1] "i = 8, case 2b: multiple decryption, only one collocation found, using it"
[1] "coast"
[1] "i = 9, case 1: unique decryption"
[1] "guards"
[1] "what"   "did"    "the"    "navy"   "raz"    "um"     "the"    "coast"  "guards"

Please do not comment that this can be golfed. Seems that few people are interested in this challenge because of my terrible verbosity, so I posted this answer to show what a possible programme could look like. You need not upvote/downvote this answer.

Answer 2

Python 3, 316 bytes

from random import*
from collections import*
def d(s,f):
 D=defaultdict(Counter);p=q=''
 for w in open(f).read().split():D[w.translate({97+c:(c-(c>17)-(c>24))//3+50for c in range(26)})].update([w]);D[p].update([w]);p=w
 for c in s.split('0'):q=choice([*(len(D[c])>1and D[c]&D[q]or D[c]).elements()]);print(q,end=' ')