.. figure:: https://raw.github.com/spotify/annoy/master/ann.png
:alt: Annoy 示例
:align: center
.. image:: https://github.com/spotify/annoy/actions/workflows/ci.yml/badge.svg
:target: https://github.com/spotify/annoy/actions
Annoy (Approximate Nearest Neighbors <http://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor> Oh Yeah) 是一个带有 Python 绑定的 C++ 库，用于搜索空间中接近给定查询点的点。它还能创建基于文件的、大型只读数据结构，这些结构通过 mmap <https://en.wikipedia.org/wiki/Mmap> 映射到内存中，以便多个进程可以共享相同的数据。
要安装，只需执行 pip install --user annoy 即可从 PyPI <https://pypi.python.org/pypi/annoy>_ 拉取最新版本。
对于 C++ 版本，只需克隆仓库并 #include "annoylib.h"。
有一些其他库可以进行最近邻搜索。Annoy 的速度几乎与最快的库相当（见下文），但实际上还有一个特性真正让 Annoy 脱颖而出：它能够使用静态文件作为索引。特别是，这意味着你可以跨进程共享索引。Annoy 还将创建索引与加载索引解耦，因此你可以将索引作为文件传递，并快速映射到内存中。Annoy 的另一个优点是它试图最小化内存占用，因此索引非常小。
这有什么用？如果你想找到最近邻并且拥有多个 CPU，你只需要构建一次索引。你还可以在生产环境、Hadoop 作业等中传递和分发静态文件。任何进程都能够将索引加载（mmap）到内存中，并立即进行查找。
我们在 Spotify <http://www.spotify.com/>__ 将其用于音乐推荐。在运行矩阵分解算法后，每个用户/项目都可以表示为 f 维空间中的一个向量。这个库帮助我们搜索相似的用户/项目。我们在高维空间中有数百万首曲目，因此内存使用是一个主要关注点。
Annoy 是由 Erik Bernhardsson <http://www.erikbern.com> 在 Hack Week <http://labs.spotify.com/2013/02/15/organizing-a-hack-week/> 期间的几个下午构建的。
欧几里得距离 <https://en.wikipedia.org/wiki/Euclidean_distance>、曼哈顿距离 <https://en.wikipedia.org/wiki/Taxicab_geometry>、余弦距离 <https://en.wikipedia.org/wiki/Cosine_similarity>、汉明距离 <https://en.wikipedia.org/wiki/Hamming_distance> 或 点积（内积）距离 <https://en.wikipedia.org/wiki/Dot_product>__Rene Hollander <https://github.com/ReneHollander>__ 贡献）.. code-block:: python
from annoy import AnnoyIndex
import random
f = 40 # 将被索引的项目向量的长度
t = AnnoyIndex(f, 'angular')
for i in range(1000):
v = [random.gauss(0, 1) for z in range(f)]
t.add_item(i, v)
t.build(10) # 10 棵树
t.save('test.ann')
# ...
u = AnnoyIndex(f, 'angular')
u.load('test.ann') # 超快，只会 mmap 文件
print(u.get_nns_by_item(0, 1000)) # 将找到 1000 个最近邻
目前，它只接受整数作为项目的标识符。请注意，它会为 max(id)+1 个项目分配内存，因为它假定你的项目编号为 0 … n-1。如果你需要其他 ID，你需要自己维护一个映射关系。
AnnoyIndex(f, metric) 返回一个新的读写索引，存储 f 维向量。度量标准可以是 "angular"、"euclidean"、"manhattan"、"hamming" 或 "dot"。a.add_item(i, v) 添加项目 i（任意非负整数）及其向量 v。注意，它会为 max(i)+1 个项目分配内存。a.build(n_trees, n_jobs=-1) 构建一个包含 n_trees 棵树的森林。树越多，查询精度越高。调用 build 后，无法再添加项目。n_jobs 指定用于构建树的线程数。n_jobs=-1 使用所有可用的 CPU 核心。a.save(fn, prefault=False) 将索引保存到磁盘并加载它（参见下一个函数）。保存后，无法再添加项目。a.load(fn, prefault=False) 从磁盘加载（mmap）索引。如果 prefault 设置为 True，它将预读整个文件到内存中（使用带有 MAP_POPULATE 的 mmap）。默认为 False。a.unload() 卸载索引。a.get_nns_by_item(i, n, search_k=-1, include_distances=False) 返回 n 个最近的项目。在查询过程中，它将检查最多 search_k 个节点，如果未提供，则默认为 n_trees * n。search_k 让你在更好的准确性和速度之间进行运行时权衡。如果你将 include_distances 设置为 True，它将返回一个包含两个列表的二元组：第二个列表包含所有对应的距离。a.get_nns_by_vector(v, n, search_k=-1, include_distances=False) 相同，但通过向量 v 查询。a.get_item_vector(i) 返回先前添加的项目 i 的向量。a.get_distance(i, j) 返回项目 i 和 j 之间的距离。注意：在 2016 年 8 月之前，此函数返回的是平方距离，但此后已更改。a.get_n_items() 返回索引中的项目数量。a.get_n_trees() 返回索引中的树的数量。a.on_disk_build(fn) 准备 Annoy 在指定文件中构建索引，而不是在 RAM 中（在添加项目之前执行，构建后无需保存）。a.set_seed(seed) 将使用给定的种子初始化随机数生成器。仅用于构建树，即仅在添加项目之前需要传递此参数。在调用 a.build(n_trees) 或 a.load(fn) 后将不起作用。注意：
sqrt(2(1-cos(u,v)))。C++ API 非常相似：只需 #include "annoylib.h" 即可访问。
调整 Annoy 只需要两个主要参数：树的数量 n_trees 和搜索期间要检查的节点数 search_k。
n_trees 在构建时提供，影响构建时间和索引大小。较大的值会给出更准确的结果，但索引也更大。search_k 在运行时提供，影响搜索性能。较大的值会给出更准确的结果，但返回时间更长。如果未提供 search_k，它将默认为 n * n_trees，其中 n 是近似最近邻的数量。否则，search_k 和 n_trees 大致独立，即，如果 search_k 保持不变，n_trees 的值不会影响搜索时间，反之亦然。基本上，建议在你能承受的内存范围内将 n_trees 设置得尽可能大，并且建议在查询时间限制内将 search_k 设置得尽可能大。
你也可以接受较慢的搜索时间，以换取更短的加载时间、更低的内存使用和磁盘 IO。在支持的平台上，索引在 load 和 save 期间会进行预取，导致文件被预先从磁盘读入内存。如果你将 prefault 设置为 False，则 mmap 索引的页面将按需从磁盘读取并缓存在内存中，这是完成搜索所必需的。这可能会显著增加早期搜索时间，但对于内存相对于索引大小较低、对加载的索引执行的查询很少，和/或索引的大部分区域不太可能与搜索查询相关的情况，可能更合适。
使用 随机投影 <http://en.wikipedia.org/wiki/Locality-sensitive_hashing#Random_projection>__ 并通过构建树来实现。在树中的每个中间节点处，选择一个随机超平面，将空间划分为两个子空间。这个超平面是通过从子集中采样两个点并取与它们等距的超平面来选择的。
我们这样做 k 次，以便得到一个森林。k 需要根据你的需求进行调整，通过观察你在精度和性能之间的权衡。
汉明距离（由 Martin Aumüller <https://github.com/maumueller>__ 贡献）在底层将数据打包成 64 位整数，并使用内置的位计数原语，因此可能非常快。所有分割都是轴对齐的。
点积距离（由 Peter Sobot <https://github.com/psobot> 和 Pavel Korobov <https://github.com/pkorobov> 贡献）使用 微软研究院的 Bachrach 等人于 2014 年发表的方法 <https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/XboxInnerProduct.pdf>__，将提供的向量从点积（或“内积”）空间转换为更易于查询的余弦空间。
Dirk Eddelbuettel <https://github.com/eddelbuettel> 提供了 Annoy 的 R 语言版本 <http://dirk.eddelbuettel.com/code/rcpp.annoy.html>。Andy Sloane <https://github.com/a1k0n> 提供了 Annoy 的 Java 版本 <https://github.com/spotify/annoy-java>，但目前仅限于余弦距离和只读模式。Pishen Tsai <https://github.com/pishen> 提供了 Annoy 的 Scala 包装器 <https://github.com/pishen/annoy4s>，它使用 JNA 调用 Annoy 的 C++ 库。Atsushi Tatsuma <https://github.com/yoshoku> 提供了 Annoy 的 Ruby 绑定 <https://github.com/yoshoku/annoy.rb>。Taneli Leppä <https://github.com/rosmo> 提供了 Go 的实验性支持 <https://github.com/spotify/annoy/blob/master/README_GO.rst>。Boris Nagaev <https://github.com/starius> 编写了 Lua 绑定 <https://github.com/spotify/annoy/blob/master/README_Lua.md>。Jim Kang <https://github.com/jimkang> 为 Annoy 编写了 Node 绑定 <https://github.com/jimkang/annoy-node>。Min-Seok Kim <https://github.com/mskimm> 构建了 Annoy 的 Scala 版本 <https://github.com/mskimm/ann4s>。hanabi1224 <https://github.com/hanabi1224> 构建了 Annoy 的只读 Rust 版本 <https://github.com/hanabi1224/RuAnnoy>，以及 dotnet、jvm 和 dart 的只读绑定。演示文稿 <http://www.slideshare.net/erikbern/approximate-nearest-neighbor-methods-and-vector-models-nyc-ml-meetup>__ 关于 Annoyconda 包 <https://anaconda.org/conda-forge/python-annoy>__ 提供。ann-benchmarks <https://github.com/erikbern/ann-benchmarks>__ 是几个近似最近邻库的基准测试。Annoy 似乎相当有竞争力，尤其是在较高精度下：.. figure:: https://raw.githubusercontent.com/erikbern/ann-benchmarks/main/results/glove-100-angular.png
:alt: ANN 基准测试
:align: center
:target: https://github.com/erikbern/ann-benchmarks
全部用 C++ 编写，并包含一些针对性能和内存使用的丑陋优化。你已被警告 :)
代码应该支持 Windows，这要感谢 Qiang Kou <https://github.com/thirdwing> 和 Timothy Riley <https://github.com/tjrileywisc>。
要运行测试，请执行 python setup.py nosetests。测试套件包含一个从互联网下载的大型真实世界数据集，因此需要几分钟才能执行。
欢迎将任何问题或评论发布到 annoy-user <https://groups.google.com/group/annoy-user> 群组。我在 Twitter 上是 @fulhack <https://twitter.com/fulhack>。