Hai un'idea generale corretta. Ma voglio sottolineare che la lunghezza del messaggio non deve essere un multiplo esatto del conteggio delle righe, ad es.
A B C reordering A C B
D E ---------> D E
potrebbe diventare AD C BE . Contabilità per questo è piuttosto difficile, in quanto non sappiamo dove sono le colonne più brevi. Supponendo che stiamo partizionando in tre colonne, potremmo ottenere A DC BE , AD C BE o AD CB E . La situazione peggiora per un numero maggiore di colonne. Una soluzione potrebbe essere decifrare inizialmente tutto tranne l'ultima riga, in modo da conoscere l'ordine delle colonne. I caratteri incerti possono quindi essere distribuiti sulle colonne principali.
Poiché le colonne possono essere riordinate, abbiamo bisogno di un modo per determinare l'ordine originale. Sfortunatamente, ci sono r ! combinazioni diverse. Questo è banale per un piccolo numero di colonne, in cui la forzatura bruta di tutte le combinazioni è una strategia praticabile. Altrimenti, dobbiamo utilizzare un euristico che ci guida attraverso tutte le combinazioni.
Un euristico adatto considera le transizioni di lettere. Possiamo costruire una tabella simile da dati di esempio sufficientemente grandi. Data una lettera a e una lettera b , possiamo quindi stimare la probabilità che a sia seguito da b in un testo. Tra due colonne, usualmente abbiamo più transizioni, quindi possiamo moltiplicare la probabilità di ogni coppia. Fare questo per tutte le colonne produce un indice che possiamo ordinare, ed esaminare prima la transizione della colonna con la probabilità più alta. Nota: si tratta di un abuso di statistiche piuttosto grossolano, ma funziona in questo semplice caso in cui le probabilità vengono utilizzate solo per decidere una transizione.
Ad esempio, supponiamo di avere il testo cifrato eleatytoaryf_s_do_hwre_l e supponiamo di avere quattro colonne. Questo ci dà:
1234
et_h
losw
ea_r
arde
tyo_
yf_l
È irrilevante quale colonna selezioniamo per prima, quindi prenderò # 2. Ora abbiamo probabilità di possibili 2 colonne (dati di frequenza ottenuti da un file di dizionario inglese):
21 23 24
te t_ th
ol os ow
ae a_ ar
ra rd re
yt yo y_
fy f_ fl
| | | raw normalized
| | '-1.6713389025628 e-06 = 0.9985
| '----1.10726823199948e-09 = 0.0007
'-------1.39822078585934e-09 = 0.0008
Guardando l'esponente, possiamo vedere che la transizione 2 → 4 è la più probabile. Ripetiamo questo per la prossima transizione:
241 243
the th_
owl ows
are ar_
rea red
y_t y_o
fly fl_
| | raw normalized
| '-1.9732647912631e-08 = 0.1122
'-----1.5611637229838e-07 = 0.8878
Questo dichiara la transizione 4 → 1 più probabile. Ora rimane solo una colonna, quindi otteniamo le transizioni 2 → 4 → 1 → 3, che produce il testo chiaro the_owls_are_ready_to_fly . Sembra che sia inglese, quindi possiamo fermarci qui. Se così non fosse, faremo backtrack all'ultimo punto decisionale, che era il 4 →? transizione. Se la scelta di 4 → 3 avesse prodotto anche parole senza senso, tornando indietro al punto di decisione precedente dovremmo esaminare 2 → 1, e quindi decidere 1 →?.
Questa euristica potrebbe essere ulteriormente ottimizzata. Il problema può essere espresso nella teoria dei grafi ordinando pigramente tutti i percorsi attraverso tutti i vertici per il loro peso totale in un grafico ponderato diretto dove i vertici sono colonne, ei bordi sono probabilità di transizione, e gli spigoli combinano moltiplicativi. Per calcolare la probabilità di transizione, dobbiamo normalizzare le probabilità in modo che i pesi di tutti i bordi in uscita si sommino a 1.