Comme si ce défi pouvait être plus pythonien dans l'esprit ... Aucune connaissance préalable des chaînes de Markov ou des techniques de chiffrement n'est requise.

Vous êtes un espion qui a besoin d'obtenir des informations cruciales du service de sécurité britannique M1S. Les agents de M1S sont bien conscients que leurs signaux Wi-Fi peuvent être interceptés, leurs vulnérabilités de sécurité Android / iOS exploitées, etc., tous utilisent donc le Nokia 3310 pour transmettre des informations textuelles tapées à l'aide de l' auto-complétion T9 .

Vous aviez précédemment piraté les téléphones à livrer à l'agence de renseignement et installé des enregistreurs de frappe sous leurs glorieux claviers en plastique, alors maintenant vous recevez des séquences de chiffres correspondant aux lettres qu'ils ont tapées, alors « l'aigle a quitté le nid pour alerter les agents » devient

84303245304270533808430637802537808430243687

Mais attendez! Certaines séquences T9 sont ambiguës ("6263" pourrait être "nom", "crinière" ou "hautbois"; plus il est obscur, plus il devient suspect!), Alors que faites-vous? Vous savez que le seul examen d'entrée utilisé par M1S résume le chef-d'œuvre de Marcel Proust «Remembrance of Things Past» en 15 secondes, alors vous voulez choisir le mot qui vient après le précédent en fonction de sa distribution de fréquence dans l'ensemble du chef-d ' œuvre de Proust!

Pouvez-vous déchiffrer le code et obtenir ce qui pourrait être le message d'origine?

Le principe du T9

Le mécanisme d'auto-complétion T9 peut être décrit comme suit. Il mappe les caractères alphabétiques aux nombres comme indiqué sur l'image ci-dessus.

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

Le décrypteur T9 reçoit une séquence de chiffres et essaie de deviner le mot qui pourrait être tapé avec ces touches. Il pourrait utiliser une table de fréquences standard, mais nous allons plus loin et prédisons le prochain mot en utilisant une chaîne de Markov!

Échantillon d'apprentissage

Le corpus est cette version très dépouillée du «Souvenir des choses passées» de Proust ( s/-/ /g, s/['’]s //get s/[^a-zA-Z ]//g- commencez à être possessif 's!) Publié à l'origine sur le site Web de l' Université d'Adélaïde (le texte de cet ouvrage est dans le domaine public en Australie).

Le texte entier doit être analysé comme une chaîne, comme une longue phrase, comme un long vecteur de mots (selon ce qui convient le mieux à votre langue), dépourvu de sauts de ligne et divisé en mots aux espaces . (Je ne fournis pas de fichier contenant un seul paragraphe car il pourrait être mal vu par les outils github.)

Comment lire le texte entier en une seule chaîne / phrase? Un exemple 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

Tâche

Étant donné une séquence de chiffres sous forme de nombre, renvoyez une chaîne de texte possible qui pourrait être saisie à l'aide des touches T9 correspondantes à l'aide d'une chaîne de probabilité pour prédire le mot suivant X en fonction de ce texte d'apprentissage traité comme une longue phrase.

Si X est le premier mot T9 du texte et qu'il y a plusieurs suppositions, choisissez-en un au hasard, sinon choisissez le seul possible.

Pour tous les mots T9 suivants X (i) précédés d'un mot déjà déchiffré w (i-1) :

1. Si un mot T9 X peut être converti en un mot normal x d'une manière unique, faites-le.
2. Si plusieurs options de conversion sont disponibles pour X , disons x1, x2, ... , recherchez le mot deviné précédent w .
   • Si w n'est jamais suivi par quelque chose qui correspond à X dans le travail original de Proust, choisissez l'un des x1, x2, ... possibles au hasard.
   • Si w X correspond toujours à w x1 dans l'original et qu'il n'y a pas de xi simultanés pouvant être mappés dans X , choisissez x1 .
   • Si w X peut être converti en w x1 , w x2 , ... qui peuvent être trouvés dans le corpus, alors comptez tous les xi possibles qui suivent w et mappez à X dans le corpus et choisissez xi avec la probabilité xi / (x1 + x2 + ...) .

Exemple 2a. Si le message est 76630489, où 489pourrait être guyou ivy(ils se produisent dans le corpus au moins une fois), 7663peut être déchiffré comme some(un premier mot très probable). Si somerien n'est suivi par quoi que ce soit 489dans le corpus, choisissez guyou ivyau hasard avec une probabilité de 0,5.

Exemple 2b. Si le message est 766302277437, où 2277437pourrait être barrierou carrier, 7663peut être déchiffré comme some. Si Proust a toujours utilisé some carrieret jamais some barrier, alors choisissez some carrier.

Exemple 2c. Supposons que vous vouliez déchiffrer la séquence 536307663. 5363a été prédit comme lend. 7663pourrait être l' un de ces: pond, roofet some. Vous comptez les occurrences du mot suivant lenddans l'exemple de corpus. Supposons que vous obteniez quelque chose comme ça (juste pour illustrer):

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

Donc, si 7663est précédé de lend, il y a une 7/(7+2+1)=70%probabilité qui 7663représente some20% pondet 10% roof. Votre algorithme devrait produire lend somedans 70% des cas, lend ponddans 20% des cas, etc.

Vous pouvez supposer en toute sécurité que les agents n'utilisent que des lettres et des espaces az (pas de signes de ponctuation, pas de possessivité 'set pas de chiffres).

