{"id":1817,"date":"2019-12-08T10:22:54","date_gmt":"2019-12-08T04:52:54","guid":{"rendered":"https:\/\/www.rangakrish.com\/?p=1817"},"modified":"2019-12-08T10:24:29","modified_gmt":"2019-12-08T04:54:29","slug":"using-definite-clause-grammars-dcg-for-information-extraction","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2019\/12\/08\/using-definite-clause-grammars-dcg-for-information-extraction\/","title":{"rendered":"Using Definite Clause Grammars (DCG) for Information Extraction"},"content":{"rendered":"

In the previous article<\/strong><\/em><\/a>, I showed how we can use ATNs<\/strong><\/em> for extracting key information from natural language text. I also pointed out in that article that Definite Clause Grammars (DCG)<\/strong><\/em> are a more compact formalism for doing this. That will be the focus of today’s article.<\/p>\n

For a nice introduction to DCG<\/strong><\/em>, read this<\/strong><\/em><\/a>.<\/p>\n

Let us first define the ATN<\/strong><\/em> arc primitives in DCG<\/strong><\/em>. Here are the definitions:<\/p>\n

\"ATN<\/a>
ATN Primitives in DCG<\/strong><\/figcaption><\/figure>\n

The predicate is_cat<\/strong><\/em> interfaces with the lexicon to determine the part-of-speech category of the given word. Here is a simple grammar that demonstrates the use of wrd<\/strong><\/em>\u00a0and cat<\/strong><\/em>\u00a0primitives:<\/p>\n

\"A<\/a>
A Simple Grammar<\/strong><\/figcaption><\/figure>\n

The sentence “The dog ran fast”<\/strong><\/em> is accepted by the above grammar:<\/p>\n

\"Applying<\/a>
Applying the Grammar<\/strong><\/figcaption><\/figure>\n

In the second sentence, the verb “chased”<\/strong><\/em> is not followed by an adverb<\/strong><\/em> and hence it is not accepted.<\/p>\n

The above grammar applies to the complete sentence, which is how we normally define and use DCG<\/strong><\/em>.<\/p>\n

How can we use DCG to parse parts of a sentence? Additionally, how do we extract<\/strong><\/em> items of interest from a sentence? The following grammar identifies simple VP<\/strong><\/em> chunks:<\/p>\n

\"Grammar<\/a>
Grammar for VP Chunks<\/strong><\/figcaption><\/figure>\n

We have used an additional argument in each grammar rule to retrieve the desired data during parsing. Here is an example using the chunking grammar:<\/p>\n

\"VP<\/a>
VP Chunk Example<\/strong><\/figcaption><\/figure>\n

As expected, the grammar correctly identifies the VP<\/strong><\/em> chunk “ran fast”<\/strong><\/em>.\u00a0 <\/span>What happens if we process the sentence “He ran fast and ate well”<\/strong><\/em>? See below.<\/p>\n

\"VP<\/a>
VP Chunk Example-2<\/strong><\/figcaption><\/figure>\n

Interesting. The reason why we get the trailing VP<\/strong><\/em> chunk and not the first one is because when we invoke the predicate, we have indicated that we are expecting no tokens after the match.\u00a0 <\/span>We can change that easily. Here is a predicate that collects all chunks:<\/p>\n

\"Getting<\/a>
Getting All VP Chunks<\/strong><\/figcaption><\/figure>\n

When we apply this on the same sentence, we get both the VP chunks:<\/p>\n

\"Getting<\/a>
Getting All Chunks Example<\/strong><\/figcaption><\/figure>\n

Using Registers<\/h3>\n

In the ATN<\/strong><\/em> implementation, we used registers as part of the structure building process. DCGs<\/strong><\/em> allow us to define additional arguments to suit our requirements and hence a separate Register<\/strong><\/em> system is not needed. However, it is easy to define a set of predicates to support the use of Registers<\/strong><\/em>. Here is the code:<\/p>\n

\"Support<\/a>
Support for Registers<\/strong><\/figcaption><\/figure>\n

It is possible to add more features, but I just wanted to give a hint as to how it can be done. The following grammar corresponding to VP<\/strong><\/em> chunks uses the Register<\/strong><\/em> system.<\/p>\n

\"Extracting<\/a>
Extracting VP Chunks Using Registers<\/strong><\/figcaption><\/figure>\n

Here is the same sentence as before, but parsed as per the revised grammar:<\/p>\n

\"Parsing<\/a>
Parsing Using Registers<\/strong><\/figcaption><\/figure>\n

You can see that the result is the same.<\/p>\n

Information Extraction Example: Homeopathy\u00a0<\/span><\/h3>\n

Now that you have a basic understanding of how to extract relevant information from a piece of text, let us look at a more interesting example. As in the previous article<\/strong><\/em><\/a>, let us try to extract the Age<\/strong><\/em> and Gender<\/strong><\/em> of the patient and Modalities<\/strong><\/em> of the disease from a homeopathic case record (simplified).<\/p>\n

We will work with this text:<\/p>\n

\"Homeopathy<\/a>
Homeopathy Case Text<\/strong><\/figcaption><\/figure>\n

This text is stored in the file \u201csample-text.txt\u201d<\/strong><\/em>. Here is the grammar to extract Age<\/strong><\/em>:<\/p>\n

\"Age<\/a>
Extracting Age\u00a0<\/strong><\/figcaption><\/figure>\n

And here is the grammar to extract Gender<\/strong><\/em>:<\/span><\/p>\n

\"Extracting<\/a>
Extracting Gender<\/strong><\/figcaption><\/figure>\n

Modality<\/strong><\/em> pattern is only slightly more involved than the above:<\/p>\n

\"Extracting<\/a>
Extracting Modalities of Disease<\/strong><\/figcaption><\/figure>\n

When we apply the above patterns to the sample text, this is what we get as output:<\/p>\n

\"Applying<\/a>
Applying Patterns to Sample Text<\/strong><\/figcaption><\/figure>\n

The actual Prolog<\/strong><\/em> code that does the processing is given below:<\/p>\n

\"Processing<\/a>
Processing the Text<\/strong><\/figcaption><\/figure>\n

In order to save space, I have not included the predicates that tokenize the input text. That part is simple and straightforward.<\/p>\n

As you would have gathered from the discussion so far, DCGs<\/strong><\/em> are a powerful formalism for processing both structured and unstructured text. All we need is a set of patterns to work with. The built-in backtracking mechanism of the Prolog<\/strong><\/em> engine makes the declarative model elegant and expressive.<\/p>\n

I have implemented the above logic in Sicstus Prolog<\/strong><\/em><\/a>\u00a0on Windows.<\/p>\n

Have a great weekend!<\/p>\n","protected":false},"excerpt":{"rendered":"

In the previous article, I showed how we can use ATNs for extracting key information from natural language text. I also pointed out in that article that Definite Clause Grammars (DCG) are a more compact formalism for doing this. That will be the focus of today’s article. For a nice introduction to DCG, read this. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[107,17,147],"tags":[100,213,212],"class_list":["post-1817","post","type-post","status-publish","format-standard","hentry","category-natural-language-processing","category-programming","category-prolog","tag-dcg","tag-definite-clause-grammars","tag-information-extraction"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-tj","jetpack-related-posts":[{"id":2832,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/06\/12\/definite-clause-grammars-in-lisp-part-4\/","url_meta":{"origin":1817,"position":0},"title":"Definite Clause Grammars in Lisp – Part 4","author":"admin","date":"June 12, 2022","format":false,"excerpt":"In a series of articles\u00a0written earlier, I had shown how it is possible to model Definite Clause Grammars (DCG) in LispWorks Lisp (Enterprise Edition). We use defgrammar\u00a0in Common Prolog (available as part of KnowledgeWorks package) to define our grammar rules. Here is a toy English grammar represented using defgrammar: This\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"DCG Using Defgrammar","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2022\/06\/defgrammar-version-300x177.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2022\/06\/defgrammar-version-300x177.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2022\/06\/defgrammar-version-300x177.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":534,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/05\/22\/definite-clause-grammars-dcg-in-lisp\/","url_meta":{"origin":1817,"position":1},"title":"Definite Clause Grammars (DCG) in Lisp","author":"admin","date":"May 22, 2017","format":false,"excerpt":"Definite Clause Grammars (DCG) are an elegant formalism for specifying context free grammars, and part of their popularity is due to their support in the Prolog language. Most books on Natural Language processing usually include a brief coverage of DCGs, even though Natural languages are not context-free. Because of the\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"DCG Grammar","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=525%2C300 1.5x"},"classes":[]},{"id":541,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/06\/04\/definite-clause-grammars-in-lisp-part-2\/","url_meta":{"origin":1817,"position":2},"title":"Definite Clause Grammars in Lisp – Part 2","author":"admin","date":"June 4, 2017","format":false,"excerpt":"In the last post, I showed how we can implement DCGs in LispWorks using the KnowledgeWorks package. The grammar discussed in that post did not take into account subject\/predicate number agreement. This is one of the basic constraints in English grammar. Today I will show how easy it is to\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Prolog Grammar","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/06\/Prolog-Grammar.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":1659,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/08\/04\/generating-poetry-in-prolog\/","url_meta":{"origin":1817,"position":3},"title":"Generating Poetry in Prolog","author":"admin","date":"August 4, 2019","format":false,"excerpt":"In an earlier article, I showed how we can generate poetry (with limitations, of course!) using my iLangGen framework. That implementation (in Lisp) made use of iLexicon, a large dictionary of English words, which I have been building over the years. I subsequently ported iLexicon to Prolog and it now\u2026","rel":"","context":"In "Natural Language Processing"","block_context":{"text":"Natural Language Processing","link":"https:\/\/www.rangakrish.com\/index.php\/category\/natural-language-processing\/"},"img":{"alt_text":"Generation Logic","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/08\/Code3.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/08\/Code3.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/08\/Code3.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":548,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/06\/23\/definite-clause-grammars-in-lisp-part-3\/","url_meta":{"origin":1817,"position":4},"title":"Definite Clause Grammars in Lisp – Part 3","author":"admin","date":"June 23, 2017","format":false,"excerpt":"In today's post, let us see how we can enhance the grammar representation discussed so far to include both Number constraint and Parse Tree. Fortunately, this turns out to be quite straightforward. Just as we do in Prolog, we need to include additional parameters, as needed, to each grammar rule.\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"POS Functions","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/06\/POS-Function.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/06\/POS-Function.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/06\/POS-Function.png?resize=525%2C300 1.5x"},"classes":[]},{"id":1711,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/09\/01\/poetry-in-prolog-part-2\/","url_meta":{"origin":1817,"position":5},"title":"Poetry in Prolog: Part-2","author":"admin","date":"September 1, 2019","format":false,"excerpt":"In an earlier post, I showed how Prolog can be used to generate poetry, making use of my \"iLexicon\". I want to continue the discussion today by giving another example, this time based on the theme of sounds emitted by various animals and birds. As hinted in my previous articles,\u2026","rel":"","context":"In "Natural Language Processing"","block_context":{"text":"Natural Language Processing","link":"https:\/\/www.rangakrish.com\/index.php\/category\/natural-language-processing\/"},"img":{"alt_text":"The DCG Grammar","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/09\/code.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/09\/code.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/09\/code.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/1817","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/comments?post=1817"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/1817\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=1817"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=1817"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=1817"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}