datasketch：大数据看起来很小

.. image:: https://static.pepy.tech/badge/datasketch/month :target: https://pepy.tech/project/datasketch

.. image:: https://zenodo.org/badge/DOI/10.5281/zenodo.598238.svg :target: https://zenodo.org/doi/10.5281/zenodo.598238

.. image:: https://codecov.io/gh/ekzhu/datasketch/branch/master/graph/badge.svg :target: https://codecov.io/gh/ekzhu/datasketch

datasketch 提供了概率数据结构，能够在几乎不损失精度的情况下，以极快的速度处理和搜索海量数据。

该包包含以下数据草图：

+-------------------------+-----------------------------------------------+ | 数据草图 | 用途 | +=========================+===============================================+ | MinHash_ | 估计 Jaccard 相似度和基数 | +-------------------------+-----------------------------------------------+ | Weighted MinHash_ | 估计加权 Jaccard 相似度 | +-------------------------+-----------------------------------------------+ | HyperLogLog_ | 估计基数 | +-------------------------+-----------------------------------------------+ | HyperLogLog++_ | 估计基数 | +-------------------------+-----------------------------------------------+

为了支持亚线性查询时间，提供了以下数据草图的索引：

+---------------------------+-----------------------------+------------------------+ | 索引 | 适用于数据草图 | 支持的查询类型 | +===========================+=============================+========================+ | MinHash LSH_ | MinHash、Weighted MinHash | Jaccard 阈值 | +---------------------------+-----------------------------+------------------------+ | LSHBloom_ | MinHash、Weighted MinHash | Jaccard 阈值 | +---------------------------+-----------------------------+------------------------+ | MinHash LSH Forest_ | MinHash、Weighted MinHash | Jaccard Top-K | +---------------------------+-----------------------------+------------------------+ | MinHash LSH Ensemble_ | MinHash | 包含性阈值 | +---------------------------+-----------------------------+------------------------+ | HNSW_ | 任何 | 自定义度量 Top-K | +---------------------------+-----------------------------+------------------------+

datasketch 必须与 Python 3.9 或更高版本、NumPy 1.11 或更高版本以及 Scipy 一起使用。

请注意，MinHash LSH_ 和 MinHash LSH Ensemble_ 还支持 Redis 和 Cassandra 存储层（参见 MinHash LSH at Scale_）。

安装

要使用 pip 安装 datasketch：

.. code-block:: bash

pip install datasketch

这也会将 NumPy 作为依赖项一起安装。

若需安装 Redis 依赖项：

.. code-block:: bash

pip install datasketch[redis]

若需安装 Cassandra 依赖项：

.. code-block:: bash

pip install datasketch[cassandra]

若需安装 Bloom 过滤器依赖项：

.. code-block:: bash

pip install datasketch[bloom]

.. _MinHash: https://ekzhu.github.io/datasketch/minhash.html .. _Weighted MinHash: https://ekzhu.github.io/datasketch/weightedminhash.html .. _HyperLogLog: https://ekzhu.github.io/datasketch/hyperloglog.html .. _HyperLogLog++: https://ekzhu.github.io/datasketch/hyperloglog.html#hyperloglog-plusplus .. _MinHash LSH: https://ekzhu.github.io/datasketch/lsh.html .. _MinHash LSH Forest: https://ekzhu.github.io/datasketch/lshforest.html .. _MinHash LSH Ensemble: https://ekzhu.github.io/datasketch/lshensemble.html .. _LSHBloom: https://ekzhu.github.io/datasketch/lshbloom.html .. _Minhash LSH at Scale: http://ekzhu.github.io/datasketch/lsh.html#minhash-lsh-at-scale .. _HNSW: https://ekzhu.github.io/datasketch/documentation.html#hnsw

贡献

我们欢迎所有人的贡献。无论您是修复错误、添加功能、改进文档，还是协助测试，您的贡献都十分宝贵。

开发环境设置 ^^^^^^^^^^^^^^^^^

该项目使用 uv 进行快速可靠的 Python 包管理。请按照以下步骤设置您的开发环境：

1. 安装 uv：请按照官方安装指南 https://docs.astral.sh/uv/getting-started/installation/ 进行安装。

2. 克隆仓库：

   .. code-block:: bash

   git clone https://github.com/ekzhu/datasketch.git
   cd datasketch
   

3. 设置环境：

   .. code-block:: bash

   # 创建虚拟环境
   # （可选：指定 Python 版本，如 --python 3.x）
   uv venv
   # 激活虚拟环境（可选，uv run 命令无需激活即可运行）
   source .venv/bin/activate
   
   # 安装所有依赖项
   uv sync
   

