Archive

Archive for the ‘Monte Carlo’ Category

Anagram Analysis

February 26, 2010 5 comments

Several people, notably Robert Teague and Philip Neal, have theorized that the cipher is based on anagrams. The idea is that to decipher the VMs text, you first convert the VMs symbols to alphabet letters, and then you find an anagram of those letters that makes a valid plaintext word.

Variations on this theme are that e.g. some of the plaintext letters in the target word are allowed to be missing and can be inferred from “context”, and/or that the VMs words are anagrams of the plaintext words that have letters arranged alphabetically.

For this analysis, we look at Folio68r3 in particular:

The labels on the stars are, from the ten o’clock pie slice going anti-clockwise, in the Voyn 101 encoding:

<68r3.pieslice_1>61oe7a9.8oay9.oae1coe=

<68r3.pieslice_2>oh1o89.8ayaee.ok98*.oK98=

<68r3.pieslice_3>ohoe19.1G9.179,9h9=

<68r3.pieslice_4>ohos.okoy9=

Anagrams: Combinations/Permutations

If you make the reasonable assumption that all the labels on the star shapes in f68r3 are star names, and you assume a target language, then this puts severe constraints on the cipher, since there are only so many star names and only so many cipher schemes that can be consistent amongst all the stars.

For each of the 12 star labels on f68r3 (61oe7a9 8oay9 oae1coe oh1o89 8ayaee ok98* oK98 ohoe19 1G9 179,9h9 ohos okoy9 ) there are a number of possible anagrams of the symbols (anagrams):

Label size 3 6 anagrams
Label size 4 24 anagrams
Label size 5 120 anagrams
Label size 6 720 anagrams
Label size 7 5040 anagrams

It appears like there is a lot of freedom: the first label “61oe7a9” can be rearranged 5040 different ways – and you can pick any letter for any of the 7 symbols! However, when you start actually choosing the mapping between symbols and alphabet characters, and require that at least one of  the anagrams for each deciphered label appears in a dictionary of star names, you rapidly eliminate many of the possibilities.

This is still true even if you allow that a single symbol in the label can map to two alphabet characters – the problem appears to be still over-constrained

For example, say you pick a mapping for the first label:

S: 6  1  o  e  7  a  9
R: d  r  e  ba an a  l
61oe7a9 -> drebaanal -> aldebaran

then you want to apply this to the next label “8oay9”. You already have the cipher for symbols o, a and 9 … they translate to e, a and l respectively – you know that the star name must contain e, a and l. You know that the star name must be between 5 and 7 characters long, and you just need to pick suitable letters for 8 and y.

Consulting a list of ~300 star names you find the following possibilities.

Alkes, Algedi, Alheka, Alhena, Elnath, Lesath, Alcyone, Algebar, Algorel, Ascella, Capella, Eltanin and Sheliak

