Simple Entity Tagger

easyFREENamed Entity RecognitionNLP 2: Applications

Given a mapping of known entities to their types, tag each word in a sentence with its entity type using BIO format.

Input:

entities: a dict mapping lowercase words to entity types (e.g., {"john": "PERSON", "google": "ORG"})
sentence: the sentence to tag, with words separated by spaces

BIO format: B-TYPE for the first word of an entity, O for non-entities. For simplicity, all entities are single words. Matching is case-insensitive, so "John" in the sentence matches the entry "john".

Output: Return a string of space-separated tags, one per word.

Example

Input

2
John PERSON
Google ORG
John works at Google

Output

B-PERSON O O B-ORG

Reasoning

Inputs: entities maps each known word (stored in lowercase) to its type: here "john" is a PERSON and "google" is an ORG. sentence is John works at Google, which has 4 words separated by spaces, so the output will have exactly 4 tags.
Matching is case-insensitive: "John" with a capital J counts as the known word "john", and "Google" counts as "google". Capitalisation in the sentence never decides whether a word is an entity.
Tagging word by word: "John" is a known PERSON, so it becomes B-PERSON. "works" and "at" are not known entities, so each gets O. "Google" is a known ORG, so it becomes B-ORG.
Output: the 4 tags joined by single spaces, B-PERSON O O B-ORG, in the same order as the words.
Notice: every entity is one word, so only the B- prefix ever appears (no I- tags). With an empty entities mapping, every word would simply be O.

Constraints

All entities are single words
Case-insensitive matching
Tags: B-TYPE or O
Output tags space-separated

Learn this in

Introduction to NLPNLP Study Plan Named Entity RecognitionNLP Study Plan

More from NLP 2: Applications

BIO Entity Span Extractoreasy Sentiment Word Countereasy Keyword Classifiereasy One-Hot Sequence Encodereasy Sequence Paddereasy

Concept primer

Background Knowledge

Named Entity Recognition (NER) is a fundamental task in Natural Language Processing (NLP) that involves identifying and categorizing named entities in unstructured text into predefined categories. These categories can include PERSON, ORGANIZATION, LOCATION, and more. The goal is to automatically extract and classify these entities, which is crucial for various applications such as information retrieval, question answering, and text summarization.

In the context of this problem, we're dealing with a simplified version of NER where each entity is a single word, and we're using the BIO format for tagging. The BIO format is a common annotation scheme used in NER tasks, where "B" stands for the beginning of an entity, "I" stands for inside an entity (though we won't be using this since our entities are single words), and "O" stands for outside an entity or a non-entity word. Understanding the BIO format is essential for correctly tagging the entities in the given sentence.

The key concept here is to match each word in the sentence against the list of known entities and their types to determine the appropriate tag. This involves string matching and dictionary lookups, which are basic operations in programming. However, the challenge lies in handling the sentence structure and ensuring that each word is correctly identified as either part of an entity or not.

Algorithm/Approach

The general approach to solving this problem involves a simple lookup algorithm. The idea is to iterate through each word in the sentence and check if it matches any of the known entities. If a match is found, the corresponding entity type is used to generate the BIO tag; otherwise, the word is tagged as "O" (outside an entity). This approach relies on the assumption that all entities are single words and that the list of known entities is comprehensive for the given sentence.

Step-by-Step Strategy

Read the Input: Start by reading the number of entity entries and then each entity entry (word and type) into a data structure (like a dictionary) for efficient lookups.
Read the Sentence: Read the sentence to be tagged and split it into individual words.
Tag Each Word: Iterate through each word in the sentence. For each word, check if it exists in the dictionary of known entities.

If the word is found, generate the "B-TYPE" tag based on the entity type.
If the word is not found, tag it as "O".

Output the Tags: After tagging each word, output the tags as a space-separated list.

Common Pitfalls

Case Sensitivity: Be mindful of case sensitivity when matching words against the entity list. The problem statement does not specify whether the matching should be case-sensitive or not, so consider how to handle this based on the test cases.
Word Boundaries: Ensure that you're correctly splitting the sentence into words and handling punctuation next to words.
Entity Dictionary: Make sure the entity dictionary is populated correctly before attempting to tag the sentence.

Time & Space Complexity

Time Complexity: The time complexity of this solution is $O(n + m)$ , where $n$ is the number of entity entries and $m$ is the number of words in the sentence. This is because we're doing a constant amount of work for each entity entry and each word in the sentence.
Space Complexity: The space complexity is $O(n + m)$ as well, as we need to store all entity entries and potentially all words in the sentence in memory for processing.

solution.py

Python 3.13

Test results