4. 验证安装：

   .. code-block:: bash

   # 运行测试以确保一切正常
   uv run pytest
   

5. 可选依赖项（用于特定开发需求）：

   .. code-block:: bash

   # 用于测试
   uv sync --extra test
   
   # 用于 Cassandra 支持
   uv sync --extra cassandra
   
   # 用于 Redis 支持
   uv sync --extra redis
   
   # 安装所有额外依赖项
   uv sync --all-extras
   

更多关于 uv 的信息，请访问 https://docs.astral.sh/uv/

开发流程 ^^^^^^^^^^^^^^^^

1. 如果您尚未在 GitHub 上 fork 该仓库，请先进行 fork。

2. 为您的更改创建特性分支：

   .. code-block:: bash

   git checkout -b feature/your-feature-name
   # 或者用于修复 bug：
   git checkout -b fix/issue-description
   

3. 按照项目的编码规范进行更改。

4. 运行测试，以确保没有破坏现有功能：

   .. code-block:: bash

   uv run pytest
   

5. 使用 ruff 检查代码质量：

   .. code-block:: bash

   # 检查问题
   uvx ruff check .
   
   # 自动修复格式问题
   uvx ruff format .
   

6. 提交更改，并附上清晰、描述性的提交信息：

   .. code-block:: bash

   git commit -m "添加功能：简要说明更改内容"
   

7. 推送到您的 fork，并在 GitHub 上创建拉取请求：

   .. code-block:: bash

   git push origin your-branch-name
   

8. 响应维护者的反馈，并迭代修改您的更改。

指导原则 ^^^^^^^^^^

• 遵循 PEP 8 代码风格指南
• 为新功能编写测试
• 根据需要更新文档
• 保持提交内容专注且原子化
• 在讨论中保持尊重

如需更多信息，请查看 GitHub issues <https://github.com/ekzhu/datasketch/issues>，了解当前的优先级或需要帮助的领域。您也可以加入关于 项目路线图和优先级 <https://github.com/ekzhu/datasketch/discussions/252> 的讨论。

datasketch 快速上手指南

datasketch 是一个提供概率数据结构的 Python 库，能够以极快的速度处理海量数据，同时保持极高的准确度。它适用于估算集合相似度（Jaccard）、基数统计等场景。

环境准备

在开始之前，请确保您的开发环境满足以下要求：

• Python 版本：3.9 或更高版本
• 核心依赖：
  • NumPy >= 1.11
  • Scipy
• 可选依赖（根据需求安装）：
  • Redis（用于分布式存储）
  • Cassandra（用于分布式存储）
  • Bloom Filter（用于特定索引）

安装步骤

推荐使用 pip 进行安装。国内开发者建议使用清华或阿里镜像源以加速下载。

1. 基础安装

安装核心功能及 NumPy 依赖：

pip install datasketch -i https://pypi.tuna.tsinghua.edu.cn/simple

2. 安装可选扩展

如果您需要使用特定的存储后端或功能，请使用以下命令：

• 支持 Redis：

  pip install "datasketch[redis]" -i https://pypi.tuna.tsinghua.edu.cn/simple
  

• 支持 Cassandra：

  pip install "datasketch[cassandra]" -i https://pypi.tuna.tsinghua.edu.cn/simple
  

• 支持 Bloom Filter：

  pip install "datasketch[bloom]" -i https://pypi.tuna.tsinghua.edu.cn/simple
  

基本使用

以下示例展示如何使用 MinHash 估算两个集合的 Jaccard 相似度。这是 datasketch 最核心的功能之一。

from datasketch import MinHash

# 定义两个数据集（模拟文档或集合）
data1 = ['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for', 'estimating', 'the', 'similarity', 'between', 'datasets']
data2 = ['minhash', 'is', 'a', 'probability', 'data', 'structure', 'for', 'estimating', 'the', 'similarity', 'between', 'documents']

# 初始化 MinHash 对象 (num_perm 表示哈希函数的数量，通常设为 128)
m1 = MinHash(num_perm=128)
m2 = MinHash(num_perm=128)

# 更新数据
for d in data1:
    m1.update(d.encode('utf8'))

for d in data2:
    m2.update(d.encode('utf8'))

# 估算 Jaccard 相似度
similarity = m1.jaccard(m2)

print(f"Estimated Jaccard similarity: {similarity}")

说明：

• update() 方法用于逐个添加数据项（需编码为 bytes）。
• jaccard() 方法返回两个 sketch 之间的估算相似度（0.0 到 1.0 之间）。
• 对于海量数据，该方法比精确计算快数个数量级，且内存占用极低。