(Since this Don Latham sent me a link to his list of star names at www.sixmilesystems.com/voynich , which I have simplified and removed any duplicates and non-alphabetic symbols from, and put here: http://pcbunn.cacr.caltech.edu/Voynich/StarNamesLatham.txt )

Choosing Alcyone (for reasons which will be obvious to some), you now have an extended mapping that includes 8 and y:

S: 6  1  o  e  7  a  9  8  y
R: d  r  e  ba an a  l  cy on
61oe7a9 -> drebaanal -> aldebaran
8oay9 -> cyeaonl -> alcyone

So far so good. Now we come to the third label: “oae1coe” which we can decipher all but one symbol of, to: “eabar?eba”.

Unhappily there are no 9 or 10 letter stars in the dictionary that can match this letter assortment. and so this eliminates our initial choice of mapping that gave us “aldebaran” for the first word, and “alcyone” for the second, because it cannot produce a dictionary word for the third label. Back to square one.

You can keep on doing this: selecting mappings, trying them out on the first two or three labels, and finding that there is no fit to the dictionary.

Although at first sight there seems to be a lot of flexibility from the use of anagrams in the cipher, in practice if an anagram of each and all the deciphered words is required to appear
in a dictionary, then that severely constrains the solution space.

Allowing Missing Characters

Looking again at the 12 star labels on f68r3:

61oe7a9 8oay9 oae1coe oh1o89 8ayaee ok98* oK98 ohoe19 1G9 179,9h9 ohos okoy9

There are 16 different VMs symbols used:

 o 9 1 e a 8 h y 7 k 6 c * K G s

Let’s assume that each of the VMs symbols maps to a single plaintext alphabet letter. Which 16 of the 26 letters in the alphabet will we choose to map? Let’s look at our list of star names and find the 16 most used alphabet letters:

 a i r e l s h n u t b k m d o c

(shown in order of frequency). How many different ways can we map the 16 VMs symbols to these 16 letters? That is:

Factorial 16 = 16! = 20,922,789,888,000

which is about 21 trillion (give or take), and is quite a lot. To explore this huge space of possibilities, we can use a Monte Carlo method. Basically we write a program to shuffle the 16 alphabet letters, look to see how that mapping works, then shuffle again, and so on. As we go, we keep track of the best mapping found so far.

Suppose we have the following mapping (cipher):

S: o 9 1 e a 8 h y 7 k 6 c * K G s
R: a e n c i l h r o s u d k t b m

Let’s go through the f68r3 star labels and convert them to plaintext using the cipher. After we convert them, let’s look the plaintext characters up in our list of star names using a “fuzzy match”. Here are the results:

61oe7a9 -> unacoie -> ?
8oay9 -> laire -> albireo (bo)
oae1coe -> aicndac -> ?
oh1o89 -> ahnale -> alhena ()
8ayaee -> liricc -> ?
ok98* -> aselk -> sheliak (hi)
oK98 -> atel -> elnath (nh)
ohoe19 -> ahacne -> achernar (rr)
1G9 -> nbe -> deneb (de)
1799h9 -> noeehe -> ?
ohos -> aham -> hamal (l)
okoy9 -> asare -> antares (nt)

Looking at the second label as an example, this is converted to plaintext characters “laire”. The fuzzy match looks up “laire” in the star names list, and finds a match with the star called “albireo”.

Fuzzy Match Rules

There is a match between the deciphered plaintext word and a dictionary word if

  1. All the letters in the plaintext word appear in the dictionary word
  2. There are no more than N missing letters in the plaintext word

In the example shown above, N is 2, so “laire” fuzzy matches “albireo”, with letters “bo” missing (shown in brackets)

Solutions

In the above example, 8 of the 12 VMs star labels have been matched to valid star names. The application continues exploring the 16! possible arrangements, trying to improve on the number of matches.

After looking at around 70 million arrangements (i.e. about 3 millionths of them), it finds this:

Iteration 67334517 Deciphered=9/12
S: o  9  1  e  a  8  h  y  7  k  6  c  *  K  G  s
R: a  e  l  b  r  h  c  d  o  t  i  u  n  s  k  m
61oe7a9 -> ilabore -> borealis (s)
8oay9 -> harde -> schedar (sc)
oae1coe -> arbluab -> ?
oh1o89 -> aclahe -> alphecca (pc)
8ayaee -> hrdrbb -> ?
ok98* -> atehn -> elnath (l)
oK98 -> aseh -> scheat (ct)
ohoe19 -> acable -> cebalrai (ri)
1G9 -> lke -> alkes (as)
1799h9 -> loeece -> ?
ohos -> acam -> almach (lh)
okoy9 -> atade -> tarazed (rz)

Just how interesting/plausible/believable is this? We can make a control experiment by using a dictionary of dog breeds of about the same size: does mapping the VMs labels on f68r3 to star names produce a better fit than mapping the labels to dog breeds?

We run the program for a few million mappings, first with the star names, then with the dog breed names. For about 4 million mappings, there is a slightly better (9 out of 12) mapping to dog breeds compared with star names (8/12):

Dogs

Iteration 3779182 Deciphered=9/12
S: o 9 1 e a 8 h y 7 k 6 c * K G s
R: e r o n h l b s d c a p t u i g
61oe7a9 -> aoendhr -> rhodesian (si)
8oay9 -> lehsr -> charles (ca)
oae1coe -> ehnopen -> ?
oh1o89 -> eboelr -> boerboel (bo)
8ayaee -> lhshnn -> ?
ok98* -> ecrlt -> central (na)
oK98 -> eurl -> tulear (ta)
ohoe19 -> ebenor -> redbone (d)
1G9 -> oir -> corgi (cg)
1799h9 -> odrrbr -> ?
ohos -> ebeg -> beagle (al)
okoy9 -> ecesr -> crested (td)

Stars

Iteration 4208178 Deciphered=8/12
S: o 9 1 e a 8 h y 7 k 6 c * K G s
R: a i e c o l b s t h n u r d k m
61oe7a9 -> neactoi -> ?
8oay9 -> laosi -> polaris (pr)
oae1coe -> aoceuac -> ?
oh1o89 -> abeali -> algieba (g)
8ayaee -> losocc -> ?
ok98* -> ahilr -> alphirk (pk)
oK98 -> adil -> alkaid (ka)
ohoe19 -> abacei -> cebalrai (lr)
1G9 -> eki -> keid (d)
1799h9 -> etiibi -> ?
ohos -> abam -> markab (rk)
okoy9 -> ahasi -> nashira (nr)

Of course, this doesn’t disprove that the labels on f68r3 are in fact star names: it may well be that one of the 16! combinations produces a perfect fit, with “61oe7a9” deciphered to “aldebaran” and “8oay9” deciphered to “alcyone” etc..

Character Position Based Cipher

Looking just at the star labels in Folio 68r, we can extract the letter/symbol frequencies as a function of position in the label.

Here’s what they look like:

1: o 1 8 4 9 k 2 A c y 7 W s ? G e 6 g ▐ h
2: o h k 1 c a 8 e y j C 9 K H 7 2 s u m J + f G ┘ W
3: o c 1 9 h a C e y 8 k K d U + 2 * s H n ª I 6 m Z J
4: o c 9 e a 8 y 1 C h i s k 7 A Q H 2 m J 3 ? d
5: 9 o 8 e y 1 c a m h s K * C 7 S 5 2
6: 9 e 8 a 1 y o 7 c s m i
7: 9 e a c y I o m p 1
8: 9 8 e y 7
9: a 9 e

In other words, the most likely symbol to find in the first position of any VMs label is “o” (this is the Voyn_101 encoding). Second most likely is “1” and so on. For the second symbol in the label, the most likely is again “o” in first position, then “k”, and so on.

This is another take on the Crust/Mantle business.

Clearly, the symbols at the ends of the words have a completely different distribution to those at the front.

Compare the VMs star labels with the English star names from Don Latham’s list of star names (simplified):

1: a  m  s  k  h  d  r  t  e  n  b  f  z  j  p  u  c  g  i  w  v  l  o  y
2: a  l  u  i  e  h  c  r  s  d  n  o  t  z  k  w  b  g  j  m  f  y  x
3: a  r  h  i  b  n  s  m  l  t  u  d  k  g  c  e  f  z  w  j  y  p  o  v
4: a  i  e  r  h  b  d  m  l  n  u  s  k  c  f  o  t  z  w  g  p  j  y  v
5: a  i  r  l  n  e  t  h  k  b  s  m  u  d  c  f  g  y  o  z  j  w  p
6: a  h  r  i  e  t  l  n  m  b  s  d  u  c  k  z  o  y  g  p  f  j  v
7: a  e  h  n  i  r  l  b  s  m  t  o  y  d  c  u  k  z  g  f  w  v
8: a  i  h  n  e  c  t  l  s  b  o  u  k  r  f  z  m  g  y  p
9: h  a  t  n  i  e  s  u  r  o  g  z  k  d  p  c  v  m  b

So the plaintext has a quite different letter distribution: basically “a” is always the most likely, regardless of the position in the word.

A hypothesis is that there is a different mapping being used depending on the character position in the word. E.g. if I am enciphering “aldebaran” I would use one mapping for the first “a”, a different mapping for the “l” and so on.

If we also allow a VMs symbol to map to two plaintext characters, we can generate a “likely” mapping as follows:

1T: a  al m  s  k  h  d  sa r  t  ha e  n  ma b  ka f  mi z  j
1S: o  1  8  4  9  k  2  A  c  y  7  W  s  ?  G  e  6  g  ▐  h 

2T: a  l  u  i  e  h  ar ha c  r  ab la al ai s  d  lg ub as n
2S: o  h  k  1  c  a  8  e  y  j  C  9  K  H  7  2  s  u  m  J 

3T: a  r  h  i  b  n  s  m  l  t  u  d  k  g  c  e  ra ha f  z
3S: o  c  1  9  h  a  C  e  y  8  k  K  d  U  +  2  *  s  H  n 

4T: a  i  e  r  h  b  d  m  l  n  u  s  ra k  at ar al ha en c
4S: o  c  9  e  a  8  y  1  C  h  i  s  k  7  A  Q  H  2  m  J 

5T: a  i  r  l  n  e  t  h  k  ah b  s  m  u  ar ra d  c  at f
5S: 9  o  8  e  y  1  c  a  m  h  s  K  *  C  7  S  5  2 

6T: a  h  r  i  e  t  l  n  m  b  ah s  d  u  c  k  an la ab ar
6S: 9  e  8  a  1  y  o  7  c  s  m  i 

7T: a  e  h  n  i  r  l  b  s  m  t  ah o  y  d  c  u  k  at an
7S: 9  e  a  c  y  I  o  m  p  1 

8T: a  i  h  n  e  c  t  l  s  in b  o  u  ch k  r  f  et at z
8S: 9  8  e  y  7 

9T: h  a  t  n  i  e  s  u  r  ha he o  to g  z  ze ab th ra k
9S: a  9  e

(where “T” labels the plaintext alphabet, and “S” labels the source VMs alphabet).

Using this set of mappings, we can translate all the labels to plaintext. The results are disappointing: there are no matches in the list of starnames to the deciphered labels, even allowing anagrams.

But we can then start shuffling the mapping order around for each character position, and use a Monte Carlo approach to see what we come up with. This is what I am trying now. It’s not clear to me that I should allow anagrams in the solutions, since shuffling the letters destroys the ordering in the tables above, that I have assumed.

Advertisements

Genetic Algorithm based Phrase Analysis

February 26, 2010 1 comment

Hypothesis

The following hypothesis occurred to me while I was investigating a cipher theory proposed by Rich Santa Coloma. (This is not a new idea amongst Voynich researchers, but it was new to me!)

The VMs “words” are codes for plaintext character groups, probably trigraphs, digraphs and single characters.

How does  one use this system?

1) Take each word in the plaintext
2) Break it up into a sequence of one or more trigraphs, digraphs and single characters by referring to a code table
3) Write the code for each, separated by a space, and terminate the last  tri/di-graph/character code by a VMs “9”.

