1

我想编写一个搜索密文并返回密码中字符的频率计数的java程序，例如密码：“jshddllpkeldldwgbdpked”将有这样的结果：

2 个字母出现：

pk = 2，ke = 2，ld = 2

3 个字母出现：

pke = 2。

有什么算法可以让我尽可能高效地做到这一点？

4

8 回答 8

4

地图策略是一个很好的策略，但我会选择HashMap<String, Integer>，因为它是被计算的字符元组。

遍历密文中的字符，您可以保存最后 X 个字符，这将为您提供所有出现的长度为 X+1 的子字符串的映射。

于 2009-11-27T10:27:01.980 回答
2

通常的方法是使用某种地图将您的角色映射到他们的数量。您可以使用HashMap<Character, Integer>例如。然后，您可以逐字符地遍历您的密文，并将字符放入地图中，计数为 1（如果它尚不存在）或增加其计数。

于 2009-11-27T10:14:51.787 回答
2

您可以将n-gram存储在trie中，颠倒正常顺序，以便 n-gram 中的最后一个字符位于 trie 的顶部。trie 中的每个节点都存储一个字符数。循环遍历字符串，跟踪最后 N 个字符（如Buhb 建议的那样）。每次通过外循环时，您都会遍历 trie，使用最后 N 个字符来选择路径，从​​最后一个字符开始，到最后的第 N个字符结束。对于您访问的每个节点，递增其计数器。

要打印 n-gram 频率，请执行 trie 的广度优先遍历。

整体表现留作练习。

于 2009-11-27T12:05:28.240 回答
1

如果您需要的序列长度集是固定的，那么显而易见的算法会采用线性数量的计数操作（例如，在哈希表中查找计数器并将其递增）。

当您说“尽可能高效”时，您是否建议花费大量精力来进行微不足道的常数因子改进，无望地搜索次线性算法，或者您根本不了解算法复杂性类别？

于 2009-11-27T12:15:49.033 回答
1

要么有一个数组，每个可能的值都有一个单元格（如果密文都是小写字符，则很容易 - 26 - 如果不是，则更难），或者选择一个 Map ，在其中传入字符并在任何一种情况下增加值。阵列更快但不太灵活。

于 2009-11-27T10:16:25.780 回答
1

您可以使用哈希或图形（感谢 outis，我现在知道它的特殊名称，这种图形称为“trie”）。散列会更慢，图会更快。哈希将获得更少的内存，图形将在糟糕的实现中占用更多。

您无法使用数组完成它，因为如果您的最大字符序列长度等于您的文本长度并且文本足够长，它将获得大量内存。如果您对其进行限制，它将获得类似([number of letters]^[max sequence length])*4字节的内容，这将是(52^4)*4 ~= 24Mb4 个小写/大写字母序列的内存。如果有限的序列长度对你来说是可以的，并且这个内存量是正常的，那么对于 <=4 个字母的序列来说，算法将非常容易。

于 2009-11-27T10:45:32.387 回答
0

这个我心里没有答案

但我觉得，这个算法与压缩算法使用字典方法创建压缩文件的算法完全相同。

如果我没记错的话，在这种方法中，字典的使用方式如下：

数据：

abccccabaccabcaaaaabcaaabbbbbccccaaabcbbbbabbabab

解析1：键：*值：abc

新数据：

*cccabacc*aaaa*aaabbbbbccccaa*bbbbabbabab

只是一个有根据的猜测，我认为（这里不确定）标准的“zip”文件使用这种方法，所以我建议你看看这些算法

于 2009-11-27T12:39:25.030 回答
0

您可以首先寻找最大可能的可重复序列，然后从那里开始。例如，如果字符串是 10 个字符，则可能出现的最大可重复序列长度为 5 个字母，因此首先查找 5 个字母序列，然后查找 4 个字母，依此类推，直到达到 2。这应该会减少程序中的迭代次数。

于 2009-11-27T11:18:42.250 回答