acl acl2010 acl2010-29 acl2010-29-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Eric Corlett ; Gerald Penn
Abstract: Letter-substitution ciphers encode a document from a known or hypothesized language into an unknown writing system or an unknown encoding of a known writing system. It is a problem that can occur in a number of practical applications, such as in the problem of determining the encodings of electronic documents in which the language is known, but the encoding standard is not. It has also been used in relation to OCR applications. In this paper, we introduce an exact method for deciphering messages using a generalization of the Viterbi algorithm. We test this model on a set of ciphers developed from various web sites, and find that our algorithm has the potential to be a viable, practical method for efficiently solving decipherment prob- lems.
Friedrich L. Bauer. 2007. Decrypted Springer-Verlag, Berlin Heidelberg. Secrets. George W. Hart. 1994. To Decode Short Cryptograms. Communications of the ACM, 37(9): 102–108. Kevin Knight. 1999. Decoding Complexity in WordReplacement Translation Models. Computational Linguistics, 25(4):607–615. Kevin Knight, Anish Nair, Nishit Rathod, Kenji Yamada. Unsupervised Analysis for Decipherment Problems. Proceedings of the COLING/ACL 2006, 2006, 499–506. George Nagy, Sharad Seth, Kent Einspahr. 1987. Decoding Substitution Ciphers by Means of Word Matching with Application to OCR. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(5):710–715. Shmuel Peleg and Azriel Rosenfeld. 1979. Breaking Substitution Ciphers Using a Relaxation Algorithm. Communications of the ACM, 22(1 1):589–605. Sujith Ravi, Kevin Knight. 2008. Attacking Decipherment Problems Optimally with Low-Order N-gram Models Proceedings of the ACL 2008, 812–819. Antal van den Bosch, Sander Canisius. 2006. Improved Morpho-phonological Sequence Processing with Constraint Satisfaction Inference Proceedings of the Eighth Meeting of the ACL Special Interest Group on Computational Phonology at HLT-NAACL 2006, 41–49. 1047