The labels are probably treated differently: there may well be a separate set of codes just for the labels.

As an example, take the following “sentence” of 33 “words” from the Herbal folios:

h1cok 2oe 1c9 4ohom 2oy 4ok1coe 1oyoy 2o82c9 4okd9 4okcc9 8am 4okC9 Kay o1c9 1oe 1oe 4ok1c9 8am 1okd9 8ae s19 k1c9 8am 8C9 ko8 8an 4okds 3o h1cc9 sam 1oh1oe 1oy Hos

Breaking the VMs “words” at each terminal “9”, this is deciphered to be a sentence of 13 words:

h1cok 2oe 1c
4ohom 2oy 4ok1coe 1oyoy 2o82c
4okd
4okcc
8am 4okC
Kay o1c
1oe 1oe 4ok1c
8am 1okd
8ae s1
k1c
8am 8C
ko8 8an 4okds 3o h1cc
sam 1oh1oe 1oy Hos

Each of these words is built of one or more codes. E.g. the first word in the list above is “h1cok 2oe 1c” and may be deciphered as

h1cok = “qui”,
2oe = “de”
1c = “m”

to make the Latin word “quidem”.

An interesting feature of this cipher/code is that you may have several choices of how to split each plaintext word into tri/di/mono-graphs, but without ambiguity for the decipherer. This may be an explanation for the different frequency distributions between the VMs folios and Currier hands: they were written by different scribes who tended to split the plaintext words differently.

