我正在研究一个问题，该问题简化为对用已知语言编写的冗长单字母替换密文的密码分析。这个问题很容易使用频率分析和单词模式手动解决，如 Sinkov 的基本密码分析中所述。我很难找到理论上验证的算法：Joux 的算法密码分析甚至没有涵盖这种基本的替换，而且我从盖恩斯的密码分析中一无所获：密码及其解决方案的研究（我应该看哪些其他资源？） .
有些方法很明显。依次决定每个替换，然后利用已知的，只有在过程中没有出错的情况下才有效。使用元启发式优化——例如，重新分配字母直到找到的有效单词数量最大化——使得很难判断搜索何时结束。也许测试变化的动态编程方法是最好的。或者，这个问题的答案包含其他可能幼稚的方法。
解决此类问题的首选算法是什么？
如果我们（不切实际地）假设给定语言中的每个字母都以某个已知概率出现，独立于附近的字母，那么可以相当有效地找到确切的最大似然估计。这是您希望使用此模型获得的最佳结果。
假设消息中有 n 个字母，字母表中有 k 个字母。
基本思想是，我们以某种方式为 k^2 个可能的字母对中的每一个得出一个数字分数，然后在两个字母表上寻找最大权重的二分完美匹配——也就是说，我们选择字母对这样一个字母表中的每个字母都与另一个字母表中的一个字母配对，并且所选配对的分数总和最大化。有两个主要问题：（1）如何定义给定对的分数；(2) 一旦我们确定了个体分数，如何解决寻找对的最高和子集的一般问题。
编码后的字母 x 与源字母 y 的配对分数应该是 log(p(y)^freq(x))，其中 p(y) 是字母 y 在语言中的已知概率，freq(x) 是字母 x 在编码输入中出现的次数。为什么？因为在这个忽略邻近字符影响的源语言简单模型下，生成任何给定的 n 个字符的源语言字符串的概率等于其中出现的字母概率的乘积，你也可以计算为 p(y)^freq(y) 对源字母表中所有字母 y 的乘积。因此，要计算生成该字符串的概率，假设每个 x “真的”是 ay（没有其他东西是 ay），我们将 freq(y) 更改为 freq(x)。如果我们然后记录日志，我们得到的就是总和源字母表中所有字母 y 的 log(p(y)^freq(x)) ——这个总和正是最大二分完美匹配算法将最大化的。
有一些算法可以解决密切相关的最大权重二分匹配问题在 O(V^2E) 时间内，这相当于 O(k^4) 时间。这个版本的问题看起来最大化所有选择对的总和，同时遵守没有项目与另一个集合中的两个或多个其他项目匹配的约束，但不要求每个项目都与其他项目匹配。幸运的是，我们可以通过在每个分数上添加一个大数 M 将这个算法变成一个非常简单地解决我们想要解决的“完美”变化的算法：直观地说，这会导致算法尝试添加尽可能多的边（因为即使省略一条边也有很大的成本，使得这样的解决方案甚至比包含全套 k 边的“愚蠢”解决方案更糟糕），