基數(shù)是數(shù)據(jù)集中不同項目的數(shù)量。無論是計算網(wǎng)站上的唯一用戶數(shù)量還是估計不同搜索查詢的數(shù)量，估計基數(shù)在處理大量數(shù)據(jù)集時都變得具有挑戰(zhàn)性。這就是超置式算法進入圖片的地方。在本文中，我們將探討HyperLoglog及其應用程序背后的關鍵概念。

Hyperloglog

HyperLogLog是一種概率算法，旨在估計具有高精度和低內(nèi)存使用情況的數(shù)據(jù)集的基數(shù)。

計算不同項目的傳統(tǒng)方法需要存儲到目前為止所看到的所有項目，例如將所有用戶信息存儲在用戶數(shù)據(jù)集中，這可以快速消耗大量內(nèi)存。另一方面，HyperLogLog使用固定數(shù)量的內(nèi)存，幾千字節(jié)，并且仍然提供了對基數(shù)的準確估計，使其非常適合大規(guī)模數(shù)據(jù)分析。

用例

在以下情況下，HyperLogLog特別有用：

有限的內(nèi)存

如果使用大量數(shù)據(jù)集(例如數(shù)百萬用戶或網(wǎng)絡流量數(shù)據(jù)的日志)，則由于內(nèi)存限制，存儲每個唯一項目可能是不可行的。

近似計數(shù)

在許多情況下，不需要確切的計數(shù)，并且良好的估計是足夠的。 HyperlogLog給出了一個估計值，該估計值與真實值足夠接近，而沒有精確計算的開銷。

流數(shù)據(jù)

當使用連續(xù)的數(shù)據(jù)流(例如實時網(wǎng)站流量或社交媒體供稿)時，超置換件可以更新其估算值，而無需重新訪問過去的數(shù)據(jù)。

一些值得注意的應用程序用例包括以下內(nèi)容：

· Web分析：估計訪問網(wǎng)站的唯一用戶數(shù)量。

· 社交媒體分析：計算社交媒體流中獨特的主題標簽，提及或其他不同項目。

· 數(shù)據(jù)庫系統(tǒng)：有效地計數(shù)大型數(shù)據(jù)庫中的不同鍵或值。

· 大數(shù)據(jù)系統(tǒng)：諸如Apache Hadoop和Apache Spark之類的框架使用HyperLoglog來計算大數(shù)據(jù)管道中的不同項目。

· 網(wǎng)絡監(jiān)控：估計網(wǎng)絡流量分析中不同IP地址或數(shù)據(jù)包的數(shù)量。

現(xiàn)有實現(xiàn)

HyperLoglog已以各種語言和數(shù)據(jù)處理框架實現(xiàn)。一些實現(xiàn)超閘紙的流行工具如下：

· REDIS提供了HyperLogLog的本機實現(xiàn)PFADD，以通過PFCOUNT和PFMERGE命令進行近似的基數(shù)估算。 REDIS允許用戶在消耗最小內(nèi)存的同時有效地跟蹤數(shù)據(jù)集中的獨特項目。

· Google BigQuery提供了一個名為的內(nèi)置函數(shù)APPROX_COUNT_DISTINCT，該功能使用超置logog來估計大數(shù)據(jù)集中不同項目的數(shù)量。 BigQuery通過使用HyperLoglog來提供高效的心臟估算，而無需全部數(shù)據(jù)來優(yōu)化查詢處理。

· Apache DataSketches是用于近似計算的算法集合，包括HyperLogLog。它是在Java中實現(xiàn)的，通常用于用于大規(guī)模數(shù)據(jù)處理的分布式計算環(huán)境中。

· Python軟件包HyperlogLog 是 超置池的實現(xiàn)，可讓您計算具有較小內(nèi)存足跡的數(shù)據(jù)集的近似基數(shù)。

· 該函數(shù)approx_count_distinct可在Pyspark的DataFrame API中獲得，并用于計算數(shù)據(jù)框列中不同值的近似計數(shù)。它基于HyperLogLog算法，提供了一種高度記憶有效的估計不同計數(shù)的方法。

示例用法

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背后的基本思想是使用哈希功能將數(shù)據(jù)集中的每個項目映射到一系列值的位置。通過分析這些項目的位置，該算法可以估計存在多少不同的項目而不明確存儲它們。這是其工作原理的分步分類：

1. 集合中的每個項目都使用哈希函數(shù)進行哈希。哈希函數(shù)的輸出是二進制字符串。

2. HyperLogLog專注于哈希值的二進制表示中的領先零。領先的零，值越稀有。具體來說，跟蹤了哈希中第一個位的位置，這使您可以了解不同項目數(shù)量的大小。

3. HyperLogLog將可能的哈希值的范圍分為多個存儲桶或寄存器。每個寄存器都跟蹤對該寄存器的任何項目觀察到的最多的領先零。

4. 處理所有項目后，HyperLogLog結合了所有寄存器的信息以計算基數(shù)的估計。登記率越多，觀察到的領先零的數(shù)量越高，估計值就越準確。

HyperLogLog提供了一個誤差范圍的估計值。錯誤率取決于算法中使用的寄存器數(shù)量。使用的寄存器越多，誤差余量越小，但內(nèi)存使用量越高。可以根據(jù)應用程序的需求進行微調(diào)進行微調(diào)。

優(yōu)勢

以下是使用超置槽的一些關鍵優(yōu)勢。

空間復雜性

與需要存儲每個唯一項目的傳統(tǒng)方法不同，HyperLoglog使用固定數(shù)量的內(nèi)存，與不同項目的數(shù)量對數(shù)縮放。這使其非常適合大規(guī)模數(shù)據(jù)集。

時間復雜性

在處理速度方面，HyperLogLog高效。它需要為處理的每個項目持續(xù)時間，使其適用于實時或流媒體應用程序。

可伸縮性

HyperLogLog與大型數(shù)據(jù)集相當良好，并且經(jīng)常用于分布式系統(tǒng)或數(shù)據(jù)處理框架中，其中需要大量數(shù)據(jù)。

簡單

該算法相對簡單實現(xiàn)，并且不需要復雜的數(shù)據(jù)結構或操作。

其他方法

還有其他幾種用于基數(shù)估計的方法，例如計數(shù)米草圖和Bloom過濾器。盡管這些方法中的每一種都具有其優(yōu)勢，但HyperLoglog在準確性和空間復雜性之間的平衡方面脫穎而出。

布盧姆過濾器

Bloom過濾器非常適合檢查是否存在物品，但它們沒有提供基數(shù)估計。另一方面，HyperLogLog可以估計基數(shù)，而無需存儲所有物品。

計數(shù)素描

這是用于頻率估計的概率數(shù)據(jù)結構，但是在基數(shù)估計中，它需要比超置槽更多的存儲器。

結論

HyperLogLog是一種非常有效且準確的算法，用于估計大數(shù)據(jù)集中的基數(shù)。利用概率技術和哈希功能將允許使用最少的內(nèi)存使用量處理大數(shù)據(jù)，這使其成為數(shù)據(jù)分析，分布式系統(tǒng)和流數(shù)據(jù)應用程序的必不可少的工具。