Does the Theory fit the Data, for Latin?

We first take a substantial body of text from the VMs, e.g. the Recipes folios, and feed it through an application code that extracts all the VMs words, and groups them according to the procedure described above, using one or more arbitrary characters as word ending marks. Typically we use VMs “9”. Each sentence so derived is analysed: each of the tokens is analysed for n-gram content and frequencies are tallied.

At the end of the processing, the n-grams are sorted into frequency order: the most frequent n-grams appear first in the list.

At this point the application moves to its second stage. It ingests a large list of Latin phrases, generated by Knox (thanks, Knox!) and processes each word in each unique phrase for n-gram content, so extracting the n-gram frequencies for Latin. The phrases are placed in a sorted list: shortest first. The n-grams are sorted by frequency, most frequent first.

Here are the Latin phrase sizes used:

A total of 53834 different phrases of size >= 2
2 4405
3 28152
4 8524
5 3866
6 2227
7 1507
8 1085
9 813
10 633
11 513
12 424
13 356
14 300
15 252
16 209
17 177
18 150
19 130

The third stage of the application is to generate a set of Genetic Algorithm chromosomes. Each chromosome takes the Top N n-grams from the Voynich n-gram list and pairs them with a random selection of the n-grams from the Latin list.

For example, for a Chromosome of length 15 (in fact the GA uses much longer lengths, typically 200) the following table might be used:

