Como si este desafío pudiera ser más de espíritu Pythonesque ... No se requieren conocimientos previos de las cadenas de Markov o las técnicas de cifrado.

Usted es un espía que necesita obtener información crucial del servicio de seguridad británico M1S. Los agentes de M1S son conscientes de que sus señales de Wi-Fi pueden ser interceptadas, sus vulnerabilidades de seguridad de Android / iOS explotadas, etc., por lo que todos ellos están utilizando Nokia 3310 para transmitir información de texto que se tipea con el autocompletado T9 .

Anteriormente había pirateado los teléfonos para ser entregados a la agencia de inteligencia e instalado keyloggers bajo sus gloriosos teclados de plástico, por lo que ahora recibe secuencias de números correspondientes a las letras que escribieron, por lo que " el águila ha dejado el nido alerta a los agentes "

84303245304270533808430637802537808430243687

¡Pero espera! Algunas secuencias T9 son ambiguas ("6263" podría ser "nombre", "mane" u "oboe"; ¡cuanto más oscuro, más sospechoso se pone!), Entonces, ¿qué haces? Usted sabe que el único examen de ingreso que utiliza M1S es resumir la obra maestra de Marcel Proust "Recuerdo de las cosas pasadas" en 15 segundos, por lo que desea elegir la palabra que viene después de la anterior de acuerdo con su distribución de frecuencias en todo el chef-d ' ¡obra de Proust!

¿Puedes descifrar el código y obtener lo que podría ser el mensaje original?

El principio de T9

El mecanismo de autocompletado T9 se puede describir de la siguiente manera. Asigna caracteres alfabéticos a números como se muestra en la imagen de arriba.

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

El descifrador T9 recibe una secuencia de dígitos e intenta adivinar la palabra que podría escribirse con esas teclas. Podría usar una tabla de frecuencias estándar, pero vamos un paso más allá y predecimos la siguiente palabra usando una cadena de Markov.

Muestra de aprendizaje

El corpus es esta versión muy simplificada de “busca del tiempo perdido” de Proust ( s/-/ /g, s/['’]s //gy s/[^a-zA-Z ]//g- begone confundir posesiva 's!), Publicado originalmente en la Universidad de Adelaida sitio web (el texto de esta obra se encuentra en el dominio público en Australia).

El texto completo debe analizarse como una cadena, como una oración larga, como un vector largo de palabras (lo que sea más conveniente para su idioma), despojado de saltos de línea y dividido en palabras en espacios . (No proporciono un archivo de un solo párrafo porque las herramientas de github lo pueden mal visto).

¿Cómo leo el texto completo como una cadena / oración? Un ejemplo en 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

Tarea

Dada una secuencia de dígitos como un número, devuelve una posible cadena de texto que podría escribirse usando las teclas T9 correspondientes usando una cadena de probabilidad para predecir la siguiente palabra X basada en este texto de entrenamiento tratado como una oración larga.

Si X es la primera palabra T9 del texto y hay varias conjeturas, elija una al azar, de lo contrario, elija la única posible.

Para todas las palabras T9 posteriores X (i) precedidas por una palabra ya descifrada w (i-1) :

1. Si una palabra T9 X se puede convertir en una palabra normal x de una manera única, hágalo.
2. Si hay varias opciones de conversión disponibles para X , digamos x1, x2, ... , busque la palabra adivinada anterior w .
   • Si w nunca es seguido por algo que se asigne a X en el trabajo original de Proust, elija cualquiera de los posibles x1, x2, ... al azar.
   • Si w X siempre corresponde a w x1 en el original y no hay xi concurrentes que puedan asignarse a X , seleccione x1 .
   • Si w X se puede convertir a w x1 , w x2 , ... que se puede encontrar en el corpus, entonces cuente todas las xi posibles que siguen w y se mapean a X en el corpus y elija xi con probabilidad xi / (x1 + x2 + ...) .

Ejemplo 2a. Si el mensaje es 76630489, dónde 489podría estar guyo ivy(se producen en el corpus al menos una vez), 7663se puede descifrar como some(una primera palabra muy probable). Si somenunca le sigue algo que se mapee 489en el corpus, entonces elija guyo ivyal azar con probabilidad 0.5.

Ejemplo 2b Si el mensaje es 766302277437, dónde 2277437podría estar barriero carrier, 7663se puede descifrar como some. Si Proust utiliza siempre some carriery nunca some barrier, a continuación, elegir some carrier.

Ejemplo 2c. Suponga que desea descifrar la secuencia 536307663. 5363fue predicho como lend. 7663podría ser cualquiera de los siguientes: pond, roofy some. Cuenta las apariciones de la palabra siguiente lenden el corpus de muestra. Supongamos que obtienes algo como esto (solo para ilustrar):

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

Entonces, si 7663está precedido por lend, hay una 7/(7+2+1)=70%probabilidad 7663de some20% pondy 10% roof. Su algoritmo debe producir lend someen 70% de los casos, lend ponden 20% de los casos, etc.

Puede suponer con seguridad que los agentes usan solo letras y espacios az (sin signos de puntuación, sin posesivos 'sy sin números).

También puede suponer que los agentes de M1S nunca usan palabras fuera del alcance de "Remembrance of Things Past" (¡que es un vocabulario enorme de 29,237 palabras!).

La funcionalidad T9 se implementó en este desafío , por lo que puede echarle un vistazo.

Si necesita ayuda, las cadenas probabilísticas se domesticaron gloriosamente en este , aquel y los siguientes desafíos, pero ni siquiera necesita conocer el principio de tales cadenas: todo está establecido en la tarea.

Casos de prueba

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

Reglas:

• Se aplican lagunas estándar .
• No conoce el mensaje original, todo lo que obtiene es una secuencia de dígitos y el archivo proust.txt que solo necesita cargar en la memoria / espacio de trabajo / lo que sea. No hay necesidad de tener nada autocontenido; Asumir proust.txtes siempre accesible.
• Su algoritmo debe ser capaz de producir diferentes salidas con probabilidades respectivas si es probable que haya más de una opción de descifrado de acuerdo con el corpus (consulte el Ejemplo 2c).

Debes mantenerte lo más discreto posible, ¡para que gane el código más corto!

PD El beneficio obvio de este algoritmo probabilístico es el hecho de que la probabilidad de que obtenga una cadena original verdadera para una cadena descifrada ambigua tiende a uno: solo espere ...

PPS Véase también Predicción por coincidencia parcial .

Solución R, ilustración no competitiva de lo que se puede hacer

En primer lugar, cargamos la secuencia de palabras en la memoria:

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

En segundo lugar, necesitamos una función que T9-ifies cualquier 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
}

Entonces, nosotros T9-ify Proust:

p9 <- t9(proust)

Preparación final: dividimos la cadena de entrada en ceros usando una función que llamamos prep):

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

Y ahora propongo una función que toma cualquier cadena de entrada de números, preps y descifra las palabras una por una:

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
}

Y ahora lo que realmente está haciendo:

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 ejemplo

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 no comente que esto se puede jugar al golf. Parece que pocas personas están interesadas en este desafío debido a mi terrible verbosidad, así que publiqué esta respuesta para mostrar cómo podría ser un posible programa. No necesita votar a favor o en contra esta respuesta.

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