algorithm - 判断文本是否有意义的字符串搜索算法

Question

我正在解密一个旧文本，我想要一个快速算法来检查一个长字符串中是否有来自字典的有意义的单词。这样我就可以判断一个特定的键是否有效。

因此，可以使用字典预处理和大表，但在 25-50 个字符上尽可能快。

谢谢！

更新

我知道语言（意大利语），但文本没有空格，可能有几个随机字母。像：

TANKSSEENNEARUDINE昨天

并且密码是一个奇怪的柱状换位，所以单个字母的频率是固定的。

score 5 · Accepted Answer

密码学中的标准方法不是检查字典，而是检查明文（假定）语言的概率模型。例如，三元组的简单统计，即三个字符相邻的序列，在英语和胡言乱语之间存在显着差异。（在英语中，“THE”是最常见的三合词。类似地，像“CXC”这样的三合词根本不会出现在英语中。）

例如，可以通过简单的自相关方案推断密钥长度，然后根据底层明文语言的语言统计信息搜索实际密钥来破解 Vigenere 密码。当我在我们大学讲授密码学时，我什至为了演示目的实施了该程序...... :)

使用这些类型的概率/马尔可夫模型的好处是，它们还可以很好地容忍恰好在特定字典之外、有错别字、或者是替代或过时形式的单词。

score 3 · Accepted Answer

如果没有更多细节，我可能会将字典编码为 trie，并尝试匹配 haystack 字符串中的每个位置。如果您不了解尝试，它是用于快速字典查找的最佳结构。

score 0 · Accepted Answer

你需要缩小你的细节。想想看。如果你有很长的单词，比如 20-30 个字符，那么你需要这个字符串中所有子字符串的所有不同排列，并将它们与字典进行比较。那将是非常繁重的计算。此外，如果你有很多这样的长词，除非你在集群或其他东西上运行它，否则这将非常困难。