Nat*_*enn 7 puzzle algorithm nlp
最近,一位同事在尝试寻找(不同的)研究工作时被问到这个问题:
给定10个128个字符的字符串,它们以完全相同的方式排列,解码字符串.原始字符串是英文文本,其中删除了空格,数字,标点符号和其他非字母字符.
在给出答案之前,他有几天时间考虑过这个问题.你会怎么做？您可以使用任何计算机资源,包括字符/单词级语言模型.
这是一个基本的转置密码.我上面的问题只是确定它是换位密码还是替换密码.这种系统的密码分析相当简单.其他人已经提到过基本方法.最佳方法将尝试首先放置最难和最稀有的字母,因为这些字母将倾向于唯一地识别它们周围的字母,这极大地减少了后续搜索空间.简单地找到一个放置"a"(没有双关语)的地方并不难,但找到"q","z"或"x"的位置是一项更多的工作.
算法质量的首要目标不是破译文本,因为它可以通过比强力方法更好地完成,也不仅仅是快速,但它应该尽可能快地消除可能性.
由于您可以同时使用多个字符串,因此尝试从最稀有字符创建单词将允许您并行测试字典攻击.尽可能快地找到每个字符串中rarest术语的正确位置将同时解密该密文PLUS所有其他字符串.
如果你搜索转置密码的密码分析,你会发现一堆遗传算法.这些旨在提高在GA工作的人的研究信誉,因为这些在实践中并不是最佳的.相反,您应该查看一些基本的优化方法,例如分支和绑定,A*以及各种统计方法.(你应该走多远取决于你在算法和统计方面的专业水平.:)我会多次在确定性方法和统计优化方法之间切换.)
在任何情况下,计算应该是便宜且快速的,因为初始猜测的规模可能非常大.最好有一种廉价的方法来首先过滤掉很多可能的位置,然后花更多的CPU时间来筛选更好的候选人.为此,有一种方法可以描述每个阶段的处理阶段和计算工作量.(至少那是我所期望的,如果我把这作为面试问题.)
更新1:查看这些幻灯片,了解有关迭代改进的更多想法.它不是一个很好的幻灯片参考集,但它很容易访问.更重要的是,虽然幻灯片是关于GA和模拟退火(在转换密码密码分析的搜索结果中出现的方法),但作者提倡在使用A*或其他方法时反对这些方法.:)