faiss_lsh.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPtcdxIsfGa0nMGfLO8Vc5k",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/weedge/doraemon-nb/blob/main/faiss_lsh.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "1. https://www.pinecone.io/learn/series/faiss/locality-sensitive-hashing/\n",
        "2. https://www.youtube.com/watch?v=e_SBq3s20M8\n"
      ],
      "metadata": {
        "id": "WXFmc_x0eKAL"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!apt install libomp-dev\n",
        "!pip install --upgrade faiss-cpu faiss-gpu\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lHcvAv2deJpA",
        "outputId": "aa005d63-17e0-4484-ce24-2859da9f39c5"
      },
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Reading package lists... Done\n",
            "Building dependency tree... Done\n",
            "Reading state information... Done\n",
            "The following additional packages will be installed:\n",
            "  libomp-14-dev libomp5-14\n",
            "Suggested packages:\n",
            "  libomp-14-doc\n",
            "The following NEW packages will be installed:\n",
            "  libomp-14-dev libomp-dev libomp5-14\n",
            "0 upgraded, 3 newly installed, 0 to remove and 18 not upgraded.\n",
            "Need to get 738 kB of archives.\n",
            "After this operation, 8,991 kB of additional disk space will be used.\n",
            "Get:1 http://archive.ubuntu.com/ubuntu jammy-updates/universe amd64 libomp5-14 amd64 1:14.0.0-1ubuntu1.1 [389 kB]\n",
            "Get:2 http://archive.ubuntu.com/ubuntu jammy-updates/universe amd64 libomp-14-dev amd64 1:14.0.0-1ubuntu1.1 [347 kB]\n",
            "Get:3 http://archive.ubuntu.com/ubuntu jammy/universe amd64 libomp-dev amd64 1:14.0-55~exp2 [3,074 B]\n",
            "Fetched 738 kB in 0s (1,480 kB/s)\n",
            "Selecting previously unselected package libomp5-14:amd64.\n",
            "(Reading database ... 120895 files and directories currently installed.)\n",
            "Preparing to unpack .../libomp5-14_1%3a14.0.0-1ubuntu1.1_amd64.deb ...\n",
            "Unpacking libomp5-14:amd64 (1:14.0.0-1ubuntu1.1) ...\n",
            "Selecting previously unselected package libomp-14-dev.\n",
            "Preparing to unpack .../libomp-14-dev_1%3a14.0.0-1ubuntu1.1_amd64.deb ...\n",
            "Unpacking libomp-14-dev (1:14.0.0-1ubuntu1.1) ...\n",
            "Selecting previously unselected package libomp-dev:amd64.\n",
            "Preparing to unpack .../libomp-dev_1%3a14.0-55~exp2_amd64.deb ...\n",
            "Unpacking libomp-dev:amd64 (1:14.0-55~exp2) ...\n",
            "Setting up libomp5-14:amd64 (1:14.0.0-1ubuntu1.1) ...\n",
            "Setting up libomp-14-dev (1:14.0.0-1ubuntu1.1) ...\n",
            "Setting up libomp-dev:amd64 (1:14.0-55~exp2) ...\n",
            "Processing triggers for libc-bin (2.35-0ubuntu3.1) ...\n",
            "/sbin/ldconfig.real: /usr/local/lib/libtbbmalloc.so.2 is not a symbolic link\n",
            "\n",
            "/sbin/ldconfig.real: /usr/local/lib/libtbbbind.so.3 is not a symbolic link\n",
            "\n",
            "/sbin/ldconfig.real: /usr/local/lib/libtbbbind_2_0.so.3 is not a symbolic link\n",
            "\n",
            "/sbin/ldconfig.real: /usr/local/lib/libtbb.so.12 is not a symbolic link\n",
            "\n",
            "/sbin/ldconfig.real: /usr/local/lib/libtbbmalloc_proxy.so.2 is not a symbolic link\n",
            "\n",
            "/sbin/ldconfig.real: /usr/local/lib/libtbbbind_2_5.so.3 is not a symbolic link\n",
            "\n",
            "Collecting faiss-cpu\n",
            "  Downloading faiss_cpu-1.7.4-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (17.6 MB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m17.6/17.6 MB\u001b[0m \u001b[31m52.5 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hCollecting faiss-gpu\n",
            "  Downloading faiss_gpu-1.7.2-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (85.5 MB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m85.5/85.5 MB\u001b[0m \u001b[31m9.1 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hInstalling collected packages: faiss-gpu, faiss-cpu\n",
            "Successfully installed faiss-cpu-1.7.4 faiss-gpu-1.7.2\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 介绍\n",
        "\n",
        "局部敏感哈希 (LSH)是近似最近邻 (ANN) 搜索中广泛使用的技术。高效相似性搜索的解决方案是一种有利可图的解决方案——它是数十亿（甚至数万亿）美元公司的核心。\n",
        "\n",
        "谷歌、Netflix、亚马逊、Spotify、Uber 等大公司的许多核心功能都依赖相似性搜索。\n",
        "\n",
        "亚马逊使用相似性搜索来比较客户，根据最相似客户的购买历史找到新产品推荐。\n",
        "\n",
        "每次使用 Google 时，您都会在查询/搜索词与 Google 索引的互联网之间执行相似性搜索。\n",
        "\n",
        "如果 Spotify 成功地推荐了好音乐，那是因为他们的相似性搜索算法成功地将您与具有类似良好（或不太好）音乐品味的其他客户匹配。\n",
        "\n",
        "LSH 是产生高质量搜索的原始技术之一，同时保持闪电般的快速搜索速度。在本文中，我们将介绍该算法背后的理论，以及易于理解的 Python 实现！\n",
        "\n"
      ],
      "metadata": {
        "id": "are8-Rj7eIDh"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 搜索复杂性\n",
        "一个包含数百万甚至数十亿个样本的数据集——我们如何有效地比较所有这些样本？\n",
        "\n",
        "即使在最好的硬件上，比较所有对也是不可能的。这产生的最佳复杂度为 O(n²)。即使将单个查询与数十亿个样本进行比较，我们仍然返回 O(n) 的最佳复杂度。\n",
        "\n",
        "我们还需要考虑单个相似性计算背后的复杂性——每个样本都存储为一个向量，通常是非常高维的向量——这进一步增加了我们的复杂性。\n",
        "\n",
        "我们怎样才能避免这种情况呢？是否有可能执行亚线性复杂度的搜索？是的！\n",
        "\n",
        "解决方案是近似搜索。我们可以近似并将搜索范围限制为最相关的向量，而不是比较每个向量（穷举搜索）。\n",
        "\n",
        "LSH 是一种为我们提供次线性搜索时间的算法。在本文中，我们将介绍 LSH 并了解其魔法背后的逻辑。\n",
        "\n",
        "## 局部敏感哈希\n",
        "\n",
        "当我们考虑[查找相似向量](https://www.pinecone.io/learn/series/nlp/dense-vector-embeddings-nlp/)的复杂性时，我们发现即使数据集相当小，比较所有内容所需的计算量也非常巨大。\n",
        "\n",
        "让我们考虑一个向量索引。如果我们只引入一个新向量并尝试找到最接近的匹配，我们必须将该向量与数据库中的每个其他向量进行比较。这给了我们一个*线性时间复杂度*——它无法扩展到更大数据集中的快速搜索。\n",
        "\n",
        "如果我们想要将所有这些向量相互比较，问题就更糟了——实现这一点的最佳排序方法至多是对*数线性时间复杂度*。\n",
        "\n",
        "所以我们需要一种方法来减少比较次数。理想情况下，我们只想比较我们认为是潜在匹配项或*候选对的*向量。\n",
        "\n",
        "局部敏感哈希（LSH）允许我们做到这一点。\n",
        "\n",
        "LSH 由多种不同的方法组成。在本文中，我们将介绍传统方法（由多个步骤组成）、shingling、MinHashing 和最终的banded LSH 函数。\n",
        "\n",
        "从本质上讲，最终的 LSH 函数允许我们对同一样本进行多次分段和哈希处理。*当我们发现一对向量至少一次*被哈希为相同的值时，我们将它们标记为*候选对*- 即*潜在*匹配。\n",
        "\n",
        "这是一个与 Python 字典中使用的过程非常相似的过程。我们有一个键值对，我们将其输入字典中。键通过字典哈希函数处理并映射到特定的桶。然后我们将相应的值连接到该存储桶。\n",
        "\n",
        "![典型的哈希函数旨在将不同的值（无论多么相似）放入不同的桶中。](https://cdn.sanity.io/images/vr8gru94/production/faaae9e55d33b08629574243d8456446650df096-1400x787.png)\n",
        "\n",
        "典型的哈希函数旨在将不同的值（无论多么相似）放入不同的桶中。\n",
        "\n",
        "然而，这种类型的哈希函数与 LSH 中使用的哈希函数有一个关键的区别。对于字典，我们的目标是最大限度地减少多个键值映射到同一个存储桶的机会 - 我们最大限度地*减少冲突*。\n",
        "\n",
        "LSH 几乎相反。在 LSH 中，我们希望*最大化碰撞*——尽管理想情况下仅适用于*相似的*输入。\n",
        "\n",
        "![LSH 函数旨在将相似的值放入相同的存储桶中。](https://cdn.sanity.io/images/vr8gru94/production/862f88182a796eb16942c47d93ee03ba4cdaee4d-1920x1080.png)\n",
        "\n",
        "LSH 函数旨在将相似的值放入相同的存储桶中。\n",
        "\n",
        "LSH 中没有*单一的*散列方法。事实上，它们都共享相同的*“通过哈希函数存储相似样本”*逻辑，但除此之外它们可能有很大差异。\n",
        "\n",
        "我们已经简要描述并将在本文的其余部分中介绍的方法可以被描述为*传统*方法，使用*shingling*、*MinHashing*和*banding*。\n",
        "\n",
        "还有其他几种技术，例如我们在另一篇文章中介绍的[随机投影。](https://www.pinecone.io/learn/series/faiss/locality-sensitive-hashing-random-projection/)\n",
        "\n",
        "------\n",
        "\n",
        "## Shingling、MinHashing 和 LSH\n",
        "\n",
        "我们正在探索的 LSH 方法由三个步骤组成。*首先，我们使用k-shingling（和 one-hot 编码）*将文本转换为稀疏向量，然后使用*minhashing*创建“签名”——将其传递到我们的 LSH 过程以清除*候选对*。\n",
        "\n",
        "![我们将在本文中讨论 LSH 流程的高级视图。](https://cdn.sanity.io/images/vr8gru94/production/89413953597fbfdd36c4fa77ca0eeafaf6cf944a-1280x980.png)\n",
        "\n",
        "我们将在本文中讨论 LSH 流程的高级视图。\n",
        "\n",
        "我们将在以后的文章中讨论其他一些 LSH 方法。但现在，让我们更深入地了解传统流程。"
      ],
      "metadata": {
        "id": "k9QHuCp3fQuG"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## k-Shingling\n",
        "k-Shingling，或简称 shingling — 是将文本字符串转换为一组“shingles”的过程。该过程类似于沿着文本字符串移动长度为 k 的窗口并在每一步拍照。我们整理所有这些图片来创建我们的shinling 集合。\n",
        "\n",
        "![](https://d33wubrfki0l68.cloudfront.net/80780df0c70ba25ef81de1b0bad918c2a3ed1729/a157b/images/locality-sensitive-hashing-5.mp4)\n",
        "\n",
        "Shingling还可以删除重复的项目（因此称为“集合”）。我们可以在 Python 中创建一个简单的 k-shingling 函数，如下所示：\n",
        "\n"
      ],
      "metadata": {
        "id": "G6aZvg73fldf"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import numpy as np\n",
        "\n",
        "def build_shingles(sentence: str, k: int):\n",
        "    shingles = []\n",
        "    for i in range(len(sentence) - k):\n",
        "        shingles.append(sentence[i:i+k])\n",
        "    return set(shingles)\n",
        "\n",
        "def build_vocab(shingle_sets: list):\n",
        "    # convert list of shingle sets into single set\n",
        "    full_set = {item for set_ in shingle_sets for item in set_}\n",
        "    vocab = {}\n",
        "    for i, shingle in enumerate(list(full_set)):\n",
        "        vocab[shingle] = i\n",
        "    return vocab\n",
        "\n",
        "def one_hot(shingles: set, vocab: dict):\n",
        "    vec = np.zeros(len(vocab))\n",
        "    for shingle in shingles:\n",
        "        idx = vocab[shingle]\n",
        "        vec[idx] = 1\n",
        "    return vec"
      ],
      "metadata": {
        "id": "-7AEHBXje_2i"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": 53,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Hwi9VULLaiwP",
        "outputId": "12a8eb54-639c-420b-a97b-ef94570cc95f"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "{'ly', 'h ', 'io', 'e ', 'fl', 'th', 'sh', ' b', 'at', 'ti', 'le', ' f', 'by', 'ac', 'he', 'fi', 'ew', 'sp', ' t', 'st', 'ng', ' s', 'yi', 'in', 'g ', 'ce', 'w ', 'is', 'pa', 'y ', 'ta'}\n",
            "{'ot', 'di', 'we', 'yo', 'al', 'e ', ' b', ' p', 'ur', ' y', 'il', 't ', ' a', 'r ', 'u ', 'rm', 'to', 'no', ' n', 'ri', 'ou', 'l ', 'lo', 'et', 'ad', 'll', 'o ', ' t', 'on', 'ng', 'in', 'ar', 'pe', 'ma', 'br', 'g ', 'wi', 'w ', 'ow', ' w'}\n",
            "{'ie', 'ha', 'we', 'ca', 'h ', 'e ', 'er', 'ed', 'th', 'tc', 'sh', ' e', 'at', ' p', 'ti', 'po', 'le', 'ur', ' f', 'hi', 'he', ' a', 'am', 'r ', 'gu', ' o', 's ', 'fi', 'ig', 'ol', 'to', 'ew', 'as', 'n ', 'fe', ' c', 'yn', 're', 'o ', 'd ', ' t', 'dy', 'ks', 'st', 'ng', ' s', 'ck', 'ea', 'mi', 'in', 'te', 'f ', 'of', 'ch', 'g ', 'na', 'w ', 'si', 'is', ' d', 'it', ' w', 'a ', 'an', 'ic'}\n",
            "102 {'ly': 0, 'ot': 1, 'al': 2, 'er': 3, ' b': 4, ' p': 5, ' y': 6, 'am': 7, 'gu': 8, 'to': 9, 'sp': 10, 'l ': 11, 'as': 12, 'n ': 13, 'll': 14, 're': 15, 'on': 16, ' s': 17, 'ck': 18, 'ma': 19, 'wi': 20, 'w ': 21, 'si': 22, ' d': 23, ' w': 24, 'ta': 25, 'ic': 26, 'ed': 27, 'fl': 28, 'at': 29, 'ti': 30, 'po': 31, ' f': 32, 'by': 33, 'ac': 34, 't ': 35, ' o': 36, 'ol': 37, 's ': 38, 'fi': 39, 'ig': 40, 'rm': 41, 'ew': 42, 'ri': 43, ' t': 44, 'd ': 45, 'ng': 46, 'ea': 47, 'yi': 48, 'ar': 49, 'pe': 50, 'br': 51, 'f ': 52, 'of': 53, 'na': 54, 'is': 55, 'pa': 56, 'ow': 57, 'it': 58, 'an': 59, 'ha': 60, 'we': 61, 'io': 62, 'yo': 63, 'e ': 64, 'tc': 65, 'sh': 66, 'le': 67, 'ur': 68, 'il': 69, 'he': 70, 'lo': 71, 'et': 72, 'fe': 73, 'ks': 74, 'st': 75, 'in': 76, 'mi': 77, 'ch': 78, 'g ': 79, 'ce': 80, 'a ': 81, 'ie': 82, 'di': 83, 'h ': 84, 'ca': 85, 'th': 86, ' e': 87, 'hi': 88, ' a': 89, 'r ': 90, 'u ': 91, 'no': 92, ' n': 93, 'ou': 94, 'ad': 95, ' c': 96, 'yn': 97, 'o ': 98, 'dy': 99, 'te': 100, 'y ': 101}\n",
            "[1. 0. 0. 0. 1. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 1. 0. 0.\n",
            " 0. 1. 0. 0. 1. 1. 1. 0. 1. 1. 1. 0. 0. 0. 0. 1. 0. 0. 1. 0. 1. 0. 1. 0.\n",
            " 1. 0. 0. 0. 0. 0. 0. 1. 1. 0. 0. 0. 0. 0. 1. 0. 1. 0. 1. 1. 0. 0. 1. 0.\n",
            " 0. 0. 0. 1. 1. 0. 0. 1. 1. 0. 0. 0. 1. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.\n",
            " 0. 0. 0. 0. 0. 1.]\n",
            "[0. 1. 1. 0. 1. 1. 1. 0. 0. 1. 0. 1. 0. 0. 1. 0. 1. 0. 0. 1. 1. 1. 0. 0.\n",
            " 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 1. 0. 1. 1. 0. 1. 0.\n",
            " 0. 1. 1. 1. 0. 0. 0. 0. 0. 1. 0. 0. 0. 1. 0. 1. 1. 0. 0. 0. 1. 1. 0. 1.\n",
            " 1. 0. 0. 0. 1. 0. 0. 1. 0. 0. 0. 1. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 1.\n",
            " 0. 0. 1. 0. 0. 0.]\n",
            "[0. 0. 0. 1. 0. 1. 0. 1. 1. 1. 0. 0. 1. 1. 0. 1. 0. 1. 1. 0. 0. 1. 1. 1.\n",
            " 1. 0. 1. 1. 0. 1. 1. 1. 1. 0. 0. 0. 1. 1. 1. 1. 1. 0. 1. 0. 1. 1. 1. 1.\n",
            " 0. 0. 0. 0. 1. 1. 1. 1. 0. 0. 1. 1. 1. 1. 0. 0. 1. 1. 1. 1. 1. 0. 1. 0.\n",
            " 0. 1. 1. 1. 1. 1. 1. 1. 0. 1. 1. 0. 1. 1. 1. 1. 1. 1. 1. 0. 0. 0. 0. 0.\n",
            " 1. 1. 1. 1. 1. 0.]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "((3, 102),\n",
              " array([[1., 0., 0., 0., 1., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.,\n",
              "         0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 1., 1., 1., 0.,\n",
              "         1., 1., 1., 0., 0., 0., 0., 1., 0., 0., 1., 0., 1., 0., 1., 0.,\n",
              "         1., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0., 0., 0., 1., 0.,\n",
              "         1., 0., 1., 1., 0., 0., 1., 0., 0., 0., 0., 1., 1., 0., 0., 1.,\n",
              "         1., 0., 0., 0., 1., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
              "         0., 0., 0., 0., 0., 1.],\n",
              "        [0., 1., 1., 0., 1., 1., 1., 0., 0., 1., 0., 1., 0., 0., 1., 0.,\n",
              "         1., 0., 0., 1., 1., 1., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0.,\n",
              "         0., 0., 0., 1., 0., 0., 0., 0., 0., 1., 0., 1., 1., 0., 1., 0.,\n",
              "         0., 1., 1., 1., 0., 0., 0., 0., 0., 1., 0., 0., 0., 1., 0., 1.,\n",
              "         1., 0., 0., 0., 1., 1., 0., 1., 1., 0., 0., 0., 1., 0., 0., 1.,\n",
              "         0., 0., 0., 1., 0., 0., 0., 0., 0., 1., 1., 1., 1., 1., 1., 1.,\n",
              "         0., 0., 1., 0., 0., 0.],\n",
              "        [0., 0., 0., 1., 0., 1., 0., 1., 1., 1., 0., 0., 1., 1., 0., 1.,\n",
              "         0., 1., 1., 0., 0., 1., 1., 1., 1., 0., 1., 1., 0., 1., 1., 1.,\n",
              "         1., 0., 0., 0., 1., 1., 1., 1., 1., 0., 1., 0., 1., 1., 1., 1.,\n",
              "         0., 0., 0., 0., 1., 1., 1., 1., 0., 0., 1., 1., 1., 1., 0., 0.,\n",
              "         1., 1., 1., 1., 1., 0., 1., 0., 0., 1., 1., 1., 1., 1., 1., 1.,\n",
              "         0., 1., 1., 0., 1., 1., 1., 1., 1., 1., 1., 0., 0., 0., 0., 0.,\n",
              "         1., 1., 1., 1., 1., 0.]]))"
            ]
          },
          "metadata": {},
          "execution_count": 53
        }
      ],
      "source": [
        "a = \"flying fish flew by the space station\"\n",
        "b = \"we will not allow you to bring your pet armadillo along\"\n",
        "c = \"he figured a few sticks of dynamite were easier than a fishing pole to catch fish\"\n",
        "\n",
        "k = 2\n",
        "a = build_shingles(a, k)\n",
        "b = build_shingles(b, k)\n",
        "c = build_shingles(c, k)\n",
        "#vocab = a.union(b).union(c)\n",
        "vocab = build_vocab([a,b,c])\n",
        "\n",
        "print(a)\n",
        "print(b)\n",
        "print(c)\n",
        "print(len(vocab),vocab)\n",
        "\n",
        "# one-hot encode our shingles\n",
        "a_1hot = one_hot(a, vocab)\n",
        "b_1hot = one_hot(b, vocab)\n",
        "c_1hot = one_hot(c, vocab)\n",
        "print(a_1hot)\n",
        "print(b_1hot)\n",
        "print(c_1hot)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "有了这个，我们就有了shingles。接下来，我们创建稀疏向量。为此，我们首先需要合并所有集合以创建一个大集合，其中包含所有集合中的所有shingles - 我们称之为词汇表（或词汇）。\n",
        "\n",
        "![我们所有的叠瓦集都被合并以创建我们的词汇。](https://cdn.sanity.io/images/vr8gru94/production/3b72d736d96c9da94344668c96a6b9b066522bb6-1280x720.png)\n",
        "\n",
        "*我们所有的shingled集合合并以创建我们的词汇*。\n",
        "\n",
        "我们使用这个词汇来创建每个集合的稀疏向量表示。我们所做的就是创建一个充满零且长度与我们的词汇相同的空向量——然后，我们看看哪些shingle出现在我们的集合中。\n",
        "\n",
        "![为了创建我们的 one-hot 编码，我们的单个 shingle 集与我们的词汇相匹配，这表明我们应该在零向量中放置词汇（我们在代码中使用 shingle-to-index 字典）。](https://cdn.sanity.io/images/vr8gru94/production/c259242606006f5c5505a6e677f3d05be75a26da-1280x720.png)\n",
        "\n",
        "为了创建我们的 one-hot 编码，我们的单个 shingle 集与我们的词汇相匹配，这表明我们应该在零向量中放置词汇（我们在代码中使用 shingle-to-index 字典）。\n",
        "\n",
        "对于出现的每个 shingle，我们识别该 shingle 在我们的词汇表中的位置，并将新的零向量中的相应位置设置为 1。可以认为这是*one-hot 编码*。\n",
        "\n",
        "### 最小哈希\n",
        "\n",
        "Minhashing 是我们过程的下一步，它允许我们将稀疏向量转换为密集向量。现在，作为一个预警——这部分过程最初可能看起来很混乱——但一旦你掌握了它，它就会非常简单。\n",
        "\n",
        "我们有稀疏向量，我们所做的就是为签名中的每个位置（例如，密集向量）随机生成一个 minhash 函数。\n",
        "\n",
        "因此，如果我们想创建一个包含 20 个数字的密集向量/签名，我们将使用 20 个 minhash 函数。\n",
        "\n",
        "现在，这些 MinHash 函数只是数字的随机顺序 - 我们从*1*计数到最终数字（即 len(vocab)）。由于这些数字的顺序已被随机化，因此我们可能会发现数字 1 位于随机化 MinHash 函数的第57位（例如）\n",
        "\n",
        "https://d33wubrfki0l68.cloudfront.net/2b77a22ec9933902bb46e2f19b753654fc58d145/91c4c/images/locality-sensitive-hashing-8.mp4\n",
        "\n",
        "*我们的签名值是通过首先采用随机排列的计数向量（从 1 到 len(vocab)+1）创建的，并找到与稀疏向量中的 1 对齐的最小数字。*\n",
        "\n",
        "上面，我们使用了包含*六个*值的较小词汇，因此我们可以轻松地可视化该过程。\n",
        "\n",
        "我们查看稀疏向量并说：“vocab[1] 处的这个shingle是否存在于我们的集合中？”。如果存在，稀疏向量值为 1，在这种情况下，它不*存在*（因此值为 0）。因此，我们转向数字*2*，确定其位置 (0) 并提出相同的问题。这次，答案是*肯定的，*所以我们的 minhash 输出是**2**。\n",
        "\n",
        "这就是我们在 minhash 签名中生成一个值的方式。但我们需要生成 20 个（或更多）这些值。因此，我们为每个签名位置分配不同的 minhash 函数 - 并重复该过程。\n",
        "\n",
        "![这里我们使用四个 minhash 函数/向量来创建一个四位签名向量。 如果您在每个 minhash 函数中进行计数（从 1 开始），并确定第一个与稀疏向量中的 1 对齐的值 — 您将得到 2412。](https://cdn.sanity.io/images/vr8gru94/production/866cea917043cfd7eb8221fc1a3b715a61e9d14f-1280x720.png)\n",
        "\n",
        "这里我们使用四个 minhash 函数/向量来创建一个四位签名向量。如果您在每个 minhash 函数中进行计数（从 1 开始），并确定第一个与稀疏向量中的 1 对齐的值 — 您将得到 2412。\n",
        "\n",
        "最后，我们生成我们的 minhash 签名 - 或密集向量。\n",
        "\n",
        "让我们继续用代码编写它。我们分三步走：\n",
        "\n",
        "1. 生成随机的 MinHash 向量。\n"
      ],
      "metadata": {
        "id": "qjOcrDqihzw9"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "hash_ex = list(range(1, len(vocab)+1))\n",
        "print(hash_ex)  # we haven't shuffled yet"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "tmHO0DnMiyKD",
        "outputId": "941a6bd8-4299-4525-989d-0bf725def483"
      },
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from random import shuffle\n",
        "\n",
        "shuffle(hash_ex)\n",
        "print(hash_ex)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GYNpFQs7i-TT",
        "outputId": "b9bbe3b3-acbd-423b-f79e-e05e576c2e80"
      },
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[6, 34, 78, 88, 12, 21, 72, 19, 28, 96, 53, 83, 33, 92, 24, 18, 98, 29, 74, 23, 42, 16, 49, 101, 15, 85, 44, 47, 45, 69, 93, 17, 71, 58, 79, 2, 86, 52, 46, 32, 65, 99, 7, 22, 82, 61, 5, 89, 95, 75, 68, 1, 48, 70, 35, 20, 37, 90, 25, 40, 87, 57, 63, 94, 38, 51, 102, 67, 8, 9, 43, 31, 91, 54, 26, 84, 36, 97, 30, 10, 55, 56, 13, 80, 4, 41, 27, 100, 66, 59, 73, 81, 60, 64, 50, 11, 62, 77, 76, 14, 3, 39]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "2. 循环遍历这个随机的 MinHash 向量（从 1 开始），并将每个值的索引与稀疏向量 a_1hot 中的等效值进行匹配。如果我们找到对应值—该索引就是我们的签名值。"
      ],
      "metadata": {
        "id": "L-r3CzJDjCQB"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print(f\"7 -> {hash_ex.index(7)}\") # note that value 7 can be found at index in hash_ex"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "dHZFecsLjDOV",
        "outputId": "18f8a129-4576-433d-cb38-506da13f0333"
      },
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "7 -> 42\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#We now have a randomized list of integers which we can use in creating our *hashed* signatures.\n",
        "#What we do now is begin counting from `1` through to `len(vocab) + 1`,\n",
        "#extracting the position of this number in our new `hash_ex` list, like so:\n",
        "\n",
        "for i in range(1, 5):\n",
        "    print(f\"{i} -> {hash_ex.index(i)}\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Kdx2884LjEj_",
        "outputId": "f9dbc865-d77a-410b-efe7-a02915d3aa8b"
      },
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1 -> 51\n",
            "2 -> 35\n",
            "3 -> 100\n",
            "4 -> 84\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#What we do with this is count up from `1` to `len(vocab) + 1`\n",
        "#and find if the resultant `hash_ex.index(i)` position\n",
        "#in our one-hot encoded vectors contains a positive value (`1`) in that position, like so:\n",
        "for i in range(1, len(vocab)+1):\n",
        "    idx = hash_ex.index(i)\n",
        "    signature_val = a_1hot[idx]\n",
        "    print(f\"{i} -> {idx} -> {signature_val}\")\n",
        "    if signature_val == 1:\n",
        "        print('match!')\n",
        "        break"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DR9ORbXdjOdZ",
        "outputId": "51782e17-d022-499d-d236-25392fc8c216"
      },
      "execution_count": 32,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1 -> 51 -> 0.0\n",
            "2 -> 35 -> 0.0\n",
            "3 -> 100 -> 0.0\n",
            "4 -> 84 -> 1.0\n",
            "match!\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "3. 从1和2的多次迭代构建签名（我们将上面的代码形式化为一些更易于使用的函数）：\n",
        "\n"
      ],
      "metadata": {
        "id": "5M3i822ljd-n"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def create_hash_func(size: int):\n",
        "    # function for creating the hash vector/function\n",
        "    hash_ex = list(range(1, len(vocab)+1))\n",
        "    shuffle(hash_ex)\n",
        "    return hash_ex\n",
        "\n",
        "def build_minhash_func(vocab_size: int, nbits: int):\n",
        "    # function for building multiple minhash vectors\n",
        "    hashes = []\n",
        "    for _ in range(nbits):\n",
        "        hashes.append(create_hash_func(vocab_size))\n",
        "    return hashes\n",
        "\n",
        "# we create 20 minhash vectors\n",
        "minhash_func = build_minhash_func(len(vocab), 20)"
      ],
      "metadata": {
        "id": "hMxn1AmnjhO1"
      },
      "execution_count": 33,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def create_hash(vector: list):\n",
        "    # use this function for creating our signatures (eg the matching)\n",
        "    signature = []\n",
        "    for func in minhash_func:\n",
        "        for i in range(1, len(vocab)+1):\n",
        "            idx = func.index(i)\n",
        "            signature_val = vector[idx]\n",
        "            if signature_val == 1:\n",
        "                signature.append(idx)\n",
        "                break\n",
        "    return signature"
      ],
      "metadata": {
        "id": "CnvC3KxWjh25"
      },
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# now create signatures\n",
        "a_sig = create_hash(a_1hot)\n",
        "b_sig = create_hash(b_1hot)\n",
        "c_sig = create_hash(c_1hot)\n",
        "\n",
        "print(a_sig)\n",
        "print(b_sig)\n",
        "print(c_sig)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WKuuZckxjkG9",
        "outputId": "d5b643d1-97b9-4c51-f54c-2ebb6ef6041e"
      },
      "execution_count": 38,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[84, 10, 21, 0, 79, 42, 86, 17, 28, 0, 0, 101, 25, 55, 84, 4, 46, 64, 21, 34]\n",
            "[79, 50, 21, 91, 50, 14, 20, 24, 50, 11, 5, 50, 68, 69, 19, 4, 46, 64, 94, 95]\n",
            "[53, 74, 27, 42, 18, 73, 82, 24, 85, 77, 5, 23, 81, 55, 84, 44, 46, 64, 74, 23]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "这就是 MinHashing——它实际上没有比这更复杂的了。我们采用了一个稀疏向量并将其压缩为一个更密集的 20 个数字签名。\n",
        "\n",
        "## 从稀疏到签名的信息传输 (Information Transfer from Sparse to Signature)\n",
        "信息是否真正保留在我们更大的稀疏向量和更小的稠密向量之间？对我们来说，直观地识别这些新的密集向量中的模式并不容易，但我们可以计算向量之间的相似度。\n",
        "\n",
        "如果在我们缩小规模的过程中信息确实被保留下来了——向量之间的相似度肯定也会相似吧？\n",
        "\n",
        "好吧，我们可以测试一下。我们使用 Jaccard 相似度来计算shingle格式的句子之间的相似度- 然后以签名格式重复相同的向量：\n",
        "\n"
      ],
      "metadata": {
        "id": "60PKwhOVjl4g"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def jaccard(a: set, b: set):\n",
        "    return len(a.intersection(b)) / len(a.union(b))"
      ],
      "metadata": {
        "id": "HCd5oaAPj1_b"
      },
      "execution_count": 39,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "jaccard(a, b), jaccard(set(a_sig), set(b_sig))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "tPW8NpAZj2nb",
        "outputId": "f1e372c2-22a4-4b19-a375-51c20b5a302f"
      },
      "execution_count": 40,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(0.109375, 0.17857142857142858)"
            ]
          },
          "metadata": {},
          "execution_count": 40
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "jaccard(a, c), jaccard(set(a_sig), set(c_sig))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3NB50eQFj34O",
        "outputId": "6561bdc5-5b7b-48cb-d05c-a71bfaf4d218"
      },
      "execution_count": 41,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(0.24675324675324675, 0.1724137931034483)"
            ]
          },
          "metadata": {},
          "execution_count": 41
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "我们看到两者的相似度分数非常接近——所以信息似乎被保留了。让我们再试一次 b 和 c：\n",
        "\n"
      ],
      "metadata": {
        "id": "90bOzdtYj8Hm"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "jaccard(b, c), jaccard(set(b_sig), set(c_sig))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ymg_uVOYj5C1",
        "outputId": "fc0b5c7a-3cc5-405f-9330-f69518a4a237"
      },
      "execution_count": 42,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(0.15384615384615385, 0.12903225806451613)"
            ]
          },
          "metadata": {},
          "execution_count": 42
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "在这里，我们发现了更高的相似性，正如我们所期望的那样——看起来我们的稀疏向量和签名之间保留了相似性信息！因此，我们现在已做好充分准备，可以进入 LSH 流程。\n",
        "\n"
      ],
      "metadata": {
        "id": "RPGovz30j-RO"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Band and Hash\n",
        "\n",
        "识别相似句子的最后一步是 LSH 函数本身。\n",
        "\n",
        "我们将采用 LSH 的Band方法——我们可以将其描述为传统方法。它将获取我们的签名，对每个签名的哈希片段进行哈希处理，并寻找哈希冲突 - 正如我们在本文前面所描述的那样。\n",
        "\n",
        "![签名构建过程的高级视图。 我们获取文本，构建一个 shingle 集，使用我们的词汇对其进行一次性编码，并通过我们的 minhashing 过程对其进行处理。](https://cdn.sanity.io/images/vr8gru94/production/1a1e12c6e1e7c229319b0a5b96d0300922215205-1280x850.png)\n",
        "\n",
        "签名构建过程的高级视图。我们获取文本，构建一个 shingle 集，使用我们的词汇对其进行一次性编码，并通过我们的 minhashing 过程对其进行处理。\n",
        "\n",
        "*通过这种方法，我们生成这些长度相等的向量，其中包含 1 → len(vocab) 范围内的正整数值——这些是我们通常输入到该*LSH算法中的签名。\n",
        "\n",
        "现在，如果我们要将这些向量中的每一个作为一个整体进行哈希处理，我们可能会很难构建一个哈希函数来准确识别它们之间的相似性——我们不要求整个向量相等，只要求其中的部分相似。\n",
        "\n",
        "在大多数情况下，即使两个向量的部分可能完全匹配 - 如果向量的其余部分不相等，该函数可能会将它们散列到*单独的*桶中。\n",
        "\n",
        "我们不想要这个。我们希望具有某些相似性的签名被散列到同一个桶中，从而被识别为候选对。\n",
        "\n",
        "### 怎么运行的\n",
        "\n",
        "banding方法通过将向量分成称为bands b的子部分来解决这个问题。然后，我们不是通过哈希函数处理完整的向量，而是通过哈希函数传递向量的每个band。\n",
        "\n",
        "想象一下我们将 100 维向量分成 20 个Band。这给了我们 20 个机会来识别向量之间的匹配子向量。\n",
        "\n",
        "![我们将签名分成 b 个子向量，每个子向量都通过哈希函数进行处理（我们可以使用单个哈希函数，或 b 个哈希函数）并映射到哈希桶。](https://cdn.sanity.io/images/vr8gru94/production/1b1fc2e08469ea024573078b275f7228e2e7d824-1920x1080.png)\n",
        "\n",
        "我们将签名分成 b 个子向量，每个子向量都通过哈希函数进行处理（我们可以使用单个哈希函数，或 b 个哈希函数）并映射到哈希桶。\n",
        "\n",
        "我们现在可以添加一个更灵活的条件 - 给定任何两个子向量之间的冲突，我们将各自的完整向量视为候选对。\n",
        "\n",
        "![我们将签名分成子向量。 所有签名中的每个等效子向量必须通过相同的哈希函数进行处理。 然而，没有必要对每个子向量使用不同的哈希函数（我们可以对所有子向量仅使用一个哈希函数）。](https://cdn.sanity.io/images/vr8gru94/production/00a27d5963a54c82b9f751845218b6beb8c09324-1280x720.png)\n",
        "\n",
        "我们将签名分成子向量。所有签名中的每个等效子向量必须通过相同的哈希函数进行处理。然而，没有必要对每个子向量使用不同的哈希函数（我们可以对所有子向量仅使用一个哈希函数）。\n",
        "\n",
        "现在，只有两个向量的一部分必须匹配，我们才能考虑它们。但当然，这也会增加误报的数量（我们将不相似的样本标记为候选匹配）。然而，我们确实尝试尽可能地减少这些。\n",
        "\n",
        "我们可以实现一个简单的版本。首先，我们首先分割签名向量**a**、**b**和**c**："
      ],
      "metadata": {
        "id": "lvf16t8kkJ3W"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def split_vector(signature, b):\n",
        "    assert len(signature) % b == 0\n",
        "    r = int(len(signature) / b)\n",
        "    # code splitting signature in b parts\n",
        "    subvecs = []\n",
        "    for i in range(0, len(signature), r):\n",
        "        subvecs.append(signature[i : i+r])\n",
        "    return subvecs"
      ],
      "metadata": {
        "id": "uevszt7yj98q"
      },
      "execution_count": 43,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Split into 10 bands, creating rows of `2`\n",
        "band_a = split_vector(a_sig, 10)\n",
        "band_b = split_vector(b_sig, 10)\n",
        "band_c = split_vector(c_sig, 10)\n",
        "\n",
        "print(band_a)\n",
        "print(band_b)\n",
        "print(band_c)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kDlfQ55HkPGb",
        "outputId": "6f7ab881-4d64-4efb-a5e2-ba60c55c3207"
      },
      "execution_count": 47,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[84, 10], [21, 0], [79, 42], [86, 17], [28, 0], [0, 101], [25, 55], [84, 4], [46, 64], [21, 34]]\n",
            "[[79, 50], [21, 91], [50, 14], [20, 24], [50, 11], [5, 50], [68, 69], [19, 4], [46, 64], [94, 95]]\n",
            "[[53, 74], [27, 42], [18, 73], [82, 24], [85, 77], [5, 23], [81, 55], [84, 44], [46, 64], [74, 23]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "然后我们循环遍历列表来识别子向量之间的任何匹配。如果我们找到任何匹配项，我们会将这些向量作为候选对。\n",
        "\n"
      ],
      "metadata": {
        "id": "mX_3kss6kWGm"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "for b_rows, c_rows in zip(band_b, band_c):\n",
        "    if b_rows == c_rows:\n",
        "        print(f\"Candidate pair: {b_rows} == {c_rows}\")\n",
        "        # we only need one band to match\n",
        "        break"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "uCgPZBUrkXzg",
        "outputId": "d9ce0368-a68e-48b4-f990-85b778fa74b6"
      },
      "execution_count": 48,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Candidate pair: [46, 64] == [46, 64]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#And let's do the same for **a**.\n",
        "for a_rows, b_rows in zip(band_a, band_b):\n",
        "    if a_rows == b_rows:\n",
        "        print(f\"Candidate pair: {a_rows} == {b_rows}\")\n",
        "        # we only need one band to match\n",
        "        break"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0zwYo2pAkZ3j",
        "outputId": "5ac463a4-823a-43da-f336-2bdc98bbfa04"
      },
      "execution_count": 49,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Candidate pair: [46, 64] == [46, 64]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "for a_rows, c_rows in zip(band_a, band_c):\n",
        "    if a_rows == c_rows:\n",
        "        print(f\"Candidate pair: {b_rows} == {c_rows}\")\n",
        "        # we only need one band to match\n",
        "        break"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RDLXerQQkdoA",
        "outputId": "ee8aa1ea-8ec8-4154-877d-3f31d652f67f"
      },
      "execution_count": 50,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Candidate pair: [46, 64] == [46, 64]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "我们发现两个更相似的句子b和 c— 被识别为候选对。三人组中不太相似的一个- 不被确定为候选者。这是一个很好的结果，但如果我们想真正测试 LSH，我们将需要使用更多数据。\n",
        "\n"
      ],
      "metadata": {
        "id": "PaCr7mIKkhCs"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 测试LSH\n",
        "\n",
        "到目前为止，我们构建的是一个非常低效的实现——如果你想实现 LSH，这肯定不是可行的方法。相反，使用为相似性搜索而构建的库——例如[Faiss](https://www.pinecone.io/learn/series/faiss/)，或托管解决方案（例如 Pinecone）。\n",
        "\n",
        "但通过这样的代码，如果没有别的事情的话，应该可以清楚地了解 LSH 的工作原理。然而，我们现在将复制更多数据，因此我们将使用 Numpy 重写迄今为止的内容。\n",
        "\n",
        "该代码将以相同的方式运行 - 您可以在[此笔记本](https://github.com/pinecone-io/examples/blob/master/learn/search/faiss-ebook/locality-sensitive-hashing-traditional/testing_lsh.ipynb)中找到每个函数（以及说明） 。\n",
        "\n",
        "### 获取数据\n",
        "\n",
        "首先，我们需要获取数据。[这里](https://github.com/brmson/dataset-sts)有一个很棒的存储库，其中包含为相似性搜索测试构建的多个数据集。我们将从[这里](https://github.com/brmson/dataset-sts/blob/master/data/sts/sick2014/SICK_train.txt)提取一组句子。\n",
        "\n"
      ],
      "metadata": {
        "id": "x19bY142knzY"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import requests\n",
        "import pandas as pd\n",
        "import io\n",
        "\n",
        "url = \"https://raw.githubusercontent.com/brmson/dataset-sts/master/data/sts/sick2014/SICK_train.txt\"\n",
        "\n",
        "text = requests.get(url).text\n",
        "\n",
        "data = pd.read_csv(io.StringIO(text), sep='\\t')\n",
        "data.head()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 206
        },
        "id": "mCYIKzL8lEo_",
        "outputId": "2968f29c-de4a-428a-d7c4-ee067077f832"
      },
      "execution_count": 51,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "   pair_ID                                         sentence_A  \\\n",
              "0        1  A group of kids is playing in a yard and an ol...   \n",
              "1        2  A group of children is playing in the house an...   \n",
              "2        3  The young boys are playing outdoors and the ma...   \n",
              "3        5  The kids are playing outdoors near a man with ...   \n",
              "4        9  The young boys are playing outdoors and the ma...   \n",
              "\n",
              "                                          sentence_B  relatedness_score  \\\n",
              "0  A group of boys in a yard is playing and a man...                4.5   \n",
              "1  A group of kids is playing in a yard and an ol...                3.2   \n",
              "2  The kids are playing outdoors near a man with ...                4.7   \n",
              "3  A group of kids is playing in a yard and an ol...                3.4   \n",
              "4  A group of kids is playing in a yard and an ol...                3.7   \n",
              "\n",
              "  entailment_judgment  \n",
              "0             NEUTRAL  \n",
              "1             NEUTRAL  \n",
              "2          ENTAILMENT  \n",
              "3             NEUTRAL  \n",
              "4             NEUTRAL  "
            ],
            "text/html": [
              "\n",
              "  <div id=\"df-4e27b261-a201-4d8e-93a8-e7452b3c63e3\" class=\"colab-df-container\">\n",
              "    <div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>pair_ID</th>\n",
              "      <th>sentence_A</th>\n",
              "      <th>sentence_B</th>\n",
              "      <th>relatedness_score</th>\n",
              "      <th>entailment_judgment</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>1</td>\n",
              "      <td>A group of kids is playing in a yard and an ol...</td>\n",
              "      <td>A group of boys in a yard is playing and a man...</td>\n",
              "      <td>4.5</td>\n",
              "      <td>NEUTRAL</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>2</td>\n",
              "      <td>A group of children is playing in the house an...</td>\n",
              "      <td>A group of kids is playing in a yard and an ol...</td>\n",
              "      <td>3.2</td>\n",
              "      <td>NEUTRAL</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>3</td>\n",
              "      <td>The young boys are playing outdoors and the ma...</td>\n",
              "      <td>The kids are playing outdoors near a man with ...</td>\n",
              "      <td>4.7</td>\n",
              "      <td>ENTAILMENT</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>5</td>\n",
              "      <td>The kids are playing outdoors near a man with ...</td>\n",
              "      <td>A group of kids is playing in a yard and an ol...</td>\n",
              "      <td>3.4</td>\n",
              "      <td>NEUTRAL</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>9</td>\n",
              "      <td>The young boys are playing outdoors and the ma...</td>\n",
              "      <td>A group of kids is playing in a yard and an ol...</td>\n",
              "      <td>3.7</td>\n",
              "      <td>NEUTRAL</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>\n",
              "    <div class=\"colab-df-buttons\">\n",
              "\n",
              "  <div class=\"colab-df-container\">\n",
              "    <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-4e27b261-a201-4d8e-93a8-e7452b3c63e3')\"\n",
              "            title=\"Convert this dataframe to an interactive table.\"\n",
              "            style=\"display:none;\">\n",
              "\n",
              "  <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\" viewBox=\"0 -960 960 960\">\n",
              "    <path d=\"M120-120v-720h720v720H120Zm60-500h600v-160H180v160Zm220 220h160v-160H400v160Zm0 220h160v-160H400v160ZM180-400h160v-160H180v160Zm440 0h160v-160H620v160ZM180-180h160v-160H180v160Zm440 0h160v-160H620v160Z\"/>\n",
              "  </svg>\n",
              "    </button>\n",
              "\n",
              "  <style>\n",
              "    .colab-df-container {\n",
              "      display:flex;\n",
              "      gap: 12px;\n",
              "    }\n",
              "\n",
              "    .colab-df-convert {\n",
              "      background-color: #E8F0FE;\n",
              "      border: none;\n",
              "      border-radius: 50%;\n",
              "      cursor: pointer;\n",
              "      display: none;\n",
              "      fill: #1967D2;\n",
              "      height: 32px;\n",
              "      padding: 0 0 0 0;\n",
              "      width: 32px;\n",
              "    }\n",
              "\n",
              "    .colab-df-convert:hover {\n",
              "      background-color: #E2EBFA;\n",
              "      box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
              "      fill: #174EA6;\n",
              "    }\n",
              "\n",
              "    .colab-df-buttons div {\n",
              "      margin-bottom: 4px;\n",
              "    }\n",
              "\n",
              "    [theme=dark] .colab-df-convert {\n",
              "      background-color: #3B4455;\n",
              "      fill: #D2E3FC;\n",
              "    }\n",
              "\n",
              "    [theme=dark] .colab-df-convert:hover {\n",
              "      background-color: #434B5C;\n",
              "      box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
              "      filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
              "      fill: #FFFFFF;\n",
              "    }\n",
              "  </style>\n",
              "\n",
              "    <script>\n",
              "      const buttonEl =\n",
              "        document.querySelector('#df-4e27b261-a201-4d8e-93a8-e7452b3c63e3 button.colab-df-convert');\n",
              "      buttonEl.style.display =\n",
              "        google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
              "\n",
              "      async function convertToInteractive(key) {\n",
              "        const element = document.querySelector('#df-4e27b261-a201-4d8e-93a8-e7452b3c63e3');\n",
              "        const dataTable =\n",
              "          await google.colab.kernel.invokeFunction('convertToInteractive',\n",
              "                                                    [key], {});\n",
              "        if (!dataTable) return;\n",
              "\n",
              "        const docLinkHtml = 'Like what you see? Visit the ' +\n",
              "          '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
              "          + ' to learn more about interactive tables.';\n",
              "        element.innerHTML = '';\n",
              "        dataTable['output_type'] = 'display_data';\n",
              "        await google.colab.output.renderOutput(dataTable, element);\n",
              "        const docLink = document.createElement('div');\n",
              "        docLink.innerHTML = docLinkHtml;\n",
              "        element.appendChild(docLink);\n",
              "      }\n",
              "    </script>\n",
              "  </div>\n",
              "\n",
              "\n",
              "<div id=\"df-06455773-5e57-4726-b676-ca979bd5941a\">\n",
              "  <button class=\"colab-df-quickchart\" onclick=\"quickchart('df-06455773-5e57-4726-b676-ca979bd5941a')\"\n",
              "            title=\"Suggest charts.\"\n",
              "            style=\"display:none;\">\n",
              "\n",
              "<svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
              "     width=\"24px\">\n",
              "    <g>\n",
              "        <path d=\"M19 3H5c-1.1 0-2 .9-2 2v14c0 1.1.9 2 2 2h14c1.1 0 2-.9 2-2V5c0-1.1-.9-2-2-2zM9 17H7v-7h2v7zm4 0h-2V7h2v10zm4 0h-2v-4h2v4z\"/>\n",
              "    </g>\n",
              "</svg>\n",
              "  </button>\n",
              "\n",
              "<style>\n",
              "  .colab-df-quickchart {\n",
              "      --bg-color: #E8F0FE;\n",
              "      --fill-color: #1967D2;\n",
              "      --hover-bg-color: #E2EBFA;\n",
              "      --hover-fill-color: #174EA6;\n",
              "      --disabled-fill-color: #AAA;\n",
              "      --disabled-bg-color: #DDD;\n",
              "  }\n",
              "\n",
              "  [theme=dark] .colab-df-quickchart {\n",
              "      --bg-color: #3B4455;\n",
              "      --fill-color: #D2E3FC;\n",
              "      --hover-bg-color: #434B5C;\n",
              "      --hover-fill-color: #FFFFFF;\n",
              "      --disabled-bg-color: #3B4455;\n",
              "      --disabled-fill-color: #666;\n",
              "  }\n",
              "\n",
              "  .colab-df-quickchart {\n",
              "    background-color: var(--bg-color);\n",
              "    border: none;\n",
              "    border-radius: 50%;\n",
              "    cursor: pointer;\n",
              "    display: none;\n",
              "    fill: var(--fill-color);\n",
              "    height: 32px;\n",
              "    padding: 0;\n",
              "    width: 32px;\n",
              "  }\n",
              "\n",
              "  .colab-df-quickchart:hover {\n",
              "    background-color: var(--hover-bg-color);\n",
              "    box-shadow: 0 1px 2px rgba(60, 64, 67, 0.3), 0 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
              "    fill: var(--button-hover-fill-color);\n",
              "  }\n",
              "\n",
              "  .colab-df-quickchart-complete:disabled,\n",
              "  .colab-df-quickchart-complete:disabled:hover {\n",
              "    background-color: var(--disabled-bg-color);\n",
              "    fill: var(--disabled-fill-color);\n",
              "    box-shadow: none;\n",
              "  }\n",
              "\n",
              "  .colab-df-spinner {\n",
              "    border: 2px solid var(--fill-color);\n",
              "    border-color: transparent;\n",
              "    border-bottom-color: var(--fill-color);\n",
              "    animation:\n",
              "      spin 1s steps(1) infinite;\n",
              "  }\n",
              "\n",
              "  @keyframes spin {\n",
              "    0% {\n",
              "      border-color: transparent;\n",
              "      border-bottom-color: var(--fill-color);\n",
              "      border-left-color: var(--fill-color);\n",
              "    }\n",
              "    20% {\n",
              "      border-color: transparent;\n",
              "      border-left-color: var(--fill-color);\n",
              "      border-top-color: var(--fill-color);\n",
              "    }\n",
              "    30% {\n",
              "      border-color: transparent;\n",
              "      border-left-color: var(--fill-color);\n",
              "      border-top-color: var(--fill-color);\n",
              "      border-right-color: var(--fill-color);\n",
              "    }\n",
              "    40% {\n",
              "      border-color: transparent;\n",
              "      border-right-color: var(--fill-color);\n",
              "      border-top-color: var(--fill-color);\n",
              "    }\n",
              "    60% {\n",
              "      border-color: transparent;\n",
              "      border-right-color: var(--fill-color);\n",
              "    }\n",
              "    80% {\n",
              "      border-color: transparent;\n",
              "      border-right-color: var(--fill-color);\n",
              "      border-bottom-color: var(--fill-color);\n",
              "    }\n",
              "    90% {\n",
              "      border-color: transparent;\n",
              "      border-bottom-color: var(--fill-color);\n",
              "    }\n",
              "  }\n",
              "</style>\n",
              "\n",
              "  <script>\n",
              "    async function quickchart(key) {\n",
              "      const quickchartButtonEl =\n",
              "        document.querySelector('#' + key + ' button');\n",
              "      quickchartButtonEl.disabled = true;  // To prevent multiple clicks.\n",
              "      quickchartButtonEl.classList.add('colab-df-spinner');\n",
              "      try {\n",
              "        const charts = await google.colab.kernel.invokeFunction(\n",
              "            'suggestCharts', [key], {});\n",
              "      } catch (error) {\n",
              "        console.error('Error during call to suggestCharts:', error);\n",
              "      }\n",
              "      quickchartButtonEl.classList.remove('colab-df-spinner');\n",
              "      quickchartButtonEl.classList.add('colab-df-quickchart-complete');\n",
              "    }\n",
              "    (() => {\n",
              "      let quickchartButtonEl =\n",
              "        document.querySelector('#df-06455773-5e57-4726-b676-ca979bd5941a button');\n",
              "      quickchartButtonEl.style.display =\n",
              "        google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
              "    })();\n",
              "  </script>\n",
              "</div>\n",
              "    </div>\n",
              "  </div>\n"
            ]
          },
          "metadata": {},
          "execution_count": 51
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "sentences = data['sentence_A'].tolist()\n",
        "sentences[:3]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ec1tQ5nWlHDX",
        "outputId": "7c4593dd-f146-425d-bc53-45113ef29ab5"
      },
      "execution_count": 52,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "['A group of kids is playing in a yard and an old man is standing in the background',\n",
              " 'A group of children is playing in the house and there is no man standing in the background',\n",
              " 'The young boys are playing outdoors and the man is smiling nearby']"
            ]
          },
          "metadata": {},
          "execution_count": 52
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Shingles\n",
        "一旦我们有了数据，我们就可以创建 one-hot 编码——这次存储为 NumPy 数组\n",
        "\n"
      ],
      "metadata": {
        "id": "_oEJ73wClJ-P"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "k = 8  # shingle size\n",
        "\n",
        "# build shingles\n",
        "shingles = []\n",
        "for sentence in sentences:\n",
        "    shingles.append(build_shingles(sentence, k))\n",
        "\n",
        "# build vocab\n",
        "vocab = build_vocab(shingles)\n",
        "\n",
        "# one-hot encode our shingles\n",
        "shingles_1hot = []\n",
        "for shingle_set in shingles:\n",
        "    shingles_1hot.append(one_hot(shingle_set, vocab))\n",
        "# stack into single numpy array\n",
        "shingles_1hot = np.stack(shingles_1hot)\n",
        "shingles_1hot.shape"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "z5s81IiXlOYb",
        "outputId": "3abd105e-6117-46f6-90ee-75320e8a4a99"
      },
      "execution_count": 54,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(4500, 36466)"
            ]
          },
          "metadata": {},
          "execution_count": 54
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "shingles_1hot[:5]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_YrPYX5rlQaF",
        "outputId": "31fe22bc-956c-40f4-ae8e-b0cc40b3f4a3"
      },
      "execution_count": 55,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[0., 0., 0., ..., 0., 0., 0.],\n",
              "       [0., 0., 0., ..., 0., 0., 0.],\n",
              "       [0., 0., 0., ..., 0., 0., 0.],\n",
              "       [0., 0., 0., ..., 0., 0., 0.],\n",
              "       [0., 0., 0., ..., 0., 0., 0.]])"
            ]
          },
          "metadata": {},
          "execution_count": 55
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "sum(shingles_1hot[0])  # confirm we have 1s"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2DlV71qMlSFr",
        "outputId": "8035cc51-f810-4afd-a14e-b870d42e4c1e"
      },
      "execution_count": 56,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "73.0"
            ]
          },
          "metadata": {},
          "execution_count": 56
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "现在我们有了独热编码。shingles_1hot 数组包含 4500 sparse 向量，其中每个向量的长度为36466。\n",
        "\n"
      ],
      "metadata": {
        "id": "lQBiAxWzlU_E"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 最小散列法\n",
        "和以前一样，我们将使用 minhashing 将稀疏向量压缩为密集向量“签名”。同样，我们将使用 NumPy 实现，您可以在此处找到完整的代码。\n",
        "\n"
      ],
      "metadata": {
        "id": "6oJLh_yUlZQu"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def minhash_arr(vocab: dict, resolution: int):\n",
        "    length = len(vocab.keys())\n",
        "    arr = np.zeros((resolution, length))\n",
        "    for i in range(resolution):\n",
        "        permutation = np.random.permutation(len(vocab)) + 1\n",
        "        arr[i, :] = permutation.copy()\n",
        "    return arr.astype(int)\n",
        "\n",
        "def get_signature(minhash, vector):\n",
        "    # get index locations of every 1 value in vector\n",
        "    idx = np.nonzero(vector)[0].tolist()\n",
        "    # use index locations to pull only +ve positions in minhash\n",
        "    shingles = minhash[:, idx]\n",
        "    # find minimum value in each hash vector\n",
        "    signature = np.min(shingles, axis=1)\n",
        "    return signature"
      ],
      "metadata": {
        "id": "3goLVxlOwy6c"
      },
      "execution_count": 57,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "arr = minhash_arr(vocab, 100)\n",
        "\n",
        "signatures = []\n",
        "\n",
        "for vector in shingles_1hot:\n",
        "    signatures.append(get_signature(arr, vector))\n",
        "\n",
        "# merge signatures into single array\n",
        "signatures = np.stack(signatures)\n",
        "signatures.shape"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jzLubJmClbaF",
        "outputId": "cfebeeea-eae2-4cde-aa5d-77876629aa69"
      },
      "execution_count": 58,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(4500, 100)"
            ]
          },
          "metadata": {},
          "execution_count": 58
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "signatures[0]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "z0i5FVwQlc6W",
        "outputId": "b91c1005-03c6-4584-eeca-e30d9937df63"
      },
      "execution_count": 59,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([ 129,  767,  447,  417,   50,  372,   93, 1989,  317,  650,  279,\n",
              "        173,  351,  995,  222,  766,  778, 1063,  189,  155,  650, 1381,\n",
              "       1345,  604, 1736,  516,  224,  173, 2673,  240,  206, 1682, 1358,\n",
              "         62,  893,  766,  448,   56,  603,  231,  264,  335,  261,  137,\n",
              "        155,  389,  299, 1064,  380,  905,  253,   33, 1290,   64,  172,\n",
              "        135,  443,   24,  173,  466,  669, 1633,  237,  572,  662,  175,\n",
              "       1559,  415,  541,  888,  764,   33,  435,   38,  410,  939,   17,\n",
              "        474, 1099, 1033,  439,   92,  230,  258,  101,  452,  811,  440,\n",
              "        152,  184,  278,  213,  348,  343,  202,   21,  451,  125,  307,\n",
              "        442])"
            ]
          },
          "metadata": {},
          "execution_count": 59
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "我们将稀疏向量从长度36466压缩到长度100的签名。这是一个很大的区别，但正如我们之前所演示的，这种压缩技术很好地保留了相似性信息。\n",
        "\n"
      ],
      "metadata": {
        "id": "ho6UQTLXlgI7"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## LSH\n",
        "最后，到 LSH 部分。我们将在这里再次使用 Python 字典来散列并存储我们的候选对。完整的代码在[这里](https://github.com/weedge/doraemon-nb/blob/main/testing_lsh.ipynb)。"
      ],
      "metadata": {
        "id": "0mgEQ74clj8W"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from itertools import combinations\n",
        "\n",
        "class LSH:\n",
        "    buckets = []\n",
        "    counter = 0\n",
        "    def __init__(self, b):\n",
        "        self.b = b\n",
        "        for i in range(b):\n",
        "            self.buckets.append({})\n",
        "\n",
        "    def make_subvecs(self, signature):\n",
        "        l = len(signature)\n",
        "        assert l % self.b == 0\n",
        "        r = int(l / self.b)\n",
        "        # break signature into subvectors\n",
        "        subvecs = []\n",
        "        for i in range(0, l, r):\n",
        "            subvecs.append(signature[i:i+r])\n",
        "        return np.stack(subvecs)\n",
        "\n",
        "    def add_hash(self, signature):\n",
        "        subvecs = self.make_subvecs(signature).astype(str)\n",
        "        for i, subvec in enumerate(subvecs):\n",
        "            subvec = ','.join(subvec)\n",
        "            if subvec not in self.buckets[i].keys():\n",
        "                self.buckets[i][subvec] = []\n",
        "            self.buckets[i][subvec].append(self.counter)\n",
        "        self.counter += 1\n",
        "\n",
        "    def check_candidates(self):\n",
        "        candidates = []\n",
        "        for bucket_band in self.buckets:\n",
        "            keys = bucket_band.keys()\n",
        "            for bucket in keys:\n",
        "                hits = bucket_band[bucket]\n",
        "                if len(hits) > 1:\n",
        "                    candidates.extend(combinations(hits, 2))\n",
        "        return set(candidates)"
      ],
      "metadata": {
        "id": "PNzaHMv7xNKl"
      },
      "execution_count": 60,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "b = 20\n",
        "\n",
        "lsh = LSH(b)\n",
        "\n",
        "for signature in signatures:\n",
        "    lsh.add_hash(signature)"
      ],
      "metadata": {
        "id": "OexCPGXYlel_"
      },
      "execution_count": 61,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "lsh.buckets"
      ],
      "metadata": {
        "id": "Or4L0wHrloPW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "值得注意的是，我们的 lsh.buckets 变量实际上为每个band包含一个单独的字典 - 我们不会在不同bands之间混合存储桶。\n",
        "\n",
        "我们在存储桶中看到向量 ID（行号），因此提取候选对所需要做的就是循环所有存储桶并提取对。\n",
        "\n"
      ],
      "metadata": {
        "id": "YoNehrCXlrNp"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "candidate_pairs = lsh.check_candidates()\n",
        "len(candidate_pairs)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zyssrJYVlszg",
        "outputId": "2a51d2e3-624d-44e3-df47-e06da816ebf4"
      },
      "execution_count": 63,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "6011"
            ]
          },
          "metadata": {},
          "execution_count": 63
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "list(candidate_pairs)[:5]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xs1UA-uGlt_a",
        "outputId": "79b69c40-8ba3-4b23-a3f0-011cf5c48f18"
      },
      "execution_count": 64,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(3877, 3878), (666, 1141), (2185, 2638), (1979, 1981), (1876, 2004)]"
            ]
          },
          "metadata": {},
          "execution_count": 64
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "识别出候选对后，我们会将相似度计算限制为仅对这些对 - 我们会发现有些将在我们的相似度阈值内，而其他则不会。\n",
        "\n",
        "这里的目标是限制我们的范围并降低搜索复杂性，同时仍然保持识别对的高精度。\n",
        "\n",
        "我们可以通过根据实际[余弦（或 Jaccard）相似度](https://www.pinecone.io/learn/semantic-search/)测量候选对分类（1 或 0）来可视化我们的性能。\n",
        "\n",
        "![显示候选对 (1) 和非候选对 (0) 相对于对签名的余弦相似度的分布的图表。](https://cdn.sanity.io/images/vr8gru94/production/547308d2f04bb52ab733485a0014696a9c7924d0-1280x720.png)\n",
        "\n",
        "显示候选对 (1) 和非候选对 (0) 相对于对签名的余弦相似度的分布的图表。\n",
        "\n",
        "现在，这似乎是一种奇怪的可视化我们表现的方式——你是对的，确实如此——但我们确实有理由。\n",
        "\n",
        "### 优化bands (Optimizing the Bands)\n",
        "\n",
        "可以优化我们的带值 b 以改变 LSH 函数的相似性阈值。相似度阈值是我们希望 LSH 函数从非候选对切换到候选对的点。\n",
        "\n",
        "我们将这种概率相似性关系形式化为：\n",
        "\n",
        "![给定相似性得分 (s)、band数 (b) 和每个band中的行数 (r) 时，一对被识别为候选对的概率 (P)。](https://cdn.sanity.io/images/vr8gru94/production/e1825efa49d55eb681d73326ea268ed4fdd68004-1780x180.png)\n",
        "\n",
        "给定相似性得分 (s)、band数 (b) 和每个band中的行数 (r) 时，一对被识别为候选对的概率 (P)。\n",
        "\n",
        "现在，如果我们要可视化当前 b 和 r 值的概率相似关系，我们应该注意到一个模式：\n",
        "\n",
        "![候选分类（左 y 轴）和根据相似性（计算或归一化余弦相似性）计算的概率 P（右 y 轴）。 这表明我们计算的概率 P 和相似度 s 值表明候选/非候选对的一般分布。 b 和 r 值分别为 20 和 5。](https://cdn.sanity.io/images/vr8gru94/production/b470799575b8e77911bacb8500977afef06d6c85-1280x720.png)\n",
        "\n",
        "候选分类（左 y 轴）和根据相似性（计算或归一化余弦相似性）计算的概率 P（右 y 轴）。这表明我们计算的概率 P 和相似度 s 值表明候选/非候选对的一般分布。b 和 r 值分别为 20 和 5。\n",
        "\n",
        "尽管对齐并不完美，但我们可以看到理论计算概率与真实候选对结果之间的相关性。现在，我们可以通过修改 b 向左或向右推动以不同相似度分数返回候选对的概率：\n",
        "\n",
        "![计算不同 b 值的相似度 s 的概率 P。 请注意，r 将是 len(signature) / b（在本例中 len(signature) == 100）。](https://cdn.sanity.io/images/vr8gru94/production/aace49fa240778e8ecf6e85ad08a2de7f5385566-1280x720.png)\n",
        "\n",
        "计算不同 b 值的相似度 s 的概率 P。请注意，r 将是 len(signature) / b（在本例中 len(signature) == 100）。\n",
        "\n",
        "这些是我们计算的概率值。如果我们认为之前的结果 b == 20 需要太高的相似度才能将对计为候选对 - 我们将尝试将相似度阈值向左移动。\n",
        "\n",
        "看看这张图，b 值 25 看起来足以改变我们的真实结果。那么，让我们可视化使用 b == 25 时的结果：\n",
        "\n",
        "![b == 25 时的真实结果和模拟结果以蓝色和洋红色显示。 显示我们之前的 LSH 结果（青色）以供比较。 请注意，这创建了更多候选对。](https://cdn.sanity.io/images/vr8gru94/production/5402cb0b40da6b128a53f69fbcbd36a1ff8bdace-1280x720.png)\n",
        "\n",
        "b == 25 时的真实结果和模拟结果以蓝色和洋红色显示。显示我们之前的 LSH 结果（青色）以供比较。请注意，这创建了更多候选对。\n",
        "\n",
        "因为我们现在返回更多的候选对，这自然会导致更多的误报——我们为不同的向量返回“候选对”。这是修改 b 不可避免的结果，我们可以将其想象为：\n",
        "\n",
        "![增加 b（左移）会增加 FP，同时减少 FN。](https://cdn.sanity.io/images/vr8gru94/production/d6b9466efa2e6875ff98f4cce94ae1737e36c53b-1280x720.png)\n",
        "\n",
        "增加 b（左移）会增加 FP，同时减少 FN。\n",
        "\n",
        "棒极了！我们从头开始构建了 LSH 流程，甚至设法调整了我们的相似性阈值。\n",
        "\n",
        "这就是本文关于 LSH 原理的全部内容。我们不仅介绍了 LSH，还介绍了 shingling 和 MinHash 函数！\n",
        "\n",
        "在实践中，我们很可能希望使用专门为相似性搜索构建的库来实现 LSH。我们将更详细地介绍 LSH（特别是随机投影方法）及其在 Faiss 中的实现。\n",
        "\n",
        "但是，如果您希望快速了解相似性搜索中的一些关键索引（及其实现），我们将在[向量索引概述](https://www.pinecone.io/learn/series/faiss/vector-indexes/)中涵盖所有这些索引。"
      ],
      "metadata": {
        "id": "FtXNqsEEl0J8"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Resources\n",
        "\n",
        "- [Jupyter Notebooks](https://github.com/pinecone-io/examples/tree/master/learn/search/faiss-ebook/locality-sensitive-hashing-traditional)\n",
        "\n",
        "- J. Ullman et al., [Mining of Massive Datasets](http://mmds.org/#ver30)\n",
        "\n",
        "  "
      ],
      "metadata": {
        "id": "HIfpqzQFmOG2"
      }
    }
  ]
}