V: am ay ae 1c8 4ohC oe 1c 4oham 8am 4ohan oham okam  oy 1c7  e
L: ed gi  n  de   et ae  p     s  du    tu   nd    d tio rum te

The chromosomes are “scored” by having them translate/decipher a training set of sentences from the input VMs folios. To calculate the score of each chromosome for each sentence, the sentence word tokens are converted to Latin n-grams using the chromosome’s table. Then the tokens are joined together to form the plaintext words. The plaintext words are looked up in the Latin dictionary: the chromosome’s score is increased for valid words, and decreased for invalid words. Once all the words in the sentence have been deciphered in this way, it is compared with each of the Latin phrases: if a Latin phrase appears in the sentence, the score of the chromosome is increased substantially.

The best chromosome found by a Monte Carlo method (basically generating random chromosomes, and retaining the best scoring chromosome) is placed at the top of a list, and then the remaining chromosomes needed for the Genetic Algorithm are generated.

The GA phase now begins: the chromosomes are genetically altered, mated and selected to optimise the best chromosome’s score on the training sentences. This phase is compute intensive.

Periodically, the GA will report on its progress:

Epoch 311 Cost/Ave 62.845588235294116/61.22993872549012 same 1 Mutated 21.608040201005025% New 1 MS 15
62.845588235294116 GAPhrases$Chromosome@41ec5a Good=128 / 408 = 31.37255% 40 phrases in 25 sentences
S: am ay ae 1c8 4ohC oe 1c 4oham 8am 4ohan oham okam  oy 1c7  e
R: ed gi  n  de   et ae  p     s  du    tu   nd    d tio rum te
Sentence 189
S: 2o ok1c - 1coe hc1 - 1Kc - ohan ae e hC - 4ohan 1cH - 1c7ay ap e2c - 2c7ae ohcay e hc8 - 1coehC - ehc - ohC - 4ohC - 4ohc - 4ohan ap -
T: endve la' binteua tunti nis te' pi et' in'* tunis

In this report, the GA has been running for 311 “epochs” (each epoch is a new generation of chromosomes). The cost (score) of the best chromosome is 62.8, whereas the average score of all the chromosomes in the population is 61.2. In this Epoch, there has been no change to the best chromosome since the last Epoch (“same 1”), 21% of the chromosomes have been mutated, a fresh chromosome (“New 1”) was inserted at this Epoch (to ensure diversity – this is not usually done in GA, but I find it produces more reliable training). “MS 15” means that the maximum number of no-change Epochs seen so far has been 15 … the larger this number is, the more stagnant the chromosome pool is, and the nearer to a solution we are.

The following line shows in detail how the best chromosome has scored: its table produces 128 valid Latin words, from a total of 408 translations i.e. about 31%. In the 25 sentences being used in training, 40 common Latin phrases have been found.

The next two lines show the first 15 n-grams in the mapping that the chromosome is using.

Then the status report shows how the chromosome fared on translating a sentence picked at random from the VMs folios. Since the GA is being trained only on the first few sentences, the remainder are essentially “unseen”, and so a valid, sensible translation in a non-trained sentence is significant.

The sentence picked is number 129 (the training set is the first 25 sentences in this run, so number 129 is well outside that). The VMs source sentence is shown with hyphens “-” separating the tokens that make up words. E.g. “2o ok1c” is the first word. Beneath is the Latin translation. A Latin word followed by a single quote means that that word appears in the Latin dictionary, and is thus valid. A star appearing after a set of valid Latin words indicates that the Latin phrase made up by the words is common, or at least appears in Knox’s list.