04 - Pattern Matching in spaCy.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "304ed7cc",
   "metadata": {},
   "source": [
    "# Finding linguistic patterns using spaCy\n",
    "\n",
    "*Content adapated from [Tuomo Hiipala'](https://www.mv.helsinki.fi/home/thiippal/) lectures\n",
    "\n",
    "This section teaches you to find linguistic patterns using spaCy, a natural language processing library for Python.\n",
    "\n",
    "After this section, you should:\n",
    "\n",
    " - know how to search for patterns based on part-of-speech tags and morphological features\n",
    " - know how to search for patterns based on syntactic dependencies"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc0b7651",
   "metadata": {},
   "source": [
    "Linguistic annotations, such as part-of-speech tags, syntactic dependencies and morphological features, help impose structure on written language. Crucially, linguistic annotations allow searching for structural patterns instead of individual words or phrases. This allows defining search patterns in a flexible way.\n",
    "\n",
    "In the spaCy library, the capability for pattern search is provided by various components named *Matchers*.\n",
    "\n",
    "spaCy provides three types of *Matchers*:\n",
    "\n",
    "1. A [Matcher](https://spacy.io/api/matcher), which allows defining rules that search for particular **words or phrases** by examining *Token* attributes.  \n",
    "2. A [DependencyMatcher](https://spacy.io/api/dependencymatcher), which allows searching parse trees for **syntactic patterns**.\n",
    "3. A [PhraseMatcher](https://spacy.io/api/phrasematcher), a fast method for matching spaCy *Doc* objects to *Doc* objects."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d23d91a",
   "metadata": {},
   "source": [
    "### Matching words or phrases"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6fb2721c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# importing the spaCy library into Python\n",
    "import spacy\n",
    "\n",
    "# loading a small language model for English; assign the result under 'nlp'\n",
    "nlp = spacy.load('en_core_web_sm')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a6990eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's again load our text\n",
    "with open('data/treaty_of_lisbon.txt', 'r', encoding='UTF-8') as f:\n",
    "    text = f.read()\n",
    "\n",
    "# and feed it to spacy\n",
    "doc = nlp(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4e62e778",
   "metadata": {},
   "outputs": [],
   "source": [
    "# just checking the length of our object\n",
    "print(len(doc))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "46619e3a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# importing the Matcher class\n",
    "from spacy.matcher import Matcher"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "352b73cf",
   "metadata": {},
   "source": [
    "Importing the *Matcher* class from spaCy's `matcher` submodule allows creating *Matcher* objects.\n",
    "\n",
    "When creating a *Matcher* object, you must provide the vocabulary of the language model used for finding matches to the *Matcher* object.\n",
    "\n",
    "The reason for this is really rather simple: if you want to search for patterns in some language, you need to know its vocabulary first.\n",
    "\n",
    "spaCy stores the vocabulary of a model in a [*Vocab*](https://spacy.io/api/vocab) object. The *Vocab* object can be found under the attribute `vocab` of a spaCy *Language* object.\n",
    "\n",
    "In this case, we have the *Language* object that contains a small language model for English stored under the variable `nlp`, which means we can access its *Vocab* object under the attribute `nlp.vocab`.\n",
    "\n",
    "We then call the *Matcher* **class** and provide the vocabulary under `nlp.vocab` to the `vocab` argument to create a *Matcher* object. We store the resulting object under the variable `matcher`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "85d7828a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# creating a Matcher and providing model vocabulary\n",
    "matcher = Matcher(vocab=nlp.vocab)\n",
    "\n",
    "# checking it out\n",
    "matcher"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e632f1c",
   "metadata": {},
   "source": [
    "The *Matcher* object is now ready to store the patterns that we want to search for.\n",
    "\n",
    "These patterns, or more specifically, *pattern rules*, are created using a [specific format](https://spacy.io/api/matcher#patterns) defined in spaCy.\n",
    "\n",
    "Each pattern consists of a Python list, which is populated by Python dictionaries. \n",
    "\n",
    "Each dictionary in this list describes the pattern for matching a single spaCy *Token*. \n",
    "\n",
    "If you wish to match a sequence of *Tokens*, you must define multiple dictionaries within a single list, whose order follows that of the pattern to be matched.\n",
    "\n",
    "Let's start by defining a simple pattern for matching sequences of pronouns and verbs, and store this pattern under the variable `pronoun_verb`.\n",
    "\n",
    "This pattern consists of a list, as marked by the surrounding brackets `[]`, which contains two dictionaries, marked by curly braces `{}` and separated by a comma. The key and value pairs in a dictionary are separated by a colon.\n",
    "\n",
    " - The dictionary key determines which *Token* attribute should be searched for matches. The attributes supported by the *Matcher* can be found [here](https://spacy.io/api/matcher#patterns).\n",
    "\n",
    " - The value under the dictionary key determines the specific value for the attribute.\n",
    "\n",
    "In this case, we define a pattern that searches for a sequence of two coarse part-of-speech tags (`POS`), namely pronouns (`PRON`) and verbs (`VERB`).\n",
    "\n",
    "Note that both keys and values must be provided in uppercase letters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2f69bf8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# defining a list with nested dictionaries that contains the pattern to be matched\n",
    "pronoun_verb = [{'POS': 'PRON'}, {'POS': 'VERB'}]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cae3d92b",
   "metadata": {},
   "source": [
    "Now that we have defined the pattern using a list and dictionaries, we can add it to the *Matcher* object under the variable `matcher`.\n",
    "\n",
    "This can be achieved using `add()` method, which requires two inputs:\n",
    "\n",
    " 1. A Python string object that defines a name for the pattern. This is required for purposes of identification.\n",
    " 2. A list containing the pattern(s) to be searched for. Because a single rule for matching patterns can contain multiple patterns, the input must be a *list of lists*. We therefore wrap the input lists into brackets, e.g. `[pattern_1]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c0e7effe",
   "metadata": {},
   "outputs": [],
   "source": [
    "# adding the pattern to the matcher under the name 'pronoun+verb'\n",
    "matcher.add(\"pronoun+verb\", patterns=[pronoun_verb])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc77aa25",
   "metadata": {},
   "source": [
    "To search for matches in the *Doc* object stored under the variable `doc`, we feed the *Doc* object to the *Matcher* and store the result under the variable `result`.\n",
    "\n",
    "We also set the optional argument `as_spans` to `True`, which instructs spaCy to return the results as *Span* objects. *Span* objects correspond to continuous \"slices\" (sequences of *tokens*) of *Doc* objects."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "00764af1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# applying the Matcher to the Doc object under 'doc' with the argument\n",
    "# 'as_spans' set to True to get Spans as output\n",
    "result = matcher(doc, as_spans=True)\n",
    "\n",
    "# calling the variable to examine the output\n",
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b53d43e3",
   "metadata": {},
   "source": [
    "The output is a list of spaCy *Span* objects that match the requested pattern. Let's examine the first object in the list of matches in greater detail."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b56b7e12",
   "metadata": {},
   "outputs": [],
   "source": [
    "result[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "178a4e97",
   "metadata": {},
   "source": [
    "The *Span* object has various useful [attributes](https://spacy.io/api/span), including `start` and `end`. These attributes contain the indices that indicate where in the *Doc* object the *Span* starts and finishes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d7074d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "result[0].start, result[0].end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f087ef6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "result[0].label"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ddd60af7",
   "metadata": {},
   "outputs": [],
   "source": [
    "result[0].label_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1eb856c8",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(result[0].start, result[0].end)\n",
    "print(result[0].label)\n",
    "print(result[0].label_)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d96f08a",
   "metadata": {},
   "source": [
    "The number stored under the `label` attribute is actually a spaCy [*Lexeme*](https://spacy.io/api/lexeme) object that corresponds to an entry in the language model's vocabulary. \n",
    "\n",
    "This *Lexeme* contains the name that we gave to the search pattern above, namely `pronoun+verb`.\n",
    "\n",
    "Another way to verify this by using the value under `result[0].label` to fetch the *Lexeme* from the *Vocab* object under `nlp.vocab` and examining its `text` attribute."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a353ca32",
   "metadata": {},
   "outputs": [],
   "source": [
    "nlp.vocab[result[0].label].text"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7b6e602",
   "metadata": {},
   "source": [
    "The information under the `label` attribute is useful for disambiguating between patterns, especially if the same *Matcher* object contains multiple different patterns, as we will see shortly below.\n",
    "\n",
    "Looking at the matches above, the pattern we defined is quite restrictive, as the pronoun and the verb must follow each other.\n",
    "\n",
    "We cannot, for example, match patterns in which the verb is preceded by auxiliary verbs.\n",
    "\n",
    "spaCy allows increasing the flexibility of pattern rules using operators (similar to operators in regular expressions). \n",
    "\n",
    "These operators are defined by adding the key `OP` to the dictionary that defines a pattern for a single *Token*. spaCy supports the following operators:\n",
    "\n",
    " - `!`: Negate the pattern; the pattern can occur exactly zero times.\n",
    " - `?`: Make the pattern optional; the pattern may occur zero or one times.\n",
    " - `+`: Require the pattern to occur one or more times.\n",
    " - `*`: Allow the pattern to match zero or more times.\n",
    "\n",
    "Let's explore the use of operators by defining another pattern rule, which extends the scope of our *Matcher*.\n",
    "\n",
    "To do so, we define another pattern for a *Token* between the pronoun and the verb. This *Token* must have the coarse part-of-speech tag `AUX`, which indicates an auxiliary verb:\n",
    "\n",
    "```python\n",
    "{'POS': 'AUX', 'OP': '+'}\n",
    "```\n",
    "\n",
    "In addition, we add another key and value pair to the dictionary for this *Token*, which contains the key `OP` with the value `+`. This means that the *Token* corresponding to an auxiliary verb must occur *one or more times*.\n",
    "\n",
    "We store the resulting list with nested dictionaries under the variable `pronoun_aux_verb`, and add the pattern to the existing *Matcher* object stored under the variable `matcher`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "14ba65dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "# defining a list with nested dictionaries that contains the pattern to be matched\n",
    "pronoun_aux_verb = [{'POS': 'PRON'}, {'POS': 'AUX', 'OP': '+'}, {'POS': 'VERB'}]\n",
    "\n",
    "# adding the pattern to the matcher under the name 'pronoun+aux+verb'\n",
    "matcher.add('pronoun+aux+verb', patterns=[pronoun_aux_verb])\n",
    "\n",
    "results = matcher(doc, as_spans=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "47fb3b14",
   "metadata": {},
   "outputs": [],
   "source": [
    "results"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f13522f9",
   "metadata": {},
   "source": [
    "### Matching morphological features"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3930bb70",
   "metadata": {},
   "source": [
    "The `morph` attribute contains a string object, in which each morphological feature is separated by a vertical bar `|`, as illustrated below.\n",
    "\n",
    "```\n",
    "We \t Case=Nom|Number=Plur|Person=1|PronType=Prs\n",
    "```\n",
    "\n",
    "As you can see, particular types of morphological features, e.g. *Case*, and their type, e.g. *Nom* (for the nominative case) are separated by equal signs `=`.\n",
    "\n",
    "Let's begin exploring how we can define pattern rules that match morphological features.\n",
    "\n",
    "To get started, we create a new *Matcher* object named `morph_matcher`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4460fb8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# creating a Matcher and provide model vocabulary\n",
    "morph_matcher = Matcher(vocab=nlp.vocab)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8da5fa9d",
   "metadata": {},
   "source": [
    "We then define a new pattern with rules for two *Tokens*:\n",
    "\n",
    " 1. Tokens that have a fine-grained part-of-speech tag `NNP` (proper noun), which can occur one or more times (operator: `+`).\n",
    " \n",
    " ```python\n",
    " {'TAG': 'NNP', 'OP': '+'}\n",
    " ```\n",
    " \n",
    " \n",
    " 2. Tokens that have a coarse part-of-speech tag `VERB` and have *all* the following morphological features (`MORPH`): `Number=Sing|Person=Three|Tense=Pres|VerbForm=Fin`.\n",
    " \n",
    " ```python\n",
    " {'POS': 'VERB', 'MORPH': 'Number=Sing|Person=Three|Tense=Pres|VerbForm=Fin'}\n",
    " ```\n",
    " \n",
    "We define the pattern using two dictionaries in a list, which we assign under the variable `propn_3rd_finite`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cf04d1b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "propn_3rd_finite = [{'TAG': 'NNP', 'OP': '+'},\n",
    "                    {'POS': 'VERB', 'MORPH': 'Number=Sing|Person=Three|Tense=Pres|VerbForm=Fin'}]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da5e3473",
   "metadata": {},
   "source": [
    "We then add the pattern to the newly-created *Matcher* stored under the variable `morph_matcher` using the `add()` method.\n",
    "\n",
    "We also provide the value `LONGEST` to the optional argument `greedy` for the `add()` method.\n",
    "\n",
    "The `greedy` argument filters the matches for *Tokens* that include operators such as `+` that search *greedily* for more than one match.\n",
    "\n",
    "By setting the value to `LONGEST`, spaCy returns the longest sequence of matches instead of returning a match every time it finds one. Put differently, spaCy will collect all the matching *Tokens* before returning them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d636af73",
   "metadata": {},
   "outputs": [],
   "source": [
    "# adding the pattern to the matcher under the name 'sing_3rd_pres_fin'\n",
    "morph_matcher.add('sing_3rd_pres_fin', patterns=[propn_3rd_finite], greedy='LONGEST')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1e458aaa",
   "metadata": {},
   "outputs": [],
   "source": [
    "# then again\n",
    "morph_results = morph_matcher(doc, as_spans=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c971ac41",
   "metadata": {},
   "outputs": [],
   "source": [
    "morph_results"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03403e6b",
   "metadata": {},
   "source": [
    "As you can see, the matches are relatively few in number, because we defined that the verb should have quite specific morphological features.\n",
    "\n",
    "The question is, then, how can we match just *some* morphological features?\n",
    "\n",
    "To loosen the criteria for morphological features by focusing on [tense](https://en.wikipedia.org/wiki/Grammatical_tense) only, we need to use a dictionary with the key `MORPH`, but instead of a string object, we provide a dictionary as its value:\n",
    "\n",
    "For this dictionary, we use the string `IS_SUPERSET` as the key. `IS_SUPERSET` is one of the attributes defined in the spaCy [pattern format](https://spacy.io/api/matcher#patterns), e.g.\n",
    "\n",
    "```python\n",
    "{'MORPH': {'IS_SUPERSET': [...]}}\n",
    "```\n",
    "\n",
    "Before proceeding any further, let's unpack the logic behind `IS_SUPERSET` a bit.\n",
    "\n",
    "We can think of morphological features associated with a given Token as a [set](https://en.wikipedia.org/wiki/Set_(mathematics)). To exemplify, a set could consist of the following four items:\n",
    "\n",
    "```\n",
    "Number=Sing, Person=Three, Tense=Pres, VerbForm=Fin\n",
    "```\n",
    "\n",
    "If we would have *another set* with just one item, `Tense=Pres`, we could describe the relationship between the two sets by stating that the first set (with four items) is a superset of the second set (with one item).\n",
    "\n",
    "In other words, the larger (super)set contains the smaller (sub)set.\n",
    "\n",
    "This is also how matching using `IS_SUPERSET` works: spaCy retrieves the morphological features for each *Token*, and examines whether these features are a superset of the features defined in the search pattern.\n",
    "\n",
    "The morphological features to be searched for are provided as a list of Python strings.\n",
    "\n",
    "These strings, in turn, define particular morphological features, e.g. `Tense=Past`, as defined in the [Universal Dependencies](https://universaldependencies.org/u/overview/morphology.html) schema for describing morphology.\n",
    "\n",
    "This list is then used as the value for the key `IS_SUPERSET`.\n",
    "\n",
    "Let's now proceed to search for verbs in the past tense and add them to the *Matcher* object under `morph_matcher`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e6efdf75",
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a list with nested dictionaries that contains the pattern to be matched\n",
    "past_tense = [{'TAG': 'NNP', 'OP': '+'},\n",
    "              {'POS': 'VERB', 'MORPH': {'IS_SUPERSET': ['Tense=Past']}}]\n",
    "\n",
    "# adding the pattern to the matcher under the name 'past_tense'\n",
    "morph_matcher.add('past_tense', patterns=[past_tense], greedy='LONGEST')\n",
    "\n",
    "morph_results = morph_matcher(doc, as_spans=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "843930e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# looping over each Span object in the list 'results'\n",
    "for result in morph_results:\n",
    "    \n",
    "    # printing out the the name of the pattern rule, the matching Span, and the morphological features of the\n",
    "    # last Token in the match (a verb).\n",
    "    print(nlp.vocab[result.label].text, '\\t', result, '\\t', result[-1].morph)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad3200cb",
   "metadata": {},
   "source": [
    "### Matching syntactic dependencies"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d9b50ae",
   "metadata": {},
   "source": [
    "If you want to match patterns based on syntactic dependencies, you must use the *DependencyMatcher* class in spaCy.\n",
    "\n",
    "As we learned, syntactic dependencies describe the relations that hold between *Token* objects.\n",
    "\n",
    "To get started, let's import the *DependencyMatcher* class from the `matcher` submodule.\n",
    "\n",
    "As you can see, the *DependencyMatcher* is initialised just as like the *Matcher* above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "badbdb70",
   "metadata": {},
   "outputs": [],
   "source": [
    "# importing the DependencyMatcher class\n",
    "from spacy.matcher import DependencyMatcher\n",
    "\n",
    "# creating a DependencyMatcher and provide model vocabulary\n",
    "dep_matcher = DependencyMatcher(vocab=nlp.vocab)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76bca218",
   "metadata": {},
   "source": [
    "This provides us with a *DependencyMatcher* stored under the variable `dep_matcher`, which is now ready for storing dependency patterns.\n",
    "\n",
    "When developing pattern rules for matching syntactic dependencies, the first step is to determine an \"anchor\" around which the pattern is built.\n",
    "\n",
    "Visualising the syntactic dependencies, can help formulate patterns. \n",
    "\n",
    "Let's import the displacy submodule to draw the syntactic dependencies for a sentence in the *Doc* object stored under the variable `doc`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56182df4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# importing the displacy submodule from spaCy\n",
    "from spacy import displacy\n",
    "\n",
    "# let's try with sentence in postion 45\n",
    "displacy.render(list(doc.sents)[45], style='dep')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6c1a2de",
   "metadata": {},
   "source": [
    "Syntactic dependencies are visualised using arcs that lead from the *head* *Token* to the *dependent* *Token*. The label of the arc gives the syntactic dependency.\n",
    "\n",
    "To exemplify, the verb \"remains\" governs the noun \"security\". \"security\", in turn governs the adjective \"national\".\n",
    "\n",
    "Let's define a pattern that searches for verbs and their nominal subjects (`nsubj`).\n",
    "\n",
    "Just as using the *Matcher* class, the pattern rules for the *DependencyMatcher* are defined using a list of dictionaries.\n",
    "\n",
    "The first dictionary in the list defines an \"anchor\" pattern and its attributes.\n",
    "\n",
    "You can think of the pattern rule as a chain that proceeds from left to right, and the first pattern on the left acts as an anchor for the subsequent patterns on its right-hand side.\n",
    "\n",
    "Hence we define the following pattern for the anchor:\n",
    "\n",
    "```python\n",
    "{'RIGHT_ID': 'verb', 'RIGHT_ATTRS': {'POS': 'VERB'}}\n",
    "```\n",
    "\n",
    "We use the required key `RIGHT_ID` to provide a name for this pattern, which can be then used to refer to this pattern by subsequent patterns on its **right-hand side**.\n",
    "\n",
    "In other words, when you see the key `RIGHT_ID`, think of a name for the *current pattern*.\n",
    "\n",
    "We then create a dictionary under the key `RIGHT_ATTRS` that holds the linguistic features of the anchor. In this case, we determine that the anchor should have `VERB` as its part-of-speech tag.\n",
    "\n",
    "Next, we determine a pattern for the next \"link\" in the chain to the right of the anchor:\n",
    "\n",
    "```python\n",
    "{'LEFT_ID': 'verb', 'REL_OP': '>', 'RIGHT_ID': 'subject', 'RIGHT_ATTRS': {'DEP': 'nsubj'}}\n",
    "```\n",
    "\n",
    "We start by providing the key `LEFT_ID`, whose value is a string object that refers to the name of a pattern on the **left-hand side** of the current pattern. This is the name that we gave to the anchor using the key `RIGHT_ID`.\n",
    "\n",
    "Next, we use the key `REL_OP` to define a [relation operator](https://spacy.io/api/dependencymatcher#patterns), which determines the relationship between this pattern and that referred to using `LEFT_ID`.\n",
    "\n",
    "The relation operator `>` defines that the pattern under `LEFT_ID` – the anchor – should be the head of the current pattern.\n",
    "\n",
    "Next, we name the current pattern using the key `RIGHT_ID`, which enables referring to this pattern on the right-hand side, if necessary. We give this pattern the name `subject`.\n",
    "\n",
    "We then use the `RIGHT_ATTRS` to determine the attributes for the current pattern. We define that the syntactic relation that holds between this pattern and that on the left should be `nsubj` or nominal subject."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b6b3ae26",
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's use a smaller piece of text...\n",
    "with open('data/treaty_of_lisbon.txt', 'r', encoding='UTF-8') as f:\n",
    "    text = f.read()\n",
    "    \n",
    "ind_begin = text.find('Article 8 A')\n",
    "ind_end = text.find('Article 8 B')\n",
    "\n",
    "text = text[ind_begin:ind_end]\n",
    "\n",
    "doc = nlp(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8e2aab1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# defining a list with nested dictionaries that contains the pattern to be matched\n",
    "dep_pattern = [{'RIGHT_ID': 'verb', 'RIGHT_ATTRS': {'POS': 'VERB'}},\n",
    "               {'LEFT_ID': 'verb', 'REL_OP': '>', 'RIGHT_ID': 'subject', 'RIGHT_ATTRS': {'DEP': 'nsubj'}}\n",
    "              ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "32b87636",
   "metadata": {},
   "outputs": [],
   "source": [
    "# adding the pattern to the matcher under the name 'nsubj_verb'\n",
    "dep_matcher.add('nsubj_verb', patterns=[dep_pattern])\n",
    "\n",
    "# applying the DependencyMatcher to the Doc object under 'doc'\n",
    "dep_matches = dep_matcher(doc)\n",
    "\n",
    "# checking it out\n",
    "dep_matches"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9cc91b6",
   "metadata": {},
   "source": [
    "Unlike the *Matcher*, the *DependencyMatcher* cannot return the matches as *Span* objects, because the matches do not necessarily form a continuous sequence of *Tokens* needed for a *Span* object.\n",
    "\n",
    "Thus the *DependencyMatcher* returns a list of tuples. \n",
    "\n",
    "Each tuple contains two items:\n",
    "\n",
    " 1. A *Lexeme* object that gives the name of the pattern\n",
    " 2. A list of indices for *Tokens* that match the search pattern in the *Doc* object"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d1b84b3e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# looping over each tuple in the list 'dep_matches'\n",
    "for match in dep_matches:\n",
    "    \n",
    "    # taking the first item in the tuple at [0] and assigning it under\n",
    "    # the variable 'pattern_name'. This item is a spaCy Lexeme object.\n",
    "    pattern_name = match[0]\n",
    "    \n",
    "    # taking the second item in the tuple at [1] and assigning it under\n",
    "    # the variable 'matches'. This is a list of indices referring to the\n",
    "    # Doc object under 'doc' that we just matched.\n",
    "    matches = match[1]\n",
    "    \n",
    "    # let's unpack the matches list into variables for clarity\n",
    "    verb, subject = matches[0], matches[1]\n",
    "    \n",
    "    # printing the matches by first fetching the name of the pattern from the \n",
    "    # Vocabulary object. Next, use the 'subject' and 'verb' variables to \n",
    "    # index the Doc object. This gives us the actual Tokens matched.\n",
    "    print(nlp.vocab[pattern_name].text, '\\t', doc[subject], '...', doc[verb])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ed95b10",
   "metadata": {},
   "source": [
    "### Exercise"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b48f5b5",
   "metadata": {},
   "source": [
    "1. Find the direct objects (dobj) for the verbs matched above. Hint: you should **not** add this as a link to the existing chain whose rightmost item is currently named `subject`. Instead, you need to start a new chain that begins from the anchor pattern `verb`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71836a1e",
   "metadata": {},
   "source": [
    "### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "57d10754",
   "metadata": {},
   "outputs": [],
   "source": [
    "# defining a list with nested dictionaries that contains the pattern to be matched\n",
    "dep_pattern_2 = [{'RIGHT_ID': 'verb', 'RIGHT_ATTRS': {'POS': 'VERB'}},\n",
    "                 {'LEFT_ID': 'verb', 'REL_OP': '>', 'RIGHT_ID': 'subject', 'RIGHT_ATTRS': {'DEP': 'nsubj'}},\n",
    "                 {'LEFT_ID': 'verb', 'REL_OP': '>', 'RIGHT_ID': 'd_object', 'RIGHT_ATTRS': {'DEP': 'dobj'}}\n",
    "                ]\n",
    "\n",
    "# adding the pattern to the matcher under the name 'nsubj_verb'\n",
    "dep_matcher.add('nsubj_verb_dobj', patterns=[dep_pattern_2])\n",
    "\n",
    "# applying the DependencyMatcher to the Doc object under 'doc'\n",
    "dep_matches = dep_matcher(doc)\n",
    "\n",
    "# looping over each tuple in the list 'dep_matches'\n",
    "for match in dep_matches:\n",
    "    \n",
    "    # taking the first item in the tuple at [0] and assigning it under\n",
    "    # the variable 'pattern_name'. This item is a spaCy Lexeme object.\n",
    "    pattern_name = match[0]\n",
    "    \n",
    "    # taking the second item in the tuple at [1] and assigning it under\n",
    "    # the variable 'matches'. This is a list of indices referring to the\n",
    "    # Doc object under 'doc' that we just matched.\n",
    "    matches = match[1]\n",
    "\n",
    "    # because we now have two patterns for matching which return lists of\n",
    "    # different length, e.g. lists with two indices for 'nsubj_verb' and\n",
    "    # lists with three indices for 'nsubj_verb_dobj', we must now define\n",
    "    # conditional criteria for handling these lists.\n",
    "    if len(matches) > 2:\n",
    "        \n",
    "        # let's unpack the matches list into variables for clarity\n",
    "        verb, subject, dobject = matches[0], matches[1], matches[2]\n",
    "    \n",
    "        # printing the matches by first fetching the name of the pattern from the \n",
    "        # Vocabulary object. Next, use the 'subject' and 'verb' variables to \n",
    "        # index the Doc object. This gives us the actual Tokens matched.\n",
    "        print(nlp.vocab[pattern_name].text, '\\t', doc[subject], '...', doc[verb], '...', doc[dobject])\n",
    "        \n",
    "    # alternative condition with just two items in the list.\n",
    "    else:\n",
    "        \n",
    "        # let's unpack the matches list into variables for clarity\n",
    "        verb, subject = matches[0], matches[1]\n",
    "    \n",
    "        print(nlp.vocab[pattern_name].text, '\\t', doc[subject], '...', doc[verb])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ad7ab6b2",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}