用python解决替换密码 [英] Solving a substitution cipher with python

问题描述

我知道有人问过类似的问题，但这是一个微不足道的案例.

给定一个用替换密码结尾的文本文件，我需要使用 python 对其进行解码.我没有给出任何正确破译单词的例子.这种关系是一对一的，大小写没有区别.此外，标点符号不会改变，空格会留在原处.我不需要代码方面的帮助，因为我需要关于如何在代码中完成的一般概念的帮助.我的主要方法包括:

1. 首先解决 1、2 或 3 个字符的单词来缩小选择范围.
2. 我可以使用不同大小的英文单词列表进行比较.
3. 我可以使用字母的频率分布.

有没有人知道我可以采取的一般方法来做到这一点?

解决方案

你可以试试这个方法:

1. 存储有效单词列表(在字典中)和您的语言的正常"字母分布(在列表中).

2. 计算乱码文本中字母的分布.

3. 将您的乱码分布与正常分布进行比较，并据此对您的文本进行改正.

4. 重复:将所有 26 个字母的数组(秩)设置为浮点数(rank('A')=rank('B')=...=rank('Z')=0.0)

5. 对照词典中的词检查生成的文本中的词.如果某个词在字典中，则提高该词的字母的等级(例如:添加一个标准值，例如 1.0).换句话说，计算分数(字典中总排名和单词数的函数).

6. 将文本保存到高分表(如果分数足够高).

7. 如果所有单词都在字典中，或者总排名足够高，或者循环次数超过 10000 次，则结束.

8. 如果不是，则随机选择两个字母并互换.但是如果分布有偏差，排名高的字母互换的机会应该更小.

9. 重复.

10. 结束:打印高分文本.

该过程类似于模拟退火

I know similar questions have been asked, but this is kind of a trivial case.

Given a text file endcoded with a substitution cipher, I need to decode it using python. I am not given any examples of correctly deciphered words. The relationship is 1-to-1 and case doesn't make a difference. Also, punctuation isn't changed and spaces are left where they are. I don't need help with the code as much as I need help with a general idea of how this could be done in code. My main approaches involve:

1. Narrowing down the choices by first solving 1, 2 or 3 character words.
2. I could use an list of English words of different sizes to compare.
3. I could use frequency distributions of the letters.

Does anyone have an idea of a general approach I could take to do this?

解决方案

You could try this approach:

1. Store a list of valid words (in a dictionary) and a "normal" letter distibution for your language (in a list).

2. Calculate the distribution of the letters in the garbled text.

3. Compare your garbled distribution with the normal one and regarble your text according to that.

4. Repeat: Set an array (rank) from all 26 letters to float (rank('A')=rank('B')=...=rank('Z')=0.0)

5. Check the words in the produced text against words in the dictionary. If a word is in the dictionary, raise the rank of that word's letters (something like: add a standard value, say 1.0). In other words calculate Score (a function of total rank and number of words in dictionary).

6. Save text into High score table (if score high enough).

7. If all words are in the dictionary or if the total rank is high enough or if the loop was done more than 10000 times, End.

8. If not, choose randomly two letters and interchange them. But with a deviated distribution, letters with high rank should have less chances of being interchanged.

9. Repeat.

10. End: Print High score texts.

The procedure resembles Simulated Annealing

这篇关于用python解决替换密码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！