Beam Search for Solving Substitution Ciphers

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 1568–1576, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Beam Search for Solving Substitution Ciphers Malte Nuhn and Julian Schamper and Hermann Ney Human Language Technology and Pattern Recognition Computer Science Department, RWTH Aachen University, Aachen, Germany <surname>@cs.rwth-aachen.de Abstract In this paper we address the problem of solving substitution ciphers using a beam search approach. We present a concep- tually consistent and easy to implement method that improves the current state of the art for decipherment of substitution ci- phers and is able to use high order n-gram language models. We show experiments with 1:1 substitution ciphers in which the guaranteed optimal solution for 3-gram language models has 38.6% decipherment error, while our approach achieves 4.13% decipherment error in a fraction of time by using a 6-gram language model. We also apply our approach to the famous Zodiac-408 cipher and obtain slightly bet- ter (and near to optimal) results than pre- viously published. Unlike the previous state-of-the-art approach that uses addi- tional word lists to evaluate possible deci- pherments, our approach only uses a letter- based 6-gram language model. Further- more we use our algorithm to solve large vocabulary substitution ciphers and im- prove the best published decipherment er- ror rate based on the Gigaword corpus of 7.8% to 6.0% error rate. 1 Introduction State-of-the-art statistical machine translation (SMT) systems use large amounts of parallel data to estimate translation models. However, parallel corpora are expensive and not available for every domain. Recently different works have been published that train translation models using only non- parallel data. Although first practical applications of these approaches have been shown, the overall decipherment accuracy of the proposed algorithms is still low. Improving the core decipherment algo- rithms is an important step for making decipher- ment techniques useful for practical applications. In this paper we present an effective beam search algorithm which provides high decipher- ment accuracies while having low computational requirements. The proposed approach allows us- ing high order n-gram language models, is scal- able to large vocabulary sizes and can be adjusted to account for a given amount of computational resources. We show significant improvements in decipherment accuracy in a variety of experiments while being computationally more effective than previous published works. 2 Related Work The experiments proposed in this paper touch many of previously published works in the deci- pherment field. Regarding the decipherment of 1:1 substitution ciphers various works have been published: Most older papers do not use a statistical approach and instead define some heuristic measures for scoring candidate decipherments. Approaches like (Hart, 1994) and (Olson, 2007) use a dictionary to check if a decipherment is useful. (Clark, 1998) defines other suitability measures based on n-gram counts and presents a variety of optimization techniques like simulated annealing, genetic algorithms and tabu search. On the other hand, statistical approaches for 1:1 substitution ciphers were published in the nat- ural language processing community: (Ravi and Knight, 2008) …

Content truncated to 500 words