matching_text_with_fuzzy_characters.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "adc71d31",
   "metadata": {},
   "source": [
    "Text matching using characters\n",
    "-----\n",
    "\n",
    "Let's say you have the following strings:\n",
    "\n",
    "1. \"fuzzy rabbit\"\n",
    "2. \"wuzzy rabbit\"\n",
    "3. \"wuzzy wabbit\"\n",
    "4. \"fuzzy wuzzy\""
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "7c804baf",
   "metadata": {},
   "source": [
    "You want to cluster the first three strings together and the last string should be in a different cluster.\n",
    "\n",
    "This is best done at the character level (an example of word-level semenatic clustering is [here](https://github.com/brianspiering/nlp-cookbook/blob/main/matching_text_with_embeddings.ipynb)).\n",
    "\n",
    "Let's frame this problem within common used terminology. Hashing is mapping an object, a string in this case, to an integer. What you want are collisions (i.e., similar objects are mapped to the same integer bucket). The goal is to pick a hashing function that has higher number of collisions based on the number of shared letters in the string.\n",
    "\n",
    "A scalable implementation of this idea is MinHash and locality-sensitive hashing (LSH). MinHash is rolling set hash of each individual character. LSH then clusters / buckets those hashes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "add844d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "from dataclasses import dataclass, field\n",
    "\n",
    "from datasketch import MinHash, MinHashLSH\n",
    "\n",
    "@dataclass\n",
    "class String:\n",
    "    name:    str \n",
    "    text:    str\n",
    "    minhash: object = field(init=False)\n",
    "    \n",
    "    def __post_init__(self):\n",
    "        self.minhash = self.set_minhash()\n",
    "\n",
    "    def set_minhash(self):\n",
    "        \"MinHash letter-by-letter\"\n",
    "        m = MinHash(num_perm=128)      \n",
    "        for c in self.text:\n",
    "            m.update(c.encode('utf8')) \n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "f87ad975",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Setup data\n",
    "s0 =  String(name=\"s0\", text=\"fuzzy rabbit\")\n",
    "s1 =  String(name=\"s1\", text=\"wuzzy rabbit\")\n",
    "s2 =  String(name=\"s2\", text=\"wuzzy wabbit\")\n",
    "s3 =  String(name=\"s3\", text=\"fuzzy wuzzy\")\n",
    "strings = [s0, s1, s2, s3]\n",
    "\n",
    "# Create LSH storage for scalable querying\n",
    "lsh = MinHashLSH(threshold=0.8, num_perm=128)\n",
    "for s in strings:\n",
    "    lsh.insert(s.name, s.minhash)\n",
    "\n",
    "# Test that the queries for the hashed values return the expected neighbors\n",
    "assert set(lsh.query(s0.minhash)) == set(['s0', 's1', 's2'])\n",
    "assert set(lsh.query(s3.minhash)) == set(['s3'])"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "9d9daf1e",
   "metadata": {},
   "source": [
    "This method is highly scalable. The hashing and LSH creation can be done in parrellel and offline. The querying is constant time O(1). The matching threshold needs to be custom tuned for the application."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5a2b1a4",
   "metadata": {},
   "source": [
    "<br>\n",
    "<br>\n",
    "<br>\n",
    "\n",
    "------"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}