Como se esse desafio pudesse ser mais Pythonesque em espírito ... Nenhum conhecimento prévio de cadeias de Markov ou técnicas de criptografia é necessário.

Você é um espião que precisa obter algumas informações cruciais do serviço de segurança britânico M1S. Os agentes do M1S sabem que seus sinais Wi-Fi podem ser interceptados, suas vulnerabilidades de segurança Android / iOS exploradas etc., portanto, todos eles usam o Nokia 3310 para transmitir informações de texto digitadas usando o preenchimento automático T9 .

Você já havia hackeado os telefones para serem entregues à agência de inteligência e tinha instalado keyloggers sob seus gloriosos teclados de plástico, agora agora recebe sequências de números correspondentes às letras que digitaram, para que “ a águia tenha deixado o ninho alerta os agentes ”.

84303245304270533808430637802537808430243687

Mas espere! Algumas seqüências T9 são ambíguas ("6263" pode ser "nome", "juba" ou "oboé"; quanto mais obscura, mais suspeita fica!), Então o que você faz? Você sabe que o único vestibular que o M1S usa é resumir a obra-prima de Marcel Proust, “Remembrance of Things Past”, em 15 segundos, então você quer escolher a palavra que vem depois da anterior, de acordo com sua distribuição de frequência em todo o chef-d ' œuvre de Proust!

Você pode decifrar o código e obter qual poderia ser a mensagem original?

O princípio de T9

O mecanismo de preenchimento automático T9 pode ser descrito a seguir. Ele mapeia caracteres alfabéticos para números, como mostrado na figura acima.

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

O decodificador T9 recebe uma sequência de dígitos e tenta adivinhar a palavra que pode ser digitada com essas teclas. Pode usar uma tabela de frequência padrão, mas estamos dando um passo adiante e prevendo a próxima palavra usando uma cadeia de Markov!

Amostra de aprendizagem

O corpus é esta versão muito despojado de “Remembrance of Things Past” de Proust ( s/-/ /g, s/['’]s //ge s/[^a-zA-Z ]//g- begone confundindo possessivo 's!) Originalmente publicado no website University of Adelaide (o texto deste trabalho está no domínio público na Austrália).

O texto inteiro deve ser analisado como uma sequência, como uma frase longa, como um longo vetor de palavras (o que for mais conveniente para o seu idioma), sem quebras de linha e divididas em palavras em espaços . (Eu não forneço um arquivo de parágrafo único porque isso pode ser desaprovado pelas ferramentas do github.)

Como leio o texto inteiro como uma sequência / frase? Um exemplo em 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

Tarefa

Dada uma sequência de dígitos como um número, retorne uma possível sequência de texto que possa ser digitada usando as teclas T9 correspondentes, usando uma cadeia de probabilidades para prever a próxima palavra X com base nesse texto de treinamento tratado como uma frase longa.

Se X é a primeira palavra T9 do texto e existem várias suposições, escolha uma aleatoriamente, caso contrário, escolha a única possível.

Para todas as palavras T9 subsequentes X (i) precedidas por uma palavra já decifrada w (i-1) :

1. Se uma palavra T9 X puder ser convertida em uma palavra normal x de uma maneira única, faça-o.
2. Se houver várias opções de conversão disponíveis para X , por exemplo , x1, x2, ... , procure a palavra adivinhada anterior w .
   • Se w nunca for seguido por nada que mapeie para X no trabalho original de Proust, escolha qualquer um dos possíveis x1, x2, ... aleatoriamente.
   • Se w X sempre corresponde a w x1 no original e não há xi simultâneos que possam ser mapeados em X , escolha x1 .
   • Se w X pode ser convertido em w x1 , w x2 , ... que pode ser encontrado no corpus, conte todos os xi possíveis que se seguem w e mapeie para X no corpus e escolha xi com probabilidade xi / (x1 + x2 + ...) .

Exemplo 2a Se a mensagem for 76630489, onde 489poderia estar guyou ivy(eles ocorrem no corpus pelo menos uma vez), 7663pode ser decifrada como some(uma primeira palavra muito provável). Se somenunca for seguido por algo que mapeie 489no corpus, escolha guyou ivyaleatoriamente com probabilidade 0,5.

Exemplo 2b Se a mensagem for 766302277437, onde 2277437poderia estar barrierou carrier, 7663pode ser decifrada como some. Se Proust sempre usou some carriere nunca some barrier, escolha some carrier.

Exemplo 2c. Suponha que você queira decifrar a sequência 536307663. 5363foi previsto como lend. 7663poderia ser qualquer um destes: pond, roofe some. Você conta as ocorrências da palavra a seguir lendno corpus de amostra. Suponha que você obtenha algo assim (apenas para ilustrar):

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

Portanto, se 7663for precedido por lend, existe uma 7/(7+2+1)=70%probabilidade 7663de some20% ponde 10% roof. Seu algoritmo deve produzir lend someem 70% dos casos, lend pondem 20% dos casos etc.

Você pode assumir com segurança que os agentes usam apenas letras e espaços em z (sem sinais de pontuação, possessivos 'se sem números).

Você também pode supor que os agentes do M1S nunca usem palavras fora do escopo de "Remembrance of Things Past" (que é um vocabulário imenso de 29.237 palavras!).

A funcionalidade T9 foi implementada nesse desafio , então você pode dar uma olhada.

Se você precisar de alguma ajuda, cadeias probabilísticas foram gloriosamente domado no presente , que e os seguintes desafios, mas você não precisa mesmo de saber o princípio dessas cadeias: tudo é afirmado na tarefa.

Casos de teste

--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

Regras:

• Aplicam-se brechas padrão .
• Você não conhece a mensagem original, tudo o que obtém é uma sequência de dígitos e o arquivo proust.txt que você só precisa carregar na memória / área de trabalho / qualquer que seja. Não há necessidade de ter nada independente; suponha que proust.txtesteja sempre acessível.
• Seu algoritmo deve ser capaz de produzir saídas diferentes com as respectivas probabilidades, se mais de uma opção de descriptografia for provável, de acordo com o corpus (consulte o Exemplo 2c).

Você precisa permanecer o mais discreto possível, para que o código mais curto ganhe!

PS O benefício óbvio desse algoritmo probabilístico é o fato de que a probabilidade de você obter uma string original verdadeira para uma string decifrada ambígua tende a uma - basta esperar ...

PPS Consulte também Previsão por correspondência parcial .

Solução R, ilustração não concorrente do que pode ser feito

Primeiro, carregamos a sequência de palavras na memória:

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

Em segundo lugar, precisamos de uma função que T9-ifies qualquer texto:

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
}

Então, nós T9-ify Proust:

p9 <- t9(proust)

Preparação final: dividimos a string de entrada em zeros usando uma função que chamamos prep):

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

E agora proponho uma função que pega qualquer sequência de números de entrada prepe decifra as palavras uma por uma:

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
}

E agora o que está realmente fazendo:

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" 

Segundo exemplo:

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"

Por favor, não comente que isso pode ser jogado no golfe. Parece que poucas pessoas estão interessadas nesse desafio por causa da minha péssima verbosidade, por isso postei essa resposta para mostrar como seria um programa possível. Você não precisa fazer voto positivo / negativo nesta resposta.

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=' ')