Sukhotin's Algorithm

Re:Sukhotin's Algorithm by daivd on Wednesday July 07, 2010 @05:06PM (#1495476)

If I understand this correctly, saying that vowels tend to be close to vowels is just a special case of using n-grams. If you have a fingerprint with the common n-gram distribution for the target language (or even subject), you get an optimization problem where you try to guess the substitutions such that the angle between the fingerprint vectors are minimized.

If it cannot be solved analytically, it seems something like a GA should solve it well.

Is there a standard method for solving substitution cryptos?

[ Parent | on HN ]

Re:Sukhotin's Algorithm by tudorachim on Wednesday July 07, 2010 @05:33PM (#1495563)

There is a much more straightforward and principled way: the Metropolis algorithm (http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_alg...). You are basically sampling from the distribution of n-gram likelihoods by following a markov chain. Here is a javascript implementation: http://www.andrew.cmu.edu/user/tachim/page.html

[ Parent | on HN ]

Re:Sukhotin's Algorithm by abecedarius on Wednesday July 07, 2010 @08:22PM (#1496027)

See also http://norvig.com/ngrams/ for Python. Random-restart hillclimbing instead of Metropolis.

[ Parent | on HN ]