最高效的字符计数算法？

Question

假设您想计算文本中字符的出现次数。我能想到的最快方法是使用类似unsigned char charcounts[256]的数组，将其初始化为零，然后查看输入文本中的每个字符并执行charcounts[c]++。然后使用两个变量进行线性搜索charcounts []，以跟踪当前最低字符及其计数，当我们找到更低的字符/计数时，用新的字符/计数替换它，直到到达末尾。因此，"text"将被计算为t=2，e=1，x=1。有没有更快的方法来完成这个任务？

- ted

---

你是想找出一个字符串中每个字符出现的次数吗？还是想获取字符（a-zA-Z）的完整列表，以及它们在字符串中出现的次数？或者还有其他什么需求？ - Matthew Schinckel

统计一段文本中每个字符出现的总次数。例如，"text" 中 t=2, e=1, x=1。 - ted

Ted，您应该通过点击上方的“编辑”按钮将这个重要的澄清编辑到您的问题中。 - Jeff Atwood

适用于ANSI非常好，但对于Unicode来说情况就不同了。 - Toon Krijthe

一般来说，从渐近意义上讲，你无法击败O(n)，因为你至少要检查所有的输入。在此基础上，你可以讨价还价隐藏常数.. - phs

Answer 1

第一部分 - 统计字母频率 有两个问题需要指出，假设这里使用的语言是C或C++:

• 你的代码不能处理出现超过255次的字母（或127，如果char恰好被视为有符号的）。将“charcounts”改为int数组可能并不会对性能产生太大影响。
• 你的代码无法处理unicode /国际字符。

第二部分 - 定位出现最少的字母

• 如果你处理的是短字符串（"text"，“fred”），那么在表中扫描所有256个条目是速率决定步骤。最好在初始扫描循环中跟踪最低频率字母。
• 但是，如果你确实想扫描所有256个条目，你可以在遇到“one”值（或零，如果算法意图如此）时立即退出循环。

- Roddy

---

我尝试接受你的答案，但是没有成功。那似乎是最快的方式... - ted

Answer 2

你的算法的第一部分是计算字符数 - 这只是生成排序键。

如果您知道您只使用字母字符 [A-Za-z ]*，那么您可以通过减少使用的桶的数量来优化您的算法，但这只是一个小调整。

第二部分只是一个稳定的排序 - 有很多方法可以做到这一点 - wikipedia page on sorting 给出了一个很好的总结。 如果您只关心出现最少的字符，则您描述的 ("Phase 2") 方法可能是您能够得到的最有效的方法。

我能想到的唯一改进的方式是，如果您可以将字母分成固定数量的桶（比如16个），均匀地分布在字符范围内，然后对每个桶进行递归。 任何没有字符的桶都可以被丢弃，在扫描/排序阶段节省一些时间。 同样，如果一个桶只有一个字符，那么它就完成了。 您还要确保仅在知道其中有多个不同字符时才将一个桶分成16个桶。

以单词test为例（假设有4个桶和只有小写字母）：

1. 生成4个桶 (A-G, H-M, N-T, U-Z)
2. 拆分单词test:
   • A-G: e，
   • H-M: t，
   • N-T: tst，
   • U-Z: 。
3. 对其他桶进行递归处理 - (A-G只有一个字符，因此必须是最小的，这样我们才能停止
4. 如果不是这种情况（例如单词 "testes"），我们可以看到H-M和U-Z为空，所以我们只需要检查N-T（其中包含tsts）。
   • 我们创建4个桶（N-O，P-Q，R-S和T）。
   • 拆分字母
   • 等等。

这种方法的优点在于我们不必扫描每个字母。如果字符范围大小相同，则这两种方法都是最好情况下的O(n)，其中n是字符串长度（因为我们总是需要查看每个字符），尽管在我的示例中构造字符列表可能会使算法变得像O(n^2)那样糟糕。但是，随着字符范围的增加，特别是对于短字符串，使用子桶将大大提高性能。对于Unicode字符串，您可以使用混合方法-例如，在第一阶段分离所有非ASCII字符，并在ASCII部分中使用更简单的方法。

- Oliver Hallam

Answer 3

你在这里描述了两个任务。第一个任务是计算流中每个ASCII字符出现的次数，第二个任务试图找到出现频率最低的字符。

第一个算法似乎相当有效率。就我个人而言，我想不到更快的方法。

然而，我对你的第二个算法不是很确定。你没有明确说明为什么要找到出现频率最低的字符，或者输入数据是什么，但我可以想象很容易有多个频率计数为零的字符，那么你希望如何区分它们？

- Andrew

Answer 4

听起来像是实现你所描述的最有效的方法之一。我不确定你想用第二部分做什么，它似乎是要找到在排序数据中出现次数最少的字符？

- Greg Hewgill

---

所以你想知道字符串中出现次数最少但至少一次的字符是什么？如果有两个字符出现次数相同怎么办？ - Matthew Schinckel

最少出现的第一个字符是我的。我主要只是对计数数组的线性搜索感到好奇。它的时间复杂度为O(n)，我很好奇是否有更快的算法。我研究了堆，可以在O(1)中返回最低值，但在O(lg n)中进行调整，这将是O(n lg n)。 - ted