Demonstrate-fuzzy-search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# fuzzy-search\n",
    "Fuzzy search modules for searching occurrences of words or phrases in low quality OCR and HTR text and text with spelling variation. \n",
    "\n",
    "This package has been developed for finding occurrences of formulaic phrases in corpora with repetitive texts, such as auction advertisements in 17th century newspapers, resolutions in political administrative archives, or notarial deeds.\n",
    "\n",
    "The basic fuzzy searcher uses character skip-grams to exhaustively search for approximately matching strings for a given list of target words and phrases. \n",
    "\n",
    "## Usage\n",
    "\n",
    "Below is an example of searching for key words and phrases in the corpus of resolutions of the States General of the Dutch Republic. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from fuzzy_search import FuzzyPhraseSearcher\n",
    "\n",
    "# highger matching thresholds for higher quality OCR/HTR (higher precision, recall should be good anyway)\n",
    "# lower matching thresholds for lower quality OCR/HTR (higher recall, as that's the main problem)\n",
    "\n",
    "config = {\n",
    "    \"char_match_threshold\": 0.6,\n",
    "    \"ngram_threshold\": 0.5,\n",
    "    \"levenshtein_threshold\": 0.6,\n",
    "    \"ignorecase\": False,\n",
    "    \"max_length_variance\": 3,\n",
    "    \"ngram_size\": 2,\n",
    "    \"skip_size\": 2,\n",
    "}\n",
    "\n",
    "# create a list of domain- or corpus-specific terms and formulaic phrases\n",
    "domain_phrases = [\n",
    "    # terms for announcing the chair and attendants of a meeting\n",
    "    \"PRAESIDE\",\n",
    "    \"PRAESENTIBUS\",\n",
    "    # some weekdays in Latin\n",
    "    \"Veneris\", \n",
    "    \"Mercurii\",\n",
    "    # some date phrase where any date in January 1725 should match\n",
    "    \"den .. Januarii 1725\"\n",
    "]\n",
    "\n",
    "# initialize a new searcher instance with the phrases and the config\n",
    "fuzzy_searcher = FuzzyPhraseSearcher(config=config, phrase_model=domain_phrases)\n",
    "\n",
    "# take some example texts: resolutoins of the meeting of the Dutch States General on\n",
    "# Friday the 5th of January, 1725\n",
    "text = (\"ie Veucris den 5. Januaris 1725. PR&ASIDE, Den Heere Bentinck. PRASENTIEBUS, \"\n",
    "        \"De Heeren Jan Welderen , van Dam, Torck , met een extraordinaris Gedeputeerde \"\n",
    "        \"uyt de Provincie van Gelderlandt. Van Maasdam , vanden Boeizelaar , Raadtpenfionaris \"\n",
    "        \"van Hoornbeeck , met een extraordinaris Gedeputeerde uyt de Provincie van Hollandt \"\n",
    "        \"ende Welt-Vrieslandt. Velters, Ockere , Noey; van Hoorn , met een extraordinaris \"\n",
    "        \"Gedeputeerde uyt de Provincie van Zeelandt. Van Renswoude , van Voor{t. Van \"\n",
    "        \"Schwartzenbergh, vander Waayen, Vegilin Van I{elmuden. Van Iddekinge ‚ van Tamminga.\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `find_matches` method returns match objects:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# look for matches in the first example text\n",
    "matches = fuzzy_searcher.find_matches(text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Printing the matches directly yields the following output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PhraseMatch(phrase: \"Veneris\", variant: \"Veneris\", string: \"Veucris\", offset: 3, ignorecase: False, levenshtein_similarity: 0.7142857142857143)\n",
      "PhraseMatch(phrase: \"den .. Januarii 1725\", variant: \"den .. Januarii 1725\", string: \"den 5. Januaris 1725\", offset: 11, ignorecase: False, levenshtein_similarity: 0.9)\n",
      "PhraseMatch(phrase: \"PRAESIDE\", variant: \"PRAESIDE\", string: \"PR&ASIDE\", offset: 33, ignorecase: False, levenshtein_similarity: 0.75)\n",
      "PhraseMatch(phrase: \"PRAESENTIBUS\", variant: \"PRAESENTIBUS\", string: \"PRASENTIEBUS\", offset: 63, ignorecase: False, levenshtein_similarity: 0.8333333333333334)\n"
     ]
    }
   ],
   "source": [
    "for match in matches:\n",
    "    print(match)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When you have many texts, you can pass them as simple dictionaries with a `text` property and an `id` property. The `id` will be added to the matches, so you can keep track of which match comes from which text."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Veneris             \tVeucris             \t    3\t0.71\tsession-3780-num-3-para-1\n",
      "den .. Januarii 1725\tden 5. Januaris 1725\t   11\t0.90\tsession-3780-num-3-para-1\n",
      "PRAESIDE            \tPR&ASIDE            \t   33\t0.75\tsession-3780-num-3-para-1\n",
      "PRAESENTIBUS        \tPRASENTIEBUS        \t   63\t0.83\tsession-3780-num-3-para-1\n",
      "Mercurii            \tMercuri             \t    0\t0.88\tsession-3780-num-7-para-1\n",
      "den .. Januarii 1725\tden 10. Jangarii, 1725\t    9\t0.82\tsession-3780-num-7-para-1\n",
      "PRAESIDE            \tPRESIDE             \t   36\t0.88\tsession-3780-num-7-para-1\n",
      "PRAESENTIBUS        \tPRA&SENTIBUS        \t   69\t0.92\tsession-3780-num-7-para-1\n"
     ]
    }
   ],
   "source": [
    "texts = [\n",
    "    {\n",
    "        'text': (\"ie Veucris den 5. Januaris 1725. PR&ASIDE, Den Heere Bentinck. PRASENTIEBUS, \"\n",
    "                 \"De Heeren Jan Welderen , van Dam, Torck , met een extraordinaris Gedeputeerde \"\n",
    "                 \"uyt de Provincie van Gelderlandt. Van Maasdam , vanden Boeizelaar , \"\n",
    "                 \"Raadtpenfionaris van Hoornbeeck , met een extraordinaris Gedeputeerde uyt de \"\n",
    "                 \"Provincie van Hollandt ende Welt-Vrieslandt. Velters, Ockere , Noey; van Hoorn , \"\n",
    "                 \"met een extraordinaris Gedeputeerde uyt de Provincie van Zeelandt. Van Renswoude \"\n",
    "                 \", van Voor{t. Van Schwartzenbergh, vander Waayen, Vegilin Van I{elmuden. Van \"\n",
    "                 \"Iddekinge ‚ van Tamminga.\"),\n",
    "        'id': 'session-3780-num-3-para-1'\n",
    "    },\n",
    "    {\n",
    "        'text': (\"Mercuri: den 10. Jangarii, 1725. ia PRESIDE, Den Heere an Iddekinge. PRA&SENTIBUS, \"\n",
    "                 \"De Heeren /an Welderen , van Dam, van Wynbergen, Torck, met een extraordinaris \"\n",
    "                 \"Gedeputeerde uyt de Provincie van Gelderland. Van Maasdam , Raadtpenfionaris van \"\n",
    "                 \"Hoorn=beeck. Velters, Ockerfe, Noey. Taats van Amerongen, van Renswoude. Vander \"\n",
    "                 \"Waasen , Vegilin, ’ Bentinck, van I(elmaden. Van Tamminga.\"),\n",
    "        'id': 'session-3780-num-7-para-1'\n",
    "    }\n",
    "]\n",
    "\n",
    "# look for matches in a list of texts\n",
    "for text in texts:\n",
    "    for match in fuzzy_searcher.find_matches(text):\n",
    "        # the phrase objects from the phrase model are added as a property\n",
    "        # so you have easy access to it, to get e.g. the phrase_string\n",
    "        print(f\"{match.phrase.phrase_string: <20}\\t{match.string: <20}\"\n",
    "              f\"\\t{match.offset: >5}\\t{match.levenshtein_similarity: >.2f}\\t{match.text_id}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Phrases can be strings, but can also represented as dictionaries with extra information. For instance, it's possible to add labels and metadata."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['latin', 'dutch', 'latin', 'latin']"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "domain_phrases = [\n",
    "    # terms for the chair and attendants of a meeting\n",
    "    {\n",
    "        'phrase': 'PRAESIDE',\n",
    "        'label': 'president',\n",
    "        'metadata': {\n",
    "            'lang': 'latin'\n",
    "        }\n",
    "    },\n",
    "    {\n",
    "        'phrase': 'PRAESENTIBUS',\n",
    "        'label': 'attendants',\n",
    "        'metadata': {\n",
    "            'lang': 'latin'\n",
    "        }\n",
    "    },\n",
    "    # some weekdays in Latin\n",
    "    {\n",
    "        'phrase': 'Veneris',\n",
    "        'label': ['date', 'weekday'],\n",
    "        'metadata': {\n",
    "            'lang': 'latin'\n",
    "        }\n",
    "    },\n",
    "    {\n",
    "        'phrase': 'Mercurii',\n",
    "        'label': ['date', 'weekday'],\n",
    "        'metadata': {\n",
    "            'lang': 'latin'\n",
    "        }\n",
    "    },\n",
    "    # some date phrase where any date in January 1725 should match\n",
    "    {\n",
    "        'phrase': 'den .. Januarii 1725',\n",
    "        'label': ['date', 'full_date'],\n",
    "        'metadata': {\n",
    "            'lang': 'dutch'\n",
    "        }\n",
    "    }    \n",
    "]\n",
    "\n",
    "# initialize a new searcher instance with the phrases and the config\n",
    "fuzzy_searcher = FuzzyPhraseSearcher(config=config, phrase_model=domain_phrases)\n",
    "\n",
    "# look for matches in the first example text\n",
    "matches = fuzzy_searcher.find_matches(texts[0])\n",
    "\n",
    "[match.phrase.metadata['lang'] for match in matches]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This makes it easy to filter matches on metadata properties:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[PhraseMatch(phrase: \"den .. Januarii 1725\", variant: \"den .. Januarii 1725\", string: \"den 5. Januaris 1725\", offset: 11, ignorecase: False, levenshtein_similarity: 0.9)]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[match for match in matches if match.phrase.metadata['lang'] == 'dutch']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Phrase Variants and Distractors\n",
    "\n",
    "If you have multiple phrases representing the same meaning or function, it is possible to register them in a single Phrase object and ask the fuzzy searcher to match with any of the variants.\n",
    "\n",
    "By default, the fuzzy searcher ignores variants for efficiency. To make sure the searcher uses them, set the `include_variants` property in the config to `True`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PRAESENTIBUS        \tPRASENTIEBUS        \t   63\t0.83\tsession-3780-num-3-para-1\n",
      "PRAESENTIBUS        \tPRA&SENTIBUS        \t   69\t0.92\tsession-3780-num-7-para-1\n",
      "PRAESENTIBUS        \tPraeside de Heer    \t    0\t0.65\tsession-3210-num-166-para-1\n",
      "PRAESENTIBUS        \tPraseat de Heeron   \t   28\t0.82\tsession-3210-num-166-para-1\n"
     ]
    }
   ],
   "source": [
    "attendants_phrases = [\n",
    "    {\n",
    "        'phrase': 'PRAESENTIBUS',\n",
    "        'variants': [\n",
    "            'Present de Heeren',\n",
    "            'Pntes die voors'\n",
    "        ],\n",
    "        'label': 'attendants'\n",
    "    }\n",
    "]\n",
    "\n",
    "config = {\n",
    "    \"char_match_threshold\": 0.6,\n",
    "    \"ngram_threshold\": 0.5,\n",
    "    \"levenshtein_threshold\": 0.6,\n",
    "    \"ignorecase\": False,\n",
    "    \"include_variants\": True,\n",
    "    \"max_length_variance\": 3,\n",
    "    \"ngram_size\": 2,\n",
    "    \"skip_size\": 2,\n",
    "}\n",
    "\n",
    "\n",
    "# initialize a new searcher instance with the phrases and the config\n",
    "fuzzy_searcher = FuzzyPhraseSearcher(config=config, phrase_model=attendants_phrases)\n",
    "\n",
    "texts = [\n",
    "    {\n",
    "        'text': 'ie Veucris den 5. Januaris 1725. PR&ASIDE, Den Heere Bentinck. PRASENTIEBUS, De Heeren Jan Welderen , van Dam, Torck , met een extraordinaris Gedeputeerde uyt de Provincie van Gelderlandt. Van Maasdam , vanden Boeizelaar , Raadtpenfionaris van Hoornbeeck , met een extraordinaris Gedeputeerde uyt de Provincie van Hollandt ende Welt-Vrieslandt. Velters, Ockere , Noey; van Hoorn , met een extraordinaris Gedeputeerde uyt de Provincie van Zeelandt. Van Renswoude , van Voor{t. Van Schwartzenbergh, vander Waayen, Vegilin Van I{elmuden. Van Iddekinge ‚ van Tamminga.',\n",
    "        'id': 'session-3780-num-3-para-1'\n",
    "    },\n",
    "    {\n",
    "        'text': 'Mercuri: den 10. Jangarii, 1725. ia PRESIDE, Den Heere an Iddekinge. PRA&SENTIBUS, De Heeren /an Welderen , van Dam, van Wynbergen, Torck, met een extraordinaris Gedeputeerde uyt de Provincie van Gelderland. Van Maasdam , Raadtpenfionaris van Hoorn=beeck. Velters, Ockerfe, Noey. Taats van Amerongen, van Renswoude. Vander Waasen , Vegilin, ’ Bentinck, van I(elmaden. Van Tamminga.',\n",
    "        'id': 'session-3780-num-7-para-1'\n",
    "    },\n",
    "    {\n",
    "        'text': 'Praeside de Heer de Knuijt, Praseat de Heeron Verbolt, Raesfelt, Huijgens, Ommercn, Wimmenum, Loo, Cats, Rhijnhuijsen, van der Hoolck Jrovestins, Eissinge,',\n",
    "        'id': 'session-3210-num-166-para-1'\n",
    "    }\n",
    "]\n",
    "\n",
    "for text in texts:\n",
    "    matches = fuzzy_searcher.find_matches(text)\n",
    "    for match in matches:\n",
    "        print(f\"{match.phrase.phrase_string: <20}\\t{match.string: <20}\"\n",
    "              f\"\\t{match.offset: >5}\\t{match.levenshtein_similarity: >.2f}\\t{match.text_id}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The  phrase \"Praeside de Heer\" is a formulaic phrase to signal the president instead of the attendants, but also matches with the PRAESENTIBUS phrase. \n",
    "\n",
    "Since it's formulaic and is frequently used in combination with the formulaic phrase \"Present de Heeren\", it will lead to many unwanted matches. To avoid them, it is possible to add it as a `distractor` phrase. Distractors are orthographically similar phrases that have a different meaning or function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PRAESENTIBUS        \tPRASENTIEBUS        \t   63\t0.83\tsession-3780-num-3-para-1\n",
      "PRAESENTIBUS        \tPRA&SENTIBUS        \t   69\t0.92\tsession-3780-num-7-para-1\n",
      "PRAESENTIBUS        \tPraseat de Heeron   \t   28\t0.82\tsession-3210-num-166-para-1\n"
     ]
    }
   ],
   "source": [
    "attendants_phrases = [\n",
    "    {\n",
    "        'phrase': 'PRAESENTIBUS',\n",
    "        'variants': [\n",
    "            'Present de Heeren',\n",
    "            'Pntes die voors'\n",
    "        ],\n",
    "        'distractors': [\n",
    "            'Praeside de Heer'\n",
    "        ],\n",
    "        'label': 'attendants'\n",
    "    }\n",
    "]\n",
    "\n",
    "config = {\n",
    "    \"char_match_threshold\": 0.6,\n",
    "    \"ngram_threshold\": 0.5,\n",
    "    \"levenshtein_threshold\": 0.6,\n",
    "    \"ignorecase\": False,\n",
    "    \"include_variants\": True,\n",
    "    \"filter_distractors\": True,\n",
    "    \"max_length_variance\": 3,\n",
    "    \"ngram_size\": 2,\n",
    "    \"skip_size\": 2,\n",
    "}\n",
    "\n",
    "\n",
    "# initialize a new searcher instance with the phrases and the config\n",
    "fuzzy_searcher = FuzzyPhraseSearcher(config=config, phrase_model=attendants_phrases)\n",
    "\n",
    "for text in texts:\n",
    "    matches = fuzzy_searcher.find_matches(text)\n",
    "    for match in matches:\n",
    "        print(f\"{match.phrase.phrase_string: <20}\\t{match.string: <20}\"\n",
    "              f\"\\t{match.offset: >5}\\t{match.levenshtein_similarity: >.2f}\\t{match.text_id}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The formulaic phrase _'Praeside de Heer'_ is a variant of the phrase _'PRAESENTIBUS'_. If it is registered as a variant, the fuzzy searcher will match occurrences like \"Praseat de Heeron\" with both _'Praeside de Heer'_ and _'Present de Heeren'_, but with both matches representing the same text string, the searcher will pick the best matching one. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PRAESIDE            \tPR&ASIDE            \t   33\t0.75\tsession-3780-num-3-para-1\n",
      "PRAESENTIBUS        \tPRASENTIEBUS        \t   63\t0.83\tsession-3780-num-3-para-1\n",
      "PRAESIDE            \tPRESIDE             \t   36\t0.88\tsession-3780-num-7-para-1\n",
      "PRAESENTIBUS        \tPRA&SENTIBUS        \t   69\t0.92\tsession-3780-num-7-para-1\n",
      "PRAESIDE            \tPraeside de Heer    \t    0\t1.00\tsession-3210-num-166-para-1\n",
      "PRAESENTIBUS        \tPraseat de Heeron   \t   28\t0.82\tsession-3210-num-166-para-1\n"
     ]
    }
   ],
   "source": [
    "attendants_phrases = [\n",
    "    {\n",
    "        'phrase': 'PRAESENTIBUS',\n",
    "        'variants': [\n",
    "            'Present de Heeren',\n",
    "            'Pntes die voors'\n",
    "        ],\n",
    "        'label': 'attendants'\n",
    "    },\n",
    "    {\n",
    "        'phrase': 'PRAESIDE',\n",
    "        'variants': [\n",
    "            'Praeside de Heer',\n",
    "        ],\n",
    "        'label': 'president'\n",
    "    }\n",
    "]\n",
    "\n",
    "config = {\n",
    "    \"char_match_threshold\": 0.6,\n",
    "    \"ngram_threshold\": 0.5,\n",
    "    \"levenshtein_threshold\": 0.6,\n",
    "    \"ignorecase\": False,\n",
    "    \"include_variants\": True,\n",
    "    \"filter_distractors\": True,\n",
    "    \"max_length_variance\": 3,\n",
    "    \"ngram_size\": 2,\n",
    "    \"skip_size\": 2,\n",
    "}\n",
    "\n",
    "\n",
    "# initialize a new searcher instance with the phrases and the config\n",
    "fuzzy_searcher = FuzzyPhraseSearcher(config=config, phrase_model=attendants_phrases)\n",
    "\n",
    "for text in texts:\n",
    "    matches = fuzzy_searcher.find_matches(text)\n",
    "    for match in matches:\n",
    "        print(f\"{match.phrase.phrase_string: <20}\\t{match.string: <20}\"\n",
    "              f\"\\t{match.offset: >5}\\t{match.levenshtein_similarity: >.2f}\\t{match.text_id}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Alternative Representations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, each match object can generate a JSON representation of the match containing all information:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{\n",
      "    \"type\": \"PhraseMatch\",\n",
      "    \"phrase\": \"PRAESIDE\",\n",
      "    \"variant\": \"PRAESIDE\",\n",
      "    \"string\": \"PR&ASIDE\",\n",
      "    \"offset\": 33,\n",
      "    \"label\": \"president\",\n",
      "    \"ignorecase\": false,\n",
      "    \"text_id\": \"session-3780-num-3-para-1\",\n",
      "    \"match_scores\": {\n",
      "        \"char_match\": 0.875,\n",
      "        \"ngram_match\": 0.6666666666666666,\n",
      "        \"levenshtein_similarity\": 0.75\n",
      "    }\n",
      "}\n",
      "{\n",
      "    \"type\": \"PhraseMatch\",\n",
      "    \"phrase\": \"PRAESENTIBUS\",\n",
      "    \"variant\": \"PRAESENTIBUS\",\n",
      "    \"string\": \"PRASENTIEBUS\",\n",
      "    \"offset\": 63,\n",
      "    \"label\": \"attendants\",\n",
      "    \"ignorecase\": false,\n",
      "    \"text_id\": \"session-3780-num-3-para-1\",\n",
      "    \"match_scores\": {\n",
      "        \"char_match\": 1.0,\n",
      "        \"ngram_match\": 0.7692307692307693,\n",
      "        \"levenshtein_similarity\": 0.8333333333333334\n",
      "    }\n",
      "}\n",
      "{\n",
      "    \"type\": \"PhraseMatch\",\n",
      "    \"phrase\": \"PRAESIDE\",\n",
      "    \"variant\": \"PRAESIDE\",\n",
      "    \"string\": \"PRESIDE\",\n",
      "    \"offset\": 36,\n",
      "    \"label\": \"president\",\n",
      "    \"ignorecase\": false,\n",
      "    \"text_id\": \"session-3780-num-7-para-1\",\n",
      "    \"match_scores\": {\n",
      "        \"char_match\": 0.875,\n",
      "        \"ngram_match\": 0.7777777777777778,\n",
      "        \"levenshtein_similarity\": 0.875\n",
      "    }\n",
      "}\n",
      "{\n",
      "    \"type\": \"PhraseMatch\",\n",
      "    \"phrase\": \"PRAESENTIBUS\",\n",
      "    \"variant\": \"PRAESENTIBUS\",\n",
      "    \"string\": \"PRA&SENTIBUS\",\n",
      "    \"offset\": 69,\n",
      "    \"label\": \"attendants\",\n",
      "    \"ignorecase\": false,\n",
      "    \"text_id\": \"session-3780-num-7-para-1\",\n",
      "    \"match_scores\": {\n",
      "        \"char_match\": 0.9166666666666666,\n",
      "        \"ngram_match\": 0.8461538461538461,\n",
      "        \"levenshtein_similarity\": 0.9166666666666666\n",
      "    }\n",
      "}\n",
      "{\n",
      "    \"type\": \"PhraseMatch\",\n",
      "    \"phrase\": \"PRAESIDE\",\n",
      "    \"variant\": \"Praeside de Heer\",\n",
      "    \"string\": \"Praeside de Heer\",\n",
      "    \"offset\": 0,\n",
      "    \"label\": \"president\",\n",
      "    \"ignorecase\": false,\n",
      "    \"text_id\": \"session-3210-num-166-para-1\",\n",
      "    \"match_scores\": {\n",
      "        \"char_match\": 1.0,\n",
      "        \"ngram_match\": 1.0,\n",
      "        \"levenshtein_similarity\": 1.0\n",
      "    }\n",
      "}\n",
      "{\n",
      "    \"type\": \"PhraseMatch\",\n",
      "    \"phrase\": \"PRAESENTIBUS\",\n",
      "    \"variant\": \"Present de Heeren\",\n",
      "    \"string\": \"Praseat de Heeron\",\n",
      "    \"offset\": 28,\n",
      "    \"label\": \"attendants\",\n",
      "    \"ignorecase\": false,\n",
      "    \"text_id\": \"session-3210-num-166-para-1\",\n",
      "    \"match_scores\": {\n",
      "        \"char_match\": 0.8235294117647058,\n",
      "        \"ngram_match\": 0.6666666666666666,\n",
      "        \"levenshtein_similarity\": 0.8235294117647058\n",
      "    }\n",
      "}\n"
     ]
    }
   ],
   "source": [
    "import json\n",
    "\n",
    "matches =[match for text in texts for match in fuzzy_searcher.find_matches(text)]\n",
    "\n",
    "for match in matches:\n",
    "    print(json.dumps(match.json(), indent=4))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `variant` property shows which phrase (main phrase or variant) was used for matching.\n",
    "\n",
    "### Web Annotations\n",
    "\n",
    "Match objects can also generate Web Annotation representations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{\n",
      "  \"@context\": \"http://www.w3.org/ns/anno.jsonld\",\n",
      "  \"id\": \"cbf33232-a07a-4f2f-8015-942ec000452b\",\n",
      "  \"type\": \"Annotation\",\n",
      "  \"motivation\": \"classifying\",\n",
      "  \"created\": \"2023-12-12T17:08:55.001999\",\n",
      "  \"generator\": {\n",
      "    \"id\": \"https://github.com/marijnkoolen/fuzzy-search\",\n",
      "    \"type\": \"Software\",\n",
      "    \"name\": \"fuzzy-search v2.0.1a\"\n",
      "  },\n",
      "  \"target\": {\n",
      "    \"source\": \"session-3780-num-3-para-1\",\n",
      "    \"selector\": {\n",
      "      \"type\": \"TextPositionSelector\",\n",
      "      \"start\": 33,\n",
      "      \"end\": 41\n",
      "    }\n",
      "  },\n",
      "  \"body\": [\n",
      "    {\n",
      "      \"type\": \"TextualBody\",\n",
      "      \"purpose\": \"tagging\",\n",
      "      \"format\": \"text\",\n",
      "      \"value\": \"PRAESIDE\"\n",
      "    },\n",
      "    {\n",
      "      \"type\": \"TextualBody\",\n",
      "      \"purpose\": \"highlighting\",\n",
      "      \"format\": \"text\",\n",
      "      \"value\": \"PR&ASIDE\"\n",
      "    },\n",
      "    {\n",
      "      \"type\": \"TextualBody\",\n",
      "      \"purpose\": \"correcting\",\n",
      "      \"format\": \"text\",\n",
      "      \"value\": \"PRAESIDE\"\n",
      "    },\n",
      "    {\n",
      "      \"type\": \"TextualBody\",\n",
      "      \"purpose\": \"classifying\",\n",
      "      \"format\": \"text\",\n",
      "      \"value\": \"president\"\n",
      "    }\n",
      "  ]\n",
      "}\n"
     ]
    }
   ],
   "source": [
    "matches = fuzzy_searcher.find_matches(texts[0])\n",
    "\n",
    "import json\n",
    "\n",
    "print(json.dumps(matches[0].as_web_anno(), indent=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Configuration\n",
    "\n",
    "The key configurable properties are:\n",
    "\n",
    "- the size of character ngrams (`ngram_size`, default is 2)\n",
    "- the number of skips (`skip_size`, default is 2)\n",
    "\n",
    "Skip-grams with these settings lead to a very exhaustive search.\n",
    "\n",
    "Other configurable properties:\n",
    "\n",
    "- `max_length_variance`: the maximum number of characters that a phrase and a matching occurrence in the text can vary in length.\n",
    "- `include_variants`: Boolean to ignore or include phrase variants.\n",
    "- `filter_distractors`: Boolean to ignore or include distractor phrases to filter out matches that are closer to distractors than to the registered phrases and variants.\n",
    "\n",
    "### The Impact of Ngram Size and Skipgram Size\n",
    "\n",
    "As mentioned above, the default setting leads to very exhaustive search, but will slow down search when the number of phrases to search for gets big (a few dozen is enough to make it _very_ slow). This is due to the nature of short character ngrams (two-character strings contain little information and are more likely to occur in words than longer ngrams) and the number of _distinct_ ngrams that are created by introducing one or more skips (two-character sequences are constrained in each language, but when skips are introduced, it creates combinations that do not occur naturally in text).\n",
    "\n",
    "This is demonstrated below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Th', 'Ti', 'Ts', 'hi', 'hs', 'h ', 'is', 'i ', 'ii', 's ', 'si', 'ss', ' i', ' s', '  ', 'is', 'i ', 'ia', 's ', 'sa', 's ', ' a', '  ', ' t', 'a ', 'at', 'ae', ' t', ' e', ' s', 'te', 'ts', 'tt', 'es', 'et', 'e ', 'st', 's ', 'ss', 't ', 'ts', 'te', ' s', ' e', ' n', 'se', 'sn', 'st', 'en', 'et', 'ee', 'nt', 'ne', 'nn', 'te', 'tn', 'tc', 'en', 'ec', 'ee', 'nc', 'ne', 'n.', 'ce', 'c.', 'e.']\n",
      "number of skipgrams: 66\n"
     ]
    }
   ],
   "source": [
    "from fuzzy_search.tokenization.string import text2skipgrams\n",
    "\n",
    "sent = \"This is a test sentence.\"\n",
    "\n",
    "skipgrams = [skipgram for skipgram in text2skipgrams(sent)]\n",
    "print([s.string for s in skipgrams])\n",
    "print('number of skipgrams:', len(skipgrams))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Increasing the ngram size strongly reduces the number of matches between phrases and the target text (character 3 grams are more specific than 2 grams), while increasing the skip size strongly increasing the number of skipgrams (allowing for 2 skips creates many more permutations than allowing for 1 skip).\n",
    "\n",
    "To see the impact of different skip sizes, count the number of skipgrams for the sentence above for skip sizes of 2, 1 and 0 respectively:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "number of skipgrams: 66\n",
      "number of skipgrams: 45\n",
      "number of skipgrams: 23\n"
     ]
    }
   ],
   "source": [
    "skipgrams = [skipgram for skipgram in text2skipgrams(sent)]\n",
    "print('number of skipgrams:', len(skipgrams))\n",
    "skipgrams = [skipgram for skipgram in text2skipgrams(sent, ngram_size=2, skip_size=1)]\n",
    "print('number of skipgrams:', len(skipgrams))\n",
    "skipgrams = [skipgram for skipgram in text2skipgrams(sent, ngram_size=2, skip_size=0)]\n",
    "print('number of skipgrams:', len(skipgrams))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The same for using `ngram_size=3`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "number of skipgrams: 124\n",
      "number of skipgrams: 64\n",
      "number of skipgrams: 22\n"
     ]
    }
   ],
   "source": [
    "skipgrams = [skipgram for skipgram in text2skipgrams(sent, ngram_size=3, skip_size=2)]\n",
    "print('number of skipgrams:', len(skipgrams))\n",
    "skipgrams = [skipgram for skipgram in text2skipgrams(sent, ngram_size=3, skip_size=1)]\n",
    "print('number of skipgrams:', len(skipgrams))\n",
    "skipgrams = [skipgram for skipgram in text2skipgrams(sent, ngram_size=3, skip_size=0)]\n",
    "print('number of skipgrams:', len(skipgrams))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Fuzzy Token Searcher \n",
    "\n",
    "### Using Word Tokens Instead of Character Ngrams\n",
    "\n",
    "With the default settings for `ngram_size` and `skip_size`, the searcher becomes very slow when the phrase model contains many phrases. An alternative to increasing the ngram size and decreasing the skip size is to use the `FuzzyTokenSearcher`. It turns the phrases and the target text into lists of word tokens (the tokenizer is configurable) and uses character skip grams to identify candidate phrase tokens matching tokens in the text. It then uses token sequences to identify fuzzy matches. \n",
    "\n",
    "This speeds up the search (especially for the default settings `ngram_size=2` and `skip_size=2`) at the cost of slightly less exhaustive search. On test corpus of 1000 texts (1 million words) with relatively high HTR quality (CER around 5%), and with a model with 67 phrases, the `FuzzyTokenSearcher` finds the same number of matches as the `FuzzyPhraseSearcher`, but is 70-100 times faster. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[PhraseMatch(phrase: \"Veneris\", variant: \"Veneris\", string: \"Veucris\", offset: 3, ignorecase: False, levenshtein_similarity: 0.7142857142857143),\n",
       " PhraseMatch(phrase: \"PRAESIDE\", variant: \"PRAESIDE\", string: \"PR ASIDE\", offset: 33, ignorecase: False, levenshtein_similarity: 0.75),\n",
       " PhraseMatch(phrase: \"PRAESENTIBUS\", variant: \"PRAESENTIBUS\", string: \"PRASENTIEBUS\", offset: 63, ignorecase: False, levenshtein_similarity: 0.8333333333333334)]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from fuzzy_search import FuzzyTokenSearcher\n",
    "\n",
    "# initialize a new searcher instance with the phrases and the config\n",
    "fuzzy_searcher = FuzzyTokenSearcher(config=config, phrase_model=domain_phrases)\n",
    "\n",
    "# take some example texts: resolutoins of the meeting of the Dutch States General on\n",
    "# Friday the 5th of January, 1725\n",
    "text = (\"ie Veucris den 5. Januaris 1725. PR&ASIDE, Den Heere Bentinck. PRASENTIEBUS, \"\n",
    "        \"De Heeren Jan Welderen , van Dam, Torck , met een extraordinaris Gedeputeerde \"\n",
    "        \"uyt de Provincie van Gelderlandt. Van Maasdam , vanden Boeizelaar , Raadtpenfionaris \"\n",
    "        \"van Hoornbeeck , met een extraordinaris Gedeputeerde uyt de Provincie van Hollandt \"\n",
    "        \"ende Welt-Vrieslandt. Velters, Ockere , Noey; van Hoorn , met een extraordinaris \"\n",
    "        \"Gedeputeerde uyt de Provincie van Zeelandt. Van Renswoude , van Voor{t. Van \"\n",
    "        \"Schwartzenbergh, vander Waayen, Vegilin Van I{elmuden. Van Iddekinge ‚ van Tamminga.\")\n",
    "\n",
    "fuzzy_searcher.find_matches(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.10.12"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}