了解超置logog以估计基数

基数是数据集中不同项目的数量。无论是计算网站上的唯一用户数量还是估计不同搜索查询的数量，估计基数在处理大量数据集时都变得具有挑战性。这就是超置式算法进入图片的地方。在本文中，我们将探讨HyperLoglog及其应用程序背后的关键概念。

Hyperloglog

HyperLogLog是一种概率算法，旨在估计具有高精度和低内存使用情况的数据集的基数。

计算不同项目的传统方法需要存储到目前为止所看到的所有项目，例如将所有用户信息存储在用户数据集中，这可以快速消耗大量内存。另一方面，HyperLogLog使用固定数量的内存，几千字节，并且仍然提供了对基数的准确估计，使其非常适合大规模数据分析。

用例

在以下情况下，HyperLogLog特别有用：

有限的内存

如果使用大量数据集(例如数百万用户或网络流量数据的日志)，则由于内存限制，存储每个唯一项目可能是不可行的。

近似计数

在许多情况下，不需要确切的计数，并且良好的估计是足够的。 HyperlogLog给出了一个估计值，该估计值与真实值足够接近，而没有精确计算的开销。

流数据

当使用连续的数据流(例如实时网站流量或社交媒体供稿)时，超置换件可以更新其估算值，而无需重新访问过去的数据。

一些值得注意的应用程序用例包括以下内容：

· Web分析：估计访问网站的唯一用户数量。

· 社交媒体分析：计算社交媒体流中独特的主题标签，提及或其他不同项目。

· 数据库系统：有效地计数大型数据库中的不同键或值。

· 大数据系统：诸如Apache Hadoop和Apache Spark之类的框架使用HyperLoglog来计算大数据管道中的不同项目。

· 网络监控：估计网络流量分析中不同IP地址或数据包的数量。

现有实现

HyperLoglog已以各种语言和数据处理框架实现。一些实现超闸纸的流行工具如下：

· REDIS提供了HyperLogLog的本机实现PFADD，以通过PFCOUNT和PFMERGE命令进行近似的基数估算。 REDIS允许用户在消耗最小内存的同时有效地跟踪数据集中的独特项目。

· Google BigQuery提供了一个名为的内置函数APPROX_COUNT_DISTINCT，该功能使用超置logog来估计大数据集中不同项目的数量。 BigQuery通过使用HyperLoglog来提供高效的心脏估算，而无需全部数据来优化查询处理。

· Apache DataSketches是用于近似计算的算法集合，包括HyperLogLog。它是在Java中实现的，通常用于用于大规模数据处理的分布式计算环境中。

· Python软件包HyperlogLog 是 超置池的实现，可让您计算具有较小内存足迹的数据集的近似基数。

· 该函数approx_count_distinct可在Pyspark的DataFrame API中获得，并用于计算数据框列中不同值的近似计数。它基于HyperLogLog算法，提供了一种高度记忆有效的估计不同计数的方法。

示例用法

from pyspark.sql import SparkSession

from pyspark.sql import functions

spark=SparkSession.builder.appName('Test').getOrCreate()

df = spark.createDataFrame([("user1", 1), ("user2", 2), ("user3", 3)])

distinct_count_estimate = df.agg(functions.approx_count_distinct("_1").alias("distinct_count")).collect()

print(distinct_count_estimate)

逻辑

HyperLoglog背后的基本思想是使用哈希功能将数据集中的每个项目映射到一系列值的位置。通过分析这些项目的位置，该算法可以估计存在多少不同的项目而不明确存储它们。这是其工作原理的分步分类：

1. 集合中的每个项目都使用哈希函数进行哈希。哈希函数的输出是二进制字符串。

2. HyperLogLog专注于哈希值的二进制表示中的领先零。领先的零，值越稀有。具体来说，跟踪了哈希中第一个位的位置，这使您可以了解不同项目数量的大小。

3. HyperLogLog将可能的哈希值的范围分为多个存储桶或寄存器。每个寄存器都跟踪对该寄存器的任何项目观察到的最多的领先零。

4. 处理所有项目后，HyperLogLog结合了所有寄存器的信息以计算基数的估计。登记率越多，观察到的领先零的数量越高，估计值就越准确。

HyperLogLog提供了一个误差范围的估计值。错误率取决于算法中使用的寄存器数量。使用的寄存器越多，误差余量越小，但内存使用量越高。可以根据应用程序的需求进行微调进行微调。

优势

以下是使用超置槽的一些关键优势。

空间复杂性

与需要存储每个唯一项目的传统方法不同，HyperLoglog使用固定数量的内存，与不同项目的数量对数缩放。这使其非常适合大规模数据集。

时间复杂性

在处理速度方面，HyperLogLog高效。它需要为处理的每个项目持续时间，使其适用于实时或流媒体应用程序。

可伸缩性

HyperLogLog与大型数据集相当良好，并且经常用于分布式系统或数据处理框架中，其中需要大量数据。

简单

该算法相对简单实现，并且不需要复杂的数据结构或操作。

其他方法

还有其他几种用于基数估计的方法，例如计数米草图和Bloom过滤器。尽管这些方法中的每一种都具有其优势，但HyperLoglog在准确性和空间复杂性之间的平衡方面脱颖而出。

布卢姆过滤器

Bloom过滤器非常适合检查是否存在物品，但它们没有提供基数估计。另一方面，HyperLogLog可以估计基数，而无需存储所有物品。

计数素描

这是用于频率估计的概率数据结构，但是在基数估计中，它需要比超置槽更多的存储器。

结论

HyperLogLog是一种非常有效且准确的算法，用于估计大数据集中的基数。利用概率技术和哈希功能将允许使用最少的内存使用量处理大数据，这使其成为数据分析，分布式系统和流数据应用程序的必不可少的工具。