Vous pouvez également supposer que les agents de M1S n'utilisent jamais de mots en dehors de la portée de «Remembrance of Things Past» (qui est un vocabulaire énorme de 29 237 mots!).

La fonctionnalité T9 a été implémentée dans ce défi , vous pouvez donc y jeter un œil.

Si vous avez besoin d'aide, les chaînes probabilistes ont été glorieusement apprivoisées en cela , cela et les défis suivants , mais vous n'avez même pas besoin de connaître le principe de telles chaînes: tout est énoncé dans la tâche.

Cas de test

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

Règles:

• Des échappatoires standard s'appliquent.
• Vous ne connaissez pas le message d'origine, tout ce que vous obtenez est une séquence de chiffres et le fichier proust.txt que vous avez juste besoin de charger dans la mémoire / l'espace de travail / quoi que ce soit. Il n'est pas nécessaire d'avoir quoi que ce soit autonome; supposer proust.txtest toujours accessible.
• Votre algorithme doit être capable de produire différentes sorties avec des probabilités respectives si plus d'une option de déchiffrement est probable selon le corpus (voir exemple 2c).

Vous devez rester aussi discret que possible, donc le code le plus court l'emporte!

PS L'avantage évident de cet algorithme probabiliste est le fait que la probabilité d'obtenir une vraie chaîne d'origine pour une chaîne déchiffrée ambiguë tend à un - attendez ...

PPS Voir aussi Prediction by Partial Matching .

Solution R, illustration non concurrente de ce qui peut être fait

Tout d'abord, nous chargeons la séquence de mots dans la mémoire:

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

Deuxièmement, nous avons besoin d'une fonction qui T9-ifies tout texte:

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
}

Ensuite, nous T9-ify Proust:

p9 <- t9(proust)

Préparation finale: nous séparons la chaîne d'entrée à zéro en utilisant une fonction que nous appelons prep):

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

Et maintenant, je propose une fonction qui prend n'importe quelle chaîne de chiffres entrée, prepet décrypte les mots un par un:

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
}

Et maintenant ce qu'il fait réellement:

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" 

Deuxième exemple:

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"

Veuillez ne pas commenter que cela peut être joué au golf. Il semble que peu de gens soient intéressés par ce défi en raison de ma terrible verbosité, j'ai donc posté cette réponse pour montrer à quoi pourrait ressembler un programme possible. Vous n'avez pas besoin de voter pour ou contre cette réponse.

Python 3, 316 octets

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