-1


假设我有一个文档，并且该文档分布在 4 台不同的机器上，我想获得一个重复次数最多的字符（所有 4 台机器相结合）。

我的一种方法是在每台机器上使用一个哈希图并单独计算每台机器上的频率，然后将该哈希图传递到主服务器，来自所有 4 台机器的哈希图将被合并。因此，我们将获得频率最高的角色。

但是这里的缓存是我想尽量减少每台机器传输的数据。

可以进行哪些改进？

[编辑]
每台机器都持有文件的一部分

4

2 回答 2

3

如果你不介意花更长的时间...

  1. 每台计算机传递最频繁的字符。希望频率最高的字符数很少。理想情况下，它几乎总是只有一个。
  2. 主服务器将它们组合成一个集合。如果该集合完成了单个字符。否则，这个集合将被传递给计算机，可能是一个数组或列表。假设每台计算机只有一个字符，则此列表将只有 2-4 个字符。
  3. 每台计算机返回集合中每个字符的频率。
  4. 主服务器对频率进行求和，得到最频繁的。
于 2013-07-16T08:01:15.030 回答
0

我断言，如果事先不知道文档中字符的分布，那么您采取的任何方法都必须将所有 4 台计算机的数据减少到其中一台计算机上。为了最小化传输的数据，有必要最小化保存每台计算机上字符数的数据结构的大小。

假设您正在使用带有N字符的字母表，那么您现在的问题是设计一个可以保存N整数（在某个范围内[0..m]，m是字母表中的字符数）的数据结构，并且可以找到任意数量的此类数据结构.

当然，如果您对字符的分布有先验知识，例如，如果您知道它是用英文编写的纯文本，那么您就有一系列可能的数据压缩方法。

鉴于在实践中可能发现的相对较小的值，N我同意评论的一般主旨，即设计一个复杂的结构来最小化传输的数据量可能不值得，发送一个整数数组就足够了最能想到的情况。mN

于 2013-07-16T07:55:25.960 回答