流字符串值的近似直方图（卡片目录算法？）
approximate histogram for streaming string values (card catalog algorithm?)
我有一个很大的按字典顺序排序的 UTF-8 字符串列表（或流）。我想创建一个计数值大致相等的直方图，根据需要改变 bin 宽度以保持计数均匀。在文献中，这些有时称为等高或等深直方图。
我不想做通常的字数统计条形图，我想找一些更像老式图书馆卡片目录的东西，里面有一组抽屉（箱子），其中一个可能装有 SAM - 已售出，下一个箱子 SOLE-STE，而所有 Y-ZZZ 都装在一个箱子里。我想计算每个箱子的截止位置。
是否有 (A) 已知算法，类似于数值的近似直方图？或 (B) 关于如何以标准数字直方图算法工作的方式对字符串进行编码的建议。该算法不应该需要字符串填充的先验知识。
到目前为止我能想到的最好的方法就是简单地等到我有一些合理数量的数据，然后通过以下方式形成逻辑箱：
number_of_strings / bin_count = number_of_strings_in_each_bin
然后，从 0 开始，向前移动 number_of_strings_in_each_bin 以获得 bin 端点。
这对我的用例来说有两个弱点。首先，它需要对可能非常多的字符串进行两次迭代，一次用于计数，一次用于查找端点。更重要的是，一个好的直方图实现可以估计值落在 bin 中的哪个位置，这将非常有用。
谢谢。
如果我们无法对数据做出任何假设，您将不得不进行一次传递以确定 bin 大小。
这意味着您要么从 bin 大小而不是 bin 编号开始，要么使用两遍模型。我只是使用线性插值来估计 bin 之间的位置，然后从那里进行二进制搜索。
当然，如果您可以对数据做出一些假设，以下一些可能会有所帮助：
例如，您可能不知道确切的大小，但您可能知道该值将落在某个区间 [a, b] 内。如果您最多想要 n 个垃圾箱，请将垃圾箱大小设置为 == a/n.
或者，如果您不特别关注大小完全相同的垃圾箱，您可以一次性通过对每个 m 元素进行采样并将其转储到一个数组中，其中 m 根据上下文是合理的。
然后，要查找 bin 端点，您需要在数组中的 size/n/m 处找到元素。
我提出的解决方案通过使用水库抽样解决了缺乏有关人口的前期信息的问题。水库抽样让您可以从未知规模的总体中高效地随机抽取给定规模的样本。有关详细信息，请参阅 Wikipedia。水库采样提供随机样本，无论流是否有序。
我们对数据进行一次遍历，收集样本。对于样本，我们有关于元素数量及其分布的明确信息。
对于直方图，我使用了 Guava RangeMap。我选择了范围的端点以在每个范围内提供偶数个结果 (sample_size / number_of_bins)。地图中的 Integer 仅存储范围的顺序，从 1 到 n。这使我能够估计落在两个值内的记录的比例：如果有 100 个大小相等的分箱，并且这些值落在分箱 25 和分箱 75 中，那么我可以估计大约 50% 的人口落在这些值之间。
这种方法的优点是适用于任何 Comparable 数据类型。
我有一个很大的按字典顺序排序的 UTF-8 字符串列表（或流）。我想创建一个计数值大致相等的直方图，根据需要改变 bin 宽度以保持计数均匀。在文献中，这些有时称为等高或等深直方图。
我不想做通常的字数统计条形图，我想找一些更像老式图书馆卡片目录的东西，里面有一组抽屉（箱子），其中一个可能装有 SAM - 已售出，下一个箱子 SOLE-STE，而所有 Y-ZZZ 都装在一个箱子里。我想计算每个箱子的截止位置。
是否有 (A) 已知算法，类似于数值的近似直方图？或 (B) 关于如何以标准数字直方图算法工作的方式对字符串进行编码的建议。该算法不应该需要字符串填充的先验知识。
到目前为止我能想到的最好的方法就是简单地等到我有一些合理数量的数据，然后通过以下方式形成逻辑箱：
number_of_strings / bin_count = number_of_strings_in_each_bin
然后，从 0 开始，向前移动 number_of_strings_in_each_bin 以获得 bin 端点。
这对我的用例来说有两个弱点。首先，它需要对可能非常多的字符串进行两次迭代，一次用于计数，一次用于查找端点。更重要的是，一个好的直方图实现可以估计值落在 bin 中的哪个位置，这将非常有用。
谢谢。
如果我们无法对数据做出任何假设，您将不得不进行一次传递以确定 bin 大小。
这意味着您要么从 bin 大小而不是 bin 编号开始，要么使用两遍模型。我只是使用线性插值来估计 bin 之间的位置，然后从那里进行二进制搜索。
当然，如果您可以对数据做出一些假设，以下一些可能会有所帮助：
例如，您可能不知道确切的大小，但您可能知道该值将落在某个区间 [a, b] 内。如果您最多想要 n 个垃圾箱，请将垃圾箱大小设置为 == a/n.
或者，如果您不特别关注大小完全相同的垃圾箱，您可以一次性通过对每个 m 元素进行采样并将其转储到一个数组中，其中 m 根据上下文是合理的。
然后，要查找 bin 端点，您需要在数组中的 size/n/m 处找到元素。
我提出的解决方案通过使用水库抽样解决了缺乏有关人口的前期信息的问题。水库抽样让您可以从未知规模的总体中高效地随机抽取给定规模的样本。有关详细信息，请参阅 Wikipedia。水库采样提供随机样本，无论流是否有序。
我们对数据进行一次遍历，收集样本。对于样本，我们有关于元素数量及其分布的明确信息。
对于直方图，我使用了 Guava RangeMap。我选择了范围的端点以在每个范围内提供偶数个结果 (sample_size / number_of_bins)。地图中的 Integer 仅存储范围的顺序，从 1 到 n。这使我能够估计落在两个值内的记录的比例：如果有 100 个大小相等的分箱，并且这些值落在分箱 25 和分箱 75 中，那么我可以估计大约 50% 的人口落在这些值之间。
这种方法的优点是适用于任何 Comparable 数据类型。