Archive

Posts Tagged ‘f1r’

Genetic Algorithm

February 26, 2010 Leave a comment

Basic Idea

In the plaintext, convert each group of 1, 2, 3 or 4 characters into a Voynich group of 1,2,3 or 4 characters. We call this a “mapping”. For example, when creating Voynich from Latin, a cipher mapping might be:

e => o, i => 9, …

er => 4o, is => ok, ti => 8a, …

ent => 9k, ant => A, …

… and so on. This can be encoded into an algorithm thus which maps strings in “repl” to strings in “seek”. For example:

	String seek[] = {"4ok1",
			 "4oh","8am","1oe","4ok","ok1","o89","1oy","oh1","o8a","oha","ohc","c89","1co","k1o","1c9",
			 "c79","h1o","1o8","oko","oho","coe","8ae","co8","k19","h19","8ay","ham","hcc","koe","oka",
			 "hco",
			 "1o", "oe", "oh", "4o", "ok", "8a", "89", "am", "1c", "oy", "o8", "co", "ay",
			 "k1", "h1", "19", "hc", "c9", "ha", "ae", "79", "2o", "cc", "ko", "ho", "c8", "9h",
			 "9k", "c7", "2c", "ka", "kc", "1a", "an", "h9", "o,", "e8", "k9", "ap", "8o", "e,",
			 ",1", "7a", "81",
			 "o",  "9",  "1",  "a",  "8",  "c",  "h",  "e",  "k",  "y",  "4",  "m",  ",",
			 "2",  "7",  "s",  "K",  "C",  "p",  "g",  "n",  "H",  "j",  "A"};

	//Latin
	String repl[] = {"un",
			 "ri", "on", "f",  "es", "g",  "em", "de", "se", "co", "ne", "ur", "si", "ic", "ui", "me",
			 "ere","eb", "la", "ma", "le", "id", "bu", "nti","no", "cu", "eba","qui","ie", "al", "ul",
			 "ns",
			 "c",  "d",  "l",  "er", "is", "ti", "nt", "en", "re", "in", "um", "am", "us",
			 "te", "it", "v",  "tu", "ta", "ra", "di", "an", "ni", "li", "et", "ba", "ae", "mi",
			 "ent","st", "h",  "nd", "ci", "pe", "im", "ua", "io", "tur","il", "ve", "iu", "as",
			 "vi", "ita","ca",
			 "e",  "i",  "a",  "t",  "u",  "s",  "r",  "n",  "m",  "o",  "p",  "b", "q",
			 "qu", "at", "or", "ia", "ar", "ce", "ib", "ec", "ab", "ru", "ant"};

Such an algorithm is used inside a Chromosome of the Genetic Algorithm. The Chromosome decodes Voynich into Latin by  matching character groups in the Voynich word against each of the strings in the “seek” list in turn. If a match occurs, then the  Voynich group is translated into the Latin group in the “repl” list at the same position. Thus “4ok1” in Voynich is translated into “un” in Latin.

Once the Voynich word has been translated into Latin, the Latin word is looked up in a Latin dictionary. If the word is found, then the “cost” (or “quality”) of the Chromosome is increased … if the word is not found, then the cost is decreased. After all words in the Voynich text have been converted to Latin, and the aggregate cost of the Chromosome evaluated, it can be judged whether the mapping “seek” to “repl” is a good one or not.

Generating the Chromosome Population

We generate a large number of Chromosomes, each of which has a different, randomised, “seek” to “repl” mapping. We do this by simply shuffling the order of the “repl” strings in each Chromosome.

Thus, one Chromosome may map “4ok1” to “s” and another may map it to “qui”.

This population of Chromosomes is then evaluated: each Chromosome converts the Voynich words to Latin, and each then gets a cost. The higher the cost, the better. The highest possible cost would be a Chromosome that had a seek-repl mapping that produced a valid Latin word for each Voynich word.

Training the Chromosomes

The Chromosomes are ordered in decreasing cost, and then the best of them (i.e. at the top of the list) are “mated” together to produce offspring Chromosomes. The mating process essentially involves taking sequences of the “repl” strings from both parents and combining them to form a new “repl” string.

Some of the offspring Chromosomes are then “mutated”. This involves replacing one of the “repl” strings with some randomly selected letters from the Latin character set.

The process repeats (ordering the Chromosomes, mating the best ones, mutating the offspring) until a predefined cost value is reached, or the population of Chromosomes refuses to improve itself.

In the end, the best, trained Chromosome will contain the optimal arrangement of “seek” to “repl” mappings for conversion of Voynich to Latin.

The same procedure can be used for a Voynich to English, to German, French or any other language, provided that a dictionary and substantial texts are available to process.

First Results – Voynich to Latin

This is a limited attack on the first five “sentences” of f1r, using 200 chromosomes and a Latin dictionary of around 15,000 words. The best chromosome scores 9.4 after 500 training epochs (cf a score of 20 for a one-to-one translation of Latin into Latin).

Here are the deciphered sentences:

1) Voynich: fa19s 9hae ay Akam 2oe !oy9 ²scs 9 hoy 2oe89 soy9 Hay oy9 hacy 1kam 2ay Ais Kay Kay 8aN s9aIy 2ch9 oy 9ham +o8 Koay9 Kcs 8ayam s9 8om okcc9 okcoy yoeok9 ?Aay 8am oham oy ohaN saz9 1cay Kam Jay Fam 98ayai29

Latin: ?ereieas vias is asasita meas ?ereis ?astuas is quinti mensis asereis vis ereis sttunti viasita viis as?as alis alis qui? asisere? nti quere ere viis ?ita alamisis altuas ereis asis quiita quantis querenti ntiviquis ?asis qui amita ere am? asere?is viis alis ?is ?is isereere?viis